On LR(k) grammars and languages

Many different definitions for LR(k) grammars exist in the literature. One of these definitions is chosen and many important implications are drawn from it. In particular, the LR(k) characterization theorem provides valuable information about chains of derivations. The LR(0) languages are then characterized by acceptance by deterministic pushdown automata with a special termination condition, by a condition on the strings in the language, and set theoretically. Important closure properties of the LR(0) languages and a related class of languages are then examined. These are used to examine some decidability questions relating to the class of LR languages. One of these questions is shown to be equivalent to the equality problem for deterministic pushdown automata.A survey of other LR(k) definitions is given and the exact differences are characterized. On the basis of this analysis, justification for the choice of definition used here is provided.     

Parsing Non-LR(k) grammars with yacc

Of the parser generating tools currently in use, yacc (or one of its several variants) is perhaps the most frequently employed. However, because of inherent ambiguities there are some languages (such as C++) that a yacc-generated parser cannot successfully compile. This paper describes a set of minor modifications to yacc-like tools that allows them to be used in a straightforward way to parse ambiguities and, more generally, grammars that require an indefinite amount of lookahead. Required changes to the lexical analyzer are also discussed, and the application of these techniques is illustrated within the context of specific examples.     

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.     

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.     

LR(0) grammars generated by LR(0) parsers

Summary Let be an LR(0) parser of a given LR(0) grammar G. Generally, does not only parse the words generated by G but also the words of some other LR(0) grammars different from G. In this paper we shall define a class of LR(0) parsers and shall present a characterization and a method for the construction of all LR(0) grammars which can be parsed by a given LR(0) parser.     

On comparingLL(k) andLR(k) grammars

A new and rigorous proof of the well-known fact thatLL(k) grammars areLR(k) grammars is provided. The proof is elementary in the sense that it is directly based on relations defining leftmost and rightmost derivations and no additional formalism is needed.     

A direct complement construction for LR(1) grammars

The traditional complement construction for grammars is long and tedious and causes all of the structure of the original grammar to be lost. A new construction method is introduced which produces a complement grammar that is closely related to the original grammar and therefore amenable to further analysis. The method is demonstrated by means of a nontrivial example. Received October 14, 1993 / July 20, 1995     

On LLP(k) grammars and languages

The paper studies the family of LLP(k) grammars introduced by Lomet. Two new grammatical characterizations for this class are presented. The first one shows that these grammars form an extension of strict deterministic grammars, in particular, any strict deterministic grammar is an LLP(0) one. LLP(k) grammars share with this subclass many important mathematical properties. The second characterization proves LLP(k) grammars to be a natural cross between LL(k) and LR(k) grammars. Relationships between corresponding families of languages are also investigated.     

On the definition of ELR(k) and ELL(k) grammars

Summary Extended context free grammars are obtained by allowing regular expressions on the right hand sides of production rules of context free grammars. The LR(k) and LL(k) conditions are made applicable to these grammars by defining canonical transformations of extended grammars into context free grammars.     

Semantic routines and LR(k) parsers

Summary Most applications of parsing require that the parser call semantic action routines while processing the input. For LR(k) parsers it is well known that a semantic action routine can be called when the end of a production is recognized. Often, however, it is desirable to call routines at other times.This paper presents fast algorithms that determine, for an LR(k) (or SLR(k)) grammar, which positions are suitable for calling routines. The algorithms are practical for use with LR(1) (SLR(1)) parser building programs, because the worst case running time is dominated by the time required to build the LR(1) (SLR(1)) parser. Applications of the algorithms to attribute grammars and automatic indentation are discussed.     

LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata

The paper introduces a subfamily of synchronized alternating pushdown automata, deterministic synchronized alternating pushdown automata, and a subfamily of conjunctive grammars, $LR(0)$ conjunctive grammars. It is shown that deterministic synchronized alternating pushdown automata and $LR(0)$ conjunctive grammars have the same recognition/generation power, analogously to the classical equivalence between acceptance by empty stack of deterministic pushdown automata and $LR(0)$ grammars. These models form the theoretical basis for efficient linear time parsing of a subfamily of conjunctive languages which properly includes the classical $LR(0)$ languages.     

LR分析的教学法探讨

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

Parsing regular grammars with finite lookahead

Summary Not every unambiguous regular grammar can be parsed by a finite state machine, even if a lookahead facility is added to the machine's capabilities. Those which can be parsed with a fixed lookahead of k are said to be FL(k). If such a grammar has n non-terminals, it never needs more than (n(n–1)/2) + 1 lookahead, and there exist grammars which do require this much. An algorithm is presented for determining whether a grammar is fixed lookahead parsable, and if so, for finding the minimum lookahead needed. The algorithm sets up and solves a set of O(n²) equations using O(n⁴) steps. Two parsing methods for FL(k) grammars are discussed. One uses a large precomputed parsing table, and operates in real time. The second parses an input string in time proportional to its length, while using approximately 3n storage locations.     

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

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

A method for transforming grammars into LL(k) form

Summary A new method for transforming grammars into equivalent LL(k) grammars is studied. The applicability of the transformation is characterized by defining a subclass of LR(k) grammars, called predictive LR(k) grammars, with the property that a grammar is predictive LR(k) if and only if the corresponding transformed grammar is LL(k). Furthermore, it is shown that deterministic bottom-up parsing of a predictive LR(k) grammar can be done by the LL(k) parser of the transformed grammar. This parsing method is possible since the transformed grammar always left-to-right covers the original grammar. The class of predictive LR(k) grammars strictly includes the class of LC(k) grammars (the grammars that can be parsed deterministically in the left-corner manner). Thus our transformation is more powerful than the one previously available, which transforms LC(k) grammars into LL(k) form.     

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.     

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.