Práctica 11: Gramaticas y parsers LR (Teoría de Lenguajes)

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

Ejercicio 1[editar]

Dada la siguiente gramática, generar la tabla SLR, graficar el autómata finito correspondiente al conjunto de items, reconocer la cadena ! = bbab y construir el árbol de derivación.

Respuesta

Ejercicio 2[editar]

Dada la gramática:

(a) Mostrar que esta gramática genera todas las expresiones regulares sobre

(b) Mostrar que la gramática es ambigua

(c) Construir un árbol de derivación para la cadena

(d) Construir el AF correspondiente al conjunto de items LR(0) y la tabla SLR.

(e) Resolver los conflictos de tal modo que los árboles de derivación resultantes respeten las precedencias de las expresiones regulares.

(f) Reconocer la cadena


Respuesta

Ejercicio 3[editar]

Dada la siguiente gramática

(a) Construir el AF del conjunto de items LR(0) (b) Construir la tabla SLR (c) ¿Es posible resolver el conflicto sin modificar la gramática? Tratar de reconocer la cadena abab.

Ejercicio 4[editar]

Dada la gramática

(a) Generar el AF correspondiente al conjunto de items LR(1).

(b) Generar la tabla LR(1).

(c) Reconocer la cadena y retornar el árbol de derivación.

Respuesta

Ejercicio 5[editar]

Dada la siguiente gramática, determinar qué elementos son tratados por el analizador lexicográfico, hallar la tabla LR(1) y reconocer una cadena (devolviendo el árbol de derivación).

< decl. de tipo > ::= < tipo > < listadetipo >
< tipo > ::= REAL \; | \; ENTERO \; | \; BOOLEANO
< listadetipo > ::= < ident >,< listadetipo > \; | \; < ident >
< ident > ::= < letra > \; | \; < ident >< letra > \; | \; < ident >< digito >
< letra > ::= A \; | \; . . . \; | \; Z
< digito > ::= 1 \; | \; . . . \; | \; 9

Respuesta

Ejercicio 6[editar]

Dada la gramática , con :

Mostrar que es pero no .


Respuesta


Ejercicio 7[editar]

Dada la gramática , con :

Determinar cuál es el tipo de parser de menor nivel que reconoce el lenguaje generado por la gramática. Justificar. Construir el autómata correspondiente.

Respuesta


Ejercicio 8[editar]

La siguiente gramática describe un subconjunto del lenguaje LISP:

, con :

(a) ¿Es ? (b) ¿Es ? (c) ¿Es ?

Respuesta

Ejercicio 9[editar]

Dada , con :

(a) Construir el conjunto de items para .

(b) Para cada una de las siguientes clases, indicar si pertenece a ella: , , .

Respuesta

Ejercicio 10[editar]

Para cada :

  • Determinar a cuáles de las siguientes clases de gramáticas pertenece : , , , .
  • Reconocer las cadenas que se indican mediante alguno de los métodos mencionados en el punto anterior.

(a) , con :

(b) , con :

Respuesta