Lazy Combinators for Executable Specifications of General Attribute Grammars
A lazy-evaluation based top-down parsing algorithm has been implemented as a set of higher-order functions (combinators) which support directly-executable specifications of fully general attribute grammars. This approach extends aspects of previous approaches and allows natural language processors to be constructed as modular and declarative specifications while accommodating ambiguous context-free grammar (including direct and indirect left-recursive rules), augmented with semantic rules with arbitrary attribute dependencies (including dependencies from right). This one-pass syntactic and semantic analysis method has polynomial time and space for processing ambiguous input, and helps language developers build and test their models with no concern for the underlying computational methods.
Keywords: Parser combinators, Lazy evaluation, Top-down parsing, Attribute grammars, Natural-language processing