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

[Peter Kooiman]

Ludwig,

Due to this:

identifier_nondigit	: Nondigit // C++0x:
			| universal_character_name // C++0x:
			| //"other implementation-defined characters" //
C++0x: <-------------!!!!!!!!!!!!!!!!!!
			;
Your identifier_nodigit can produce empty...I guess you wanted that last
"|" inside the comment. This in turn makes it so that

identifier	: identifier_nondigit (identifier_nondigit | Digit)* //
C++0x
		;
Can produce empty, this keeps cascading so that type_name, then
simple_type_specifier, then trailing_type_specifier, then type_specifier
can all produce empty.

Of course then rule
type_specifier_seq	: type_specifier attribute_specifier_seq? //
C++0x:
			| type_specifier type_specifier_seq
			;
Is left recursive because type_specifier can produce empty...same applies
for the other two rules.
The error message from ANTLR is a bit confusing in that it can be taken to
mean that the 3 rules in the error message are mutually left recursive,
when in fact ANTLR is giving 3 sets of MLR rules, each set containing one
rule, ie due to identifier producing empty, each of the three rules is
left recursive by itself.

HTH
Peter



-----Original Message-----
From: antlr-interest-bounces at antlr.org
[mailto:antlr-interest-bounces at antlr.org] On Behalf Of Ludwig Maes
Sent: 07 April 2012 23:56
To: John B. Brodie
Cc: ANTLR Interest
Subject: Re: [antlr-interest] C++ grammar, troubleshooting mutually left
recursive rules

Well, I still fail to find the recursion cycle, so maybe you are
right, perhaps the wrong error message is displayed? either way if a
(mutual) left recursion is found (a cycle was detected by antlr) why
cant it print out the cycle sequence?

On 7 April 2012 23:06, John B. Brodie <jbb at acm.org> wrote:
> Sorry!
>
>
> On 04/06/2012 04:10 PM, Ludwig Maes wrote:
>>
>> 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?
>
>
> Sorry for my error.
>
> You are correct. Mutual left recursion is a (possibly indirect) cycle.
>
> For some reason I mis-read your question and was responding to removing
> ambiguity by finding common left prefixes. Which was not your question
and
> may not be a problem with these particular rules.
>
>
>>
>> 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
>>
>>
>
> Sorry for the noise.
>   -jbb
>

List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe:
http://www.antlr.org/mailman/options/antlr-interest/your-email-address