AT&T Labs Research - Mandelbaum, Yitzhak H.

(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in 11th International Workshop on Language Descriptions, Tools, and Applications (LDTA 2011) , 2011-03-26

{Yakker is a parser generator that supports both semantic actions and speculative parsing techniques such as backtracking and context-free lookahead. To avoid executing semantic actions in parses which will eventually be discarded, we divide parsing into two phases. In the first (early) phase, the parser explores multiple possible parse trees before settling on a final parse tree or parse trees, without executing semantic actions. The second (late) phase executes the delayed semantic actions. We structure the early phase as a transducer which maps the input language to an output language of labels. A string in the output language is a history of the semantic actions that would have been executed in a parse of the input. The late phase is implemented as a deterministic, recursive descent parse of the history. We formalize delayed semantic actions and discuss a number of practical issues involved in implementing them in Yakker, including our support for regular right part grammars and dependent parsing, the design of the history data structure, and memory management techniques critical for efficient implementation. }

The definitive version was published in2011 European Symposium on Programming. , 2011-03-26

{Dependent grammars extend context-free grammars by allowing semantic values to be bound to variables and used to constrain parsing. Dependent grammars can cleanly specify common features that cannot be handled by context-free grammars, such as length fields in data formats and significant indentation in programming languages. Few parser generators support dependent parsing, however. To address this we have developed a new method for implementing dependent parsers by extending existing parsing algorithms. Our method proposes a point-free language of dependent grammars, which we believe closely corresponds to existing context-free parsing algorithms, and gives a novel transformation from conventional dependent grammars to point-free ones. To validate our technique, we have specified the semantics of both source and target dependent grammar languages, and proven our transformation sound and complete with respect to those semantics. Furthermore, we have empirically validated the suitability of our point-free language by adapting four parsing engines to support it: an Earley parsing engine; a GLR parsing engine; memoizing, arrow-style parser combinators; and PEG parser combinators.}

AT&T Labs Research — Leading Invention, Driving Innovation

site map