[antlr-interest] Left recursion removal
Loring Craymer
lgcraymer at yahoo.com
Mon May 7 15:12:15 PDT 2007
Unless I missed something, these two rules are
identical, except that element_access is incorrectly
defined (the three occurrences of primary_expression
with suffixes are in fact just primary expression
variants). Take a closer look to be sure, then change
occurrences of "element_access" to
"primary_expression" and delete the element_access
rule.
--Loring
--- Johannes Luber <jaluber at gmx.de> wrote:
> 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
> > grammar CSharpRecursion;
>
> //
>
D:\Studium\Diplomarbeit_Eclipse\CSharpParser\csharpml
>
> tokens {
> ABSTRACT='abstract';
> AS='as';
> BASE='base';
> BOOL='bool';
> BREAK='break';
> BYTE='byte';
> CASE='case';
> CATCH='catch';
> CHAR='char';
> CHECKED='checked';
> CLASS='class';
> CONST='const';
> CONTINUE='continue';
> DECIMAL='decimal';
> DEFAULT='default';
> DELEGATE='delegate';
> DO='do';
> DOUBLE='double';
> ELSE='else';
> ENUM='enum';
> EVENT='event';
> EXPLICIT='explicit';
> EXTERN='extern';
> FALSE='false';
> FINALLY='finally';
> FIXED='fixed';
> FLOAT='float';
> FOR='for';
> FOREACH='foreach';
> GOTO='goto';
> IF='if';
> IMPLICIT='implicit';
> IN='in';
> INT='int';
> INTERFACE='interface';
> INTERNAL='internal';
> IS='is';
> LOCK='lock';
> LONG='long';
> NAMESPACE='namespace';
> NEW='new';
> NULL='null';
> OBJECT='object';
> OPERATOR='operator';
> OUT='out';
> OVERRIDE='override';
> PARAMS='params';
> PRIVATE='private';
> PROTECTED='protected';
> PUBLIC='public';
> READONLY='readonly';
> REF='ref';
> RETURN='return';
> SBYTE='sbyte';
> SEALED='sealed';
> SHORT='short';
> SIZEOF='sizeof';
> STACKALLOC='stackalloc';
> STATIC='static';
> STRING='string';
> STRUCT='struct';
> SWITCH='switch';
> THIS='this';
> THROW='throw';
> TRUE='true';
> TRY='try';
> TYPEOF='typeof';
> UINT='uint';
> ULONG='ulong';
> UNCHECKED='unchecked';
> UNSAFE='unsafe';
> USHORT='ushort';
> USING='using';
> VIRTUAL='virtual';
> VOID='void';
> VOLATILE='volatile';
> WHILE='while';
> }
>
> primary_expression
> : array_creation_expression
> | primary_no_array_creation_expression
> ;
>
> primary_no_array_creation_expression
> : literal
> | simple_name
> | parenthesized_expression
> | member_access
> | invocation_expression
> | element_access
> | this_access
> | base_access
> | post_increment_expression
> | post_decrement_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
> ;
>
> member_access
> : primary_expression '.' identifier
> type_argument_list?
> | predefined_type '.' identifier
> type_argument_list?
> | qualified_alias_member '.' identifier
> type_argument_list?
> ;
>
> invocation_expression
> : primary_expression '(' argument_list? ')'
> ;
>
> element_access
> : primary_no_array_creation_expression '['
> expression_list ']'
> ;
>
> post_increment_expression
> : primary_expression '++'
> ;
>
> post_decrement_expression
> : primary_expression '--'
> ;
>
> // Here additional rules needed to resolve errors.
>
> predefined_type
> : BOOL
> | BYTE
> | CHAR
> | DECIMAL
> | DOUBLE
> | FLOAT
> | INT
> | LONG
> | OBJECT
> | SBYTE
> | SHORT
> | STRING
> | UINT
> | ULONG
> | USHORT
> ;
>
> anonymous_object_creation_expression
> :
> ;
>
> pointer_element_access
> :
> ;
>
> pointer_member_access
> :
> ;
>
> sizeof_expression
> :
> ;
>
> anonymous_method_expression
> :
> ;
>
> default_value_expression
> :
> ;
>
> unchecked_expression
> :
> ;
>
> checked_expression
> :
> ;
>
> typeof_expression
> :
> ;
>
> delegate_creation_expression
> :
> ;
>
>
=== message truncated ===
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
More information about the antlr-interest
mailing list