¿Por qué PRIMERO y SEGUIR en Compiler Design?

¿Por qué PRIMERO?
Vimos la necesidad de retroceder en el artículo anterior de Introducción al análisis de sintaxis, que es realmente un proceso complejo de implementar. Puede haber una manera más fácil de resolver este problema:

Si el compilador hubiera llegado a saber de antemano cuál es el «primer carácter de la string que se produce cuando se aplica una regla de producción», y lo compara con el carácter o token actual en la string de entrada que ve, sabiamente puede tomar decisión sobre qué norma de producción aplicar.

Tomemos la misma gramática del artículo anterior:

S -> cAd
A -> bc|a 
And the input string is “cad”. 

Por lo tanto, en el ejemplo anterior, si supiera que después de leer el carácter ‘c’ en la string de entrada y aplicar S->cAd, el siguiente carácter en la string de entrada es ‘a’, habría ignorado la regla de producción A-> bc (porque ‘b’ es el primer carácter de la string producida por esta regla de producción, no ‘a’ ), y usar directamente la regla de producción A->a ( porque ‘a’ es el primer carácter de la string producida por esta regla de producción, y es lo mismo que el carácter actual de la string de entrada que también es ‘a’ ).
Por lo tanto, se valida que si el compilador/analizador conoce el primer carácter de la string que se puede obtener aplicando una regla de producción, puede aplicar sabiamente la regla de producción correcta para obtener el árbol de sintaxis correcto para la string de entrada dada.

¿Por qué SEGUIR?
El analizador se enfrenta a un problema más. Consideremos a continuación la gramática para entender este problema.

 A -> aBb
 B -> c | ε
 And suppose the input string is “ab” to parse. 

Como el primer carácter de la entrada es a, el analizador aplica la regla A->aBb.

          A
        / |  \
      a   B   b

Ahora, el analizador busca el segundo carácter de la string de entrada, que es b, y el no terminal a derivar es B, pero el analizador no puede obtener ninguna string derivable de B que contenga b como primer carácter.
Pero la gramática contiene una regla de producción B -> ε, si se aplica, B desaparecerá y el analizador obtiene la entrada «ab», como se muestra a continuación. Pero el analizador puede aplicarlo solo cuando sabe que el carácter que sigue a B en la regla de producción es el mismo que el carácter actual en la entrada.

En RHS de A -> aBb, b sigue a Non-Terminal B, es decir, FOLLOW(B) = {b}, y el carácter de entrada actual leído también es b. Por lo tanto, el analizador aplica esta regla. Y puede obtener la string «ab» de la gramática dada.

           A                    A
        /  |  \              /    \                                                
      a    B    b    =>     a      b       
           |
           ε 

Entonces FOLLOW puede hacer que un No-terminal desaparezca si es necesario para generar la string desde el árbol de análisis.

 

La conclusión es que necesitamos encontrar los conjuntos PRIMERO y SIGUIENTE para una gramática determinada para que el analizador pueda aplicar correctamente la regla necesaria en la posición correcta.

En el próximo artículo, discutiremos las definiciones formales de PRIMERO y SIGUIENTE, y algunas reglas sencillas para calcular estos conjuntos.

Cuestionario sobre análisis de sintaxis

Este artículo ha sido compilado por Vaibhav Bajpai . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *