[antlr-interest] Left recursion removal

Johannes Luber jaluber at gmx.de
Mon May 7 15:00:58 PDT 2007


Hello,

I'm at a bit of loss here. I have tried to reform some mutually left
recursive rules in my C# grammar and got down from originally 7 rules to
 2 through inlining, as Gavin Lambert suggested in another email
(hopefully I didn't interpret it wrong). The two rules are:


primary_expression
    :    (array_creation_expression
         |    literal
         |    simple_name
         |    parenthesized_expression
         |    predefined_type '.' identifier type_argument_list?
         |    qualified_alias_member '.' identifier type_argument_list?
         |    element_access '[' expression_list ']'
         |    this_access
         |    base_access
         |    object_creation_expression
         |    delegate_creation_expression
         |    typeof_expression
         |    checked_expression
         |    unchecked_expression
         |    default_value_expression
         |    anonymous_method_expression
         |    sizeof_expression
         |    {isUnsafeContext}?=> pointer_member_access
         |    {isUnsafeContext}?=> pointer_element_access
         |    {allowOrcas}?=> anonymous_object_creation_expression)
         ('.' identifier type_argument_list? | '(' argument_list? ')'
         | '++' | '--')*
    ;

element_access
    :    literal
    |    simple_name
    |    parenthesized_expression
    |    primary_expression '.' identifier type_argument_list?
    |    predefined_type '.' identifier type_argument_list?
    |    qualified_alias_member '.' identifier type_argument_list?
    |    primary_expression '(' argument_list? ')'
    |    this_access
    |    base_access
    |    primary_expression '++'
    |    primary_expression '--'
    |    object_creation_expression
    |    delegate_creation_expression
    |    typeof_expression
    |    checked_expression
    |    unchecked_expression
    |    default_value_expression
    |    anonymous_method_expression
    |    sizeof_expression
    |    {isUnsafeContext}?=> pointer_member_access
    |    {isUnsafeContext}?=> pointer_element_access
    |    allowOrcas}?=> anonymous_object_creation_expression
    ;

The problem is that I can't figure out how to merge both rules into one.
Simple inlining requires parentheses over the whole subexpression and
prevents ANTLRworks to remove the last left recursion. And because
everywhere where one rule references the other rule there is some
trailing I can't remove the parentheses without changing the grammar.

In case I followed the wrong strategy I've attached my simplified
grammar with the 7 original rules.

Thanks for any help!
Johannes Luber
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Kopie von CSharpRecursion.g
Url: http://www.antlr.org/pipermail/antlr-interest/attachments/20070508/ea7f61d5/attachment-0001.pl 


More information about the antlr-interest mailing list