Nice ! It will make debugging easier too I imagine. Michael
On 20 February 2011 13:21, Terence Parr <[email protected]> wrote: > howdy. Finally got around to supporting left-recursion in limited > circumstances. I started looking at it 2008: > > http://www.antlr.org/wiki/display/~admin/2008/03/23/Faster+expression+parsing+for+ANTLR > > Specifically, the building of perhaps 20 rules to handle the different > precedence levels of arithmetic expressions and top-down parsers is heinous. > The LR bottom up version is much easier to read but is, of course is > ambiguous. I'm working on a little prototype where you specify an LR-like > rule for arithmetic expressions and ANTLR can translate it to a "precedence > climbing" rule without left recursion. It uses a predicate to simply compare > the precedence of the previous operator with the precedence of the next > operator coming down the road. The order of the alternatives provides the > precedence of operations from loosest to tightest binding. > > At least for now, I'm distinguishing rules with left recursion you want > removed by using '/' instead of '|' for the alternative operator. In > principle, I can simply look for patterns in any rule (works great for > declarations too) and avoid the special operator. > > Anyway, here is my test cases: > > grammar V; > options {output=AST;} > > e : e ('+'^|'-'^) e > / e '*'^ e > / '-'^ e > / e '.'^ ID > / INT > / ID > ; > > ID : 'a'..'z'+ ; > INT : '0'..'9'+ ; > WS : (' '|'\t'|'\n')+ {skip();} ; > > it gets translated to > > start: e : e_[0] ; > e_[int _p] > : e_primary > ( {1 >= _p}?=> ('+'^|'-'^) e_[2] > | {2 >= _p}?=> '*'^ e_[3] > | {4 >= _p}?=> '.'^ ID > )* > ; > e_primary > : '-'^ e_[3] > | INT > | ID > ; > > here are some sample input-output pairs using my test rig; input text to > trees: > > 3+a.b (+ 3 (. a b)) > a.b+3 (+ (. a b) 3) > a.b+3*4 (+ (. a b) (* 3 4)) > -b * c (* (- b) c) > a + -b * c (+ a (* (- b) c)) > > I have to get the left vs right associativity in still, but I am encouraged > by these early results. This translation results in a massive space reduction > in the generated parsers over the typical 20-level chain of rules for > arithmetic expression parsing. It should also prove incredibly fast in > comparison. For example, the standard solution requires 20 method calls to > match an integer vs 1 or 2 here. > > And, oh yea, it will actually work for C declarators too :) > > declarator > : '*' declarator > / declarator '[' e ']' > / declarator '[' ']' > / declarator '(' ')' > / '(' declarator ')' > / ID > ; > > ter > > List: http://www.antlr.org/mailman/listinfo/antlr-interest > Unsubscribe: > http://www.antlr.org/mailman/options/antlr-interest/your-email-address > List: http://www.antlr.org/mailman/listinfo/antlr-interest Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address -- You received this message because you are subscribed to the Google Groups "il-antlr-interest" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/il-antlr-interest?hl=en.
