Incremental generation of LR parsers

Implementation of a new compiler usually requires making frequent adjustments to grammar definitions. An incremental technique for updating the parser tables after a monor change to the grammer could potentially save much computational effort. More importantly, debugging a grammar is made easier if the grammar is re-checked for correctness after each small change to the grammar. The basic design philosophy of an incremental parser generator, and incremental algorithms for LR(0), SLR(1) and LALR(1) parser generation are discussed in this paper. Some of these algorithms have been incorporated into an implementation of an incremental LALR(1) parser generator.     

LR分析的教学法探讨

LR分析法是编译程序语法分析中最常用且有效的自下而上的分析方法,理论较完善,适用于大多数上下文无关语言的分析。本文主要探讨LR分析的教学方法,采用"启发+关联式"教学法,引导学生理解LR分析的内涵。     

Error handling in a parallel LR substring parser

Parallel parsing is currently receiving attention but there is little discussion about the adaptation of sequential error handling techniques to these parallel algorithms. We describe a noncorrecting error handler implemented with a parallel LR substring parser. The parser used is a parallel version of Cormack's LR substring parser. The applicability of noncorrecting error handling for parallel parsing is discussed. The error information provided for a standard set of 118 erroneous Pascal programs is analysed. The programs are run on the sequential LR substring parser.     

Comparison of syntactic error handling in LR parsers

Error recovery techniques for LR parsers presented in the literature are described and classified. The techniques considered range from the non-correcting ones to interactive and incremental ones. Also, some of the techniques presented are compared and evaluated. An example showing the advantages and the disadvantages of each class of strategies is given and is used as a guideline for classifying syntax errors according to the recovery strategies which are more adequate to correct them.     

On the space optimizing effect of eliminating single productions from LR parsers

Summary Single productions in the syntax of a programming language usually have no semantic significance, and thus parsers can be modified so that they do not perform reductions by single productions. In this paper we show that the basic method developed by Pager for eliminating all undesired single productions from LR parsers can cause a quadratic increase in the number of states of the parser. We then define an improvement of Pager's basic method such that generally smaller parsers are produced; in fact, even a quadratic decrease in the number of states is possible. This improvement is further evaluated by giving a sequence of practically motivated grammars for which substantial savings in space are obtained. We also characterize this improvement by a grammatical condition under which it is guaranteed that no increase in the number of states can occur. This condition is compared with a similar condition derivable in the case of Pager's original method.Part of this work was carried out when the author was visiting the University of California, Department of Mathematics, at Santa Barbara as an ASLA Fulbright Scholar     

Embedding semantics in LR parser tables

This paper addresses two of the problems commonly associated with LR parsing and syntax directed translation schemes, namely grammar stratification and excessively large table size, A solution is discussed which can eliminate stratification of the grammar by allowing the designer to embed semantics directly within the LR table (i.e., at shift and error entries instead of just at reduce entries) and to use global context to determine what semantics should be performed. The non-stratified grammar can produce a significantly smaller LR table than the corresponding stratified grammar. The compatibility of this scheme with commonly used table compaction techniques is also discussed.     

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.     

Upper bounds on the size of LR(k) parsers

It is shown that in many cases the trivial upper bound 2^{|G|k + 1} on the number of states of an LR(k) parser for a grammar G is too conservative. In particular, if G is not right-recursive, the canonical LR(k) parser for G has at most |G^k|G|·2^|G| states. Examples of grammars with large LR(k) parsers are given.     

编译原理中的LR类分析方法的教学研究

编译原理课程的教学不仅要介绍编译的基本原理和技术,还要培养学生的学习兴趣、专业思维和科学研究的方法及能力,文章以LR类分析方法为例,以还原知识的发现过程为主线,重现解决问题的思路与方法,以期培养学生的专业学习兴趣和科研能力。     

An LR parsing technique for extended context-free grammars

Extended context-free grammars allow regular expressions to appear in productions right hand sides, and are a clear and natural way to describe the syntax of programming languages.In this paper an LR parsing technique for extended context-free grammars is presented, which is based on an underlying transformation of the grammar into an equivalent context-free one.The technique is suitable for inclusion in one-pass compilers: the implementation requires little extensions to the algorithms working for normal LR grammars. Besides describing the parsing method, the paper shows also the algorithms for deriving the parsing tables; tables optimization is also discussed. Finally, this technique is compared with other proposals appeared in the literature.     

