[antlr-interest] Simple question on resolving non-determinism in tree walker

[Bharath Sundararaman]

Hi Monty,

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. 

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?

I appreciate your comments, Monty. Thank you.

Bharath.



-----Original Message-----
From: Monty Zukowski [mailto:monty at codetransform.com] 
Sent: Wednesday, June 23, 2004 3:05 PM
To: antlr-interest at yahoogroups.com
Cc: Monty Zukowski
Subject: Re: [antlr-interest] Simple question on resolving non-determinism
in tree walker


Typically you'll have the parser change the type so it's not ambiguous. 
  It kinda depends on your parser rule(s), post them and I'll advise 
more specifically.  In general you can do something like:

#(IDENT #(TYPEDECL Type_Name) #(VALUE (constant)?)
| #(IDENT_SUB #(TYPEDECL subRange) #(VALUE (signed_Int)?)

Monty

On Jun 23, 2004, at 12:41 PM, Bharath Sundararaman wrote:

> Hi Grp,
>
> In my tree walker, I am trying resolve non-determinisms between these
> two
> rules in vain:
>
> #(IDENT #(TYPEDECL Type_Name) #(VALUE (constant)?)
> #(IDENT #(TYPEDECL subRange) #(VALUE (signed_Int)?)
>
> I get a non-determinism warning on TYPEDECL. The problem is, if I club 
> TYPEDECL parts to form this rule:
>
> Soln 1:
> --------
> #(IDENT #(TYPEDECL (Type_Name|subRange)) #(VALUE
> (constant|signed_Int)?)
> -- this will work but It leads to the possibility of "Type_Name" 
> appearing
> with "signed_Int" as its value. Type_Name should only have a "constant"
> value.
>
> Soln 2:
> --------
> #(TYPEDECL (Type_Name #(VALUE (constant)?) | subRange #(VALUE
> (signed_Int)?))
> Should not work either because "VALUE" would become a child of
> "Type_Name".
>
> I'm sure this is a common problem and that I'm missing something.
>
> Any ideas?
>
> Thanks!
>
>
> -----Original Message-----
> From: Monty Zukowski [mailto:monty at codetransform.com]
> Sent: Tuesday, June 22, 2004 1:56 PM
> To: antlr-interest at yahoogroups.com
> Cc: Monty Zukowski
> Subject: Re: [antlr-interest] Generating tree walkers.
>
>
> On Jun 22, 2004, at 9:14 AM, Bharath Sundararaman wrote:
>
>> I have the lexer, parser and an AST for a PASCAL-like grammar and I 
>> would like to perform semantic analysis/symbol table checks/constant 
>> folding etc.
>> Is it a cumbersome task to write a tree walker for the abstract syntax
>> tree
>> to perform these checks? When you perform semantic analysis on your
>> input,
>> would you prefer to walk the tree or would you just embed it in your
>> grammar
>> as actions?
>
> I prefer to build the symbol table during the parse (necessary to 
> parse C).  Analysis I like to do in tree passes, it's cleaner because 
> it's a simplification of the grammar which you build so that it 
> doesn't have ambiguities or extraneous punctuation, etc.
>
> 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
>
>
>
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>
>

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



 




 
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/