Feliz/YACC la reducción cuando se debe hacer el cambio

Question

Estoy trabajando en un analizador y estoy realmente frustrado.En el lenguaje, podemos tener una expresión como la siguiente:

new int[3][][]

o

new int[3]

La mayoría de analiza correctamente, excepto para las matrices vacías al final.En mi analizador tengo:

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

y, a continuación, un NewExpression es:

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

y, a continuación, EmptyArrays es uno o más vacía llaves - si EmptyArrays deriva la cadena vacía, se agrega 20 shift/reduce los conflictos:

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

Sin embargo, cuando me miro en el .info archivo para el analizador, me sale esto:

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

Esperamos, sin embargo, que si estamos en el estado de 214 y vemos a la izquierda llave, se debe hacer el cambio en la pila y continuar para analizar EmptyArrays.

No estoy exactamente seguro de lo que está ocurriendo, porque cuando me tira todo el exceso de equipaje (por ejemplo), iniciando el análisis con NewExpression, el paréntesis analizar correctamente.No es posible que una Expresión o una Instrucción o no terminal de la gramática para iniciar con una llave a la izquierda.Sobre todo porque tengo una regla similar para las if/else, que genera un cambio o a reducir los conflictos, sino que elige a cambio si el siguiente token es una cosa (este problema es bien documentado).

Me puede ayudar a averiguar lo que está mal?Realmente aprecio su ayuda, estoy muy de inclinación en los molinos de viento tratando de averiguar el problema.

Answer 1

Usted probablemente tiene una precedencia establecida para '[' y ']' con algo como %left '[' que la causa de este comportamiento.Quitar la prioridad de la declaración, y esto revelará al cambio o a reducir los conflictos que tenemos aquí.En cuanto a por qué su cambio o a reducir los conflictos, probablemente también tiene una regla:

Expression: Expression '[' Expression ']'

para una matriz de acceso.El problema es que desde un NewExpression es un Expression puede ser seguido por un índice como este, y cuando se mira en el lookahead de '[', que no se puede saber si ese es el comienzo de una expresión de índice o el comienzo de un EmptyArray - que requeriría de 2 token de oteo.

Una cosa que usted puede intentar para este caso específico sería tener tu lexer hacer el extra de oteo necesita aquí y reconocer [] como un solo token.