2. Example

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
    ;

// $<OutOfSight

// Here additional rules needed to resolve errors.
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):