ANTLR: resolving non-LL(*) problems

2
votes

assume following rules in EBNF:

<datum> --> <simple datum> | <compound datum>
<simple datum> --> <boolean> | <number>
     | <character> | <string> |  <symbol>
<symbol> --> <identifier>
<compound datum> --> <list> | <vector>
<list> --> (<datum>*) | (<datum>+ .  <datum>)
       | <abbreviation>
<abbreviation> --> <abbrev prefix> <datum>
<abbrev prefix> --> ' | ` | , | ,@
<vector> --> #(<datum>*)

For the list rule, the ANTLR grammar would look like:

list : '(' datum+ '.' datum ')'
     | '(' datum* ')'
     | ABBREV_PREFIX datum   
     ;

which prdocues an non-LL(*) decision error for alts 1,2. I tried to refactor this statement but can't get up with something working.

for example:

list : '(' datum* (datum'.' datum)? ')'
     | ABBREV_PREFIX datum 
     ;

produces the same error. The main problem for me is that one rule has a + while the other uses a * so the left-factoring isn't as simple as it usually is.

2
antlr

2 Answers

1
votes

Your list rule:

      //   A       B
      //   |       |
list  //   |       |
  :  '(' datum* (datum '.' datum)? ')'
  |  ABBREV_PREFIX datum 
  ;

does not know when a datum should be matched by "sub"-production rule A or B. You'll need to do it like this:

list
  :  '(' (datum+ ('.' datum)?)? ')' // also matches: '(' datum* ')'
  |  ABBREV_PREFIX datum 
  ;
0
votes

How about:

 list : '(' ')'
     | '(' datum+ ('.' datum )? ')' 
     | ABBREV_PREVIX_DATUM
     ;