y seguir de los no terminales en dos gramáticas

Question

Dada siguiente gramática

S -> L=L 
s -> L 
L -> *L 
L -> id 

¿Cuál es la primera y seguir para los no terminales?

Si se cambia la gramática en

S -> L=R 
S -> R 
L -> *R 
L -> id 
R -> L 

¿Cuál será el primero y seguir?

Answer 1

Cuando tomé un curso de compilación en la universidad, no entendí PRIMERO y SIGUE en absoluto. Implementé los algoritmos descritos en el libro del Dragón, pero no tenía idea de qué estaba pasando. Creo que ahora.

Supongo que tiene un libro que da una definición formal de estos dos conjuntos, y el libro es completamente incomprensible. Intentaré dar una descripción informal de ellos, y espero que eso te ayude a dar sentido a lo que hay en tu libro.

El PRIMER conjunto es el conjunto de terminales que posiblemente pueda ver como la primera parte de la expansión de un terminal no terminal. El conjunto FOLLOWS es el conjunto de terminales que podrías ver después de la expansión de un terminal no terminal.

En su primera gramática, solo hay tres tipos de terminales: =, * y id. (También puede considerar $, el símbolo de fin de entrada, como un terminal). Los únicos no terminales son S (una declaración) y L (un valor L - una "cosa" que puede asignar).

Piense en FIRST (S) como el conjunto de no terminales que posiblemente podría iniciar una declaración. Intuitivamente, sabes que no comienzas una declaración con =. Entonces no esperarías que apareciera en FIRST (S).

Entonces, ¿cómo comienza una declaración? Hay dos reglas de producción que definen cómo se ve un S, y ambos comienzan con L. Entonces, para descubrir qué hay en FIRST (S), realmente debes mirar lo que está en FIRST (L). Hay dos reglas de producción que definen cómo luce un Lvalue: o bien comienza con un * o con un id. Entonces FIRST (S) = FIRST (L) = {*, id}.

SIGUE (S) es fácil. Nada sigue a S porque es el símbolo de inicio. Entonces, lo único en FOLLOWS (S) es $, el símbolo del final de la entrada.

SIGUE (L) es un poco más complicado. Debe observar todas las reglas de producción donde aparece L, y ver qué viene después. En la primera regla, verá que = puede seguir L. Entonces = está en SIGUIENTE (L). Pero también observa en esa regla que hay otra L al final de la regla de producción. Entonces, otra cosa que podría seguir L es cualquier cosa que pueda seguir a esa producción. Ya descubrimos que lo único que puede seguir a la producción S es el final de la entrada. Entonces SIGUE (L) = {=, $}. (Si mira las otras reglas de producción, L siempre aparece al final de ellas, por lo que solo obtiene $ de esas.)

Echa un vistazo a este Easy Explanation, y por ahora ignora todo lo relacionado con ϵ, porque no tienes ninguna producción que contenga la cadena vacía. En "Reglas para primeros conjuntos", las reglas # 1, # 3 y # 4.1 deben tener sentido. Debajo de "Reglas para grupos de seguidores", las reglas # 1, # 2 y # 3 deben tener sentido.

Las cosas se vuelven más complicadas cuando tiene ϵ en sus reglas de producción. Suponga que tiene algo como esto:

D -> S C T id = V // Declaration is [Static] [Const] Type id = Value 
S -> static | ϵ // The 'static' keyword is optional 
C -> const | ϵ  // The 'const' keyword is optional 
T -> int | float // The Type is mandatory and is either 'int' or 'float' 
V -> ...   // The Value gets complicated, not important here. 

Ahora bien, si desea calcular PRIMERO (D) no se puede simplemente mirar primero (S), ya que S puede ser "vacío". Sabes intuitivamente que FIRST (D) es {static, const, int, float}. Esa intuición está codificada en la regla # 4.2. Piense en SCT en este ejemplo como Y1Y2Y3 en las reglas de "Explicación fácil".

Si desea calcular los SIGUIENTES (S), no puede simplemente mirar PRIMERO (C), porque puede estar vacío, por lo que también debe mirar PRIMERO (T). Así que SIGUE (S) = {const, int, float}. Usted obtiene eso aplicando "Reglas para conjuntos de seguimiento" # 2 y # 4 (más o menos).

Espero que ayude y que usted pueda descubrir FIRST y FOLLOWS para la segunda gramática por su cuenta.

Si ayuda, R representa un Rvalue - una "cosa" que no puede asignar, como una constante o un literal. Un Lvalue también puede actuar como un Rvalue (pero no al revés).

a = 2; // a is an lvalue, 2 is an rvalue 
a = b; // a is an lvalue, b is an lvalue, but in this context it's an rvalue 
2 = a; // invalid because 2 cannot be an lvalue 
2 = 3; // invalid, same reason. 
*4 = b; // Valid! You would almost never write code like this, but it is 
     // grammatically correct: dereferencing an Rvalue gives you an Lvalue.