[antlr-interest] Simple question on resolving non-determinism in tree walker
Monty Zukowski
monty at codetransform.com
Wed Jun 23 14:41:21 PDT 2004
On Jun 23, 2004, at 2:28 PM, Bharath Sundararaman wrote:
> I used syntactic predicates to overcome the problem. I understand that
> I
> could use $setType command and just add IDENTSUB to the tokens { }
> section
> of the parser. The problem is, I have around a dozen rules in the same
> fashion and I don't want to add a dozen extra imaginary tokens just to
> resolve non-determinism.
I would want to. I think I added about 40 imaginary tokens to a SQL
parser I recently did. Syntactic predicates cost time when tree
walking. The idea is to make the tree easy to walk.
>
> Another problem is, I'm getting many non-determinism warnings in the
> tree
> walker because all the punctuations (brackets, commas, semicolons,
> dots) in
> the parser rules are ignored in the AST. Without them, most rules are
> clashing and it will be cumbersome to remove such non-dets because I
> have to
> restructure all my rules (as I only have a lookahead depth of 1 in the
> tree
> walker) or I have to overload the tree walker with syntactic
> predicates. Is
> this a common issue? I believe that for any grammar, if you stripped
> the
> punctuations, it would lead to some or lot of non-determinisms. What's
> the
> usual way of handling this?
Two ways. First is to use "root"ing appropriately to group things that
belong together. Sometimes I root with punctuation itself, like
rooting with LPAREN, then dropping the RPAREN, which is implied by the
end of the children of LPAREN.
Second is to root with imaginary nodes. Like #(STATEMENT ...) which
would imply the semicolon at the end of the statement's children.
Then sometimes you make the tree structure very regular to imply
punctuation. C's "for" construct allows empty loops like for (;;) --
remove the semicolons and then if there is only one expression in there
you don't now if it is first, second or third. So instead i use a NONE
placeholder inserted by the parser. Then my tree rule is like #(FOR
expr expr expr) and one of expr's alts is NONE.
Plenty of examples are in my GCC grammar.
Monty
ANTLR & Java Consultant -- http://www.codetransform.com
ANSI C/GCC transformation toolkit --
http://www.codetransform.com/gcc.html
Embrace the Decay -- http://www.codetransform.com/EmbraceDecay.html
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/antlr-interest/
<*> To unsubscribe from this group, send an email to:
antlr-interest-unsubscribe at yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list