grammar - tipos - Convertir la gramática ambigua en no ambigua.
que problemas genera una gramatica ambigua (2)
De Wikipedia (en Reconocimiento de gramáticas ambiguas ):
Algunas gramáticas ambiguas se pueden convertir en gramáticas no ambiguas, pero no es posible ningún procedimiento general para hacer esto, ya que no existe un algoritmo para detectar gramáticas ambiguas.
Para llegar a la segunda gramática, tienes que encontrar una gramática que sea
- Equivalente al primero: ambos generan el mismo lenguaje.
- Sin ambigüedades: para cada oración del lenguaje, el árbol de análisis es único.
¿No entendí cómo una gramática no ambigua se deriva de una gramática ambigua? Considere el ejemplo en el sitio: Example . Cómo se derivó la gramática es confuso para mí.
¿Alguien por favor me puede guiar?
El ejemplo tiene dos gramáticas:
Ambiguo:
E → E + E | E ∗ E | (E) | a
No ambiguo
E → E + T | T
T → T ∗ F | F
F → (E) | a
La gramática no ambigua se derivó de la ambigua utilizando información no especificada en la gramática ambigua:
- El operador ''*'' se enlaza más fuerte que el operador ''+''.
- Tanto los operadores ''*'' como ''+'' se dejan asociativos.
Sin la información externa, no hay manera de hacer la transformación.
Con la información externa, podemos decir que:
a * a + b * b
Se agrupa como si estuviera escrito:
(a * a) + (b * b)
en lugar de como
a * ((a + b) * b)
El segundo supone que ''+'' se une más que ''*'', y que los operadores se unen de derecha a izquierda en lugar de izquierda a derecha.
Comentario
¿Cómo podría la asociatividad entrar en escena en ejemplos como:
S → aA | Ba
A → BA | a
B → aB | epsilon
Esta es una gramática ambigua, entonces, ¿cómo convertirla en no ambigua?
Me pregunto si el ''épsilon'' es ε, la cadena vacía; Analicemos la gramática en ambos sentidos.
ε es la cadena vacía
La regla para B dice que B es una cadena vacía o una seguida de una B válida, lo que equivale a una cadena indefinidamente larga de 0 o más a.
La regla para A dice que una A es una a o una B seguida de una a. Por lo tanto, una cadena de a indefinidamente larga podría ser una A también. Por lo tanto, no hay forma de que la gramática elija si una cadena de a es una A o una B.
Y la regla para S no es de ayuda; una S es una a seguida de una cadena indefinidamente larga de a o una cadena indefinidamente larga de a seguida de una a. Requiere al menos una a, pero cualquier número de a desde uno hacia arriba está bien, pero la gramática no tiene base para decidir entre las alternativas de izquierda y derecha.
Por lo tanto, esta gramática es intrínsecamente ambigua y, en mi opinión, no puede hacerse sin ambigüedades; Ciertamente, no se puede hacer sin ambigüedades sin otra información que no esté en nuestro poder.
ε no es la cadena vacía
¿Qué pasa si ε no es la cadena vacía?
- B es ε o un aε.
- A es una a o una B seguida de una a (por lo tanto una a o una a o una aa).
- O bien: S es un a seguido de una A (por lo tanto, aa, aaε o aaaε)
- O: S es una B seguida de una a (por lo tanto, εa o aεa).
En este caso, la gramática es inequívoca en su forma actual (aunque no necesariamente LR (1)). Claramente, mucho depende del significado de ''épsilon'' en el comentario / pregunta.
Asociatividad
No creo que la asociatividad afecte esta gramática. Generalmente entra en juego con operadores de infijo (como el ''+'' en ''a + b'').