[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