[antlr-interest] Splitting rules to avoid nondeterminism

[Tom Verbeure]

Hi All,

this is probably a very basic question, but I must be missing a basic
piece of information regarding the operation of LL parsers (and
downloading the PhD thesis of Terence didn't really make me see the
light...:-)

Here is a rule in my grammar:

simple_expression: (sign)? term (adding_operator term)*;
term: factor (multiplying_operator factor)*;

...

Running this through antlr results in an ambiguity. No understanding
why, I eventually tried this:

simple_expression: (sign)? simple_expression_tail;
simple_expression_tail: term (adding_operator term)*;
term: factor (multiplying_operator factor)*;

This passes without any problems. The problem is: I can more or less
'feel' that the second case is less ambiguous, but I don't think
really understand it.

The look-ahead factor of this grammar is 2. My assumption is that, in
the first case, after the presence of a sign is determined, you only
have 1 token left to look into the rules of 'term'. In the second
case, by going into the second rule, you start back from square one,
with 2 tokens of lookahead available. And thus you can disambiguate
the lower rules. Is this a correct assumption?

What I don't understand is why can't the tool do this automatically?
Once it has determined the presence of 'sign', why can't it simply
consume the first token and load a new one? One could argue that in
this way, you effectively become look-ahead 3, but this is not
strictly the case in my opinion.

Assume you have a rule like simple_expression where you have one and
only one sequece of subrules on the right. Could it not 'simply'
interally start to break this linear sequence of subrules into tails
automatically when it sees that is it ambiguous? This would save me
and other from doing a trivial split-up of a linear rule.

I'd love to understand the mechanics of this a bit better.

That being said: one more question: what is your favorite way to debug
nondeterminisms? Right now, I'm having a very hard time figuring
what's going wrong and fixing it is, at this moment, simply by trial
and error. Not a very intelligent way of doing things...

Tom


 
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/