Segundo Parcial 2C 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 describe la sintaxis de un lenguaje de programacion (bastante limitado). En este lenguaje hay una unica variable x. Un programa en este lenguaje es una serie de asignaciones a esa variable. El terminal num representa una constante entera.

S -> x = E | S ; S
E -> num | x | E + E | (E) 

Ejercicio 1[editar]

  • a) Dar la tabla SLR para G, se˜nalando todos los conflictos que tenga.
  • b) ¿Se pueden resolver los conflictos seleccionando en cada caso una de las entradas de la tabla de manera que el lenguaje reconocido sea L(G)? En caso afirmativo, ¿es unica la solucion?
  • c) ¿Se resolverıan los conflictos si se usara LALR?

Respuesta

  • a)
  • b)
  • c) No porque la gramatica es ambigua -> no es LALR

Ejercicio 2[editar]

(25 pts) Dar una gramatica extendida para L(G) que sea ELL(1).

Respuesta

S --> I S2 
S2 --> ; S | \ 
I --> x = E 
E --> ENS E2 
E2 --> + E | \
ENS --> num | x | ( E ) 

Pasando a ELL(1):

Ejercicio 3[editar]

(25 pts)

  • a) Dar la tabla de precedencia simple para G, se˜nalando todos los conflictos que tenga.
  • b) ¿Se pueden resolver los conflictos seleccionando en cada caso una de las entradas de la tabla de manera que el lenguaje reconocido sea L(G)? En caso afirmativo, ¿es unica la solucion?

Respuesta

S -> x = E | S ; S
E -> num | x | E + E | (E) 
  • a)
    P+    U+            P*
S   x     E S num x )   x
E   (     E num x )     (
  S E x = ; n x + ( ) $
S
E
x 
=
;
n
x
+
(
)
$

Ejercicio 4[editar]

(25 pts) Convertir G en una gramatica de atributos que sintetice el valor final asignado a la variable x. El terminal num tiene un atributo val de tipo entero. Al comienzo de la ejecucion de un programa en este lenguaje, la variable x no esta inicializada. Se deben rechazar los programas en los que el resultado sea indefinido.

Respuesta

Agregamos estas producciones:

S' -> x = E'        {E'.inc = S'.inc}{S'.val = E'.val}
S' -> x = E' ; S   {E'.inc = S'.inc ; S.inc = S'.inc}{S'.val = S.val}
E' -> num          {E'.val = num.val}
E' -> E'1 + E'2    {E1.inc = E.inc ; E2.inc = E.inc}{E'.val = E'1.val + E'2.val}
E' -> (E'1)         {E'1.inc = E'.inc}{E'.val = E'1.val}
S -> x = E          {E.inc = S.inc}{S.val = E.val}
S -> S1 ; S2        {S2.inc = S.inc ; S1.inc = S.inc}{S.val = S2.val}{S.inc = S1.val}
E -> num            {E.val = num.val}
E -> x              {E.val = E.inc}
E -> E1 + E2        {S1.inc = S.inc ; S2.inc = S.inc}{E.val = E1.val + E2.val}
E -> (E1)           {E1.inc = E.inc}{E.val = E1.val}