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

[Seref Arikan]

Kyle,
Sounds very interesting. I'm still trying to get my head around handling LL
approach. I found out that the grammar I have at hand has been created with
a LR parser framework. I'll probably have to move forward with antlr3, and
I'm sure Honey Badger will become a good option exactly when I finish my
work with antlr3...

Will keep an eye on this.

Cheers
Seref


On Wed, Jan 4, 2012 at 9:05 PM, Kyle Ferrio <kferrio at gmail.com> wrote:

>
> 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
>>
>
>