[antlr-interest] ANTLR3 AST construction with options andalternatives

[Foolish Ewe]

Hello All:

Just in case anyone besides me is reading this, I've discovered another 
construct
where the "do it or skip it" construct may require refactoring in order to 
build an
AST from a working parser.  I'm not sure if these are of general interest, 
unless
I hear interest from the community, I'll drop this topic.

If you have a construct like:

a: B (C)?;  // valid parser construction if (i)A is a token and (ii) B and C 
are defined in the lexer

then ANTLR3 does not seem to like something of the form:

a: b=b (c+=C)?->^(A $b $c+); // Doesn't seem to work if C is not scanned

so some refactoring is required to avoid using an uninitialized $c+ in the 
AST

I'm going to try something like

a:  B                 ->^(A $b)
  | B C              ->^(A $b $c)
  ;

I think some additional discussion should be added to the wiki by someone
knowledgeable about ANTLR about what sorts of restrictions there are
on ANTLR grammars if you want to have AST support.  It is not clear
to me that if a grammar parses that the AST can be built directly from that
grammar.  If that is so, it may be a good idea for a seasoned veteran or two 
to
write about what constructs to avoid and how to refactor preexisting 
constructs
to bring the grammar into compliance with the AST construction requirements.

Regards:

Bill M.

>From: "Foolish Ewe" <foolishewe at hotmail.com>
>To: foolishewe at hotmail.com, antlr-interest at antlr.org
>Subject: Re: [antlr-interest] ANTLR3 AST construction with options 
>andalternatives
>Date: Mon, 13 Nov 2006 15:43:31 +0000
>
>
>Hello All:
>
>I think the previous approach had an error in it, which was detected at 
>run-time.
>The problem lies in that a "zero repetition" scenario may leave an 
>attribute uninitilized,
>in which case it should not be inserted into the AST.
>
>This can be fixed by refactoring rules to use recursion and not variable 
>repetition operators.
>Note that the proposed changes may impact treewalking. So a rule of the 
>form:
>
>a: (b=B)? c:C->^(A $b $c);
>
>may run into trouble if the optional B is not encountered, since $b will be 
>uninitialized
>We can fix this by doing:
>
>a: b=optionalB c:C->^(A $b $c);
>
>optionalB: b=B->^(OPTIONALB $b)
>             |      ->^(OPTIONALB) // empty case
>             ;
>
>And if we have a case like say
>
>a: (B | C)+  D;
>
>we can then create an AST using something like
>tokens{
>    BORC; // B or C
>}
>
>a: (bc+=bOrC)+ d=D    ->^(A $bc+ $d)
>
>bOrC:  b=B                 ->^(BORC $b)
>       | c=C                  ->^(BORC $c)
>       ;
>
>At this point however, I am less certain about how to handle a zero or more 
>repetition case
>such that we don't try to insert an uninitialized attribute into the AST, 
>e.g.
>
>What should we do with:
>
>a: (B|C)* D;
>
>Regards:
>
>Bill M.
>
>>From: "Foolish Ewe" <foolishewe at hotmail.com>
>>To: antlr-interest at antlr.org
>>CC: FoolishEwe at hotmail.com
>>Subject: ANTLR3 AST construction with options and alternatives
>>Date: Mon, 13 Nov 2006 02:27:05 +0000
>>
>>Hello All:
>>
>>I've not heard back on a previous question about how to generate AST's.
>>
>>I have a construct in a grammar that looks something like:
>>
>>// allows optional override of default version id
>>versionInfo: (id+=versionId)? (f1+=fieldType1 | f2+=fieldType2 | 
>>f3+=fieldType3)*
>>   ->^(VERSIONINFO $id+ $f1+ $f2+ $f3+);
>>
>>but it doesn't work the way I would like, meaning that I run the debugger 
>>for a test case that
>>has well defined ASTs are constructed for some of the fields, but some 
>>some are not populated.
>>This debugger halts and won't proceed to construct the VERSIONINFO node, 
>>although
>>before I decorated the grammar with action annotations for AST 
>>construction, the grammar
>>created a well formed parse tree.   I looked at the wiki  for AST related 
>>stuff, and
>>I am still not sure how to fix this problem or if it is a bug in ANTLR3.
>>
>>Regards:
>>
>>Bill M.
>>
>>_________________________________________________________________
>>Find a local pizza place, music store, museum and more…then map the best 
>>route!  http://local.live.com?FORM=MGA001
>>
>
>_________________________________________________________________
>Get today's hot entertainment gossip  
>http://movies.msn.com/movies/hotgossip?icid=T002MSN03A07001
>

_________________________________________________________________
Try the next generation of search with Windows Live Search today!  
http://imagine-windowslive.com/minisites/searchlaunch/?locale=en-us&source=hmtagline