Tema 3: Análisis sintáctico - Ejercicios de modelado LL(1) y RLL(1)
Ejercicio M2
Apartado M2.1
La siguiente gramática incontextual G1 modela expresiones
formadas con identificadores, un operador aditivo binario asociativo
por la izquierda, un operador multiplicativo binario asociativo por la
izquierda y más prioritario, un operador de cambio de signo unario
prefijo más prioritario que ambos, y paréntesis:
<Expresión> -> <Expresión> opmas <Término> | <Término>
<Término> -> <Término> opmul <Factor> | <Factor>
<Factor> -> id
| apar <Expresión> cpar
| opmenos <Factor>
Es obvio que G1 no es LL(1), al tener recursión por la izquierda. Como ejercicio, verifícalo construyendo la correspondiente tabla de análisis.
Apartado M2.2
Aplicando el método de eliminación de la recursión por la izquierda, obtén una gramática incontextual G2 equivalente a la anterior (es decir, que genere el mismo lenguaje).
Comprueba si G2 es LL(1).
Observa que en G2 se ha perdido el modelado de las asociatividades de los operadores !!!
Apartado M2.3
Averigua si la siguiente gramática G3 es RLL(1). Para
ello, primero observa si hay problemas obvios, debidos a prefijos
comunes o recursividad por la izquierda. Después, construye la tabla
de análisis de la gramática incontextual equivalente que se obtiene
con las transformaciones que hemos estudiado.
<Expresión> -> <Término> (opmas <Término>)*
<Término> -> <Factor> (opmul <Factor>)*
<Factor> -> id
| apar <Expresión> cpar
| opmenos <Expresión>
De hecho, esta gramática es ambigua, y viéndolo no hace falta construir la tabla de análisis para saber que no es RLL(1). Encuentra un ejemplo de cadena que tenga dos árboles de derivación diferentes, para demostrar que es ambigua.
Apartado M2.4
Averigua si la siguiente gramática G4 es RLL(1):
<Expresión> -> <Término> (opmas <Término>)*
<Término> -> <Factor> (opmul <Factor>)*
<Factor> -> id
| apar <Expresión> cpar
| opmenos <Factor>
Observa muy bien en qué se diferencia de la anterior.
Piensa cuál de todas ellas es más adecuada para un analizador RLL(1) en el que queramos tener en cuenta las prioridades y asociatividades de los operadores indicadas al principio.