Recuerda que en las ciencias informáticas cualquier problema casi siempre tiene varias soluciones, no obstante aquí compartimos lo más óptimo y mejor.
Solución:
El ejemplo tiene dos gramáticas:
Ambiguo:
E → E + E | E ∗ E | (E) | a
inequívoco:
E → E + T | T
T → T ∗ F | F
F → (E) | a
La gramática inequívoca se derivó de la ambigua utilizando información no especificada en la gramática ambigua:
- El operador ‘*’ enlaza más fuerte que el operador ‘+’.
- Tanto los operadores ‘*’ como ‘+’ son asociativos a la izquierda.
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 asume que ‘+’ enlaza más estrechamente que ‘*’, y que los operadores enlazan de derecha a izquierda en lugar de izquierda a derecha.
Comentario
¿Cómo entraría en escena la asociatividad 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 ε, el vacío string; Analicemos la gramática en ambos sentidos.
ε es el vacío string
La regla para B dice que B es un vacío string o una a seguida de una B válida, lo que equivale a una longitud indefinida string de 0 o más a’s.
La regla para A dice que una A es una a o una B seguida de una a. Entonces, un tiempo indefinido string de a podría ser una A también. Entonces, no hay forma de que la gramática elija si un string de a es A o B.
Y la regla para S no es de ayuda; una S es una a seguida de una longitud indefinida string de a o indefinidamente largo string de a seguido 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 izquierda y derecha.
Entonces, esta gramática es inherentemente ambigua y no puede, en mi opinión, ser unívoca; ciertamente no puede quedar sin ambigüedades sin otra información que no esté en nuestro poder.
ε no es el vacío string
¿Qué pasa si ε no es el vacío? string?
- B es ε o un aε.
- A es una a o una B seguida de una a (entonces una a o una aε o una aaε).
- O bien: S es una a seguida 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 no es ambigua tal como está (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 infijos (como el ‘+’ en ‘a + b’).
De Wikipedia (sobre el reconocimiento de gramáticas ambiguas):
Algunas gramáticas ambiguas se pueden convertir en gramáticas no ambiguas, pero no es posible un procedimiento general para hacerlo, al igual que no existe ningún 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 idioma, el árbol de análisis es único
Si te gustó nuestro trabajo, tienes la habilidad dejar un enunciado acerca de qué le añadirías a este artículo.