UNIVERSIDAD TECNOLÓGICA NACIONAL

Facultad Regional Tucumán

TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 3
Cátedra: Sintaxis y Semántica de los Lenguajes

GRUPO DE TRABAJO
Profesor: Fecha de Entrega
Nº de Grupo: División:
Auxiliar: ___/___/___
Orden Apellido y Nombre de los Integrantes Nro. Legajo
1
2
3
4
5

UNIDAD Nº 3: Lenguajes-Gramáticas Independientes del Contexto y Autómatas de Pila.

Gramáticas Independientes del Contexto (GIC) y sus lenguajes (LIC). Árboles de derivación y árbol
total de un lenguaje. Ambigüedad. Formato BNF y Diagramas de Sintaxis. Autómatas de Pila (AP).
Formas estándares de una GIC. Criterios de aceptación por estado final y por pila vacía. Diseño de un
AP a partir de una GIC. Transductores Push Down. Analizador Sintáctico (Parser).

1. Problemas a resolver en clase

1.1. Encontrar GIC que generen los siguientes lenguajes. Simular con JFLAP.

a) L1 = { a2n bn+1 / n ≥ 0 }
b) L2 = { an bm / n,m ≥ 0 , |n-m| = 1 }
c) L3 = { an bn+m cm / n,m ≥ 1 }
d) L4 = { an bm cp / m ≥ 0 , n ≥ m , p impar}
1.2. Para dos de las gramáticas obtenidas en el ejercicio anterior, dibujar los árboles de derivación de dos pa-
labras de longitud mayor que 4 y los árboles totales de los lenguajes. Simular con JFLAP.

1.3. Comprobar si son ambiguas las siguientes GIC. En caso afirmativo y de ser posible, obtener gramáticas
equivalentes sin ambigüedad. Simular con JFLAP.

a) S → aS | aaS | aa b) S → aSbb | Sb | λ

1.4. Desarrollar la Forma Normal de Backus para representar la sintaxis de los siguientes lenguajes:

a) Todas las secuencias con ∑ = { a , b } que comienzan con y terminan con el mismo símbolo
b) Todas las secuencias w ε { a , b , c }* / w = w-1 , |w| impar y w no tiene símbolos consecutivos
iguales

1.5. Representar diagramas de sintaxis para:

a) Todas las secuencias de dígitos y letras que comienzan con letra y no tienen dígitos consecutivos
b) Las secuencias que tienen la forma an bm / n > m
c) El conjunto de números enteros sin ceros no significativos
d) Las sentencias de selección (simple y doble)

Página 1/5
 UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 3
Cátedra: Sintaxis y Semántica de los Lenguajes

1.6. Obtener Autómatas de Pila que acepten los siguientes lenguajes. Plantear soluciones con criterio de acep-
tación por Estado Final y por Pila Vacía. Simular con JFLAP.

a) L1 = { an+m bn cm / n,m ≥ 1 }
b) L2 = { an (b + c)m / n,m ≥ 0 , | w |b = | w |a }

1.7. Obtener gramáticas simplificadas para las siguientes GIC y pasarlas a la Forma Normal de Chomsky.
Simular con JFLAP.

a) S → aS | aXc | bYa | Z b) S → x | AB | SA
W → aXa | λ A → xEzz | xAy | λ
X → aXbc | b B → xCx | yCy
Y → aYb | bYa C → zzB | λ
Z → aZa | λ D → A | xx | Byy

1.8. Obtener la Forma Normal de Greibach de las siguientes GIC. Simular con THOTH.

a) S → SA | aa b) S → aX | Wbb | λ
A → aAb | cBa | ab W → bWa | c
B → abc | Bba X → Ya | Wa
Y → Zb | cc
Z → Xc | ab

1.9. Resolver las factorizaciones por izquierda presentes en las siguientes gramáticas y obtener gramáticas
equivalentes en FNG sin factores comunes. Simular con THOTH. ¿Se pueden obtener AP deterministas?

a) S → aBC | aD | λ b) S → aSbb | bSaa | a | b

B → baB | a
C → cacD | cabb | ccB
D → bC | bb

1.10. Para la gramática dada,

a) obtener la Forma Normal de Chomsky y construir un Autómata de Pila que acepte el lenguaje genera-
do, usando análisis ascendente y criterio de aceptación por estado final.
b) obtener la Forma Normal de Greibach y construir un Autómata de Pila que acepte el lenguaje genera-
do, con análisis descendente y criterio de aceptación por pila vacía.

P: S → aX | aY | λ
X → Ybb
Y → aX | b

Simular con JFLAP y THOTH.

Página 2/5
 UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 3
Cátedra: Sintaxis y Semántica de los Lenguajes

2. Problemas a resolver por los alumnos

2.1. Encontrar GIC que generen los siguientes lenguajes. Simular con JFLAP.

a) L1 = { xn (y + z)n / n ≥ 0 }
b) L2 = { an+m bn cm / n,m ≥ 1 }
c) L3 = { 0n 1m / n,m ≥ 1 , n=2m o m=2n }
d) L4 = { (a + b)n cm / n,m ≥ 0, |w|a = m }
e) L5 = { x2n+1 zm yn / n, > 0, m impar}

2.2. Para las gramáticas obtenidas en el ejercicio anterior, seleccionar dos palabras de longitud mayor que 5 y
dibujar los árboles de derivación correspondientes a cada una. Graficar los árboles totales de los lenguajes
(considerar al menos 4 niveles de profundidad). Simular con JFLAP.

2.3. Comprobar si son ambiguas las siguientes GIC. En caso afirmativo y de ser posible, obtener gramáticas
equivalentes sin ambigüedad. Si hubiera algún caso donde no se pueda encontrar una GIC no ambigua,
encontrar el patrón del lenguaje y decir cómo se denomina en general a este tipo de lenguajes. Simular
con JFLAP.

