[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