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

Ejercicio M6

Imagina que quieres introducir en un lenguaje sentencias de selección en las que la parte else es opcional. Prescindiendo ahora de otras sentencias y expresiones, podrías escribir una gramática incontextual G₁ así:

<Sentencia> -> escribe id
<Sentencia> -> if <Condición> then <Sentencia>
<Sentencia> -> if <Condición> then <Sentencia> else <Sentencia>
<Condición> -> id

Imagina ahora que quieres implementar un analizador LL(1) o RLL(1) para ese lenguaje. Es obvio que G₁ no es LL(1), al tener prefijos comunes. Al resolver ese problema eliminando prefijos comunes, podrías obtener la siguiente gramática G₂ con partes derechas regulares:

<Sentencia> -> escribe id
<Sentencia> -> if <Condición> then <Sentencia> ( else <Sentencia>) ?
<Condición> -> id

que es equivalente a la siguiente gramática incontextual G₃:

<Sentencia> -> escribe id
<Sentencia> -> if <Condición> then <Sentencia> <Sentencia2>
<Sentencia2> -> else <Sentencia> |
<Condición> -> id

Obtén la tabla de análisis para comprobar que, en este caso, con la factorización no se ha evitado tener conflictos LL(1), es decir, que G₃ no es LL(1) y, por tanto, G₂ no es RLL(1).

De hecho, estamos ante el "problema del else ambiguo" que describe Louden en la seccion 3.4.3 e ilustra con una gramática similar. Puedes comprobar fácilmente que la siguiente cadena:

if id then if id then escribe id else escribe id

tiene dos árboles de derivación con cada una de las 3 gramáticas anteriores. Por lo tanto, las 3 son ambiguas. Y si son ambiguas, no son LL(1) ni RLL(1).

En la práctica este problema tiene al menos 3 soluciones diferentes:

1. Modificar el lenguaje, añadiendo un delimitador de cierre a las sentencias de selección [Louden p. 122].
2. Modificar la gramática, para obtener una equivalente que no sea ambigua; en este caso, esto resulta complejo [Louden p. 121].
3. Modificar el analizador para que, donde está el conflicto, se escoja siempre la opción que empareja el else con el if más cercano [Louden p. 156]. Esto es lo que se denomina "manipular la tabla de análisis".

Piensa cuál de las 3 soluciones preferirías si estuviese en tus manos tanto el diseño del lenguaje como el diseño del compilador, y si tú sólo pudieses diseñar el compilador y el lenguaje te viniese dado.

---