In this lecture we study how we can derive parsers from context-free grammars. We start with looking again at the semantics of context-free grammars as derivations. Then we observe that parsing is the inverse of derivation, i.e. reducing a sentence to a (start) symbol or parse tree. A shift-reduce parsers computes a right-most derivation for a sentence. The question is then how to make that process deterministic and efficient. First we see how item sets encode the state of a shift-reduce parser and make it clear what actions can be undertaking without consulting the grammar. Next, we compute the FOLLOW set of a grammar in order to determine which action to take next in case there are multiple possible actions in a state. This approach yields a linear deterministic parser for grammars in the the SLR(1) format, i.e. those grammars for which this method produces a parse table without shift/reduce conflicts.
Slides
References
-
Syntax definitions are pervasive in modern software systems, and serve as the basis for language processing tools like parsers and compilers. Mainstream parser generators pose restrictions on syntax definitions that follow from their implementation algorithm. They hamper evolution, maintainability, and compositionality of syntax definitions. The pureness and declarativity of syntax definitions is lost. We analyze how these problems arise for different aspects of syntax definitions, discuss their consequences for language engineers, and show how the pure and declarative nature of syntax definitions can be regained.
-
Disambiguation methods for context-free grammars enable concise specification of programming languages by ambiguous grammars. A disambiguation filter is a function that selects a subset from a set of parse trees---the possible parse trees for an ambiguous sentence. The framework of filters provides a declarative description of disambiguation methods independent of parsing. Although filters can be implemented straightforwardly as functions that prune the parse forest produced by some generalized, this can be too inefficient for practical applications. In this paper the optimization of parsing schemata, a framework for high-level description of parsing algorithms, by disambiguation filters is considered in order to find efficient parsing algorithms for declaratively specified disambiguation methods. As a case study the optimization of the parsing schema of Earley's parsing algorithm by two filters is investigated. The main result is a technique for generation of efficient LR-like parsers for ambiguous grammars modulo priorities.
-