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

[Ludwig Maes]

Hello, thanks for helping me out

My misunderstanding was that I thought recursion meant (in)directly
calling itself (of which I could not find a cycle). If I understand
correctly, you point out that "mutually left-recursive" actually means
that the call trees of the 3 functions intersect. Why is that not
allowed? it would seem to imply every rule may only be usaged in just
one other rule?

I.e. : if I define a rule called digit, I can use/call this rule in
other rules. Why would that be allowed but not what we have here be
allowed?

Perhaps there is a real recursion but when I draw the directed graph
of calls in the steps you mention I get an acyclic graph...

I must be misunderstanding something

On 5 April 2012 05:06, John B. Brodie <jbb at acm.org> wrote:
> 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
>