ANTLR4 Mutually Left-recursive Error When Parsing C++ Source

Question

I'm trying to parse a subset of cpp source syntax. The follow ANTLR4 parser rules are directly copied from the c++ language specification (except hypens are replaced by underscores):

abstract_declarator:
    ptr_operator abstract_declarator?
  |  direct_abstract_declarator
;
direct_abstract_declarator:
    direct_abstract_declarator? '(' parameter_declaration_clause ')' cv_qualifier_seq? exception_specification?
   |   direct_abstract_declarator? '[' constant_expression? ']'
   |   '(' abstract_declarator ')'
;

But I got this error when org.antlr.v4.Tool is parsing the grammar:

error(119): cppProcessor.g4::: The following sets of rules are mutually left-recursive [direct_abstract_declarator]

It seems that direct_abstract_declarator? syntax at the left hand side causes the error. How should I correct it? Why can't ANTLR4 support it?

Manually refactoring the rules to this form doesnt produce the error:

direct_abstract_declarator:
       direct_abstract_declarator '(' parameter_declaration_clause ')' cv_qualifier_seq? exception_specification?
     |  '(' parameter_declaration_clause ')' cv_qualifier_seq? exception_specification?
     | direct_abstract_declarator '[' constant_expression? ']'
     | '[' constant_expression? ']' 
     | '(' abstract_declarator ')'

So is it possible for ANTLR4 to support the first syntax directly when handling left recursive rules?

Dakar

Answer 1

ANTLR 4 supports direct left recursion, but not indirect or hidden left recursion. You can address the situation above by explicitly expanding the optional construct.

direct_abstract_declarator
   :   direct_abstract_declarator '(' parameter_declaration_clause ')' cv_qualifier_seq? exception_specification?
   |   direct_abstract_declarator '[' constant_expression? ']'
   |   '(' parameter_declaration_clause ')' cv_qualifier_seq? exception_specification?
   |   '[' constant_expression? ']'
   |   '(' abstract_declarator ')'
;

Aerotherapeutics