Software visualization of LR parsing and synthesized attribute evaluation

Visual YACC is a tool that automatically creates visualizations of the YACC LR parsing process and synthesized attribute computation. The Visual YACC tool works by instrumenting a standard YACC grammar with graphics calls that draw the appropriate data structures given the current actions by the parser. The new grammar is processed by the YACC tools and the resulting parser displays the parse stack and parse tree for every step of the parsing process of a given input string. Visual YACC was initially designed to be used in compiler construction courses to supplement the teaching of parsing and syntax directed evaluation. We have also found it to be useful in the difficult task of debugging YACC grammars. In this paper, we describe this tool and how it is used in both contexts. We also detail two different implementations of this tool: one that produces a parser written in C with calls to Motif; and a second implementation that generates Java source code. Copyright © 1999 John Wiley & Sons, Ltd.     

Grammar engineering for multiple front-ends for Python

In this paper, we describe our experience in grammar engineering to construct multiple parsers and front ends for the Python language. We present a metrics-based study of the evolution of the Python grammars through the multiple versions of the language in an effort to distinguish and measure grammar evolution and to provide a basis of comparison with related research in grammar engineering. To conduct this research, we have built a toolkit, pygrat , which builds on tools developed in other research. We use pygrat to build a system that automates much of the process needed to translate the Python grammars from EBNF to a formalism acceptable to the bison parser generator. We exploit the suite of Python test cases, used by the Python developers, to validate our parser generation. Finally, we describe our use of the menhir parser generator to facilitate the parser and front-end construction, eliminating some of the transformations and providing practical support for grammar modularisation.     

利用YAY最终解决VHDL中歧义文法问题的方案

提出了一种使用新的编译器产生工具YAY来编写VHDL语法分析器的方法,实践表明,用这种方法设计的语法分析器完全解决了VHDL中歧义文法的问题而且其对应的代码效率较高,可读性较好。     

Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking

A wide range of parser generators are used to generate parsers for programming languages. The grammar formalisms that come with parser generators provide different approaches for defining operator precedence. Some generators (e.g. YACC) support precedence declarations, others require the grammar to be unambiguous, thus encoding the precedence rules. Even if the grammar formalism provides precedence rules, a particular grammar might not use it. The result is grammar variants implementing the same language. For the C language, the GNU Compiler uses YACC with precedence rules, the C-Transformers uses SDF without priorities, while the SDF library does use priorities. For PHP, Zend uses YACC with precedence rules, whereas PHP-front uses SDF with priority and associativity declarations.The variance between grammars raises the question if the precedence rules of one grammar are compatible with those of another. This is usually not obvious, since some languages have complex precedence rules. Also, for some parser generators the semantics of precedence rules is defined operationally, which makes it hard to reason about their effect on the defined language. We present a method and tool for comparing the precedence rules of different grammars and parser generators. Although it is undecidable whether two grammars define the same language, this tool provides support for comparing and recovering precedence rules, which is especially useful for reliable migration of a grammar from one grammar formalism to another. We evaluate our method by the application to non-trivial mainstream programming languages, such as PHP and C.     

Neural Parse Combination

Analyzing the syntactic structure of natural languages by parsing is an important task in artificial intelligence. Due to the complexity of natural languages, individual parsers tend to make different yet complementary errors. We propose a neural network based approach to combine parses from different parsers to yield a more accurate parse than individual ones. Unlike conventional approaches, our method directly transforms linearized candidate parses into the ground-truth parse. Experiments on the Penn English Treebank show that the proposed method improves over a state-of-the-art parser combination approach significantly.     

LALR(1)解析器的再工程:YACC和CUP剖析

现有的前端分析多数是通过编写相应的可能含有二义的LALR（1）文法规范,利用YACC或其变种自动生成的。在这些解析器的Java再工程中,可以用CUP去替代YACC,这样再工程的焦点转移到对文法规范的变换。由于YACC及CUP在二义的解决、解析器的构造等有细微的差别,因此对复杂的文法规范的变换并不是一件容易的事。该文通过剖析YACC和CUP,指出了它们的不同之处,并总结出有二义的YACC文法到CUP文法变换的基本原则和几个变换法则。     

Towards Effective Parsing with Neural Networks: Inherent Generalisations and Bounded Resource Effects

This article explores how the effectiveness of learning to parse with neural networks can be improved by including two architectural features relevant to language: generalisations across syntactic constituents and bounded resource effects. A number of neural network parsers have recently been proposed, each with a different approach to the representational problem of outputting parse trees. In addition, some of the parsers have explicitly attempted to capture an important regularity within language, which is to generalise information across syntactic constituents. A further property of language is that natural bounds exist for the number of constituents which a parser need retain for later processing. Both the generalisations and the resource bounds may be captured in architectural features which enhance the effectiveness and efficiency of learning to parse with neural networks. We describe a number of different types of neural network parser, and compare them with respect to these two features. These features are both explicitly present in the Simple Synchrony Network parser, and we explore and illustrate their impact on the process of learning to parse in some experiments with a recursive grammar.     

