Tema 3: Análisis sintáctico - Ejercicios de modelado LL(1) y RLL(1)

Ejercicio M4

Apartado M4.1

La siguiente gramática incontextual G₁ modela expresiones formadas con identificadores, un operador potencia binario asociativo por la derecha, y un operador de cambio de signo unario prefijo más prioritario:

<Expresión> -> <Término> oppot <Expresión> | <Término>
<Término> -> id | opmenos <Término>

Es obvio que G₁ no es LL(1), al tener prefijos comunes. Como ejercicio, verifícalo construyendo la correspondiente tabla de análisis.

Apartado M4.2

Aplicando el método de factorización por la izquierda, obtén una gramática incontextual (sin partes derechas regulares) G₂ equivalente a la anterior (es decir, que genere el mismo lenguaje).

Comprueba si G₂ es LL(1).

Observa que, a diferencia de lo que sucede con el método de eliminación de la recursión por la izquierda, ahora no se ha perdido el modelado de la asociatividad.

Apartado M4.3

Averigua si la siguiente gramática G₃ es RLL(1), construyendo la tabla de análisis de la gramática incontextual equivalente que se obtiene con las transformaciones que hemos estudiado.

<Expresión> -> <Término> (oppot <Término>)?
<Término> -> opmenos <Expresión> | id

Igual que pasaba en el ejercicio M2.3, 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 M4.4

Averigua si la siguiente gramática G₄ es RLL(1):

<Expresión> -> <Término> (oppot <Término>)?
<Término> -> opmenos <Término> | id

Observa muy bien en qué se diferencia de la anterior. Observa también que ninguna de las dos tiene prefijos comunes ni recursividad por la izquierda.

Apartado M4.5

Averigua si la siguiente gramática G₅ es RLL(1):

<Expresión> -> <Término> (oppot <Expresión>)?
<Término> -> opmenos <Término> | id

Compárala con tu solución del apartado M4.2.

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.

---