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.     

Parsing extended LR(k) grammars

Summary An extended LR(k) (ELR(k)) grammar is a context free grammar in which the right sides of the productions are regular expressions and which can be parsed from left to right with k symbol look-ahead. We present a practical algorithm for producing small fast parsers directly from certain ELR(k) grammars, and an algorithm for converting the remaining ELR(k) grammars into a form that can be processed by the first algorithm. This method, when combined with previously developed methods for improving the efficiency of LR(k) parsers, usually produces parsers that are significantly smaller and faster than those produced by previous LR(k) and ELR(k) algorithms.     

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.     

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.     

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.     

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.     

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.     

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     

Stochastic grammars and languages

This paper summarizes some recent results concerned with the extension of formal languages to their corresponding stochastic versions. Weighted grammars and languages are first defined, and stochastic grammars and languages are defined as a special case of weighted grammars and languages. Fuzzy grammars and languages, which have some properties similar to weighted grammars and languages, are also discussed. Stochastic automata are defined from the language recognition viewpoint. Languages accepted by stochastic finite-state and pushdown automata, with and without a cutpoint, are studied. Weighted and stochastic programmed and indexed grammars, and stochastic nested stack automata are defined. Finally, some decidability problems of stochastic (weighted, fuzzy) languages are discussed, and problems for further research are suggested.This work was supported by the National Science Foundation Grant GK-18225.     

On derivation languages corresponding to context-free grammars

Summary A derivation language associated with a context-free grammar is the set of all terminating derivations. Hierarchy and closure properties of these languages are considered. In addition to the formerly known solvability of the emptiness and finiteness problems the equivalence problem is shown to be solvable for derivation languages.     

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.     

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.     

On the languages generated by context-sensitive fuzzy grammars

It is proved that the family of the languages generated by 1-fold fuzzy grammars with context-sensitive rules and grade larger than λ,0≦λ<1, is equal to the family of the context sensitive languages. Also, one shows that the family of the languages generated by fuzzy grammars with context-sensitive rules and grade larger than λ,0≦λ<1, is included in the family of the context-sensitive languages.     

Simple chain grammars and languages

A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar.Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.     

Tile rewriting grammars and picture languages

Tile rewriting grammars (TRG) are a new model for defining picture languages. A rewriting rule changes a homogeneous rectangular subpicture into an isometric one tiled with specified tiles. Derivation and language generation with TRG rules are similar to context-free grammars. A normal form and some closure properties are presented. We prove this model has greater generative capacity than the tiling systems of Giammarresi and Restivo and the grammars of Matz, another generalization of context-free string grammars to 2D. Examples are shown for pictures made by nested frames and spirals.     

Adaptive star grammars and their languages

Motivated by applications that require mechanisms for describing the structure of object-oriented programs, adaptive star grammars are introduced, and their fundamental properties are studied. In adaptive star grammars, rules are actually schemata which, via the cloning of so-called multiple nodes, may adapt to potentially infinitely many contexts when they are applied. This mechanism makes adaptive star grammars more powerful than context-free graph grammars. Nevertheless, they turn out to be restricted enough to share some of the basic characteristics of context-free devices. In particular, the underlying substitution operator enjoys associativity and confluence properties quite similar to those of context-free graph grammars, and the membership problem for adaptive star grammars is decidable.     

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

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