An LR parsing technique for extended context-free grammars
5
Citation
16
Reference
10
Related Paper
Citation Trend
Keywords:
Parsing expression grammar
S-attributed grammar
LR parser
Indexed grammar
Derivations from Two-Level Grammars have been defined only in terms of the infinite context-free grammars that can be generated from them. This fact has proven a severe theoretical obstacle to solving the parsing problem for two-level grammars. So far, partial solutions exist for Van Wijngaarden Grammars, Extended Affix Grammars, and Affix Grammars which allow parsing in a single pass from left to right, because these special cases could be handled without developing a full theory of parsing for two-level grammars. In this paper, we propose a new theory of Extended Affix Grammar derivations. The key idea is to use a graph grammar for modelling the two-level derivation process. This allows us to give a precise definition of a parse, which applies correctly to any well-formed Extended Affix Grammar. The concept of multi-pass parsing originates from practical compiler design, where parses are organized as a sequence of passes in order to avoid random access to the full parse tree. We demonstrate how this concept can be incorporated into our theoretical framework by means of canonical graph derivations. This allows us not only to establish the adequacy of the multi-pass approach, but can also be used as a complexity measure for Extended Affix Grammars.
Affix
S-attributed grammar
Cite
Citations (1)
Existing technology can parse arbitrary context-free grammars, but only a single, static grammar per input. In order to support more powerful syntax-extension systems, we propose reflective grammars, which can modify their own syntax during parsing. We demonstrate and prove the correctness of an algorithm for parsing reflective grammars. The algorithm is based on Earley's algorithm, and we prove that it performs asymptotically no worse than Earley's algorithm on ordinary context-free grammars.
Parsing expression grammar
Indexed grammar
S-attributed grammar
Cite
Citations (0)
In this paper we will present a way to parse two-dimensional languages using LR parsing tables. To do this we describe two-dimensional (positional) grammars as a generalization of the context-free string grammars. The main idea behind this is to allow a traditional LR parser to choose the next symbol to parse from a two-dimensional space. Cases of ambiguity are analyzed and some ways to avoid them are presented. Finally, we construct a parser for the two-dimensional arithmetic expression language and implement it by using the tool Yacc.
Parsing expression grammar
S-attributed grammar
Indexed grammar
LR parser
Top-down parsing language
Cite
Citations (6)
Existing technology can parse arbitrary context-free grammars, but only a single, static grammar per input. In order to support more powerful syntax-extension systems, we propose reflective grammars, which can modify their own syntax during parsing. We demonstrate and prove the correctness of an algorithm for parsing reflective grammars. The algorithm is based on Earley's algorithm, and we prove that it performs asymptotically no worse than Earley's algorithm on ordinary context-free grammars.
Parsing expression grammar
Indexed grammar
S-attributed grammar
Cite
Citations (0)
Parsing expression grammar
S-attributed grammar
LR parser
Indexed grammar
Cite
Citations (5)
This report describes a new algorithm for top-down parsing of general context-free grammars. The algorithm does not require any changes to be made to the grammar, and can parse with respect to any grammar non-terminal as the start symbol. It is possible to generate all possible parse trees of the input string in the presence of ambiguous grammars. The algorithm reduces to recursive descent parsing on LL grammars. This algorithm is ideal for use in software development environments which include tools such as syntax-directed editors and incremental parsers, where the language syntax is an integral part of the user-interface. General context-free grammars can describe the language syntax more intuitively than, for example, LALR(1) grammars. This algorithm is also applicable to batch-oriented language processors, especially during the development of new languages, where frequent changes are made to the language syntax and new prototype parsers need to be developed quickly. A prototype implementation of a parser generator that generates parsers based on this algorithm has been built. Parsing speeds of around 1000 lines per second have been achieved on a Sun SparcStation 2. This demonstrated performance is more than adequate for syntax-directed editors and incremental parsers, and in most cases, is perfectly acceptable for batch-oriented language processors.
Parsing expression grammar
LR parser
Indexed grammar
S-attributed grammar
Cite
Citations (0)
We consider methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions. These methods involve the use of ambiguous context-free grammars together with rules to resolve syntactic ambiguities. We show how efficient LL and LR parsers can be constructed directly from certain classes of these specifications.
Parsing expression grammar
S-attributed grammar
LR parser
Top-down parsing language
Cite
Citations (16)
In this paper M-grammars that are used in the Rosetta translation system will be looked at as the specification of attribute grammars. We will show that the attribute evaluation order is such that instead of the special-purpose parsing and generation algorithms introduced for M-grammars in Appelo et al.(1987), also Earley-like context-free parsing and ordinary generation strategies can be used. Furthermore, it is illustrated that the attribute grammar approach gives an insight into the weak generative capacity of M-grammars and into the computational complexity of the parsing and generation process. Finally, the attribute grammar approach will be used to reformulate the concept of isomorphic grammars.
Parsing expression grammar
Indexed grammar
S-attributed grammar
Definite clause grammar
Synchronous context-free grammar
Embedded pushdown automaton
Cite
Citations (0)
Methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions are considered. These methods involve the use of ambiguous context-free grammars together with rules to resolve syntactic ambiguities. It is shown how efficient LR and LL parsers can be constructed directly from certain classes of these specifications.
Parsing expression grammar
LR parser
S-attributed grammar
Cite
Citations (108)
This technical report presents a general framework for parsing a variety of grammar formalisms. We develop a grammar formalism, called an Abstract Grammar, which is general enough to represent grammars at many levels of the hierarchy, including Context Free Grammars, Minimalist Grammars, and Generalized Context-free Grammars. We then develop a single parsing framework which is capable of parsing grammars which are at least up to GCFGs on the hierarchy. Our parsing framework exposes a grammar interface, so that it can parse any particular grammar formalism that can be reduced to an Abstract Grammar.
Parsing expression grammar
S-attributed grammar
Cite
Citations (0)