Felice / yacc riducendo quando dovrebbe cambiare

Question

Sto lavorando su un parser e sono davvero frustrato. Nella lingua, possiamo avere un'espressione come:

new int[3][][]

.

o

new int[3]

.

La maggior parte di essa analizza correttamente, ad eccezione degli array vuoti alla fine. Nel mio parser ho:

Expression : int
             char
             null
             (...many others...)
             new NewExpression

.

E poi una newExpression è:

NewExpression : NonArrayType '[' Expression ']' EmptyArrays
              | NonArrayType '[' Expression ']' 

.

e poi i vuoti è una o più bretelle vuote - Se i vuoti derivano la stringa vuota, aggiunge 20 conflitti di spostamento / riducono:

EmptyArrays : EmptyArrays EmptyArray
            | EmptyArray
EmptyArray  : '[' ']'

.

Tuttavia, quando guardo nel file .info per il parser, ottengo questo:

State 214¬
¬
▸   NewExpression -> NonArrayType lbrace Expression rbrace . EmptyArrays    (rule 80)¬
▸   NewExpression -> NonArrayType lbrace Expression rbrace .    (rule 81)¬
¬
▸   dot            reduce using rule 81¬
▸   ';'            reduce using rule 81¬
▸   ','            reduce using rule 81¬
▸   '+'            reduce using rule 81¬
▸   '-'            reduce using rule 81¬
▸   '*'            reduce using rule 81¬
▸   '/'            reduce using rule 81¬
▸   '<'            reduce using rule 81¬
▸   '>'            reduce using rule 81¬
▸   '<='           reduce using rule 81¬
▸   '>='           reduce using rule 81¬
▸   '=='           reduce using rule 81¬
▸   '!='           reduce using rule 81¬
▸   ')'            reduce using rule 81¬
▸   '['            reduce using rule 81    --I expect this should shift
▸   ']'            reduce using rule 81¬
▸   '?'            reduce using rule 81¬
▸   ':'            reduce using rule 81¬
▸   '&&'           reduce using rule 81¬
▸   '||'           reduce using rule 81

.

Mi aspetto che se siamo in stato 214 e vediamo un tutore sinistro, dovremmo spostarlo sulla pila e continuare ad analizzare vuotiArrays.

Non sono esattamente sicuro di cosa sta succedendo perché quando spogliamo tutto l'eccesso dal bagaglio (ad es.) Avviando l'analisi con NewExpression, le parentesi aggiuntive analizzano correttamente. Non è possibile per un'espressione o una dichiarazione o qualsiasi non terminale nella grammatica per iniziare con un tutore sinistro. Soprattutto perché ho una regola simile per le dichiarazioni se / altrimenti, che genera un conflitto di spostamento / riduce, ma sceglie di spostarsi se il token successivo è un altro (questo problema è ben documentato).

Puoi aiutarmi a capire cosa sta andando storto? Apprezzo molto il tuo aiuto, sto davvero inclinando i mulini a vento che cercano di capire il problema.

Answer 1

You probably have a precedence set for '[' and/or ']' with something like %left '[' which causes this behavior. Remove that precedence declaration, and this will reveal the shift/reduce conflict you have here. As for why its a shift/reduce conflict, you probably also have a rule:

Expression: Expression '[' Expression ']'

for an array access. The problem being that since a NewExpression is an Expression it may be followed by an index like this, and when looking at the lookahead of '[', it can't tell whether that's the beginning of an index expression or the beginning of an EmptyArray -- that would require 2-token lookahead.

One thing you could try for this specific case would be to have your lexer do the extra lookahead needed here and recognize [] as a single token.