BTW, I spent a week recently and got ANTLR to support left-recursion with
linear algorithm that correctly handles precedence:
http://www.antlr.org/pipermail/antlr-interest/2011-February/040830.html
http://www.antlr.org/wiki/display/~admin/2008/04/10/Still+more+about+expression+parsing
[That stuff is all out of date (I don't use / anymore, for example).]
I use Hanson's expr alg.
http://onlinelibrary.wiley.com/doi/10.1002/spe.4380151206/abstract
Used in LCC compiler. More recently called "precedence climbing".
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing
Works great. ANTLR recognizes left prefix, suffix, binary, and ternary
operations with pattern matcher and transforms grammar to predicated
non-left-recursive grammar with linear performance. Parse tree is identical to
what left-recur grammar would yield. E.g., here is part of Java grammar that
works:
expression
: parExpression
| 'this'
| 'super'
| literal
| Identifier
| expression '.' Identifier
| expression '.' 'class' // should be type.class but causes backtracking
| expression '.' 'this'
| expression '.' 'super' '(' expressionList? ')'
| expression '.' 'super' '.' Identifier arguments?
| expression '.' 'new' Identifier '(' expressionList? ')'
| expression '.' explicitGenericInvocation
| 'new' creator
| expression '[' expression ']'
| '(' type ')' expression
| expression ('++' | '--')
| expression '(' expressionList? ')'
| ('+'|'-'|'++'|'--') expression
| ('~'|'!') expression
| expression ('*'|'/'|'%') expression
| expression ('+'|'-') expression
...
;
Example from upcoming PLDI paper:
declarator
: declarator '[' expression ']'
| declarator '[' ']'
| declarator '(' ')'
| '*' declarator
| '(' declarator ')'
| ID
;
becomes
declarator : declarator_[0] ;
declarator_[int _p]
: declarator_primary
(
( {_p <= 7}?=> '[' expression ']'
| {_p <= 6}?=> '[' ']'
| {_p <= 5}?=> '(' ')'
)
)*
;
declarator_primary
options {backtrack=true;}
: '*' declarator_[4] {}
| '(' declarator ')'
| ID
;
Only limitation is immediate-left-recur handled only. In my experience, that's
good enough :) No point in some complicated algorithm when this covers any
grammar I'd care about.
Coming soon to a theater near you (ANTLR v4 this year).
Terence_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
