[antlr-interest] Simple expression grammar

Daniels, Troy (US SSA) troy.daniels at baesystems.com
Wed May 14 09:49:16 PDT 2008


 

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org 
> [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Johannes Luber
> Sent: Wednesday, May 14, 2008 7:26 AM
> To: Maciej Bakalarz
> Cc: antlr-interest at antlr.org
> Subject: Re: [antlr-interest] Simple expression grammar
> 
> Maciej Bakalarz schrieb:
> > Hi !
> > 
> > I am newbie to ANTLR. I am trying to make very simple grammar which 
> > will be used to build AST for Guard Condition expressions. Guard 
> > Conditions expression are used as a labels in automata transitions.
> > 
> > This is my grammar:
> > 
> > grammar GuardCondition2;
> > 
> > options {
> >     output=AST;
> >     ASTLabelType=CommonTree;
> > }
> > 
> > prog:
> >     logical_or_expression+
> >     ;
> > 
> > logical_or_expression:
> >     logical_and_expression (OR_OP^ logical_and_expression)*
> >     ;
> > 
> > logical_and_expression
> >     : rel_expression (AND_OP^ rel_expression)*
> >     ;
> > 
> > rel_expression
> >     : expression (REL_OP^ expression)*
> >     ;
> > expression
> >     : ALFANUM
> >     ;
> > 

In this case, I think all you need to do is modify the grammar to be

expression
    :   ALPHANUM | LPAREN logical_or_expression RPAREN ;

This is a continuation of the idea that each rule refers to the next
higher operator in the operator precedence chain.  Once you've gotten to
expression, the only things you have left atomic tokens (ALPHANUM) and
parenthesized expressions.  There's no precedence between them: you just
have to choose whichever one you actually have.  If you do find a
parenthesized expression, then you have to go all the way back to the
bottom of the rule chain to resolve that.

Troy


> > LPAREN     :    '(' ;
> > RPAREN    :    ')' ;
> > REL_OP       :      '==' | '<' | '>' | '<=' | '>='|'!=' ;
> > OR_OP     :     '||' ;
> > AND_OP     :     '&&' ;
> > ALFANUM     :     (ID|INT)+;
> > ID      :       ('a'..'z'|'A'..'Z')+ ;
> > INT     :       '0'..'9'+ ;
> > WS      :       (' '|'\t')+ {skip();} ;
> > 
> > 
> > This grammar is working fine. Using this grammar I can parse 
> > expressions like "a>=3 || b<=4 && c>=4".
> > 
> > I need to parse expressions which are using nested 
> parenthesis, like:
> > "( a>=3 || b<=4 ) && c>=4" or "((a>=3 || b<=4) && c>=4) || a>=3 )"
> > 
> > I wast trying to modify grammar to achieve this goal but I 
> it always 
> > came up that I am using Left Recursion.
> > 
> > Does anybody knows how to modify grammar so nested 
> parenthesis would 
> > be possible ?
> 
> Left-recusrion isn't that much of a showstopper as you 
> believe. If your grammars orientates itself on the Java or C# 
> grammar, then you can use 
> <http://www.antlr.org/wiki/display/ANTLR3/Left-Recursion+Remov
> al> to get rid of the left-recursion.
> 
> Johannes
> 


More information about the antlr-interest mailing list