[antlr-interest] ast rewrites in left-recursive rules

Douglas Godfrey douglasgodfrey at gmail.com
Thu Feb 24 07:31:33 PST 2011


Each parse state where a binary operator is encountered there must be a left
and right sub-expression.
For the Antlr grammar something like $lhs and $rhs would be a natural
expression of these sub-expressions:
e :
     ( e '.' ID    -> ^( '.' e ID)                 | e '.' 'this'    -> ^(
'.' e 'this' )  )             // group equal precedence rules
  |  ( '-' e        -> ^( '-' e )                     | '+' e           ->
^( '+' e )   )                   // equal precedence and unary operators
  |  ( e '*' e     -> ^( '*' e.$lhs e.$rhs )  | e '/' e         -> ^( '/'
e.$lhs e.$rhs )  )   // equal precedence and binary operators
  |  ( e '-' e     -> ^( '-' e.$lhs e.$rhs )  | e '+' e         -> ^( '+'
e.$lhs e.$rhs )  ) // equal precedence and binary operators
  |  ( INT        -> INT                          | ID               -> ID
)                              // no operator
  ;

On Wed, Feb 23, 2011 at 7:37 PM, Terence Parr <parrt at cs.usfca.edu> wrote:

> So I have it working with rewrite rules now:
>
> e : e '.' ID                    -> ^('.' e ID)
>  | e '.' 'this'                -> ^('.' e 'this')
>  | '-' e                       -> ^('-' e)
>  | e '*' b=e                   -> ^('*' e $b)
>  | e (op='+'|op='-') b=e       -> ^($op e $b)
>  | INT                         -> INT
>  | ID                          -> ID
>  ;
>
> But take a look at the multiplication rule: it needs a label on the second
> e. plain e is ambiguous. I decided that plain e references the left
> recursive version; since it will disappear during the transformation,
> putting a label on that one won't work. we have to put a label on the second
> reference as you see above. this is not optimal. can anyone think of a
> better way to differentiate between the left and right e references in a
> single alternative? [Note that e refers to the entire tree created so far.]
>
> Ter
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>


More information about the antlr-interest mailing list