¿Cómo trata el algoritmo yacc/bison LALR (1) las reglas "vacías"?

Question

En un analizador LALR (1), las reglas en la gramática se convierten en una tabla de análisis que dice efectivamente "Si tiene esta entrada hasta ahora, y el token de búsqueda anticipada es X, cambie al estado Y o reduzca por regla R ".

He construido con éxito un analizador LALR (1) en un lenguaje interpretado (ruby), no usando un generador, pero calculando una tabla de análisis sintáctico en tiempo de ejecución y evaluando la entrada usando esa tabla de análisis sintáctico. Esto funciona sorprendentemente bien y la generación de tablas es bastante trivial (lo cual me sorprendió un poco), apoyando reglas autorreferenciales y asociación izquierda/derecha.

Una cosa que estoy teniendo algunas dificultades para entender, sin embargo, es cómo yacc/bison procesa conceptualmente las definiciones de reglas vacías. Mi analizador no puede manejarlos, ya que al generar la tabla, observa cada símbolo en cada regla, de forma recursiva, y "vacío" no es algo que provenga del lector, ni será reducido por una regla. Entonces, ¿cómo pueden los analizadores LALR (1) procesar la regla vacía? ¿Lo tratan especialmente, o es un concepto "natural" con el que debería funcionar un algoritmo válido, sin siquiera tener que tener un conocimiento particular de tal concepto?

Digamos, una regla que puede coincidir con cualquier número de paréntesis, emparejado con nada en el medio:

expr: /* empty */ 
     | '(' expr ')' 
     ; 

de entrada como la siguiente se correspondería con esta regla:

((((())))) 

Esto significa que al leyendo '(' y viendo ')' en el token de búsqueda anticipada, las opciones del analizador:

1. Cambie el ')' (no es posible)
2. Reducir la entrada de acuerdo con alguna otra regla (no es posible)
3. otra cosa ...

no encajan bien en el algoritmo básico de "cambio" o "reducir". El analizador efectivamente no necesita cambiar nada a la pila, reducir "nada" a expr, luego cambiar el siguiente token ')', dando '(' expr ')', que por supuesto se reduce a expr, y así sucesivamente.

Es el "cambio nada" que me confunde. ¿Cómo la tabla de análisis transmite tal concepto? Considere también que debería ser posible invocar alguna acción semántica que devuelva un valor a $$ al reducir el valor vacío, por lo que una vista bastante simplista de simplemente omitirlo de la tabla de análisis sintáctico y decir que '(' en la pila y ')' en la búsqueda futura simplemente traducir a un cambio, no produciría genuinamente la secuencia '(' expr ')', sino que simplemente produciría la secuencia '(' ')'.

Answer 1

A pesar de pensar en esto por días, desde que pensé en esto al escribir la pregunta y en los minutos siguientes, algo simplemente me pareció tan increíblemente obvio y simple.

La reducción por todas las reglas es siempre: desconectar X entradas de la pila, donde X es el número de componentes en la regla, luego cambiar el resultado a la pila y pasar a cualquier estado en la tabla después de esa reducción .

En el caso de la regla vacía, no necesita considerar que "vacío" es siquiera un concepto.La tabla de análisis solo necesita incluir una transición que diga "dado '(' en la pila y 'cualquier cosa que no sea '(' en el futuro, reduzca según la regla' vacía '". Ahora, dado que la regla vacía tiene un tamaño de cero componentes, sacar cero de la pila significa que la pila no cambia, entonces cuando el resultado de reducir nada se traslada a la pila, estás viendo algo que sí aparece en el gramática y todo se vuelve claro.

Stack  Lookahead Remaining Input  Action 
-------------------------------------------------------------- 
$   (   ())$     Shift '(' 
$(   (   ))$     Shift '(' 
$((  )   )$     Reduce by /* empty */ 
$((expr )   )$     Shift ')' 
$((expr) )   $     Reduce by '(' expr ')' 
$(expr  )   $     Shift ')' 
$(expr)  $         Reduce by '(' expr ')' 
$expr           Accept 

La razón por la que "simplemente funciona" es porque para reducir por la regla vacía, solo tiene que extraer cero elementos de la pila.

Answer 2

Otro punto de vista para redondear tal vez fuera una gran respuesta de d11wtq, si eso es posible:

Una regla anulable (que deriva ε) se contabiliza durante la construcción del analizador bajo las funciones FOLLOW(X) y FIRST(X). Por ejemplo, si tiene A -> B x, y B puede derivar ε, entonces tenemos que incluir x en el conjunto calculado por FIRST(A). Y también en el conjunto FOLLOW(B).

Además, las reglas vacías se representan fácilmente en los conjuntos de elementos canónicos LR(1).

Una cosa útil es imaginar que hay un símbolo no terminal adicional $ que representa el final del archivo.

Tomemos la gramática:

S -> X | ϵ 
X -> id 

Para el primer conjunto LR(1) elemento canónica, podemos tomar la primera LR(0) Conjunto de objetos y añadir búsqueda hacia delante con el símbolo '$':

S -> . X , '$' 
S -> .  , '$' 
X -> . id , '$' 

Entonces tenemos uno para el lookahead siendo id:

S -> . X , 'id' 
S -> .  , 'id 
X -> . id , 'id' 

Ahora vamos a ver los FIRST y FOLLOW conjuntos:

S -> . X , '$' 

Este no es un "punto final" artículo, así que aquí quieren cambiar, pero sólo si el conjunto FIRST(X) contiene nuestro símbolo de búsqueda hacia delante $. Esto es falso, entonces no llenamos la entrada de la tabla.

siguiente:

S -> .  , '$' 

Se trata de un "punto final" elemento, por lo que quiere reducir. Para validar el contexto de una reducción, nos fijamos en FOLLOW(S): ¿puede seguir el símbolo de gramática que deseamos reducir lo que está en la búsqueda anticipada? De hecho si. $ siempre está en FOLLOW(S) porque el símbolo de inicio es por definición seguido del final de la entrada. Entonces sí, podemos reducir. Y como estamos reduciendo el símbolo S, la reducción es en realidad una acción accept: el análisis finaliza. Llenamos la entrada de la tabla con una acción accept.

De manera similar, podemos repetir para el siguiente elemento establecido con lookahead id.Vamos a saltar a la regla vacía derivando-S-:

S -> .  , 'id' 

Puede S ser seguido por id? Apenas. Entonces esta reducción no es apropiada. No completamos la entrada de la tabla de analizador.

Para que pueda ver que una regla vacía no plantea ningún problema. Inmediatamente se convierte en un punto final LR(0) o LR(1) elemento (según el método de construcción del analizador), y se trata de la misma manera que cualquier otro elemento final de punto con respecto a considerar la búsqueda anticipada y llenar las tablas.