Happy/YACC reduzindo quando deveria mudar

Question

Estou trabalhando em um analisador e estou muito frustrado.Na linguagem, podemos ter uma expressão como:

new int[3][][]

ou

new int[3]

A maior parte é analisada corretamente, exceto as matrizes vazias no final.No meu analisador eu tenho:

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

e então uma NewExpression é:

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

e então EmptyArrays é um ou mais colchetes vazios - se EmptyArrays derivar a string vazia, ele adiciona 20 conflitos de mudança/redução:

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

No entanto, quando olho no .info arquivo para o analisador, recebo isto:

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

Espero, porém, que se estivermos no estado 214 e virmos uma chave esquerda, devemos transferi-la para a pilha e continuar a analisar os EmptyArrays.

Não tenho certeza do que está acontecendo porque quando retiro todo o excesso da bagagem (por exemplo), iniciando a análise com NewExpression, os colchetes adicionais serão analisados ​​corretamente.Não é possível que uma Expressão ou uma Declaração ou qualquer não-terminal na gramática comece com uma chave esquerda.Principalmente porque tenho uma regra semelhante para instruções if/else, que gera um conflito shift/reduce, mas opta por shift se o próximo token for um else (esse problema está bem documentado).

Você pode me ajudar a descobrir o que está errado?Eu realmente aprecio sua ajuda, estou realmente lutando contra moinhos de vento tentando descobrir o problema.

Answer 1

Você provavelmente tem uma precedência definida para '[' e/ou ']' com algo como %left '[' o que causa esse comportamento.Remova essa declaração de precedência e isso revelará o conflito de mudança/redução que você tem aqui.Quanto ao motivo de ser um conflito de mudança/redução, você provavelmente também tem uma regra:

Expression: Expression '[' Expression ']'

para um acesso ao array.O problema é que desde há NewExpression é um Expression ele pode ser seguido por um índice como este e, ao olhar para o lookahead de '[', não é possível dizer se esse é o início de uma expressão de índice ou o início de uma EmptyArray - isso exigiria uma antecipação de 2 tokens.

Uma coisa que você poderia tentar neste caso específico seria fazer com que seu lexer fizesse a análise extra necessária aqui e reconhecesse [] como um único token.