a) S → aX | Yb | λ b) S → aX | Yb | λ c) S → XY | YZ d) S → XY | YX
X → aXb | aa | b X → aXb | aX | b X → aXb | ab X → aaX | a
Y → aYb | b | a Y → aYb | Yb | a Y → aY | a Y → abY | a
Z → bXa | ba

2.4. Expresar en BNF las gramáticas cuyas producciones se indican a continuación, usando todos los meta-
caracteres que sean posibles:

a) S → XYZ b) S → aSa | bSb | XYd

X → aX | λ X → cc | cd
Y → aaYc | a Y → Ydd | λ
Z → cc | λ

2.5. Desarrollar la Forma Normal de Backus y el diagrama de sintaxis de los siguientes lenguajes:

a) Todas las secuencias de la forma anbmcp / n ≥ 1 , m ε {0,2}, p = n+1

b) Todas las secuencias de la forma anbmcp / n ≠ 1 , m ≥ 2 , p > m
c) El conjunto de todos los números enteros con puntos de unidades de mil, millón, etc.

2.6. Desarrollar diagramas de sintaxis para los siguientes lenguajes:

a) Secuencias de letras formadas por una mayúscula seguida de una o más minúsculas, que no tienen
vocales consecutivas
b) Expresiones aritméticas con paréntesis balanceados
c) Las estructuras iterativas de programación

Página 3/5
 UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 3
Cátedra: Sintaxis y Semántica de los Lenguajes

2.7. Obtener Autómatas de Pila que acepten los siguientes lenguajes. Plantear soluciones con criterio de acep-
tación por Estado Final y por Pila Vacía. Simular con JFLAP.

a) L1 = { an bn+m am / n,m ≥ 0 }
b) L2 = { (x + y)n zn / n ≥ 0 }
c) L3 = {(a + b + c) n / n > 0 , |w|a = |w|b }
d) L4 = { xn ym zp / n ≥ 0, m par, p=2n+1 }
e) L5 = { xn ym / n> 0 m > n }
f) L6 = { xn ym / n < m }

2.8. Obtener gramáticas simplificadas para cada una y pasarlas a la Forma Normal de Chomsky.
Simular con JFLAP.

a) S → aaS | X b) S → aX | bZa | λ c) S → bY | ZX
W → abX | bbZ X → bS | Z X → aXb | λ
X → aaX | bY | aZ Y → abX | ZXa Y → abb | bZ
Y → bYa | aaY Z → bZa | b Z → aZb | λ
Z → bZa | bbT | ba

2.9. Simplificar y pasar a la Forma Normal de Greibach las siguientes GIC. Simular con THOTH.

a) S → aaX | bW | λ b) S → Zb | abY | aT
T → bXb | aYa T → aW | λ
V → Vaa | bb W → aWa | bWb
X → Sb | Z | Yaa X → Xbb | T
Y → aYa | Ybb Y → Sa | aW | λ
Z → Xb | aa Z → Ya | aXb

2.10. A partir de las gramáticas en Forma Normal de Chomsky del ejercicio 2.8, obtener los respectivos Autó-
matas de Pilas que acepten los lenguajes generados por las gramáticas, con análisis ascendente y criterio
de aceptación por estado final. Simular con JFLAP.

2.11. A partir de las gramáticas en Forma Normal de Greibach del ejercicio 2.9, obtener los respectivos Autó-
matas de Pilas que acepten los lenguajes generados por las gramáticas, con análisis descendente y criterio
de aceptación por pila vacía. Simular con JFLAP.

2.12. Resolver las factorizaciones por izquierda de las siguientes GIC, pasarlas a FNG y encontrar AP determi-
nistas para cada una, en caso que sea posible. Simular con THOTH.

a) S → abaX | ababY | aa b) S → XY c) S → Xb | Yab

X → aX | ab X → aXb | bb | bZ X → aXbb | aab
Y → abY | abbX Y → abY | abZ | λ Y → aYb | aaX
Z → ccZ | caZ

Página 4/5
 UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 3
Cátedra: Sintaxis y Semántica de los Lenguajes

3. Ejercicio de Aplicación

Intérprete de Expresiones Algebraicas.

Podemos decir que una MEF es un AFD al que se le agregó una función de salida. De igual modo se puede de-
finir un Transductor de Pila (conocido como Push Down Transducer - PDT), como un APD al que se le agrega
una función de salida. Esta salida definida sobre un alfabeto de salida S tiene en general el mismo dominio
que la función de transición del APD y el rango en S*.

Es decir si “g” es la función de salida del PDT, tenemos: g: (Q-F) x (E  { , } ) x P* → S*

De tal modo que en cada transición puede escribir una secuencia de símbolos en una cinta de salida infinita,
que eventualmente puede ser la palabra vacía, en cuyo caso se interpreta como que no se escribe nada en la
cinta de salida.

3.1. Aplicar el concepto de PDT para diseñar un modelo capaz de hacer el análisis sintáctico o reconocimiento
de una expresión aritmética de sumas, productos, divisiones y restas, con paréntesis, en notación infija y
convertirla a notación posfija. Suponer como operandos, identificadores de variables o constantes repre-
sentados por una letra del alfabeto inglés.

3.2. Implementar un algoritmo que use un modelo similar al APD, para evaluar una expresión posfija, dados
los valores numéricos de sus identificadores de variable o constante. La idea de este “evaluador” es que
cuando lea operandos los introduzca en la pila, cuando lea un operador saque los operandos necesarios de
la pila, haga la operación y coloque el resultado en la pila. Y así sucesivamente hasta que al terminar de
leer la expresión posfija, tenga el resultado como único valor en la pila.

Página 5/5