parsing - sintactico - tabla ll1

¿Cómo identificar si una gramática es LL(1), LR(0) o SLR(1)?

Question

¿Cómo identifica si una gramática es LL (1), LR (0) o SLR (1)?

¿Alguien puede explicarlo usando este ejemplo o cualquier otro ejemplo?

X → Yz | un

Y → bZ | ε

Z → ε

Answer 1

Con estos dos pasos podemos verificar si LL (1) o no. Ambos deben estar satisfechos.

1.Si tenemos la producción: A-> a1 | a2 | a3 | a4 | ..... | an. Entonces, Primera (a (i)) intersección Primero (a (j)) debe ser phi (conjunto vacío) [a (i) - subíndice i.]

2. Para cada ''A'' no terminal, si Primero (A) contiene épsilon, entonces Primero (A) la intersección Follow (A) debe ser phi (conjunto vacío).

Answer 2

La gramática LL (1) es una gramática sin ambigüedades libre de contexto que puede ser analizada por analizadores LL (1).

En LL (1)

• First L significa escaneo de entrada de izquierda a derecha. Second L significa Left Most Derivation. 1 significa el uso de un símbolo de entrada en cada paso.

Para verificar la gramática es LL (1) puede dibujar una tabla de análisis predictivo. Y si encuentra entradas múltiples en la tabla, entonces puede decir que la gramática no es LL (1).

También es un atajo para verificar si la gramática es LL (1) o no. Técnica de atajo

Answer 3

Para verificar si una gramática es LL (1), una opción es construir la tabla de análisis LL (1) y verificar si hay algún conflicto. Estos conflictos pueden ser

• FIRST / FIRST conflictos, donde dos producciones diferentes tendrían que ser predichas para un par no terminal / terminal.
• FIRST / FOLLOW conflictos, donde se predicen dos producciones diferentes, una que representa que debe tomarse cierta producción y se expande a un número distinto de cero de símbolos, y una que representa que se debe usar una producción que indique que algún no terminal debe expandirse finalmente al cuerda vacía.
• CONFLICTOS DE SEGUIMIENTO / SEGUIMIENTO, donde dos producciones que indican que un no terminal debe expandirse finalmente al conflicto de cadena vacía entre sí.

Probemos esto en su gramática construyendo los conjuntos FIRST y FOLLOW para cada uno de los no terminales. Aquí, obtenemos eso

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 

También tenemos que los conjuntos de SEGUIMIENTO son

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

A partir de esto, podemos construir la siguiente tabla de análisis LL (1):

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

Como podemos construir esta tabla de análisis sin conflictos, la gramática es LL (1).

Para verificar si una gramática es LR (0) o SLR (1), comenzamos construyendo todos los conjuntos de configuración LR (0) para la gramática. En este caso, suponiendo que X es su símbolo de inicio, obtenemos lo siguiente:

(1)
X'' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X'' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

A partir de esto, podemos ver que la gramática no es LR (0) porque hay conflictos de desplazamiento / reducción en los estados (1) y (6). Específicamente, porque tenemos los artículos de reducción Z →. e Y →., no podemos decir si reducir la cadena vacía a estos símbolos o cambiar algún otro símbolo. De manera más general, ninguna gramática con producciones ε es LR (0).

Sin embargo, esta gramática podría ser SLR (1). Para ver esto, aumentamos cada reducción con el conjunto de anticipación para los no terminales particulares. Esto devuelve este conjunto de conjuntos de configuración SLR (1):

(1)
X'' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X'' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

Ahora, no tenemos más conflictos de cambio-reducción. El conflicto en el estado (1) se ha eliminado porque solo reducimos cuando la búsqueda anticipada es z, que no entra en conflicto con ninguno de los otros elementos. Del mismo modo, el conflicto en (6) se ha ido por la misma razón.

¡Espero que esto ayude!

Answer 4

Respuesta simple: se dice que una gramática es LL (1), si la tabla de análisis LL (1) asociada tiene casi una producción en cada entrada de la tabla.

Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals]
   then find the First and follow sets A.
    First{A}={b}.
    Follow{A}={$,a}.

    Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element.

        a            b                   $
    --------------------------------------------
 S  |               A-->a                      |
    |               A-->Aa.                    |
    -------------------------------------------- 

Como [S, b] contiene dos producciones, existe una confusión en cuanto a qué regla elegir. Por lo tanto, no es LL (1).

Algunas verificaciones simples para ver si una gramática es LL (1) o no. Verificación 1 : La Gramática no debe quedar Recursiva. Ejemplo: E -> E + T. no es LL (1) porque es recursivo a la izquierda. Verificación 2 : la gramática debe tener un factor de izquierda.

Se requiere factoraje a la izquierda cuando dos o más opciones de reglas gramaticales comparten una cadena de prefijo común. Ejemplo: S -> A + int | A

Verificación 3 : La gramática no debe ser ambigua.

These are some simple checks.

Answer 5

Si no tiene conflictos FIRST / FIRST ni conflictos FIRST / FOLLOW, su gramática es LL (1).

Un ejemplo de un conflicto PRIMERO / PRIMERO:

S -> Xb | Yc
X -> a 
Y -> a 

Al ver solo el primer símbolo de entrada a, no puede saber si aplicar la producción S -> Xb o S -> Yc, porque a está en el PRIMER conjunto de X e Y.

Un ejemplo de un conflicto FIRST / FOLLOW:

S -> AB 
A -> fe | epsilon 
B -> fg 

Al ver solo el primer símbolo de entrada f, no puede decidir si aplicar la producción A -> fe o A -> epsilon, porque f está en el PRIMER conjunto de A y el conjunto SEGUIR de A (A puede ser analizado como epsilon y B como f).

Tenga en cuenta que si no tiene producciones épsilon no puede tener un conflicto FIRST / FOLLOW.