Skip to main content

Research Repository

Advanced Search

Modular and efficient top-down parsing for ambiguous left-recursive grammars

Frost, Richard; Hafiz, Rahmatullah; Callaghan, Paul

Authors

Richard Frost

Rahmatullah Hafiz

Paul Callaghan



Abstract

In functional and logic programming, parsers can be built as modular executable specifications of grammars, using parser combinators and definite clause grammars respectively. These techniques are based on top-down backtracking search. Commonly used implementations are inefficient for ambiguous languages, cannot accommodate left-recursive grammars, and require exponential space to represent parse trees for highly ambiguous input. Memoization is known to improve efficiency, and work by other researchers has had some success in accommodating left recursion. This paper combines aspects of previous approaches and presents a method by which parsers can be built as modular and efficient executable specifications of ambiguous grammars containing unconstrained left recursion.

Citation

Frost, R., Hafiz, R., & Callaghan, P. (2007). Modular and efficient top-down parsing for ambiguous left-recursive grammars. In 10th International Conference on Parsing Technologies, IWPT07, 23-24 June 2007, Prague, Czech Republic ; proceedings (109-120)

Conference Name 10th International Conference on Parsing Technology : IWPT'07
Conference Location Prague
Start Date Jun 23, 2007
End Date Jun 24, 2007
Publication Date Jun 1, 2007
Deposit Date Jan 9, 2009
Publisher Association for Computing Machinery (ACM)
Pages 109-120
Book Title 10th International Conference on Parsing Technologies, IWPT07, 23-24 June 2007, Prague, Czech Republic ; proceedings.
Keywords Parsing, Left-recursion, Ambiguity, Parsing combinators.
Publisher URL http://www.latl.unige.ch/iwpt2007/
Additional Information Conference dates: 23-24 June 2007.