[antlr-interest] Treewalking : non-determinism error

mzukowski at yci.com mzukowski at yci.com
Tue Apr 1 08:30:44 PST 2003


Try to make the important parts of the tree come first by signaling it at
the root, because tree parsers only have k=1 lookahead.  Ric showed how to
fix it in the treeparser, which is ok, but clearly more coffee is needed :)
I recommend fixing it in the parser to make your treeparser as simple as
possible.

First define an imaginary token OUTP.

parser:
printst : (pr:"PRINT"^ expr (COLONPRINT {##.setType(OUTP)})?  );

treeparser:
printst: #(PRINT {System.out.println("PRNT");} expr) 
		| #(OUTP {System.out.println("OUTP");} expr) 

Note that if you are actually outputting code you probably want the "PRNT"
to be printed before the expr, so I put the action in the right place for
that.

Monty

-----Original Message-----
From: Ric Klaren [mailto:klaren at cs.utwente.nl]
Sent: Tuesday, April 01, 2003 6:40 AM
To: antlr-interest at yahoogroups.com
Subject: Re: [antlr-interest] Treewalking : non-determinism error


Hi,

On Tue, Apr 01, 2003 at 11:56:28AM +0100, Anthony Youngman wrote:
> I think I know what the problem is, I just don't know how to fix it ...
> 
> In my main parser, I have the following two rules:
> 
> printst : (pr:"PRINT"^ expr (COLONPRINT)? {System.out.println(pr+" print
> ");} );
> expr : ( catexpr | logicexpr ) ;
> 
> This seems to be fine - the traces are printing what I expect.
> 
> In my treewalker I then have the rule:
> 
> printst
> 	: #(PRINT expr COLONPRINT) {System.out.println("PRNT");}
> 	| #(PRINT expr) {System.out.println("OUTP");}
> 	;

Provided I don't have a coffee shortage or overdose ;)

Tree parsers only use a lookahead of 1 so the above rule will indeed give
nondeterminism. One way to fix it might be:

printst
 	: ( #(PRINT expr COLONPRINT) ) => #(PRINT expr COLONPRINT)
{System.out.println("PRNT");}
 	| #(PRINT expr) {System.out.println("OUTP");}
 	;

Alternatively:

printst { bool colon = false; }
	: #(PRINT expr ( COLONPRINT { colon = true; } )? )
		{
			if( colon )
				System.out.println("PRNT");
			else
				System.out.println("OUTP");
		}
	;

Cheers,

Ric
-- 
-----+++++*****************************************************+++++++++----
---
    ---- Ric Klaren ----- j.klaren at utwente.nl ----- +31 53 4893722  ----
-----+++++*****************************************************+++++++++----
---
  "You know how to use that thing?" [pointing to the sword]
  "Sure.. The pointy end goes into the other guy."
  --- The Mask of Zorro


 

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


 

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



More information about the antlr-interest mailing list