We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Frost, R. and Hafiz, R. and 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. Morristown, NJ: Association for Computing Machinery, pp. 109-120.


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.

Item Type:Book chapter
Keywords:Parsing, Left-recursion, Ambiguity, Parsing combinators.
Full text:Full text not available from this repository.
Publisher Web site:
Record Created:09 Jan 2009
Last Modified:12 Nov 2010 11:03

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library