[antlr-interest] How to resolve the left-recursion problem?
Robin Davies
rerdavies at rogers.com
Tue Jun 5 16:44:09 PDT 2007
> attribute_expression
> : NAME | dot_operator_exp
> ;
>
> dot_operator_exp
> : attribute_expression DOT NAME
> ;
The generic way to deal with left-recursive structures is to convert them to
match the right side with EBNF loops: "(something)*". See page 275 of the
PDF manual for more details.
attribute_expression
: NAME ('.' NAME) *
;
After using LALR grammars this seemed very unnatural, at first. But, after
gradually mind-shifting to the LL mind-set, this now seems very natural. And
very easy to deal with when you get to actually processing the grammar! To
convert this to AST, for example, you write:
attribute_expression
: NAME ('.'^ NAME) *
;
and you will get exactly the tree that you want: a left-recursive tree
structure.
> attribute_expression
> : NAME | dot_operator_exp
> ;
>
> dot_operator_exp
> : attribute_expression DOT NAME
> ;
>
> Thanks for any help,
>
> Yiqing
>
> -----Original Message-----
> From: John B. Brodie [mailto:jbb at acm.org]
> Sent: Monday, June 04, 2007 7:33 PM
> To: yiqing at objectivity.com
> Cc: antlr-interest at antlr.org
> Subject: Re: [antlr-interest] How to resolve the left-recursion problem?
>
> Greetings!
>
>>I need to write a parser rule for an extended class attribute namme
>>expression. It could be simply a single attribute name with the class
>>scope
>>as option (persion::name) or a series of attribute names chained by "."
> (ie,
>>"employer.ceo.name": "ceo" is an attribute of "employer" corresponded
> class.
>>"name" is an attribute of "ceo" corresponded class).
>
> does this work for you?
>
> attribute_expression : NAME ( ( '::' NAME ) | ( '.' NAME )+ )? ;
>
> (e.g. either we have a single pair of NAMEs separated by :: or we have a
> list
> of names separated by a . or we have just a single NAME)
>
>>I wrote the parser rules as following which contains left-recursion. I do
>>not know how to resolve this problem without changing the semantic. I
>>would
>>appreciate if anyone could help.
>>
>>-----------------------------------------------------
>>attribute_expression
>> : attribute_name
>> | dot_operator_exp
>> ;
>>
>>dot_operator_exp
>> : attribute_expression DOT attribute_name
>> ;
>>
>>attribute_name
>> : n1:NAME (SCOPE n2:NAME)?
>> ;
>>------------------------------------------------------
>
> these rules seem (to me) to permit phrases such as
> a.b::c.d.e::f.g
> or
> h.i::j
> or
> k::l.m
>
> is this later stuff what you want? (e.g. any sequence of dot separated
> names
> which are in turn separated by '::')
>
> if so maybe try these two rules
>
> attribute_expression : dotted_name_list ( SCOPE dotted_name_list )* ;
> dotted_name_list : NAME ( DOT NAME )* ;
>
> All of the above are UNTESTED, sorry; but I hope this helps...
> -jbb
>
>
>
More information about the antlr-interest
mailing list