Cómo identificar 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)?
¿Puede alguien explicarlo usando este ejemplo, o cualquier otro ejemplo?
X → Yz / a
Y → bZ / ε
Z → ε
5 answers
Para comprobar si una gramática es LL(1), una opción es construir la tabla de análisis LL(1) y comprobar si hay conflictos. Estos conflictos pueden ser
- PRIMER/PRIMER conflicto, donde dos producciones diferentes tendrían que ser predichas para un par no terminal/terminal.
- Conflictos PRIMERO / SIGUIENTE, donde se predicen dos producciones diferentes, una que representa que alguna producción debe tomarse y se expande a un número distinto de cero de símbolos, y una que representa que una producción debe ser usado indicando que algún no terminal debe ser expandido a la cadena vacía.
- FOLLOW/FOLLOW conflicts, donde dos producciones que indican que un no terminal debe expandirse finalmente a la cadena vacía entran en conflicto entre sí.
Vamos a probar esto en su gramática construyendo los PRIMEROS y SIGUIENTES conjuntos para cada uno de los no terminales. Aquí, obtenemos que
FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}
También tenemos que los siguientes conjuntos son
FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}
De esto, podemos construya la siguiente tabla de análisis LL(1):
a b z $
X a Yz Yz
Y bZ eps
Z eps
Dado que 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 de 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.
De esto, podemos ver que la gramática no es LR(0) porque hay conflictos shift/reduce en los estados (1) y (6). Concretamente, porque tenemos los elementos 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. Más generalmente, ninguna gramática con ε-productions es LR (0).
Sin embargo, esta gramática podría ser SLR(1). Para ver esto, aumentamos cada reducción con el lookahead establecido para los no terminales particulares. Esto devuelve este conjunto de conjuntos de configuración de 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 reducción de turnos. El conflicto en el estado (1) se ha eliminado porque solo reducimos cuando el lookahead 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!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-12-13 22:03:50
Si no tiene conflictos PRIMERO/PRIMERO y no tiene conflictos PRIMERO/SEGUIR, su gramática es LL(1).
Un ejemplo de un PRIMER/PRIMER conflicto:
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 PRIMERO/SIGUIENTE:
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á tanto en el PRIMER conjunto de A como en el SIGUIENTE conjunto de A (A se puede analizar como epsilon y B como f).
Tenga en cuenta que si no tiene epsilon-productions no puede tener un conflicto DE PRIMERA/SIGUIENTE.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-12-02 17:18:19
Respuesta simple:Se dice que una gramática es una LL(1),si la tabla de análisis LL(1) asociada tiene más de 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 hay una confusión en cuanto a qué regla a choose.So no es LL (1).
Algunas comprobaciones simples para ver si una gramática es LL(1) o no. Marque 1 : La gramática no debe dejarse Recursiva. Ejemplo: E > > E + T. no es LL(1) porque se deja recursivo. Compruebe 2 : La Gramática se Debe Dejar Factorizado.
Se requiere factorización izquierda cuando dos o más opciones de reglas gramaticales comparten una cadena de prefijo común. Ejemplo: S> > A+int| A.
Comprobar 3 : La gramática no debe ser ambigua.
These are some simple checks.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-08-05 12:29:06
La gramática LL(1) es una gramática sin contexto que puede ser analizada por los analizadores LL(1).
In LL (1)
- First L significa escanear la entrada de izquierda a derecha. Segundos soportes L para la Derivación Más Izquierda. 1 significa usar un símbolo de entrada en cada paso.
Para Comprobar la gramática es LL(1) se puede dibujar tabla de análisis predictivo. Y si encuentra varias entradas 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 . Técnica de acceso directo
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-05-01 12:39:18
Con estos dos pasos podemos comprobar si LL(1) o no. Ambos tienen que estar satisfechos.
1.Si tenemos la producción:A->a1|a2|a3|a4|.....|un. Entonces, Primero(a(i)) intersección Primero (a (j)) debe ser phi (conjunto vacío)[a (i)-un subíndice i.]
2.Para cada 'A' no terminal, si Primero (A) contiene epsilon Entonces Primero(A) intersección Siguiente(A) debe ser phi (conjunto vacío).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-06-24 05:39:51