Methods for the automatic construction of error correcting parsers

Summary Methods for the automatic construction of error handling parsers are presented. The resulting parsers are capable of correcting all syntax errors by insertion and/or deletion of terminal symbols to the right of the error location. Thus, the output of the parser always corresponds to a syntactically valid program. This contributes significantly to the reliability and robustness of a compiler. The speed of parsing correct parts of a program is not affected by the presence of the error handling capability. The correction algorithm is easy to implement. Apart from the parsing tables only one character per parser state is required to control the correction process. The method is applicable to a wide class of stack automata including LL(k), LR(k), SLR(k), and LALR(k) parsers. It is shown that for LL(k) grammars error correction can be obtained as a byproduct of the canonical LL(k) parser generation. A similar result can be obtained for LR(k) grammars if the parser generator is slightly modified. The method has been successfully added to an LALR(1) parser generator.     

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.     

Eliminating unit reductions from LR(k) parsers using minimum contexts

Summary This paper presents a new approach to the design and the proof of bypassed LR(k) parsers; a bypassed LR(k) parser is an LR(k) parser which does not perform any reductions caused by insignificant unit productions. We show that bypassed LR(k) parsers having minimum set of reduction contexts always exist for Knuth LR(k) parsers, but do not necessarily exist for SLR(k) and LALR(k) parsers. As byproducts of our approach, we naturally derive Anderson, Eve and Homing's algorithm [5] and a sufficient condition for the existence of bypassed SLR(1) parsers.     

Constructing LR parsers for regular right part grammars

Summary Regular right part (RRP) grammars differ from context free (CF) grammars by virtue of the fact that the production right parts are nondeterministic finite automatons (FAs). LR(k) parsers for RRP grammars are linear time parsers which can determine the right end of each handle by considering at most k terminal symbols to its right and the left end (after the right end has been found) by considering at most one parse stack state to its left. This paper is concerned with the construction of a class of LR(k) parsers for RRP grammars which makes use of FAs for determining both the right and left ends of the handle.This work has been supported by a Carleton University grant and National Research Council of Canada grant no. A3585     

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.     

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.     

Lar(m,c, l) grammars

We present the class of LAR(M, C, L) context-free grammars: a generalization of several classes of fixed and arbitrary lookahead LR grammars that appear in the literature. The parser construction is based on three parameters M, C and L; M and C determine the type of parser, and L is the amount of lookahead. Specific settings of these parameters yield fixed-lookahead grammar classes such as LALR(k), SLR(k) and NQLALR, along with several arbitrary lookahead classes, all of which are subsets of LR-Regular. Thus both fixed and arbitrary lookahead LR techniques are described (and implemented) by one powerful model.     

Yet another generation of LALR parsers for regular right part grammars

In this paper we introduce two methods for building LALR parsers for regular right part grammars (RRPGs). Both methods build a parser directly from a grammar, require no extra state or data structure, and can deal with all LALR RRPGs. The first method is quite simple. For almost all LALR RRPGs, including the majority of grammars with stacking conflicts, parsing actions are similar to those of LALR parsers for usual context free grammars. No extra action is required to recognize a handle in this case. For other LALR RRPGs, the right hand side of a production is checked to recognize a handle. The second method does not require checking of the right hand side of a production to recognize a handle. Instead, it records the number of conflicts in LR items and in the stack. Unlike previous methods, our method needs no extra data structure. Received: 23 September 1998 / 16 March 2001     

Dynamic LL(k) parsing

A new class of context-free grammars, called dynamic context-free grammars, is introduced. These grammars have the ability to change the set of production rules dynamically during the derivation of some terminal string. The notion of LL() parsing is adapted to this grammar model. We show that dynamic LL() parsers are as powerful as LR() parsers, i.e. that they are capable to analyze every deterministic context-free language while using only one symbol of lookahead. Received: 24 August 1994 / 5 January 1996     

Generation of efficient LALR parsers for regular right part grammars

Summary A method for building small fast LALR parsers for regular right part grammars is given. No grammar transformation is required. No extra state of the LALR parser for the recognition of strings generated by a right part is required. At some reduce states the parser may refer to lookback states (states in which the parser may be restarted after the reduction). An optimizing algorithm to reduce these references is also given.     

Eliminating unit productions from LR parsers

Summary In this paper we show how one can improve upon an algorithm by Aho and Ullman [3] for eliminating unit productions from an LR(k) parser so that the elimination concerned can be made in all cases, instead of only in the special case required by [3] where no two unit productions have the same left-hand side. In most practical grammars this special case does not in fact arise. Since the elimination of unit productions both reduces the size of the parser and increases its speed, it is of value to have a general method for achieving this objective.The algorithm provided eliminates from the parser all nonterminals that occur as left-hand sides of unit productions. This substantially contributes to the reduction in size obtained, and also provides a solution to an open problem by Aho and Ullman [3]. An application of the Algorithm to the parser construction method of Pager [19] is considered, and a method is provided for the use of default reductions and the elimination of final states in conjunction with the elimination of unit reductions. The sizes of the parsers obtained using the parser's algorithm are compared with those of Anderson, Eve, and Horning [4].This work was supported by the National Science Foundation under Grant GJ-43362. A shortened version of the paper was presented at the 2nd colloquium on Automata, Languages and Programming, University of Saarbrücken, July 1974     

A convenient way to incorporate semantic actions in two-pass compiling schemes

We present a simple method for connecting semantic actions to parsers. Although applicable to any kind of parser it is especially suited for LR parsers. The method is based on the idea of separating syntax analysis and semantic processing and executing semantic actions by procedures, similar to those of a recursive descent compiler. The procedures are driven by structural information about the source program, which is collected during parsing. The method is applicable to L-attributed grammars. It can be incorporated easily into any existing parser.     

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 parsing automata approach to LR theory

Two simple but powerful tools are introduced in LR theory, viz. item grammars and parsing automata. Parsing automata are used to define a large class of correct prefix parsers operating in linear time. DeRemer's and Pager's parsing methods turn out to be special cases. LL and LC tests, as well as inclusion theorems for the classes of LL, LC, and LR grammars will be based on parsing automata, too.     

Parallel <Emphasis Type="Italic">LL</Emphasis> parsing

A deterministic parallel LL parsing algorithm is presented. The algorithm is based on a transformation from a parsing problem to parallel reduction. First, a nondeterministic version of a parallel LL parser is introduced. Then, it is transformed into the deterministic version—the LLP parser. The deterministic LLP(q,k) parser uses two kinds of information to select the next operation — a lookahead string of length up to k symbols and a lookback string of length up to q symbols. Deterministic parsing is available for LLP grammars, a subclass of LL grammars. Since the presented deterministic and nondeterministic parallel parsers are both based on parallel reduction, they are suitable for most parallel architectures.     

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.     

Foundations of Fast Communication via XML

Communication with XML often involves pre-agreed document types. In this paper, we propose an offline parser generation approach to enhance online processing performance for documents conforming to a given DTD. Our examination of DTDs and the languages they define demonstrates the existence of ambiguities. We present an algorithm that maps DTDs to deterministic context-free grammars defining the same languages. We prove the grammars to be LL(1) and LALR(1), making them suitable for standard parser generators. Our experiments show the superior performance of generated optimized parsers. Our results generalize from DTDs to XML schema specifications with certain restrictions, most notably the absence of namespaces, which exceed the scope of context-free grammars.     

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.