The first example showed only a limited pool of possibilities, so I decided to use the second mutual left-recursive rules loop in the C# grammar as another example.
Preparations
After the execution of the first step, as explained in the first example, I had the following C# grammar snippet. I realized at this point that it would be a good idea to use more of the original rules instead stand-ins because I wanted to be sure that there is no hidden interaction between the two recursion loops.
grammar CSharpRecursion2;
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
| anonymous_object_creation_expression
| typeof_expression
| checked_expression
| unchecked_expression
| default_value_expression
| anonymous_method_expression
| sizeof_expression
| pointer_member_access
| pointer_element_access
;
member_access
: primary_expression DOT IDENTIFIER type_argument_list?
| predefined_type DOT IDENTIFIER type_argument_list?
| qualified_alias_member DOT IDENTIFIER type_argument_list?
;
invocation_expression
: primary_expression OPEN_PARENS argument_list? CLOSE_PARENS
;
post_increment_expression
: primary_expression OP_INC
;
post_decrement_expression
: primary_expression OP_DEC
;
pointer_member_access
: primary_expression OP_PTR IDENTIFIER
;
pointer_element_access
: primary_no_array_creation_expression OPEN_BRACKET expression CLOSE_BRACKET
;
element_access
: primary_no_array_creation_expression OPEN_BRACKET expression_list CLOSE_BRACKET
;
argument_list
:COMMA
;
expression
:DEFAULT
;
expression_list
:THIS
;
array_creation_expression
:DELEGATE
;
anonymous_method_expression
:DO
;
default_value_expression
:DOUBLE
;
unchecked_expression
:ELSE
;
checked_expression
:ENUM
;
typeof_expression
:EVENT
;
anonymous_object_creation_expression
:EXPLICIT
;
delegate_creation_expression
:EXTERN
;
object_creation_expression
:FALSE
;
base_access
:FINALLY
;
this_access
:FIXED
;
parenthesized_expression
:FLOAT
;
simple_name
:FOR
;
literal
:FOREACH
;
contextual_keyword[string identifier]
: { input.LT(1).Text == $identifier }? IDENTIFIER
;
predefined_type
: BOOL
;
right_shift
: OP_LT OP_LT
;
sizeof_expression
: SIZEOF OPEN_PARENS unmanaged_type CLOSE_PARENS
;
unmanaged_type
: (namespace_or_type_name
| simple_type
| OBJECT
| STRING
| VOID STAR
) (STAR | INTERR | rank_specifier)*
;
namespace_or_type_name
: (IDENTIFIER type_argument_list? | qualified_alias_member) (DOT IDENTIFIER type_argument_list?)*
;
IDENTIFIER
: 'a'..'z'
;
simple_type
: BOOL
;
rank_specifier
: OPEN_BRACKET COMMA* CLOSE_BRACKET
;
qualified_alias_member
: IDENTIFIER DOUBLE_COLON IDENTIFIER type_argument_list?
;
type_argument_list
: OP_LT type_arguments OP_GT
;
type_arguments
: type_argument (COMMA type_argument)*
;
type_argument
: type
;
type
: (namespace_or_type_name
| simple_type
| OBJECT
| STRING
| VOID STAR
) (STAR | INTERR | rank_specifier)*
;
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';
OPEN_PARENS:'(';
CLOSE_PARENS:')';
OPEN_BRACKET:'[';
CLOSE_BRACKET:']';
OPEN_BRACE:'{';
CLOSE_BRACE:'}';
STAR:'*';
INTERR:'?';
DOT:'.';
COMMA:',';
OP_PTR:'->';
DOUBLE_COLON:'::';
OP_LT:'<';
OP_GT:'>';
OP_INC:'++';
OP_DEC:'--';
After this all mutually left-recursive rules are checked if they are referenced in any other rule besides themselves in the original grammar. The original list consists of invocation_expression, primary_expression, primary_no_array_creation_expression, post_increment_expression, post_decrement_expression, element_access, member_access, pointer_element_access and pointer_member_access.
Out of those, only element_access, pointer_element_access and pointer_member_access aren't referenced elsewhere, so they are inlined before I save a copy. Next to the absence of the aforementioned rules primary_no_array_creation_expression looks like this. Its single left-recursion points it to be the first surviving rule.
primary_no_array_creation_expression
: literal
| simple_name
| parenthesized_expression
| member_access
| invocation_expression
| primary_no_array_creation_expression OPEN_BRACKET expression_list CLOSE_BRACKET
| this_access
| base_access
| post_increment_expression
| post_decrement_expression
| object_creation_expression
| delegate_creation_expression
| anonymous_object_creation_expression
| typeof_expression
| checked_expression
| unchecked_expression
| default_value_expression
| anonymous_method_expression
| sizeof_expression
| primary_expression OP_PTR IDENTIFIER
| primary_no_array_creation_expression OPEN_BRACKET expression CLOSE_BRACKET
;
Sections
My siblings (including me):