| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO Problema Unidad 8.4 Problemas 1-10 Problemas 11-20 Problemas 21-30

Problemas 31-40

Problemas 41-50

Bibliografía

PROBLEMARIO

Problemas 41-50

> 41.- Realizar el ejercicio de reconocimiento con retroceso, escribir la gramática y el programa KPM que reconozca las dos cadenas que forman el lenguaje {ab, ac}.

> La gramática es:

> Y el programa KPM, es:

> si reconocemos la sentencia "a c $" tendremos:

> Observamos que a pesar de comenzar bien, la metanoci6n A no se encuentra,
> con lo que hay retroceso y el isave = 1 que se guardó a su entrada, se restaura al dar F, (naturalmente esto se evitaría que la gramática equivalente
> S → aA; A → b | c ).

> 42.- Siguiendo a Hilbert, se dice que una fórmula lógica esta bien formada si:

> a.- Es una variable elemental, que se indica como a, b, c, …

> b.- Si A es una fórmula lógica bien formada (FBF), también lo es ~A.
> c.- Si A y B son FBF’S también lo son las (A ˅ B), (A ˄ B), (A B) y (A ≡ B).
> d.- Solo se pueden formar FBF’S con los tres métodos anteriores. Escribir la gramática y un programa de reconocimiento. Aplicarlo a:

> “(a ˄ (~b)) $”

> La gramática, ya en forma normal es:

> A continuación se da el programa KPM correspondiente:

> B, C, D (análogos al A, cambiando el operador lógico).
> La traza del reconocimiento de (a ˄ (~b)) $ es:

> Los grandes retrocesos que aparecen en el reconocimiento. Knuth, lógicamente, recomienda el "factoring" adecuado que hemos visto en ejercicios anteriores. Una solución intermedia podría ser:

> S → a | b | c | A | (~S)
> A → (S L S)
> L → ˄ | ˅ | U | ≡

> 43.- Calcular las relaciones de precedencia simple para la gramática siguiente:

> S → b A b A → (B | a B → Aa)

> Realizar el reconocimiento de “b(aa)b$”.

> Las tres relaciones de precedencia son:

> 44.- Escribir un diagrama del intérprete que sea capaz de ejecutar un programa LP con las características siguientes:

> a.- Parte izquierda de producción LP con longitud ≤ 4 símbolos.
> b.- Parte derecha de producción LP con longitud ≤ 2 símbolos.
> c.- Que admita el símbolo ANY.
> d.- Que admita acciones (llamada scanner, parada correcta …)

> El diagrama N/S es el siguiente:
> Se comenta lo siguiente:

> a) J es el número de la línea LP a ejecutar. Comienza con J=l.

> b) Se hace un bucle ilimitado con SIGUE, que sólo se detiene con
> una ACCION(J)= $HALTC/).

> c) El DO L=l TO NIZQ(J) compara los símbolos superiores de la pila
> PILAC con la parte izquierda.
> Si hubiera un ANY anota su posición.

> d) Sólo si la comparación con la parte izquierda ha ido bien (MATCH=
> true) se aplica la parte derecha de la producción actual.

> e) La parte derecha supone:
> - Una rutina semántica (que pasa a RPN).
> Transformación de la parte derecha (DO M=...)
> Una acción (llamada explorador, parada, ...)
> Bifuración a la siguiente producción.

> f) No se emplean etiquetas, se pone a qué línea se va a bifurcar (si se activa la producción).

> 45.- Definir la gramática de un bloque y que haga lo siguiente:

> a.- Abreviar con “D” cada declaración y con “S” cada sentencia, escribir si es posible
> un autómata de reconocimiento.
> b.- Escribir un programa LP de reconocimiento.

> La gramática de un bloque BEGIN d; d; d; ... ;... ; s END es la siguiente:

> <Bloque> → begin <lista _ d> ; <lista _ s> end
> <lista d> → d | d; <lista _ d>
> <lista s> → s | s; <lista _s>

> El autómata es el que se describió en el autómata del problema 36.
> El programa LP se incluye a continuación:

> 46.- Calcular las relaciones de precedencia simple de la gramática siguiente:

> S → aAa A → bB
> A → c B → Acd

> Los elementos con círculo son del cálculo de +. Las relaciones son:

> 47.- Calcular las relaciones de precedencia simple para la gramática que representa la sentencia de asignación múltiple:

> S → v := S | A
> A → v := a

> Los elementos con círculo son del cálculo de +. Las relaciones son:

> 48.- Calcular las relaciones de precedencia simple para la gramática siguiente:

> S → if i then S | write (B)
> B → A | A, B
> A → I | n

> La metanoción B es re cursiva por la derecha, estratificado:

> B → B’ B; → A | A, B’

> Resulta:

> 49.- Dado el lenguaje de programación siguiente:

> S → v := E | write E
> E → E ˅ T | E T | E ≡ T’ | E T | T
> T → (E) | ˅ | ~T

> Escribir un programa LP que reconozca sus sentencias. Y aplicarlo a:

> write a ˄ (b ~d) ≡ a ˅ g

> 50.- Buscar características de algún lenguaje de programación conocido que no cumpla la “prefix property”.

> a)La sentencia condicional:
> viendo sólo

> if a > 0 then b := 0

> no es posible saber si está completa la S o falta la parte else ... y en general todas las reglas BNF de una gramática cuyas alternativas acaban con algo entre llaves o paréntesis cuadrados.

> b) Dentro de una expresión aritmética "a + b + c + ..." al tomar la siguiente
> "a + b" sin mirar lo siguiente no se sabe si está o no completa.

> c)Las listas de etiquetas del tipo que sean como sigue:

> De etiquetas etiquetal : etiqueta2
> de parámetros (a, b, c, ...)
> de dimensiones [a:b, c:d, ... ]

> también son imposibles de reconocer sin mirar lo que sigue.

> d) La sentencia de asignación múltiple de PL/I o de ALGOL por el susodicho
> motivo.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello