180 Park Ave - Building 103
Florham Park, NJ
Subject matter expert in Security, Programming Languages
Delayed semantic actions in a dependent parser
Yitzhak Mandelbaum, Trevor Jim
11th International Workshop on Language Descriptions, Tools, and Applications (LDTA 2011),
2011.
[PDF]
[BIB]
ACM Copyright
(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.
}
A new method for dependent parsing
Trevor Jim, Yitzhak Mandelbaum
2011.
[BIB]
{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.}
A new method for dependent parsing
Yitzhak Mandelbaum, Trevor Jim
2011 European Symposium on Programming,
2011.
[PDF]
[BIB]
Springer-Verlag Copyright
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.}
Method for prevention of recursive loops between network elements,
Tue Jan 02 18:11:48 EST 2007
The occurrence of recursive loops between network elements are detected and prevented. One or more queries are generated that are sent between the network elements. One or more of the network elements detect the imminent occurrence of a recursive loop between the network elements, and prevent the recursive loop by generating an intensional answer in response to the query. The intensional answer contains rules.
