/ 
Parse-Eyapp-1.21
River stage one • 1 direct dependent • 4 total dependents
/ examples/debuggingtut/nopackrat2.eyp

SYNOPSIS

Packrat parsers cannot recognize some unambiguous grammars, such as the following Example taken from Bryan Ford (2002): Functional Pearl: Packrat Parsing: Simple, Powerful, Lazy, Linear Time

S : x' S 'x' | 'x'

In fact, neither LL(k) nor LR(k) parsing algorithms are capable of recognizing this example.

This grammar is a more complex variant of the former.

Compile this grammar with:

eyapp -C nopackrat2.eyp

Run the program with s.t. like:

./nopackrat2.pm -t -m 1 -i -c '2*3; 4+2; a+1; 2; a;'

SEE ALSO

  • File nopackrat.eyp

  • http://en.wikipedia.org/wiki/Parsing_expression_grammar, entry 'Parsing expression grammar' in the Wikipedia

  • Bryan Ford (2002). Functional Pearl: Packrat Parsing: Simple, Powerful, Lazy, Linear Time http://pdos.csail.mit.edu/~baford/packrat/icfp02/packrat-icfp02.pdf

  • "Packrat Parsers Can Support Left Recursion". PEPM '08. January 2008. http://www.vpri.org/pdf/tr2007002_packrat.pdf. Retrieved 2009-08-04.