[antlr-interest] C++ grammar, troubleshooting mutually left recursive rules

John B. Brodie jbb at acm.org
Wed Apr 4 20:06:35 PDT 2012


Greetings!

On 04/04/2012 09:06 PM, Ludwig Maes wrote:
> The grammar in attachment contains the following 3 rules which are
> supposedly mutually left recursive:
>
>
> decl_specifier_seq	: decl_specifier attribute_specifier_seq? // C++0x:
> 			| decl_specifier decl_specifier_seq // C++0x:
> 			;
>
>
> type_specifier_seq	: type_specifier attribute_specifier_seq? // C++0x:
> 			| type_specifier type_specifier_seq
> 			;
>
>
> trailing_type_specifier_seq	: trailing_type_specifier
> attribute_specifier_seq? // C++0x:
> 				| trailing_type_specifier trailing_type_specifier_seq // C++0x:
> 				;
>
> However I fail to find the mutual left-recursion ( have been
> navigating through usages and trying to find how one of these three
> can call one of the other two but failed to find such a path). I
> believe it is something about the way they are defined, since all 3
> share the same structure... what am I doing wrong?
>

1) the leftmost element of decl_specifier_seq is decl_specifier

2) the second alternative of decl_specifier is type_specifier

3) the leftmost element of type_specifier_seq is type_specifier

4) therefore decl_specifier_seq and type_specifier_seq are mutually left 
recursive

5) the leftmost element of trailing_type_specifier_seq is 
trailing_type_specifier

6) the first alternative of type_specifier is trailing_type_specifier

7) therefore trailing_type_specifier_seq is mutually left recursive with 
both decl_specifier_seq and type_specifier_seq



Hope this helps!
    -jbb



More information about the antlr-interest mailing list