[antlr-interest] How to resolve the left-recursion problem?
YiQing Yang
yiqing at objectivity.com
Tue Jun 5 10:24:28 PDT 2007
Thanks for your reply.
Forget about the scope name for now. Say that I want to recognize a series
of name linked by ".", but I want to treat the "." as an operator which I
want to associate some operation to it. I also want the . operator to be
left associative. For example, "employer.ceo.name" is equivalent to
((employer.ceo).name) which generates the AST as
.
/ \
. name
/ \
employer ceo
This is the only parser rule I can think of that will do what I want. But
it's left recursive.
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