A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time
Authors:
Open Access
- 1 May 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 41 (5) , 46-54
Abstract
Top-down backtracking language processors are highly modular, can handle ambiguity, and are easy to implement with clear and maintainable code. However, a widely-held, and incorrect, view is that top-down processors are inherently exponential for ambiguous grammars and cannot accommodate left-recursive productions. It has been known for many years that exponential complexity can be avoided by memoization, and that left-recursive productions can be accommodated through a variety of techniques. However, until now, memoization and techniques for handling left recursion have either been presented independently, or else attempts at their integration have compromised modularity and clarity of the code.Keywords
This publication has 5 references indexed in Scilit:
- Mímico: a monadic combinator parser generatorJournal of the Brazilian Computer Society, 2003
- Guarded attribute grammarsSoftware: Practice and Experience, 1993
- Higher-order functions for parsingJournal of Functional Programming, 1992
- Efficient Parsing for Natural Language1986
- The predictive analyzer and a path elimination techniqueCommunications of the ACM, 1965