Análisis de resolución de turnos: preguntas

Recientemente me encontré con un artículo que describe la técnica de análisis mencionada en el título. Desafortunadamente, la terminología utilizada en dicho documento está más allá de mi comprensión, por lo que he estado tratando de comprender el algoritmo de construcción de manera más intuitiva. Creo que tuve éxito ( esta presentación fue la fuente del momento ah-ha), pero una verificación de la corrección por parte de alguien familiarizado con la técnica o la terminología contenida en ella sería muy apreciada.

Voy a describir mi opinión sobre la solución (si es correcta, creo que podría ser de ayuda para otras personas que intentan comprender la técnica) y luego haré preguntas adicionales. Para asegurar que no hay malentendidos, voy a utilizar la siguiente notación estándar: , A , B , C , . . . ∈ N , . . . X , Y , Z ∈ N ∪ T , α , $a, b, c, ... \in T$$A, B, C, ... \in N$$... X, Y, Z \in N \cup T$ y, como en el artículo, A i → ω para denotar la regla número i . Sin embargo, probablemente usaré diferentes nombres para los conceptos que el documento original.$\alpha, \beta, \gamma, ... \in \{N \cup T\}^*$$A \xrightarrow{i} \omega$$i$

Además, a lo largo de la descripción, se usa la relación de equivalencia .$\kappa_0$

Construcción

Hay dos tipos de elementos dentro del autómata de análisis: elementos simples LR (0) de la forma que llamo elementos de cambio y elementos de la forma A i → α ∙ β , m , n que llamo resolver artículos ; estos le dicen al analizador que empuje n símbolos hacia atrás en el flujo de entrada y luego reduzca por regla número m sobre el primer símbolo de β .$A \xrightarrow{i} \alpha \bullet \beta$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$n$$m$$\beta$

La gramática se aumenta con la regla y la construcción comienza con el elemento de cambio S ′ 0 → ∙ S $ en el estado inicial.$S' \xrightarrow{0} S \$$$S' \xrightarrow{0} \bullet S \$$

Ahora, para construir el autómata, decida entre estas alternativas para cada elemento en un estado :$q$

1. Si el ítem es un ítem de desplazamiento , habrá una transición q X → q ′ en el autómata, donde X es el primer símbolo de β .$A \xrightarrow{i} \alpha \bullet \beta$$q \xrightarrow{X} q'$$X$$\beta$

2. Si el ítem es un ítem de turno terminado , agregue un ítem de resolución B j → α A ∙ β , i , 0 para cada regla B j → α A β .$A \xrightarrow{i} \omega \bullet$$B \xrightarrow{j} \alpha A \bullet \beta, i, 0$$B \xrightarrow{j} \alpha A \beta$

3. Si el ítem es un ítem de resolución , sea X el primer símbolo de β . Si X ∈ N , agregue un elemento de cambio X j → ∙ ω para cada regla X j → ω . Si otros elementos que no sean A i → α ∙ β , m , n tienen X como punto de referencia, agregue una transición q X → q $A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$\beta$$X \in N$$X \xrightarrow{j} \bullet \omega$$X \xrightarrow{j} \omega$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$q \xrightarrow{X} q'$al autómata Cada elemento de resolución en q dará como resultado un elemento de resolución C i → α X ∙ β , m , n + 1 en q ′ .$C \xrightarrow{i} \alpha \bullet X \beta, m, n$$q$$C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$$q'$

4. Si el ítem es un ítem de resolución no aportará ninguna información anticipada y puede descartarse, pero primero agregue un ítem de resolución B j → α A ∙ β , m , n para cada regla B j → α A β .$A \xrightarrow{i} \omega \bullet, m, n$$B \xrightarrow{j} \alpha A \bullet \beta, m, n$$B \xrightarrow{j} \alpha A \beta$

Esto es, por supuesto, solo un boceto; en realidad, un cierre del estado debe calcularse primero y solo entonces podemos lidiar con las transiciones / cambios y resoluciones.

Transformar el autómata en una tabla de análisis de resolución de cambio es trivial después; solo, como una variación menor, los autores del artículo interpretan una resolución como la acción de aceptar. Dado el autómata resultante, me pareció más útil simplemente tratar un cambio de $ como la acción de aceptar.$r_{0,0}$$\$$

Preguntas

El primero es, obviamente, si el proceso descrito anteriormente es correcto.

El segundo es sobre las relaciones de equivalencia. Solo puedo adivinar que la relación de equivalencia es la responsable de decidir qué elementos de resolución se traen cuando se ve un elemento de turno terminado. κ 0 parece dar lugar a un lookahead sorprendentemente similar a los conjuntos de analizadores LSLR F O L L O W L M. El documento describe una "relación de equivalencia más fina" en la página 11; ¿Hay alguna manera de interpretar esta relación en términos intuitivos? ¿Se conocen otras relaciones?$\kappa$$\kappa_0$$FOLLOW_{LM}$

Y el último es sobre resolución de conflictos. El artículo describe bien lo que constituye una insuficiencia en un autómata de resolución de turnos; ¿Hay alguna forma de resolver estas deficiencias, similar a las formas de resolver conflictos en un analizador LR tradicional? ¿Podría implementarse algo como la resolución de conflictos al estilo yacc mediante la precedencia y la asociatividad en un generador de analizador ShRe?

Gracias si lees todo esto y cualquier respuesta será muy apreciada :)

Verifique si esto se discute en la enciclopedia D. Grune, CJH Jacobs, "Técnicas de análisis: una guía práctica" (Spinger, 2008). Si no, tal vez sea lo suficientemente similar a una técnica discutida.