How to design a connectionist holistic parser

Connectionist holistic parsing offers a viable and attractive alternative to traditional algorithmic parsers. With exposure to a limited subset of grammatical sentences and their corresponding parse trees only, a holistic parser is capable of learning inductively the grammatical regularity underlying the training examples that affects the parsing process. In the past, various connectionist parsers have been proposed. Each approach had its own unique characteristics, and yet some techniques were shared in common. In this article, various dimensions underlying the design of a holistic parser are explored, including the methods to encode sentences and parse trees, whether a sentence and its corresponding parse tree share the same representation, the use of confluent inference, and the inclusion of phrases in the training set. Different combinations of these design factors give rise to different holistic parsers. In succeeding discussions, we scrutinize these design techniques and compare the performances of a few parsers on language parsing, including the confluent preorder parser, the backpropagation parsing network, the XERIC parser of Berg (1992), the modular connectionist parser of Sharkey and Sharkey (1992), Reilly's (1992) model, and their derivatives. Experiments are performed to evaluate their generalization capability and robustness. The results reveal a number of issues essential for building an effective holistic parser.     

Building syntax graphs from syntax equations: A case study in modular programming

A system is described which inputs EBNF syntax equations as text, checks them and builds a corresponding syntax graph representation. An EBNF parser, with full error recovery, is included. The system is designed using the principles of modular decomposition and data abstraction, and is presented as a case study in the application of these principles to program design. The system is programmed in Pascal-plus, and has been used as a basis for the automatic generation of parsers.     

The parser generating system PGS

PGS is a parser generating system accepting LALR(1) and related grammars in extended BNF notation and producing parsers based on table-driven stack automata. To enable syntax-directed translation, semantic actions can be attached to rules of the input grammar. An attribution mechanism allows the transfer of information between rules. The generated parsers have an automatic error recovery which can be tailored to satisfy specific needs of the language to be accepted. PGS generates parsers written in Pascal, Modula-2, C or Ada. Compared with existing systems, e.g. YACC¹, a parser generated by PGS is twice as fast and the parse tables require 25 per cent less storage. This paper gives a survey of algorithms involved in the generator and the generated parsers, and compares them with algorithms used in other systems. In detail, it compares several parse-table representations and their implications for space and time efficiency of the generated parsers.     

面向移进—归约句法分析器的单模型系统整合算法

该文提出了一种面向移进—归约句法分析器的单模型系统整合算法。在训练阶段,该方法通过调整训练数据的分布,来构建用于整合的多个移进—归约句法分析器。在解码阶段,该方法首先使用各个移进—归约句法分析器对待分析的句子进行句法分析,然后利用一个线性模型对各句法分析器输出的句法树进行评分,从中选出得分最高的句法树作为最终结果。该文中的实验是在宾州英文树库上进行的。实验结果表明,该文中的方法能够显著改善基准系统的性能。     

On a method for optimizing LR parsers

It is shown that if the basic method for eliminating single productions from canonical LR parsers developed by Pager is applied to an SLR parser and the resulting parser is free of conflicts, then the resulting parser is a valid parser which accepts exactly the strings in the language. However, if the elimination process is performed during the construction of an SLR parser, then the resulting parser may be invalid even if it were free of conflicts.     

GPU-Driven Scalable Parser for OBJ Models

这篇论文用为巨大的基于文章的文件处理单位(GPU ) 的图形论述一个可伸缩的分析器框架。明确地,我们的解决方案被设计高效地分析哪个指定 3D 几何学和他们的拓扑学的波前 OBJ 模型文章。我们的工作把它的可伸缩性和效率基于基于块的处理。全部分析问题被细分进其块能独立地被处理并且无缝地合并了的 subproblems。处理的在内块被使高度平行,由 GPU 利用了。我们的途径从而克服存在 OBJ 分析器的瓶颈。执行估计我们的系统的性能的实验证明我们的解决方案显著地超过存在基于中央处理器的解决方案和基于 GPU 的解决方案也。     

Analyzing holistic parsers: implications for robust parsing and systematicity

