[antlr-interest] mutual recursion in tree grammars

[Matthew Wilson]

corrections:
I forgot the 'tree grammar yYyTree;' in the tree grammar, and the tokenVocab
option is extraneous; sorry!

On Tue, Dec 21, 2010 at 8:51 PM, Matthew Wilson <diakopter at gmail.com> wrote:

> 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
>>
>>
>