[antlr-interest] How to remove mutual left recursion from this grammar?

[Kyle Ferrio]

Hi Seref.

I see Jim Idle has already provided a perfect answer to your question.  I'd
just like to make a shameless plug for Honey Badger (and save Ter from a
bit of embarrassing self-promotion) by pointing out that in antlr4 you will
be able to do this:

grammar Boolean;

rul
  : contains_expr
  ;

contains_expr
  : 'CONTAINS' contains_expression
  ;

contains_expression : class_expression
                    | contains_expression_boolean
                    |'(' contains_expression_boolean ')'
                    ;

contains_expression_boolean
  : contains_expression_boolean 'AND' contains_expression_boolean
  | contains_expression_boolean 'OR'  contains_expression_boolean
  | contains_expression_boolean 'XOR' contains_expression_boolean
  | class_expression
  ;

class_expression
   : ID
   ;

ID
  : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
  ;

and with that, turn this

CONTAINS a OR b AND c

into this [1]

(rul (contains_expr CONTAINS (contains_expression
(contains_expression_boolean (contains_expression_boolean_
(contains_expression_boolean_primary (class_expression a)) OR
(contains_expression_boolean_ (contains_expression_boolean_primary
(class_expression b)) AND (contains_expression_boolean_
(contains_expression_boolean_primary (class_expression c)))))))))

N.B. Looking closely, you will spy two very large clues as to how Honey
Badger deals with (direct) left-recursion.

Note the nesting (or just look at how AND binds more tightly than OR in the
attached PDF [2]) -- you get direct left-recursion and precedence control
for free!

What is really neat (to me at least) is how in some common situations (and
your grammar fits the pattern) being able to handle direct left-recursion
actually eliminates the mutual left recursion.  To be sure, it is not hard
to generate mutual left-recursion problems.  But it's nice when something
good goes our way.

"Honey Badger is bad ass."

Cheers!
Kyle

[1] generated with

$ java org.antlr.v4.runtime.misc.TestRig Boolean rul -print
BooleanTest01.txt

[2] generated with

$ java org.antlr.v4.runtime.misc.TestRig Boolean rul -gui -ps
out.psBooleanTest01.txt
$ ps2pdf out.ps out.ps





On Wed, Jan 4, 2012 at 10:34 AM, Seref Arikan <
serefarikan at kurumsalteknoloji.com> wrote:

> Greetings,
> This simple grammar represents a setup  I could not fix. Obviously the
> target is to create nested boolean statements, but I could not fix the
> recursion. This pattern repeats in a larger grammar, so solving this will
> help me fix more problems. Any clues that you can think of?
>
>
> //--------------------------------------------------------------------------------
> grammar testg;
>
> rul    :  contains_expr    ;
>
> contains_expr: 'CONTAINS' contains_expression
>                  //'CONTAINS' contains_or
>        ;
>
> contains_expression : class_expression
>                        | contains_expression_boolean
>                        |'(' contains_expression_boolean ')'
>        ;
>
> contains_expression_boolean : contains_expression 'OR' contains_expression
>                              | contains_expression 'AND'
> contains_expression
>                              | contains_expression 'XOR'
> contains_expression
>        ;
>
>
>
>
> class_expression
>    : ID
>    ;
>
>
>
> ID  :    ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
>    ;
>
>
>
> Best regards
> Seref
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: out.pdf
Type: application/pdf
Size: 3016 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20120104/0654c43d/attachment.pdf