Segundo Recuperatorio 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 de las expresiones de tipos del lenguaje Haskell. En este subconjunto podemos tener nombres de tipo (identificadores que empiezan con mayuscula), variables de tipo (identificadores que empiezan con minuscula), el tipo nulo, funciones, listas y tuplas de tipos.

T -> Num | var | [T] | () | ( L ) | [ T ] | T --> T
L -> T | L , L

Ejercicio 1[editar]

  • a) Mostrar que G es ambigua.
  • b) Dar una gramatica G1 que genere L(G) y sea SLR, teniendo en cuenta que la expresion
var -> var -> [ Nom ]

se debe interpretar como:

var -> (var -> [ Nom ])

Dar la tabla SLR de la gramatica propuesta.

Respuesta

  • a) Es ambigua ya que por ej. ( var , var , var ) tiene 2 arboles de derivacion
  • b)
T -> NF | F
NF -> Num | var | [T] | () | ( L ) | [ T ]
F -> NF --> T
L -> T | T , L


Ejercicio 2[editar]

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

Respuesta

(Revisar)

T -> Num T' | var T' | [T] T' | ( P'
L -> T L'
L' -> , L L' | \
T' -> --> T T' | \
P' -> ) T' | L ) T'

Pasando a ELL(1):

T -> { Num | var | [T] | ( L? ) } (--> T)*
L -> T (, L)*

Ejercicio 3[editar]

(25 pts) Dar la tabla de precedencia simple de G1.

Respuesta

Ejercicio 4[editar]

(25 pts) Convertir G1 en una gramatica de atributos de manera que solo se acepten expresiones en las que ninguna variable de tipo aparezca en la parte izquierda de una funcion.

Respuesta