[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