语法分析方法研究评述及其应用

语法分析作为编译过程中一个不可缺少的步骤,对其进行研究有着非常重要的意义.阐述了语法分析方法研究的现状,并对之进行了具体的分析和探讨,介绍了语法分析方法的各种应用,对语法分析方法进行了总结和展望.     

On the relationship between the LL(k) and LR(k) grammars

In the literature various proofs of the inclusion of the class of LL(k) grammars into the class of LR(k) grammars can be found. Some of these proofs are not correct, others are informal, semi-formal or contain flaws. Some of them are correct but the proof is less straightforward than demonstrated here.     

A practical general method for constructing LR(k) parsers

Summary The paper presents in detail the case for k=1 of a practical general method for constructing LR(k) parsers. For k=1 this method is of rival efficiency to the previous general algorithm described by the author in [21]. The method involves combining the states of an LR(k) parser as they are generated, reducing to a fraction, in the process, the number of configurations that need actually be evaluated, or for which space must be assigned — compared to such general methods as those of [1, 11, 12, 17]. The criteria of compatibility introduced for this purpose are such that the parser obtained is in practice identical in size to, or negligibly larger than, that obtained by resolving the inadequacies of an LR(o) parser (as is done for various subsets of the LR(k) grammars in [5, 8, 14, 20]).This paper is a development of one of the ideas proposed in Pager [16]. The work was supported by the National Science Foundation under Grant GJ-43362.     

A practical minimum distance method for syntax error handling

We present a method for recovering from syntax errors encountered during parsing. The method provides a form of minimum distance repair, has linear time complexity, and is completely automatic. A formal method is presented for evaluating the performance of error recovery methods, based on global minimum-distance error correction. The minimum-distance error recovery method achieves a theoretically best performance on 80% of Pascal programs in the weighted Ripley-Druseikis collection. Comparisons of performance with other error recovery methods are given.     

程序设计语言的GLR优化分析

阐述了在程序设计语言语法分析器的构造中采用通用LR(generalized LR,简称GLR)分析算法的动机.提出了一个多层次的优化策略,加快了GLR分析器的分析速度.为基本的GLR算法增加了必要的运行时控制机制,以实现语法分析时调用文法规则附带的语义动作,化解输入串的二义性,同时避免GLR分析器可能存在的语义动作延迟问题.优化后的算法已在一个可视化语法分析器自动生成环境VPGE中实现.实验结果表明,在分析确定性的编程语言时,自动生成的GLR分析器的分析速度与自由软件基金会的Bison生成的LALR(1)分析器的分析速度有可比性.     

On the correct elimination of chain productions from lr parsers

A criterion is formally described which guarantees the correctness of a variety of chain-free LR parsers including the case of grammars containing ?-nonterminals. Using the criterion Pager's algorithm for the elimination of chain productions is shown to produce correct parsers for any compatible merging relation. Also, a mildly restricted version of a claim concerning chain-free SLR parsers made in [K&S 79] is proved correct.     

A scheme for LR(k) parsing with error recovery part II: error recovery

The paper is the second in a series of three papers devoted to a detailed study of LR(k) parsing with error recovery and correction. Error recovery in LR(k) parsing of a context-free grammar is formalized by extending an LR(k) parser of the grammar such that it accepts all strings over the terminal vocabulary. The parse produced by this extension for a terminal string is a right parse if the string is in the language. In the case of a string not in the language the parse produced by the extension contains so-called error productions which represent the error recovery actions performed by the extension. The treatment is based on the formalization of LR(k) parsing presented in the first paper in the series and it covers practically all error recovery methods designed for LR(k) parsing.     

LR(k)任意文法位置的断点调试方法

LR(k)文法能描述所有确定型上下文无关语言,广泛应用于各类分析器生成器中.传统的LR(k)文法断点调试方法仅支持在产生式右部末尾设置断点(后文简称尾部断点),不支持在产生式右部中间位置设置断点(后文简称中间断点),这给分析器的开发和调试带来了不便.文中提出了一种新颖的LR(k)文法断点调试方法,不但支持传统的尾部断点,还支持中间断点.该方法可显著增加可利用的断点数量,可以跟踪到更细粒度的文法成分,从而帮助用户更好地进行文法调试,降低分析器的开发难度.