¿Cómo se identifica si una gramática es LL (1), LR (0) o SLR (1)?¿Cómo identificar si una gramática es LL (1), LR (0) o SLR (1)?
¿Alguien puede explicarlo utilizando este ejemplo o cualquier otro ejemplo?
X → Yz | a
Y → bZ | & épsilon;
Z → & epsilon;
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
Probemos esto en su gramática construyendo los conjuntos FIRST y FOLLOW para cada uno de los no terminales. Aquí, tenemos que
FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}
También tenemos que los conjuntos siguen son
FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}
partir de esto, podemos construir la siguiente LL (1) tabla de análisis sintáctico:
a b z $
X a Yz Yz
Y bZ eps
Z eps
Desde podemos construir esta tabla de análisis sin conflictos, la gramática es LL (1).
Para comprobar 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 el 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.
partir de esto, podemos ver que la gramática no es LR (0) porque hay desplazamiento/reducción conflictos en los Estados (1) y (6). Específicamente, porque tenemos los artículos de reducción Z →. y 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 & epsilon; -productions 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 da vuelta este conjunto de SLR (1) conjuntos configurating:
(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, que no tienen más de reducción por desplazamiento conflictos. 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!
Si no tiene PRIMEROS/PRIMER conflictos y no FIRST/FOLLOW conflictos, su gramática es LL (1).
Un ejemplo de un primer primer conflicto /:
S -> Xb | Yc
X -> a
Y -> a
Al ver sólo el primer símbolo de entrada a, no se puede saber si se debe aplicar la producción S -> Xb o S -> Yc, debido a es en el primer conjunto de ambos X e Y.
un ejemplo de un primer conflicto/SEGUIR:
S -> AB
A -> fe | epsilon
B -> fg
al ver sólo el primer símbolo de entrada f, no se puede decidir si se debe aplicar la produc ción A -> fe o A -> epsilon, porque f está en el primer conjunto de A y el conjunto de SEGUIMIENTO de A (A puede ser analizado como epsilon y B como f).
Observe que si no tiene producciones épsilon no puede tener un conflicto FIRST/FOLLOW.
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. |
--------------------------------------------
AS [S, b] contiene dos producciones hay una confusión en cuanto a la regla a choose.So no se LL (1).
Algunas verificaciones simples para ver si una gramática es LL (1) o no. Verificar 1: La gramática no se debe dejar recursiva. Ejemplo: E -> E + T. no es LL (1) porque se deja recursivo. Verificar 2: La gramática debe tenerse en cuenta.
La factorización a la izquierda se requiere cuando dos o más opciones de reglas de gramática comparten una cadena de prefijo común. Ejemplo: S ->A + int | A.
Comprobación 3: La gramática no debe ser ambiguo.
These are some simple checks.
Su respuesta podría mejorarse incluyendo una ejemplo de cómo aplicar esta regla y potencialmente una fuente para respaldar sus reclamos. –
Gracias por el comentario. He agregado un ejemplo y otra información útil. –
LL (1) gramática es Contexto gramática no ambigua libre que puede ser analizado por LL (1) programas de análisis.
En LL (1)
Para verificar la gramática es LL (1) puede dibujar la 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 comprobar si la gramática es LL (1) o no. Shortcut Technique
¿No hay un FIRST/FIRST conflicto entre X y Y en su LL (1) discusión de la gramática? Ambos contienen b. –
@ JohnRoberts: se produce un conflicto FIRST/FIRST cuando dos producciones para el mismo no terminal tienen conjuntos FIRST superpuestos. Aunque X e Y contienen b en sus PRIMEROS conjuntos, no hay no terminal en la gramática con dos producciones, una de las cuales comienza con X y una de ellas comienza con Y. ¿Tiene sentido eso? – templatetypedef
Entonces, ¿está diciendo que debido a que las dos producciones se relacionan con diferentes no terminales, no hay conflicto? –