[antlr-interest] mutual recursion in tree grammars

[Matthew Wilson]

I don't understand, since upon entering/descending into a node, it is the
children who are being examined, not the node itself.  Here's an example
(albeit extremely contrived):

// in yYy.g
grammar yYy;
options {
output=AST;
ASTLabelType=CommonTree;
backtrack=true;
}
rule1 : rule3 EOF ;
rule2 : 'y'! rule3 'a'* ;
rule3 : rule2? ('Y'! rule2)* 'b'* ;  // extremely backtracking heavy

// in yYyTree.g

options {
backtrack=true;
tokenVocab=yYy;
rewrite=true;
}
rule1 : rule3 ;
rule2 : rule3 'a'* ; // some transformation using the 'a's
rule3 : rule2? rule2* 'b'* ; // some transformation using the 'b's
// end

In this "scannerless" grammar, 'y' and 'Y' are treated as different kinds of
prefix whitespace (but whitespace that must follow certain patterns), and
rules 2 and 3 care only about 'a' and 'b', as far as the tree grammar is
concerned.  With the input   yYyYyaaaaabbbbb<EOF>   , a correct parse tree
(after scads of backtracking) would be sent to the tree parser, but the
grammar complains as mentioned above.

My only workaround is to duplicate the whitespace portions of those rules in
the tree grammar so they don't "appear" to be mutually left recursive to
antlr.  They are not truly mutually left recursive since they can never
enter an infinite cycle while descending/recursing the TokenStream.

I guess my point/question is:  if there's no possibility of a cycle in the
input AST, why bother checking for left recursion in the rules' dependency
graph... since the resulting tree parser won't ever infinitely recurse?

Thanks! (also thanks for the great/free products!)


On Tue, Dec 21, 2010 at 8:15 PM, Terence Parr <parrt at cs.usfca.edu> wrote:

> Well, i use LL(*) to parse the tree so same rules apply.
>
> a : b ;
> b : a ;
>
> Ter
> On Dec 21, 2010, at 8:13 PM, Matthew Wilson wrote:
>
> > Hi,
> >
> > I was wondering why I'm getting the mutual recursion error in my tree
> > grammar (antlrworks 1.4.2).  Why would left recursion (mutual/indirect or
> > direct) matter at all in a tree grammar?  (How could there be referential
> > cycles in the tree?)
> >
> > Thanks,
> > Matthew Wilson
> > diakopter at gmail.com
> >
> > List: http://www.antlr.org/mailman/listinfo/antlr-interest
> > Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>