[antlr-interest] Simple left recursive grammar and rewriting (how can it be done)

edA-qa mort-ora-y e.mortoray at ecircle.com
Fri Nov 28 06:26:44 PST 2008

I want a very basic expression parsing in my grammer so that expressions
like this can be parsed:

( ( A OR B OR D ) AND (E OR F) )

The resulting tree should be:
  OR A, B, D
  OR E,F

The ideal grammar looks like

    : terminal
    | '(' expr ( OR expr ) ')' -> ^(OR expr*)
    | '(' expr ( AND expr ) ')' -> ^(AND expr*)

Where terminal is some other rule (simple) and OR : 'OR'; , AND : 'AND'; 

This causes the troublesome non-LL(*) error due to the left recursion.

These can usually be factored out, but there are two problems here I
don't know how to resolve.
1. Each bracketed section may contain only OR or AND, not combinations
thereof (there is no precedence supported)
2. The rewriting should group the entire bracketed section into a single
node under OR or AND.

Any help would be appreciated.


edA-qa mort-ora-y
Director Quality Assurance
eCircle AG - Inside Digital Marketing
Nymphenburger Str. 86
80636 München

Tel    +49-89-12009-773
Fax    +49-89-12009-750

E-Mail mailto:e.mort-ora-y at ecircle.com
Web    http://www.ecircle.com

"Inside Digital Marketing" - der Newsletter für die
Online-Branche von eCircle. Jeden Monat neu & voll
mit aktuellen Fallstudien und hilfreichen Tipps!
Jetzt kostenlos abonnieren:


eCircle AG, HRB 136 334, Handelsregister München
Vorstand:  Lothar Lanz, Volker Wiewer (Vorsitzende), 
Thomas Wilke, Lars Wössner, Alexander Meyer
Vorsitzender des Aufsichtsrates: Dr. Mark Wössner

More information about the antlr-interest mailing list