Holistic parsers offer a viable alternative to traditional algorithmic parsers. They have good generalization performance and are robust inherently. In a holistic parser, parsing is achieved by mapping the connectionist representation of the input sentence to the connectionist representation of the target parse tree directly. Little prior knowledge of the underlying parsing mechanism thus needs to be assumed. However, it also makes holistic parsing difficult to understand. In this article, an analysis is presented for studying the operations of the confluent preorder parser (CPP). In the analysis, the CPP is viewed as a dynamical system, and holistic parsing is perceived as a sequence of state transitions through its state-space. The seemingly one-shot parsing mechanism can thus be elucidated as a step-by-step inference process, with the intermediate parsing decisions being reflected by the states visited during parsing. The study serves two purposes. First, it improves our understanding of how grammatical errors are corrected by the CPP. The occurrence of an error in a sentence will cause the CPP to deviate from the normal track that is followed when the original sentence is parsed. But as the remaining terminals are read, the two trajectories will gradually converge until finally the correct parse tree is produced. Second, it reveals that having systematic parse tree representations alone cannot guarantee good generalization performance in holistic parsing. More important, they need to be distributed in certain useful locations of the representational space. Sentences with similar trailing terminals should have their corresponding parse tree representations mapped to nearby locations in the representational space. The study provides concrete evidence that encoding the linearized parse trees as obtained via preorder traversal can satisfy such a requirement.     

A user-extensible and adaptable parser architecture

Some parsers need to be very precise and strict when parsing, yet must allow users to easily adapt or extend the parser to parse new inputs, without requiring that the user have an in-depth knowledge and understanding of the parser’s internal workings. This paper presents a novel parsing architecture, designed for parsing Postfix log files, that aims to make the process of parsing new inputs as simple as possible, enabling users to trivially add new rules (to parse variants of existing inputs) and relatively easily add new actions (to process a previously unknown category of input). The architecture scales linearly or better as the number of rules and size of input increases, making it suitable for parsing large corpora or months of accumulated data.     

Visual language implementation through standard compiler–compiler techniques

We present a technique for implementing visual language compilers through standard compiler generation platforms. The technique exploits eXtended Positional Grammars (XPGs, for short) for modeling the visual languages in a natural way, and uses a set of mapping rules to translate an XPG specification into a translation schema. This lets us generate visual language parsers through standard compiler–compiler techniques and tools like YACC. The generated parser accepts exactly the same set of visual sentences derivable through the application of XPG productions. The technique represents an important achievement, since it enables us to perform visual language compiler construction through standard compiler–compilers rather than specific compiler generation tools. This makes our approach particularly appealing, since compiler–compilers are widely used and rely on a well-founded theory. Moreover, the approach provides the basis for the unification of traditional textual language technologies and visual language compiler technologies.     

Incremental LR parsers

Summary The concept of incremental parsing is briefly introduced. An algorithm which augments an LR parser with the capability of reanalyzing a limited part of a modified program is illustrated. The algorithm operates on a sequence of configurations representing the parse of the old input and finds the smallest part of the sequence which must be recomputed to obtain the parse of the new input.The implementation is discussed: a suitable data structure and a version of the algorithm which operates upon it are introduced; finally the problem of realizing efficient incremental parsers is faced, showing a modification to the basic algorithm which enable the reanalysis to be performed in linear time.Work supported by C.N.R., Italy     

Towards Incremental Parsing of Natural Language Using Recursive Neural Networks

In this paper we develop novel algorithmic ideas for building a natural language parser grounded upon the hypothesis of incrementality. Although widely accepted and experimentally supported under a cognitive perspective as a model of the human parser, the incrementality assumption has never been exploited for building automatic parsers of unconstrained real texts. The essentials of the hypothesis are that words are processed in a left-to-right fashion, and the syntactic structure is kept totally connected at each step.Our proposal relies on a machine learning technique for predicting the correctness of partial syntactic structures that are built during the parsing process. A recursive neural network architecture is employed for computing predictions after a training phase on examples drawn from a corpus of parsed sentences, the Penn Treebank. Our results indicate the viability of the approach and lay out the premises for a novel generation of algorithms for natural language processing which more closely model human parsing. These algorithms may prove very useful in the development of efficient parsers.     

BRNGLR: a cubic Tomita-style GLR parsing algorithm

Tomita-style generalised LR (GLR) algorithms extend the standard LR algorithm to non-deterministic grammars by performing all possible choices of action. Cubic complexity is achieved if all rules are of length at most two. In this paper we shall show how to achieve cubic time bounds for all grammars by binarising the search performed whilst executing reduce actions in a GLR-style parser. We call the resulting algorithm Binary Right Nulled GLR (BRNGLR) parsing. The binarisation process generates run-time behaviour that is related to that shown by a parser which pre-processes its grammar or parse table into a binary form, but without the increase in table size and with a reduced run-time space overhead. BRNGLR parsers have worst-case cubic run time on all grammars, linear behaviour on LR(1) grammars and produce, in worst-case cubic time, a cubic size binary SPPF representation of all the derivations of a given sentence.