A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time

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.

REFERENCES

• 1: Camarao, C., Figueiredo, L. and Oliveira, R. H. (2003) Mimico: A Monadic Combinator Compiler Generator. Journal of the Brazilian Computer Society Vol 9(1).
• 2: Frost, R. A. and Hafiz, R. (2006) Using monads to accommodate ambiguity and left recursion with parser combinators. Technical Report 06-007 School of Computer Science, University of Windsor, Canada.
• 3: Frost, R. A. (2003) Monadic memoization --- Towards Correctness-Preserving Reduction of Search. AI 2003 eds. Y. Xiang and B. Chaib-draa. LNAI 2671 66--80.
• 4: R. A. Frost, Guarded attribute grammars, Software—Practice & Experience, v.23 n.10, p.1139-1156, Oct. 1993 [doi>10.1002/spe.4380231006]
• 5: Hutton, G. (1992) Higher-order functions for parsing. J. Functional Programming 2 (3) 323--343.
• 6: Mark Johnson, Memoization in top-down parsing, Computational Linguistics, v.21 n.3, September 1995
• 7: Pieter W. M. Koopman , Marinus J. Plasmeijer, Efficient Combinator Parsers, Selected Papers from the 10th International Workshop on 10th International Workshop, p.120-136, September 09-11, 1998
• 8: K. Koskimies, Lazy recursive descent parsing for modular language implementation, Software—Practice & Experience, v.20 n.9, p.749-772, August 1990
• 9: Susumu Kuno, The predictive analyzer and a path elimination technique, Communications of the ACM, v.8 n.7, p.453-462, July 1965 [doi>10.1145/364995.365689]
• 10: Rene Leermakers, The Functional Treatment of Parsing, Kluwer Academic Publishers, Norwell, MA, 1993
• 11: Lickman, P. (1995) Parsing With Fixed Points. Master's Thesis, University of Cambridge.
• 12: Nederhof, M. J. and Koster, C. H. A. (1993) Top-Down Parsing for Left-recursive Grammars. Technical Report 93-10 Research Institute for Declarative Systems, Department of Informatics, Faculty of Mathematics and Informatics, Katholieke Universiteit, Nijmegen.
• 13: Peter Norvig, Techniques for automatic memoization with applications to context-free parsing, Computational Linguistics, v.17 n.1, March 1991
• 14: Shiel, B. A. 1976 Observations on context-free parsing. Technical Report TR 12-76, Center for Research in Computing Technology, Aiken Computational Laboratory, Harvard University.
• 15: Masaru Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publishers, Norwell, MA, 1985
• 16: Philip Wadler, How to replace failure by a list of successes, Proc. of a conference on Functional programming languages and computer architecture, p.113-128, January 1985, Nancy, France

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Language models; Language parsing and understanding

Keywords:
backtracking, left-recursion, memoization, parser combinators, top-down parsing