Gramática que resuelve Mayúsculas/Reducir conflictos

Question

Estoy usando Jison (Bison) para crear un lenguaje de marcado simple. Soy claramente nuevo en esto, pero las pequeñas variaciones funcionan muy bien. Simplemente no entiendo la fuente del conflicto S/R.

No parece importar que 'Texto' sea devuelto por dos acciones lexer (con diferentes Condiciones de inicio) y esto me gusta porque parece permitir que la gramática tenga menos reglas y porque los mensajes de error para el usuario son consistente. Intenté hacer que la regla 'Texto' fuera común, independientemente del contexto, y también intenté asignar a cada token un nombre diferente, pero no parece tener ningún efecto en los Conflictos S/R cuando todo está en conjunto.

El analizador se SUPONE para crear un objeto json con texto plano, sub-arreglos y varios nodos especiales.

Especificación:

/* lexical grammar */ 
%lex 

%s bracketed 

%% 

<bracketed>(\\.|[^\\\,\[\]])+  { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; } 
<INITIAL>(\\.|[^\\\[])+    { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; } 
"["         { this.begin('bracketed'); return '['; } 
"]"         { this.popState(); return ']'; } 
","         return ',' 
<<EOF>>        return 'END' 

/lex 

%start template 

%%  

template 
    : sentence END 
    ; 

sentence 
    : /* empty */ 
    | sentence Text 
    | sentence '[' ']' 
    | sentence '[' dynamic ']' 
    ; 

dynamic 
    : sentence 
    /*| dynamic ',' sentence*/ 
    ; 

Advertencias:

Conflict in grammar: multiple actions possible when lookahead token is ] in state 5 
- reduce by rule: sentence -> 
- shift token (then go to state 6) 

States with conflicts: 
State 5 
    sentence -> sentence [ .] #lookaheads= END Text [ ] 
    sentence -> sentence [ .dynamic ] #lookaheads= END Text [ ] 
    dynamic -> .sentence #lookaheads= ] 
    sentence -> . #lookaheads= ] Text [ 
    sentence -> .sentence Text 
    sentence -> .sentence [ ] 
    sentence -> .sentence [ dynamic ] 

Diferentes algoritmos generadores tienen más o menos problemas, pero todos ellos parecen tener problemas.

Gracias!

Answer 1

El conflicto viene fundamentalmente de estas dos reglas:

sentence: sentence '[' Text ']' 
     | sentence '[' sentenceList ']' 

La razón es que después de ver un sentence y una [ y mirando a la siguiente token siendo Text, el analizador no se sabe si para cambiar el Text, haciendo coincidir la primera regla, o para tratar ese Text como el comienzo de un sentenceList yendo hacia la coincidencia de la segunda regla.

Ahora bien, si tuviera un generador de analizadores que utilizara 2-token lookahead, esto no sería un problema, pero bison es LALR (1) (el 1 es un token lookahead).

Hay un par de cosas que podría intentar:

• hacer lookahead extra en el analizador léxico para diferenciar texto seguido por caso]] como dos fichas de subproductos-no seguían de texto distintos luego reescribe las reglas para usar ambos tokens.

• Utilice la función% glr-parser de bison para usar el analizador GLR. Esto analizará la oración en ambos sentidos y luego arrojará la que no concuerda con

• refactorizando la gramática para no necesitar 2-token lookahead.

Una refactorización que funciona en su caso sería volver a escribir las reglas sentence para hacerlos bien recursiva en lugar de izquierda recursiva:

sentence: /* empty */ 
     | Text sentence 
     | '[' ']' sentence 
     | '[' Text ']' sentence 
     | '[' sentenceList ']' sentence 
     ; 

Esto evita tener sentence (o cualquier otra norma que comienza con sentence como sentenceList) comienza con una reducción nula de la regla sentence: /*empty*/. Entonces, el analizador puede cambiar libremente un Text en el caso problemático difiriendo la reducción hasta que vea el siguiente token.Sin embargo, tiene implicaciones en el uso de la memoria, ya que da como resultado un analizador sintáctico que esencialmente cambiará la entrada completa a la pila del analizador y luego la reducirá una oración a la vez.

Otra refactor que podría hacer sería subsumir los [Text] y [] construcciones en el [sentenceList]:

sentence: /* empty */ 
     | sentence Text 
     | sentence '[' sentenceList ']' 
     ; 

sentenceList: sentence 
      | sentenceList ',' sentence 

Así que ahora un sentenceList es uno o más frases separadas por comas (en lugar de dos o más), y en la acción para la regla sentence '[' sentenceList ']', debe marcar sentenceList para ver si se trata de dos o más oraciones y actuar de forma adecuada.