parsing - ¿El propósito de los conjuntos FIRST y FOLLOW en los analizadores LL(1)?

context-free-grammar

Question

¿Puede alguien explicarme cómo se deben usar PRIMERO y SIGUIENTE en la gramática LL (1)? Entiendo que se utilizan para la construcción de tablas de sintaxis, pero no entiendo cómo.

Answer 1

En un analizador de LL (1), el analizador funciona manteniendo un espacio de trabajo inicialmente sembrado con el símbolo de inicio seguido por el marcador de fin de cadena (generalmente indicado como $). En cada paso, realiza una de las siguientes acciones:

• Si el primer símbolo del área de trabajo es un terminal, lo compara con el siguiente token de entrada (o informa de un error si no coincide).
• Si el primer símbolo del área de trabajo es un no terminal, predice con qué producción reemplazará ese no terminal.

El paso de predicción es donde aparecen PRIMERO y SIGUIENTE. El analizador debe poder adivinar, basándose únicamente en el no terminal actual y en el siguiente token de entrada, qué producción utilizar. La pregunta es cómo hacer esto.

Supongamos que el actual no terminal es A y el siguiente token de entrada es t. Si conoces las producciones de A, ¿cuál elegirías para aplicar? Hay un caso simple a considerar: si hay una producción de la forma A → tω, donde ω es una cadena arbitraria, entonces debe seleccionar esa producción porque la t que está viendo como entrada coincidirá con la t en la parte delantera de la producción.

También hay algunos casos complejos a considerar. Supongamos que tiene una producción de la forma A → Bω, donde B es un no terminal y ω es una cadena. ¿En qué circunstancias querrías adivinar esta producción? Bueno, si sabe que el siguiente símbolo de terminal está en, no querría adivinar esta producción a menos que sepa que B puede expandirse a una cadena que comienza con la terminal t (hay otro caso del que hablaremos en una segundo). Aquí es donde entran los conjuntos FIRST. En las gramáticas sin producciones ε, el conjunto FIRST (X) para algunos X no terminales es el conjunto de todos los terminales que potencialmente pueden aparecer al comienzo de alguna cadena derivada de X. Si tiene una producción de la forma A → Bω y usted ve el no terminal t, supondría que usaría esa producción precisamente cuando t ST PRIMERO (B); es decir, B puede derivar una cadena que comienza con t. Si B no deriva nada que comience con t, entonces no hay razón para elegirlo, y si B deriva algo que comience con t, querría hacer esta elección para poder eventualmente igualar la t con ella.

Las cosas se complican un poco cuando se introducen las producciones ε. Ahora, supongamos que tiene una producción de la forma A → BCω, donde B y C no son terminales y ω es una cadena. Supongamos también que el siguiente token de entrada es t. Si t ∈ FIRST (B), entonces elegiríamos esta producción, como se mencionó anteriormente. Sin embargo, ¿qué pasa si t ∉ PRIMERO (B)? Si hay producciones ε en la gramática, es posible que aún queramos elegir esta producción si B puede derivar ε y t ∈ PRIMERO (C). ¿Por qué es esto? Si esto sucede, significa que podríamos igualar la t produciendo BCω, luego produciendo ε desde B, dejando a Cω contra la cual coincidir con la t. Este es un contexto en el que podríamos tener que "revisar" un no-terminal. Afortunadamente, esto es manejado por primeros conjuntos. Si un X no terminal puede producir ε, entonces ε ∈ PRIMERO (X). Por lo tanto, podemos usar los conjuntos FIRST para verificar si necesitamos "revisar" un no terminal al ver si ε ∈ FIRST (X).

Hasta ahora no hemos hablado de los sets SIGUIENTES. ¿Dónde entran? Bueno, supongamos que estamos procesando el terminal A, vemos el terminal t, pero ninguna de las producciones para A puede consumir el t. ¿Qué hacemos entonces? Resulta que todavía hay una manera de que podamos comer esa t. Recuerde que los analizadores de LL (1) funcionan manteniendo un espacio de trabajo con una cadena en él. Es posible que la t que estamos viendo no deba coincidir con la actual A no terminal en absoluto, y en su lugar se supone que debemos producir A y luego dejar que otra no terminal posterior en el espacio de trabajo coincida con la t. Aquí es donde entran los siguientes conjuntos. El conjunto SIGUIENTE de un X no terminal, indicado como SIGUIENTE (X), es el conjunto de todos los símbolos terminales que pueden aparecer inmediatamente después de X en alguna derivación. Al elegir qué producción elegir para A, agregamos una regla final: si el símbolo terminal t está en el conjunto SIGUIENTE de A, elegimos alguna producción que finalmente producirá ε. De esa manera, la A "desaparecerá" y podemos comparar la t con algún carácter que aparezca después del no A.

Esta no es una introducción completa al análisis de LL (1), pero espero que le ayude a ver por qué necesitamos los conjuntos FIRST y FOLLOW. Para obtener más información, elija un libro sobre análisis (recomiendo Técnicas de análisis: una guía práctica de Grune y Jacobs) o tome un curso sobre compiladores. Como un complemento totalmente desvergonzado, di un curso de compiladores en el verano 2012-2013 y todas las diapositivas de las conferencias están disponibles en línea .

¡Espero que esto ayude!