[antlr-interest] Left recursion removal

[Loring Craymer]

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