Segundo Parcial 1C 2006 (Teoría de Lenguajes)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

La siguiente gramatica G representa un subconjunto del lenguaje de especificaci on de gramaticas utilizado por YACC y otras herramientas derivadas de el. En este lenguaje, una gramatica esta compuesta por una serie de reglas (Rs), donde cada regla (R) se compone de un identificador (la parte izquierda de la produccion) seguido por ‘:’, la parte derecha (PD), reglas optativas (Ropt), y puede opcionalmente estar terminada con ‘;’ (Popt).

S -> R | S R
R -> id : PD Ro Po
Ro -> \ | | PD Ro
PD -> \ | PD id
Po -> \ | ;

Ejercicio 1[editar]

(35 pts) Dar la tabla SLR para G, señalando todos los conflictos que tenga. Decidir si se pueden solucionar los conflictos eligiendo en cada caso una de las entradas de la tabla sin modificar la gramatica. Explicar que caracterıstica del lenguaje es la que provoca los conflictos.

Respuesta

Ejercicio 2[editar]

(30 pts) Escribir una gramatica extendida que genere L(G) y que no utilice recursion. Decidir si la gramatica propuesta es ELL(1).

Respuesta

S0 -> S$

S -> R S'
S' -> R S' | \
R -> id : PD Ro Po
Ro -> \ | ! PD Ro
PD -> PD'
PD' -> id PD' | \
Po -> \ | ;

a ELL(1):

S0 -> ( id : (id)* ( ! | (id)* )* ( ; ? ) )+ $

Ejercicio 3[editar]

(5 pts) Decidir si G es de precedencia simple.

Respuesta

No ya que tiene producciones lambda distintas de S->\, lo cual es una condicion de las gramaticas PS.

Ejercicio 4[editar]

(30 pts) Convertir a G en una gramatica de atributos de manera que no se acepten especificaciones de gramaticas en las que haya recursion a izquierda inmediata. El token id tiene un atributo nombre de tipo String.

Respuesta