[antlr-interest] non-determinism error

Alexey Demakov demakov at ispras.ru
Wed Sep 14 23:33:07 PDT 2005


Hi,

rule

expr : subexpr (slash subexpr)* 
     | subexpr
     ; 

is ambigious because both alternatives start with the same non-terminal.
So, ANTLR can't decide which one should be used. Try to extract common parts
of alternatives to the front of alternative:

expr : subexpr rule1 | subexpr rules2 ; 

becomes

expr : subexpr ( rule1 | rule2 ) ;

Moreover, in this case the empty sequence can be matched by both alternatives again
because * means zero or more. So, the second alternative is excessive.
Th? correct rule:

expr : subexpr (slash subexpr)* ;

Regards,
Alexey

-----
Alexey Demakov
TreeDL: Tree Description Language: http://treedl.sourceforge.net
RedVerst Group: http://www.unitesk.com

 
  ----- Original Message ----- 
  From: Jay O'Leary 
  To: antlr-interest at antlr.org 
  Sent: Thursday, September 15, 2005 2:09 AM
  Subject: [antlr-interest] non-determinism error


  Hello:

  I'm new to ANTLR and I'm trying to construct a very simple grammar that can parse a string in the form "A / B C /D" to produce a boolean query.  The twist is that if A,B, C, or D is in the form <city>,<stateabbrev>  (eg: orlando, FL)  I have to handle that specially.

  I'm starting with a very simple lexer to handle WORDS, COMMAS, AND SLASH and a very simple parser which will print out the tokens.

  However, when I compile the grammar file, I get the error:
  foo.g:3: warning:nondeterminism between alts 1 and 2 of block upon
  foo.g:3:     k==1:"FL",WORD

  I have tried various predicates to work around the conflict to no avail.

  Also, if I have a string such as "a b / c d / e" the whole string is parsed.
  However, as soon as I add a state abbreviation such as "a b / FL c d / e" everything after and including the state abbreviation seems to get swallowed up.

  I realize this is a "newbie" question but if anyone could point me in the right direction, I would greatly appreciate it. 

  Thanks,
  Jay
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20050915/4d2a435e/attachment.html


More information about the antlr-interest mailing list