[antlr-interest] Re: nice threads

Terence Parr parrt at jguru.com
Fri Jun 14 10:58:44 PDT 2002

Folks, Monty's email is not getting thru to the list...so here is a side 
thread to be weaved back in ;)


On Friday, June 14, 2002, at 07:15  AM, mzukowski at yci.com wrote:
> Tree grammars for analysis.  Why wouldn't that work?  Do you really 
> need a
> cyclic graph/network structure?

Well, yes/no.  Turns out it is a tree now loring says ;)  You really 
need to convert a grammar to an NFA and then run a bounded k level 
NFA->DFA conversion to do the analysis (that is the algorithm I designed 
during my thesis).

> Is grammar subclassing still appropriate?

I think it should be a function of the environment.  I.e, have a library 
of rules/grammars in your repository and then pick and choose stuff to 
grab to begin a new grammar.  A live push-forward-changes sort of thing 
is the same as inheritance ;) (I think they call that RCS) ;) ;)

> When I think about grammars and aspects I think actions--AspectANTLR 
> would
> be the tool to weave your actions into your pure antlr grammars.  The 
> trick

Oooooooohhhhhh.  Now THAT is the perfect explanation of what an Aspect 
is.  You don't want to modify a grammar physically just to add actions 
into the right spot!.  Oohhhh.

> is how to specify the join points and the answer is???  Note that your 
> could still let you edit the actions as if they were attached to the .g
> file, but in reality they don't have to be.  Nice for multipass tree
> transforms and mixing C++ and Java output languages.

Oh man...i think we're on to something.  AspectANTLR :)

> I like the separation of antlr phases concept.  When I was digging into
> lookahead to generate a lookahead dependency graph I was frustrated by 
> the
> caching of lookahead info.  I don't remember exactly now but it seems 
> like
> maybe I was trying to find the specific rules contributing to the 
> ambiguity
> but sometimes when I got to the ambiguous rule the lookahead was already
> computed without the backlinks to what rules contributed to the 
> lookahead
> set.  Because you don't just want to know that a rule is ambiguous.  
> 50% of
> the time it's because another rule called it and I was automating that
> manual process of figuring out which caller rules were to blame.

Yes, the cached lookahead information is useless for determining the 
paths in the grammar that are nondeterministic.  I would really like to 
have ANTLREclipse or whatever be able to highlight the paths for you.

The caching is absolutely necessary for efficiency of this algorithm.  
Without it I cannot claim it is O(nk) where n is size of grammar.  But, 
a new version of antlr could avoid the caching when finding the problem 

Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org


Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 

More information about the antlr-interest mailing list