[antlr-interest] Help with parser and non-determinism...

jbfraleigh jbfraleigh at hotmail.com
Thu Apr 8 11:36:00 PDT 2004


I've just recently started working with Antlr.  I'm trying to  
generate a "simple" grammar utilizing the parser and have run into a  
problem. 

The idea is to be able to parse something along the lines of the  
following:

Example 1: x in table y

Example 2: (x in table y and q in table z)

Example 3: ((x in table y and q in table z) and b in table p)

The code in the .g file for the parser looks something like this:

logic_1	: (LPAREN! if_br RPAREN!) | if_br ;
logic_2	: (LPAREN!)=> (LPAREN! logic_1 ((AND|OR) logic_2)* RPAREN!) 
                    | (logic_1 ((AND^|OR^) logic_2)*) ;

For reference, if_br is an expression that looks something like
"x in table y."  logic_1 will evaluate this as either: 
("x in table y") or "x in table y."  

Now, logic_2 is essentially two conditions.  If the first token is 
LPAREN, the following expression should be evaluated:

(a) LPAREN! logic_1 ((AND|OR) logic_2)* RPAREN!

Otherwise, the following expression should be evaluated:

(b) logic_1 ((AND^|OR^) logic_2)*

Note that this is recursive logic – in either evaluation of
logic_2, we're potentially looking at the expression logic_1
AND/OR logic_2

You've probably figured out by now that there are a few problems
here.

1) Because there are two expressions that evaluate to the same 
expression with multiple tokens, the following error is generated:

a.g:25: warning:nondeterminism upon
a.g:25:     k==1:"and","or"

2) Because of the recursive nature of this expression, the following 
error is also generated:

a.g:25: warning:nondeterminism upon
a.g:25:     between alt 1 and exit branch of block


Hopefully you've figured out the intent of this code: (I'm
using regular expression logic to simplify)

1) if LPAREN logic_1 (AND/OR logic_1)* RPAREN then don't mark the 
AND/OR token as a parent in the AST

2) if logic_1 (AND/OR logic_1)* then mark the AND/OR token as a 
parent in the AST

The rest is kind of fluff to allow for nesting.

I've played with this for quite some time and can't seem to
write it to produce the desired results.  I do understand why I'm
receiving the warning messages, but can't see any way around
them.  

The way I see it, I believe that I need both of the expressions in  
logic_2.  I can't use something like (LPAREN)? .. (RPAREN)?
because I need to balance the parentheses.  I also need two different 
action evaluations for the AND/OR token –- under one set of 
circumstances, it's a parent in the AST.  Under another set of 
circumstances, it isn't a parent in the AST.

Hopefully someone can enlighten me.

Thanks in advance.





 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
     http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
     antlr-interest-unsubscribe at yahoogroups.com

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



More information about the antlr-interest mailing list