Universidad Autónoma del Estado de México

Facultad deIngeniería

PROGRAMACION DE SISTEMAS II

Un compilador es un programa traductor que lee un programa escrito en un lenguaje (programa

fuente) y lo traduce a un programa equivalente en otro lenguaje (programa objeto). Una parte importante
durante el proceso de traducción, es que el compilador indique los errores ocurridos.

PROGRAMA PROGRAMA
COMPILADOR
FUENTE OBJETO

MENSAJES DE
ERROR

El programa fuente puede estar escrito en varios lenguajes, así mismo, el programa objeto puede
ser diferente, quizás otro lenguaje, código intermedio, o código de máquina, el cual puede ser
ejecutado "directamente" por un microprocesador.

Existen compiladores de un paso, o de varios pasos, dependiendo de las lecturas que hagan del
archivo fuente o archivos con representaciones intermedias. También existen de optimización de
código, etc.
FASES DE UNA COMPILACION

Análisis.- Descompone el programa fuente en piezas para obtener una representación intermedia
del mismo.

Síntesis.- Toma la representación intermedia para generar el código máquina, o cuando menos, el
código intermedio.

Durante la fase de análisis se crean estructuras jerárquicas como los árboles de sintaxis.

X=2*Y+C

X +

C *

2 Y

Existen impresoras que permiten la impresión con diferentes tipos de FONTS y los programas con
sangrías. Estos pueden considerarse como parte de un compilador.
PREPROCESADORES

Existen algunos editores que van realizando algunas tareas adicionales, por ejemplo: Si se coloca
un "if automáticamente se agrega un "then", o bien cuando se trabaja con paréntesis se verifica el
balanceo de expresiones.

Los "Static Chequers" son otro tipo de preprocesadores que descubren posibles ciclos sin criterio
de paro, detectar las partes de código que nunca serán ejecutadas; es similar a un proceso de
optimización de código. Es decir, se enfoca más hacia errores lógicos o semánticos.

-1- Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

En el libro se considera a un intérprete como un preprocesador, un intérprete tiene que "realizar

toda" la tarea del compilador para una línea de código, es decir, revisar léxico, sintaxis, semántica,
crear una representación de una expresión (quizás un árbol en el caso de una asignación) y evaluarla.
Algunas ventajas son que en algunos casos no es posible conocer cuanta memoria se utilizar para
datos, y con un compilador, habrá que reservarla.

Se puede pensar también que durante la fase de análisis se habla de intérpretes de QUERYS, o
procesadores de palabras, etc.

El contexto en el que se desarrolla un compilador puede variar, ya que pueden existir

preprocesadores que realicen operaciones sobre el programa fuente, tal como expansiones de macros.
Por ejemplo quizá el lenguaje original de alto nivel no tenga un WHILE, pero si estructuras IF,
entonces el preprocesador modifica el código WHILE simulándolo con IF'S.

Regularmente se piensa que el compilador genera código en ensamblador, esto no

necesariamente es cierto, pero es factible en algunos casos.
CONTEXTO GENERAL DE UN COMPILADOR
ESQUELETO DE PROGRAMA FUENTE

PREPROCESADOR

PROGRAMA FUENTE

COMPILADOR

PROGRAMA OBJETO EN ENSAMBLADOR

ENSAMBLADOR

CODIGO MAQUINA RELOCALIZABLE

Librerías para
LIGADOR los archivos
objeto
CODIGO MAQUINA (EJECUTABLE) relocalizables.

En la parte de análisis se tienen estas partes para un compilador:

1. Análisis Lineal, o lexicográfico: Separar un archivo en cadenas de caracteres (unidades

léxicas o tokens) con algún formato particular.

2. Análisis Jerárquico o Sintáctico: Se agrupan los tokens obtenidos del análisis lexicográfico
con alguna jerarquía (arboles).

3. Análisis Semántico: Verifica que las estructuras tengan congruencia (verificación de tipos
principalmente).

-2- Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

ANALISIS LEXICOGRAFICO: Separación en tokens:

a:=b+4*a*c.

LEXEMAS = { :=, b, +, 4, *, a, *, c }
TOKENS = { asig, id, op_ar, num, op_ar, id, op_ar, id }

No se consideran los espacios.

ANALISIS SINTACTICO: Es un análisis jerárquico (parsing) que agrupa los tokens en frases
gramaticales. Es frecuente representar frases gramaticales con arboles:

ASIGNACION

IDENTIFICADOR := EXPRESION

a EXPRESION + EXPRESION

IDENTIFICADOR EXPRESION * EXPRESION

b IDENTIFICADOR EXPRESION * EXPRESION

4 IDENTIFICADOR IDENTIFICADOR

a c
✓ Si identificador es una expresión y
✓ Si número es una expresión 
✓ Si EXP1 y EXP2 son expresiones  EXP1*EXP2 y EXP1+EXP2 y (EXP1) también son
expresiones
Así en programación:

✓ Si IDENTIFICADOR1 es un identificador y EXPRESION2 es una expresión entonces

IDENTIFICADOR1:=EXPRESION2 es una afirmación.
✓ Si EXPRESION1 es una expresión y AFIRMACION2 es una afirmación entonces
✓ WHILE (EXPRESION1) DO AFIRMACION2 IF(EXPRESION1) THEN AFIRMACION2 son
afirmaciones.
El árbol jerárquico se simplifica como:

:= := Semantico

a + a +

b * b *

4 * real *

a c 4 a c

-3- Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

ANALISIS SEMANTICO: En programación prácticamente son las verificaciones de tipos en

expresiones; validez de índices en arreglos, etc.

Conceptualmente un compilador trabaja en fases, y en cada fase el programa fuente se

transforma de una representación a otra.

PROG. FUENTE

A. LEXICO

F. ANALISIS A. SINTACTICO

A. SEMANTICO
TABLAS DE MANEJADOR
SIMBOLOS DE ERRORES
GEN. COD. INT.

F. SINTESIS OPT. CODIGO

GEN. COD. OBJ.

PROG. OBJETO
Los manejadores de tablas de símbolos y errores, no son arbitrariamente fases; interactúan
implícitamente "todo el tiempo" con las otras fases.

La función esencial de una tabla de símbolos es almacenar los tokens leídos de un programa
fuente junto con la serie de atributos que lo definen, tales como la línea y columna donde se encuentra
en el programa fuente, dirección de almacenamiento, tipo, tamaño (en caso de strings), alcance de
variables en procedimientos, número de argumentos de entrada y salida, etc.

Se selecciona normalmente un registro por cada identificador, con un número x de campos para
almacenar los atributos del token. La información de esta tabla debe recuperarse rápidamente. Con
frecuencia los atributos no pueden ser detectados en la fase lexicográfica, entonces hay que esperar el
análisis sintáctico y semántico. Se puede hablar de compiladores que se frenan cuando existe un error,
no obstante, algunas fases (sintáctica) permiten los mecanismos necesarios para indicar el error y
continuar la revisión y atrapar así más errores.

Para mostrar cómo funciona un compilador completo. Supongamos que se tiene un programa
fuente con la siguiente expresión:

PRECIO := CANTIDAD + DESC * 60

-4- Héctor Torres Aguilar

Universidad Autónoma del Estado de México
Facultad deIngeniería

PRECIO := CANTIDAD + DESC * 60

A. LEXICO

id1 asig id2 + id3 * num

A. SINTACTICO

asig

id1 +

id2 *

id3 num

A. SEMANTICO

asig

id1 +

id2 *

id3 real(num)

GEN. COD. INT.

var1 := real(60)
var2 := id3 * var1
var3 := id2 + var2
id1 := var3

OPT. CODIGO

var1 := id3 * 60.0

id1 := id2 + var1

GEN. CODIGO

MOV R1 ,id3
MUL R2,60.0
MOV R2,id2
ADD R1 ,R2
MOV id1 ,R1

-5- Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

En algunos casos es recomendable reducir el número de pasadas en la revisión de un archivo de

entrada, por ejemplo, normalmente se pueden mezclar las fases léxica y sintáctica en una sola pasada.
ANALISIS LEXICOGRAFICO

El analizador léxico es la primera fase de un compilador. Las principales tareas que realiza son la
lectura de caracteres de un archivo de entrada, la provisión de un token para el parser y el
almacenamiento de atributos en una tabla de símbolos tanto como sea posible. Es frecuente añadir un
analizador léxico como una simple rutina del parser.

Pide un token

PROG. FUENTE A. LEXICO A. SINTACTICO

Devuelve token

TABLA DE
SIMBOLOS

Al analizador léxico se le dejan normalmente tareas como:

✓ Eliminación de espacios, tab's, líneas en blanco.

✓ Eliminación de comentarios.
✓ En algunos casos almacenar los números de línea del archivo para relacionarlos con los
errores.
✓ La elaboración de una copia del programa fuente con los errores señalados.

En ocasiones se separa un analizador lexicográfico en dos fases consecutivas "scanner" para las
tareas más sencillas y "analizador léxico para las más complejas". Por ejemplo, un scanner se puede
encargar únicamente de la eliminación de espacios, tabuladores, líneas en blanco y comentarios.

Distinguiendo tokens de lexemas:

TOKEN LEXEMA
const const
if if Los tokens son tratados
op_rel >, <, =, >=, <=, <> como elementos
id valor, i, Precio, D1 terminales del lenguaje
num 3, 3.5, -7, -12.3e-15

Cuando un token se asocia con más de un lexema se debe almacenar información adicional para
que pueda ser distinguido en las siguientes fases, tal es el caso del token num y del token id:

-6- Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

✓ VAR1 → <id, apuntador a la tabla de símbolos para su lexema>

✓ * → <*, >
✓ 3 → <num, valor 3>
✓ = → <op_rel, igual>

Algunas tareas sofisticadas, pero que pueden confundir al parser en un analizador léxico, son:

✓ Borrar caracteres extraños.

✓ Insertar un carácter donde se requiera.
✓ Remplazar un carácter incorrecto por uno correcto.
✓ Invertir dos caracteres adyacentes, etc.

El analizador léxico es prácticamente la única fase que leerá el archivo de entrada carácter por
carácter, lo cual puede llevar mucho tiempo.

Una técnica para agilizar esta tarea, es leer los caracteres en un buffer de tamaño 2n partido por
la mitad, y colocar dos apuntadores, (Ap_inicio, Ap_avance); al principio ambos se encuentran en el
carácter de inicio del lexema a leer, y Ap_avance, avanza carácter por carácter hasta formar un lexema
que pueda ser asociado, en ese momento, se empatan Ap_inicio y Ap_avance en el inicio del siguiente
lexema, si Ap_avance llega al fin de la primera mitad del buffer, llama a la segunda mitad del buffer, si
Ap_avance llega al final de la segunda mitad, llena la primera mitad, y avanza al principio de la
primera. Esto no representa problemas si el analizador no tiene que hacer visitas adela ntadas, pero si
requiriera visitas adelantadas, hay problemas en caso de que la cantidad adelantada de caracteres sea
mayor que n.

2n

n n

/0 /0

Ap_ini Ap_ava n-izq.

LENGUAJES.

ALFABETO: Conjunto finito de símbolos.

STRING: Secuencia finita de símbolos pertenecientes a un alfabeto.
LENGUAJE: Conjunto de strings sobre un determinado alfabeto.

La longitud de un string 𝑥 se denota por |𝑥|. Así |∈|=0, donde ∈ denota la cadena vacía.

Si 𝑥 y 𝑦 son dos strings, la concatenación de los strings denotada por 𝑥𝑦 es la añadidura de 𝑦 a 𝑥.

El elemento de identidad para la concatenación es la cadena vacía ∈, ya que 𝑆 ∈ = ∈ 𝑆 = 𝑆.

Si se piensa la concatenación como un producto y exponenciación, definimos 𝑆 0 = ∈, y definimos

para 𝑖 > 0 𝑐𝑜𝑚𝑜 𝑆 𝑖 = 𝑆 𝑖−1 𝑆 entonces

𝑆0 = ∈

𝑆1 = 𝑆 0 𝑆 = ∈ 𝑆 = 𝑆

-7- Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

𝑆 2 = 𝑆 1 𝑆 = 𝑆𝑆

𝑆 3 = 𝑆 2 𝑆 = 𝑆𝑆𝑆 ….

Existen algunos términos asociados con strings:

PREFIJO DE S: El string obtenido quitando símbolos de S cero o más veces desde una posición
hasta el final, ∈ también es un prefijo de S.

SUFIJO DE S: El string obtenido quitando símbolos de S cero o más veces desde el principio
hasta cierta posición, ∈ también es un prefijo de S.

SUBSTRING DE S: El string obtenido borrando un PREFIJO y un SUFIJO de S. Ambos S y ∈ son

substrings de S.

PREFIJO, SUFIJO, SUBSTRING PROPIO DE S: Un string X prefijo, sufijo o substring

respectivamente, tal que 𝑋 ≠ 𝑆 𝑦 𝑋 ≠ ∈.

SUBSECUENCIA: El string obtenido borrando 0 o más símbolos de S no necesariamente

continuos.

Para la implementación del análisis léxico existen tres importantes operaciones aplicadas a
lenguajes, la unión, la concatenación y la cerradura. Si extendemos el concepto de exponenciación a
lenguajes, (denotando con letras mayúsculas un lenguaje; ej : D = {O, 1, 2, 3, 4, 5, 6, 7, 8, 9})
obtenemos las siguientes operaciones:

Unión de L y M 𝐿∪𝑀 = {𝑆|𝑆ℰ𝐿 𝑜 𝑆ℇ𝑀}

𝐿∪𝑀

Concatenación de L y M 𝐿𝑀 = { 𝑆𝑇 | 𝑆 ℇ 𝐿 𝑦 𝑇 ℇ 𝑀 }
𝐿𝑀

Cerradura de L 𝐿∗ = ⋃∞
𝑖=0 𝐿
𝑖
(L es 0 o más concatenaciones de L)
𝐿∗

Cerradura positiva de L 𝐿+ = ⋃∞
𝑖=1 𝐿
𝑖
(L es 1 o más concatenaciones de L)
𝐿+

Ej : Sean A = { A, B, … , Z, a, b, … , z} y B = { 0, 1, … , 9} dos alfabetos, (se pueden observar

como lenguajes). Se pueden crear algunos otros lenguajes como:

1.- 𝐴 ∪ 𝐵
2.- 𝐴𝐵
3.- 𝐴3
4.- 𝐴∗
5.- 𝐴+
6.- 𝐴(𝐴 ∪ 𝐵)∗
7.- 𝐵 +
EXPRESIONES REGULARES

Existe una notación con la que se pueden representar lenguajes como el ejemplo (6) anterior,
utilizando paréntesis, el símbolo de alternación |, * y +. Así 𝒍𝒆𝒕𝒓𝒂(𝒍𝒆𝒕𝒓𝒂|𝒅𝒊𝒈𝒊𝒕𝒐)∗ es similar a (6).

-8- Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

De esta manera, una expresión regular sobre un alfabeto Σ puede generar un lenguaje particular,
este lenguaje se denota como L(r) dada la expresión regular r. Algunas reglas que definen una
expresión regular sobre Σ y los lenguajes generados son :

1.- ∈ es una expresión regular que denota el lenguaje { ∈ }.

2.- Si a es un símbolo en Σ, entonces a es un expresión regular que denota el lenguaje {a}.

3.- Si r y s son expresiones regulares que generan los lenguajes L(r) y L(s) respectivamente,
entonces:
a).- (r) | (s) es una expresión regular denotando 𝐿(𝑟) ∪ 𝐿(𝑠).
b).- (r)(s) es una expresión regular denotando 𝐿(𝑟)𝐿(𝑠).
c). 𝑟 ∗ es una expresión regular denotando (𝐿(𝑟))∗ .
d).- (𝑟)es una expresión regular denotando 𝐿(𝑟).

Un lenguaje denotado por una expresión regular se llama conjunto regular. Pueden omitirse
muchos paréntesis en un expresión regular si se asume:

1.- El operador * tiene la jerarquía más alta.

2.- La concatenación tiene la segunda jerarquía.
3.- La alternación | tiene la más baja jerarquía.
4.- Los tres anteriores son asociativos por la izquierda.

(𝑎) | ((𝑏)∗ (𝑐)) es equivalente a 𝑎 | 𝑏 ∗ 𝑐

Ej:
1).- 𝑎|𝑏
2).- (𝑎 |𝑏) (𝑎 |𝑏)
3).- 𝑎∗
4).- (𝑎 | 𝑏)∗ ≠ 𝑎 ∗ | 𝑏 ∗ 𝑝𝑒𝑟𝑜 𝑖𝑔𝑢𝑎𝑙 𝑎 (𝑎 ∗ 𝑏 ∗ )∗

En el ejemplo (4) las dos expresiones son equivalentes denotadas con un signo igual r=s.

Las expresiones regulares tienen las siguientes propiedades

AXIOMA DESCRIPCION
𝑟 | 𝑠 = 𝑠 |𝑟 | es conmutativo
𝑟 | (𝑠 | 𝑡) = (𝑟 | 𝑠) | 𝑡 | es asociativo
𝑟(𝑠𝑡) = (𝑟𝑠)𝑡 La concatenación es asociativa
𝑟(𝑠 | 𝑡) = 𝑟𝑠 | 𝑟𝑡 La concatenación es distributiva sobre |
(𝑠 | 𝑡)𝑟 = 𝑠𝑟 | 𝑡𝑟
∈𝑟=𝑟 ∈ es el elemento idéntico para la concatenación
𝑟 ∈= 𝑟
𝑟 ∗ = (𝑟| ∈)∗ * es idempotente
𝑟 ∗∗ = 𝑟 ∗
DEFINICIONES REGULARES

Es conveniente etiquetar cada expresión regular con un nombre. Dado un alfabeto Σ , una
definición regular es una secuencia de definiciones de la forma:
𝑑1 → 𝑟1
𝑑2 → 𝑟2
.
.
.
𝑑𝑛 → 𝑟𝑛

-9- Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

donde cada 𝑑𝑖 es un nombre distinto y cada 𝑟𝑖 es una expresión regular de símbolos sobre Σ ∪
{𝑑1 , 𝑑2 , … , 𝑑𝑖−1 }. No se vale la recursión.

Ej 1:  = {A, B, …, Z, a, b, … ,z, 0,1, …, 9}

𝒍𝒆𝒕𝒓𝒂 → 𝐴|𝐵| … |𝑍|𝑎|𝑏| … |𝑧

𝒅𝒊𝒈𝒊𝒕𝒐 → 0|1| … |9
𝒊𝒅 → 𝒍𝒆𝒕𝒓𝒂(𝒍𝒆𝒕𝒓𝒂|𝒅𝒊𝒈𝒊𝒕𝒐)∗

Ej 2:  = {0,1, …, 9, +, -, ., E}

𝒅𝒊𝒈𝒊𝒕𝒐 → 0|1| … |9
𝒅𝒊𝒈𝒊𝒕𝒐𝒔 → 𝒅𝒊𝒈𝒊𝒕𝒐 𝒅𝒊𝒈𝒊𝒕𝒐∗
𝒇𝒓𝒂𝒄𝒄𝒊𝒐𝒏 → . 𝒅𝒊𝒈𝒊𝒕𝒐𝒔| ∈
𝒆𝒙𝒑𝒐𝒏𝒆𝒏𝒕𝒆 → 𝐸(+| − |∈) 𝒅𝒊𝒈𝒊𝒕𝒐𝒔 | ∈
𝒏𝒖𝒎𝒆𝒓𝒐 → 𝒅𝒊𝒈𝒊𝒕𝒐𝒔 𝒇𝒓𝒂𝒄𝒄𝒊𝒐𝒏 𝒆𝒙𝒑𝒐𝒏𝒆𝒏𝒕𝒆

Reduciendo la notación

1.- Utilizando la cerradura positiva, dada (𝑟)+ quiere decir "una o más veces", se genera (𝐿(𝑟))+ y
entonces 𝑟𝑟 ∗ = 𝑟 + y 𝑟 ∗ = 𝑟 + | ∈.

2.- Utilizando el signo (-), dada (𝑟)− , quiere decir "cero o una vez", entonces (𝑟)− genera 𝐿(𝑟) ∪ {∈} y
𝑟 − = 𝑟| ∈.

3.- Utilizando paréntesis cuadrados para clases de caracteres se tiene 𝑎|𝑏|𝑐 = [𝑎𝑏𝑐] y 𝐴|𝐵|𝐶| … |𝑍 como
[𝐴 − 𝑍] , y se pueden expresar expresiones regulares como [𝐴 − 𝑍𝑎 − 𝑧][𝐴 − 𝑍𝑎 − 𝑧0 − 9]∗ =
𝒍𝒆𝒕𝒓𝒂(𝒍𝒆𝒕𝒓𝒂|𝒅𝒊𝒈𝒊𝒕𝒐)∗

Así la definición regular anterior es:

𝒅𝒊𝒈𝒊𝒕𝒐 → 0|1| … |9
𝒅𝒊𝒈𝒊𝒕𝒐𝒔 → 𝒅𝒊𝒈𝒊𝒕𝒐+
𝒇𝒓𝒂𝒄𝒄𝒊𝒐𝒏 → (. 𝒅𝒊𝒈𝒊𝒕𝒐)−
𝒆𝒙𝒑𝒐𝒏𝒆𝒏𝒕𝒆 → (𝐸(+|−)− 𝒅𝒊𝒈𝒊𝒕𝒐𝒔)−
𝒏𝒖𝒎𝒆𝒓𝒐 → 𝒅𝒊𝒈𝒊𝒕𝒐𝒔 𝒇𝒓𝒂𝒄𝒄𝒊𝒐𝒏 𝒆𝒙𝒑𝒐𝒏𝒆𝒏𝒕𝒆

CONJUNTOS NO REGULARES

Existen algunos conjuntos que no pueden ser expresados con una "expresión regular", pero sí con
una gramática de contexto libre. No obstante, existen algunos conjuntos que no pueden ser
expresados ni aún con una gramática de contexto libre.
AUTOMATAS NO-DETERMINISTICOS

Un autómata finito es un diagrama que permitir saber si una cadena es o no aceptada por una
expresión regular. Un NFA es un modelo matemático que consiste de:

1.- Un conjunto S de estados.

2.- Un conjunto de símbolos de entrada Σ.
3.- La función de transición " mueve" que mapea pares estado-símbolos hacia un conjunto de
estados.
4.- Un estado de inicio 𝑆0 .

- 10 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

5.- Un conjunto de estados de aceptación o finales F.

Diagramáticamente se ve como un grato dirigido. Ej:

A={a,b} Expresión: (𝑎|𝑏)∗ 𝑎𝑏𝑏

Estados del NFA={0,1,2,3}, 𝑆0 = 0 F={3}

0 a 1 b 2 b 3

El autómata puede ser representado fácilmente en una computadora como una matriz.

SIMBOLOS
ESTADOS
a b
0 {0,1} {0}
1 - {2}
2 - {3}

Por ejemplo, el NFA acepta aabb como:

0 a 0 a 1 b 2 b 3

Se debe llegar al estado de aceptación.

Ejemplo: para 𝑎𝑎 ∗ |𝑏𝑏 ∗

1 a 2



3 b 4

b
AUTOMATAS FINITOS DETERMINISTICOS

Un DFA es un caso particular de un NFA en el cual:

1.- No hay estados con una∈ −𝑡𝑟𝑎𝑛𝑠𝑖𝑐𝑖ó𝑛.

2.- Para cada estado S y cada símbolo "a" hay cuando más una flecha saliendo de S etiquetada

- 11 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

por "a".

Si se elabora una matriz para un DFA, ésta contiene exactamente como elementos un estado.

Ejemplo:

(𝑎|𝑏)∗ 𝑎𝑏𝑏

b
b

0 a 1 b 2 b 3

a a
a

ALGORITMO PARA SIMULAR UN DFA

Se recibe una cadena de entrada y al final la marca de fin de archivo, se inicia con el estado 0, y
se usa la función mueve(S,C), que devuelve el siguiente estado moviéndose a partir del estado S a
través de C. Además se tiene un conjunto F de estados de aceptación.

Comienza
S=So
C= lee_car()
Mientras C<> ┴
S=mueve(S,C)
C = lee_car()
Fin mientras
Si (S  F) entonces
Aceptada
otro
Rechazada
Fin si
termina

CONVERSION DE UN NFA EN UN DFA

El motivo de la conversión es el siguiente: En un NFA existen muchos caminos diferentes para

hacer una transición de un símbolo x de entrada, y es probable que seleccionando un camino se logre
reconocer una cadena de entrada, pero también es probable que se seleccione justamente el camino
equivocado. Como saber cuál es el correcto?, pues solamente recorriendo todas las transiciones
posibles.

Si se intenta recorrer todas las transiciones posibles, puede crecer la búsqueda exponencialmente
y consecuentemente ser un proceso muy lento.

En contraparte, un DFA no permite mas que un solo camino, lo cual es mucho más eficiente para
implementarse en un programa, pero el problema radica en que es muy difícil construir un DFA de

- 12 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

primera intención. A continuación se presenta un algoritmo que convierte un NFA (que es sencillo
elaborar) en un DFA. No obstante este algoritmo de conversión puede crecer exponencialmente en
tiempo de ejecución.

Antes de mostrar el algoritmo se explican algunas funciones requisito para el algoritmo:

A).- 𝑚𝑢𝑒𝑣𝑒(𝑆0 , 𝑎): Indica el nuevo estado de transición de un estado 𝑆0 a través de un carácter a

Ejemplo:

a a
c
0 a 1 b 2 3
b
c

mueve(0,a) = 1 mueve(1,a) =1
mueve(1 ,b) = 2 etc.
B).- 𝑚𝑢𝑒𝑣𝑒(𝑇, 𝑎): Donde T es un conjunto de estados, indica las transiciones sobre cada elemento del
conjunto.

Considerando el diagrama anterior. Ejemplo:

T={0,1,2}
mueve(T,a) = { 1,2 }
mueve(T,b) = { 2,3 }

C).- ∈ − 𝑐𝑒𝑟𝑟𝑎𝑑𝑢𝑟𝑎(𝑆): Estados de un NFA que pueden ser visitados al recorrer el NFA a través de ∈-
transiciones con comenzando por el estado S inclusive.

Ejemplo:

∈ − 𝑐𝑒𝑟𝑟𝑎𝑑𝑢𝑟𝑎(5) = { 1,2,4,5,6,7 }

C).- ∈ − 𝑐𝑒𝑟𝑟𝑎𝑑𝑢𝑟𝑎(𝑇): Donde T es un conjunto de estados. Es aplicar la ∈ − 𝑐𝑒𝑟𝑟𝑎𝑑𝑢𝑟𝑎 para cada uno

- 13 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

de los elementos de T.

∈ − 𝑐𝑒𝑟𝑟𝑎𝑑𝑢𝑟𝑎({3,8}) = { 1,2,3,4,6,7,8 }

ALGORITMO

D: Conjunto de conjuntos de estados

AUTO: Matriz para representar el DFA obtenido
So: Estado inicial del NFA

comienza
D contiene a -cerradura(So) sin marcar
Mientras haya un T sin marcar en D
Marcar T
Para cada símbolo a   hacer
U=-cerradura(mueve(T,a))
Si U no esta en D entonces
añade U a D sin marcar
Fin si
AUTO[T,a]=U
Fin para
Fin mientras
termina

CONSTRUCCION DE UN NFA A PARTIR DE UNA EXPRESION REGULAR

A continuación se presenta un algoritmo para construir un NFA a partir de una expresión regular
considerando la concatenación, la alternación y la cerradura.
ALGORITMO

Entrada.- Expresión regular "r" sobre un alfabeto .

Salida.- NFA aceptando L(r).
Método.- Primero se construyen NFA's muy sencillos para cada símbolo en , y para  como se
muestra en (1) y (2).

Posteriormente, usando la estructura sintáctica de la expresión regular "r", se van combinando los
incisos de (3). Los NFA's obtenidos tienen exactamente un estado inicial (al que no entran flechas) y
un estado final (del que no salen flechas).

1.- Para  construir el NFA:


inicio i f

2.- Por cada a en  construir el NFA:

a
inicio i f

3.- Suponga que N(s) y N(t) son NFA's para las expresiones "s" y "t" respectivamente.

- 14 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

a).- Para la expresión regular s|t se construye el NFA N(s|t) como:

N(s)

 

inicio i f

 N(t) 

b).- Para la expresión regular "st" se construye el NFA N(st) como:

N(s) N(t)
inicio i f

c).- Para la expresión regular 𝑠 ∗ se construye el NFA 𝑁(𝑠 ∗ ) como:

 N(s) 
inicio i f

d).- Para expresiones en paréntesis como (s) usar N(s).

ALGORITMO PARA SIMULAR UN NFA

El siguiente algoritmo sirve para simular un NFA, devuelve un "si" si una cadena X es aceptada por
el autómata:

comienza
S=-cerradura(So)
a= lee_car()
MIENTRAS a <> ┴
S=-cerradura(mueve(S,a))
a=lee_car()
FIN MIENTRAS
SI SF <> {} ENTONCES

- 15 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

aceptada
OTRO
no aceptada
FINSI
termina

Se puede pensar que en un archivo de entrada, los identificadores van separados por espacios o
tabs o newlines. Entonces se puede hacer una definición regular para este propósito:

𝒅𝒆𝒍𝒊𝒎𝒊𝒕𝒂𝒅𝒐𝒓 → 𝒆𝒔𝒑𝒂𝒄𝒊𝒐|𝒕𝒂𝒃|𝒏𝒆𝒘𝒍𝒊𝒏𝒆
𝒔𝒆𝒑𝒂𝒓𝒂𝒅𝒐𝒓 → 𝒅𝒆𝒍𝒊𝒎𝒊𝒕𝒂𝒅𝒐𝒓∗

Con lo anterior, si el analizador lexicográfico encuentra un separador, no hay que hacer nada. El
objetivo de un analizador lexicográfico es analizar la entrada y devolver al parser un par, el token
asociado y el atributo correspondiente al token, por ejemplo : Considerando LT, GE, GT, EQ como
constantes

EXPRESION TOKEN ATRIBUTO

REGULAR
separador - -
if if -
then then -
else else -
id id Apuntador a la tabla de símbolos
num num Apuntador a la tabla de símbolos
< op_rel LT
> op_rel GT
>= op_rel GE
= op_rel EQ

DIAGRAMAS DE TRANSICION

Un diagrama de transición es una gráfica que describe las acciones seguidas por un analizador
lexicográfico cuando un token es encontrado, los diagramas de transición se forman con flechas
etiquetadas con los caracteres que se deben asociar a la entrada, conectados a círculos llamados
estados para indicar la transición de un estado a otro por medio de la flecha etiquetada.

El diagrama cuenta con una flecha para el estado inicial y un círculo doble indica el estado final.

Ej: para operadores relacionales

- 16 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

0 < 1 = 2 return(op_rel, LE)

> 3 return(op_rel, NE)

= otro 4 * return(op_rel, LT)

> 5 return(op_rel, EQ)

6 = 7 return(op_rel, GE)

otro 8 * return(op_rel, GT)

El asterisco significa que hay que regresar el apuntador en el buffer (Ap_avance) una posición
para que dicho carácter sea releído y pasado por otro diagrama de transición. Si no se puede hacer la
transición de un estado a otro, y hay más posibilidades, se trata de hacer la transición con la siguiente
posibilidad, y si con ninguna se logra, ha ocurrido un error léxico. Se asume además, que los
diagramas de transición son deterministicos, es decir, entre otras cosas, no se permiten dos o más
flechas saliendo del mismo estado. Cuando se tienen varios diagramas de transición si no se logra
trazar el camino en uno de ellos por medio de la entrada, se pasa al siguiente diagrama, si ya no
existen más diagramas donde buscar ocurre un error léxico:

digito digito digito

9 digito 10 . 11 digito 12 E 13 +o- 14 digito 15 otro 16 *

E digito

return(num)

digito digito

17 digito 18 . 19 digito 20 otro 21 *

retrun(num)

digito

22 digito 23 otro 24 *

- 17 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

retrun(num)

digito

25 letra 26 otro 27 *

letra

Los diagramas equivalen a:

𝒏𝒖𝒎 → 𝒅𝒊𝒈𝒊𝒕𝒐+ ( . 𝒅𝒊𝒈𝒊𝒕𝒐+ )− ( 𝐸(+|−)− 𝒅𝒊𝒈𝒊𝒕𝒐+ )−

𝒊𝒅 → 𝒍𝒆𝒕𝒓𝒂(𝒍𝒆𝒕𝒓𝒂|𝒅𝒊𝒈𝒊𝒕𝒐)∗

Es importante observar en los diagramas para reconocimiento de números que el proceso requiere
en ocasiones del cambio de diagrama para llegar a un estado de aceptación. Por ejemplo, para
reconocer un 12.5 comenzamos con el estado de inicio 9 y se leen 2 dígitos 1 y 2, y posteriormente un
. y luego un 5 quedando en el estado 12, si luego viene otra cosa como un =, no se puede hacer la
transición así que se debe cambiar al diagrama que empieza con 17, y se vuelven a hacer todas las
transacciones de nuevo, al repasar 1, 2, ., 5 se llega al estado 20; luego al leer = se puede llegar al
estado de aceptación 21 con lo que el 12.5 queda reconocido. Por esto, el orden de los diagramas es
importante y es precisamente el mostrado anteriormente, de otra manera el reconocimiento puede
fallar.

En lugar de construir los 3 diagramas para el reconocimiento de números, podemos construir un

único diagrama más robusto agregando más estados de aceptación y renumerando todos los estados
para tener lo siguiente:

digito digito digito

9 digito 10 . 11 digito 12 E 13 +o- 14 digito 15 otro 16 *

E digito

otro 17 * otro 18 *

digito

19 letra 20 otro 21 * return(id)

letra

Un diagrama de transición para eliminar los espacios (tabs, espacios y CR) es:

- 18 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

delim

22 delim 23 otro 27 * return(nosirve)

IMPLEMENTACION DE UN DIAGRAMA DE TRANSICION

Para implementar diagramas de transición se hacen dos procesos fundamentales. Uno para
seleccionar que diagrama utilizar y otro para simular el recorrido a través del diagrama.

El tamaño del programa es proporcional al número de estados en los diagramas de transición,

porque cada estado genera un fragmento de código, si salen dos flechas a más de un estado, se lee el
carácter siguiente, y con éste se selecciona el camino a seguir. Se asume que al leer un carácter del
buffer se recorre automáticamente Ap_avance. Si hay una flecha en el estado actual que se asocie con
el carácter leído, se transfiere el control al siguiente estado indicado por la flecha; si no se asocia con
ninguna flecha, se llama a un proceso que permita seleccionar otro diagrama de transic ión. Este último
proceso se muestra a continuación; utiliza dos variables ESTADO y COMIENZO; ESTADO contiene el
número del estado actual, y COMIENZO contiene el número del estado inicial del diagrama actual. Las
rutinas para el cambio de diagrama y la simulación de los diagramas se basan en los diagramas
mostrados anteriormente y el que sigue para identificadores:

FUNCION lee_car():carácter
carac=car[Ap_avance]
Ap_avance=Ap_avance + 1
RETURN(carac)
FIN FUN

FUNCION diagrama():entero
Ap_avance = Ap_inicio
Caso de
COMIENZ0=0: COMIENZ0=9
COMIENZ0=9: COMIENZ0=19
COMIENZ0=19: COMIENZ0=22
COMIENZ0=22: error()
Fin caso
return(COMIENZO)
FIN FUN

FUNCION TOKEN():cadena
Repite
Caso ESTADO=0
C=lee_car()
Caso C='<'
ESTADO=1
Caso C='='
ESTADO=5
Caso C='>'
ESTADO=6
Otro
ESTADO=diagrama()
Fin caso
Caso ESTADO=1
C=lee_car()
Caso C='='
ESTADO=2

- 19 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

Caso C='>'
ESTADO=3
Otro
ESTADO=4
Fin caso
Caso ESTADO=2
Ap_inicio=Ap_avance
TokenVal='EQ'
return(op_rel)
.
.
.
Caso ESTADO=4
Ap_avance=Ap_avance-1
Ap_inicio=Ap_avance
TokenVal='LT'
return(op_rel)
.
.
.
Caso ESTADO=21
Ap_avance=Ap_avance-1
TokenVal=Anexa_Lex() /* Anexa a taba, devuelve apuntador */
Ap_inicio=Ap_avance
return(id)
.
.
.
Caso ESTADO=27
Ap_avance=Ap_avance-1
ESTADO=0
Fin caso
Fin repite
FIN FUN

Comienza
Ap_inicio=1
Ap_avance=1
escribe("Digitar cadena y al final *")
lee(cad)
Repite
ESTADO=0
COMIENZ0=0
T=TOKEN()
escribe("Token encontrado: ",T)
Ap_inicio=Ap_avance
Hasta(car[Ap_avancej="*")
Termina
ANALISIS LEXICOGRAFICO

En programación se distinguen cuatro elementos fundamentales:

✓ Palabras reservadas (if, while, begin, end, div, mod, etc.).

✓ Operadores (<, :=, ==, >=, +, *, etc.).
✓ Identificadores (variables, constantes, etiquetas, proc., etc.).

- 20 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

✓ Números (enteros, reales, hexadecimales, etc.).

Cuando una secuencia de dígitos es encontrada en el analizador léxico, se pasa el token (#, num,
etc.) al parser; aunque en alguna parte se debe almacenar el valor del numero en cuestión. Por
ejemplo, en parejas:

19 + 20 + 21

<#,19> <+,> <#,20> <+,> <#,21>

De la misma manera, cuando se tienen identificadores, al parser se le pasa un token como "id"
simplemente, aunque el lexema y sus atributos son almacenados en alguna parte. Así

CONT = CONT + SUMA id= id + id

Se debe conocer si un lexema ya ha sido encontrado con anterioridad, esto es viable con una
tabla de símbolos, donde se almacena el lexema, un apuntador y algunos Atributos asociados Al
lexema. La forma de distinguir entre identificadores y palabras reservadas, es fácil, ya que las palabras
reservadas son conocidas con anterioridad, normalmente se almacenan en alguna otra parte. En
muchas ocasiones el analizador lexicográfico debe adelantarse a leer algunos caracteres más ( >= )
para decidir que es, y hay que regresarse en ocasiones porque se está tomando un carácter de más,
pero del siguiente token.

El analizador lexicográfico se puede integrar al parser como un simple procedimiento.

Una forma útil de implementar una tabla de símbolos es como sigue:

TABLA DE SIMBOLOS

Ap Token Atributos
1 id
2 mod
3 num
4 div
5 id

c o n t /0 m o d /0 3 . 5 /0
Arreglo de lexemas

Lo conveniente en el análisis lexicográfico es la eliminación de los espacios, los tabuladores, y la

líneas en blanco, ya que si se eliminan, no tendrán que ser analizadas por el parser. Es posible
considerarlos en la gramática, pero resulta problemático.

- 21 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

El caso de los números puede ser implementado en la gramática, haciendo producciones para la
sintaxis de un número, pero se deja esta tarea al analizador léxico. Este se encarga de recolectar
secuencias de dígitos; de esta manera son tratados como un simple token en al analizador sintáctico.
ANALISIS SINTACTICO

Se presenta una GRAMATICA DE CONTEXTO LIBRE o BNF (Backus-Naur Form).

GRAMATICA DE CONTEXTO LIBRE.

1.- Conjunto de terminales

2.- Conjunto de no terminales
3.- Producciones
4.- Símbolo inicial de la gramática.

1) LISTA → LISTA + DIGITO

2) LISTA → LISTA - DIGITO
3) LISTA → DIGITO
4) DIGITO → 0|1|2|3|4|5|6|7|8|9

Así, 9-5+2

a.- 9 es una lista, y es un dígito por 3)

b.- 9-5 es una lista por 2), 9 es lista y 5 dígito

c.- 9-5+2 es lista por 1) 9-5 es lista y2 dígito

LISTA

LISTA + DIGITO

LISTA - DIGITO 2

DIGITO 5

Existe la notación de  para indicar cadenas vacías.

ARBOL DE PARSER

Dada una producción X → A B C

- 22 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

raiz (no terminal)

A B C

Hijos(no terminal), hojas(terminal)

Un ARBOL DE PARSER se forma por:

1.- La raíz es el símbolo inicial de la gramática.

2.- Cada hoja es etiquetada por un token o por .
3.- Cada hijo ( nodo ) es etiquetado por un no terminal.
4.- Consecuentemente, un árbol de raíz A con 𝑋1 𝑋2 … 𝑋𝑛 como hijos, sean terminales
o no terminales, es una producción 𝐴 → 𝑋1 𝑋2 … 𝑋𝑛 .

En el caso particular A→, el árbol tiene un solo hijo llamado .

Una gramática es ambigua si tiene dos o más árboles distintos de parser por ejemplo:

EXP → EXP + EXP Para 9-5+2 se puede expandir

EXP → EXP - EXP por la derecha o por la izquierda.
EXP → 0|1|2|3|4|5|6|7|8|9

Expansión por derecha ó izquierda.

EXP EXP

EXP + EXP EXP - EXP

EXP - EXP 2 9 EXP + EXP

9 5 5 2

En contraparte, la siguiente gramática produce el mismo lenguaje pero no es ambigua.

LISTA → DIGITO + LISTA

LISTA → DIGITO - LISTA
LISTA → DIGITO
DIGITO → 0|1|2|3|4|5|6|7|8|9

- 23 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

El orden natural es que ( + y -) y (* y / ) sean asociados por la izquierda, es decir, al expandir el

árbol con la gramática anterior para 9 - 5 + 2 quedaría:

LISTA

DIGITO - LISTA

9 DIGITO + LISTA

5 DIGITO

Perser es el proceso mediante el cual se determina si un string de tokens puede ser generado por
una gramática. Existen métodos top-down y bottom up.

Para hacer la expansión de un árbol de sintaxis e ir asociado con el árbol una cadena de entrada,
se comienza con el símbolo inicial de la gramática, y se toma el primer token de la entrada y se busca
la producción que derive el no-terminal y que comience con el token de entrada. Con dicha producción
se construyen las ramas para el nodo. En caso de que uno de los hijos se asocie con uno de los
símbolos de entrada, se recorre el árbol de izquierda a derecha hacia el siguiente hijo y también se
toma el siguiente token de la entrada.
TIPO → SIMPLE | id | array [SIMPLE] of TIPO
SIMPLE → integer | char | #..#

Probar la entrada : array [ # .. #] of integer

En este caso se puede presentar "backtrack", porque se seleccione una producción incorrecta.
Existen m,todos en los cuales no ocurre el backtrack, estos son los parsers predictivos.

En el análisis sintáctico es recomendable utilizar un modelo matemático conocido como gram ática
de contexto libre (BNF), ya que:

Una BNF expresa una estructura sintáctica clara.

✓ Con algunas clases de gramáticas es muy fácil construir un programa metódico que revise
sintaxis, además que la BDF muestra posibles ambigüedades en el diseño de la gramática
que podrían no ser detectadas sin su elaboración.
✓ Un diseño adecuado por medio de una gramática permite una fácil translación a código
intermedio u objeto.
✓ Es más sencillo hacer correcciones o ampliar el lenguaje.

FRONTERA PARSER-LEXICO

En la construcción de un compilador es recomendable utilizar una gramática de contexto libre para

especificar sintaxis y una definición regular para la estructura de tokens, es decir, el análisis léxico, así
considere la gramática:

AFIRMACION → if EXP then AFIRMACION

AFIRMACION → IF EXP then AFIRMACION else AFIRMACION

- 24 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

AFIRMACION → 
EXP → TERMINO op_rel TERMINO | TERMINO
TERMINO → id | num

Para los terminales if, then, else, op_rel, id, num construimos una definición regular como:

𝒊𝒇 → 𝑖𝑓
𝒕𝒉𝒆𝒏 → 𝑡ℎ𝑒𝑛
𝒆𝒍𝒔𝒆 → 𝑒𝑙𝑠𝑒
𝒐𝒑_𝒓𝒆𝒍 → < | <= | > | >= | = | <>
𝒍𝒆𝒕𝒓𝒂 → 𝐴|𝐵| … |𝐶|𝑎|𝑏| … |𝑧
𝒅𝒊𝒈𝒊𝒕𝒐 → 0|1| … |9
𝒊𝒅 → 𝒍𝒆𝒕𝒓𝒂 (𝒍𝒆𝒕𝒓𝒂|𝒅𝒊𝒈𝒊𝒕𝒐)∗
𝒏𝒖𝒎 → 𝒅𝒊𝒈𝒊𝒕𝒐+ ( . 𝒅𝒊𝒈𝒊𝒕𝒐+ )− (𝐸(+|−)− 𝒅𝒊𝒈𝒊𝒕𝒐+ )−

Peticion

Programa ANALIZADOR ANALIZADOR RESTO DEL

Fuente LEXICO SINTACTICO Arbol de Parser FRONT END

Token

TABLA DE
SIMBOLOS

Existen métodos generales para procesos de parser, pero son demasiado ineficientes, por lo cual
se prefieren métodos como el top-down y el bottom-up El primero construye árboles sintácticos de la
raíz a las hojas y el segundo de las hojas a la raíz. En ambos casos se revisa la entrada de izquierda a
derecha tomando un símbolo a la vez.

Los parsers top-down y bottom-up más eficientes trabajan sobre subclases de gramáticas como
las LL o las LR, y con estas gramáticas se pueden implementar prácticamente todos los lenguajes
actuales de programación.
PARSER RECURSIVO-DESCENDENTE

Es un método de parser top-down. Este m,todo asocia un procedimiento, o una función por cada
elemento no terminal de la gramática. El procedimiento seleccionado esta en función del símbolo de
entrada. La ejecución de los procedimientos durante la ejecución, implícitamente define el árbol de
parser para la entrada. Se añade un procedimiento para la asociación de los tokens de entrada con las
hojas del árbol.

Ejemplo:
TIPO → SIMPLE | ^id | array [SIMPLE] of TIPO
SIMPLE → integer | char | num . . num

PROC asocia(token)
comienza
Si CABEZA = token entonces
CABEZA = SIG_CABEZA
otro
Error()

- 25 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

Fin si
termina

PROC tipo()
comienza
CASO DE
CABEZA ={integer o char o #}
simple()
CABEZA = ^
asocia(^)
asocia(id)
CABEZA = array
asocia(array)
asocia([)
simple()
asocia(])
asocia(of)
tipo()
OTRO
Error()
FIN CASO
Termina

PROC simple()
comienza
CASO DE
CABEZA = integer
asocia(integer)
CABEZA = char
asocia(char)
CABEZA = num
asocia(num)
asocia(.)
asocia(.)
asocia(num)
OTRO
Error()
FIN CASO
termina

Este parser utiliza información sobre los primeros símbolos de la parte derecha de las
producciones; esto es, sobre los conjuntos FIRST.

Así

FIRST(simple) = {integer,char,#}

FIRST(^id) = {^}

FIRST(array [SIMPLE] of TIPO) = {array}

Cuando se tienen producciones A →  y A → , el parser recursivo descendente requiere que

FIRST()<>FIRST() para poder decidir por medio del símbolo de entrada que producción tomar, si
CABEZA esta en FIRST( ) se toma A → , si CABEZA esta en FIRST( ) se toma A → . Si la gramática
no está diseñada como se indica, habrá que factorizarla.

En caso de que se tengan -producciones, se deben tratar con cuidado. El parser recursivo

- 26 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

descendente usa una -producción cuando no existe el símbolo de entrada en el FIRST de la parte
derecha de la producción en cuestión.
FACTORIZACION DE UNA GRAMATICA

Si se tienen producciones de la forma

A → a | a

el parser no podrá decidir que producción usar porque ambas comienzan en la parte derecha con
"a". Esto se soluciona reemplazando las producciones por

A → aA'
A' →  | 

Esta regla se puede generalizar como sigue:

Para cada no terminal A se encuentra el prefijo  más grande común a dos o más producciones y
se reemplazan las A-producciones 𝐴 → 𝛼𝛽1 | 𝛼𝛽2 | … |𝛼𝛽𝑛 por

𝐴 → 𝛼𝐴′ NOTA:  puede ser 

𝐴′ → 𝛽1 |𝛽2 | … |𝛽𝑛

Para el diseño de un parser recursivo descendente se requiere:

1.- Una gramática

2.- Eliminar recursión izquierda y factorizarla.

3. - Además:

- El parser decide qué producción usar por medio del token de entrada. Se selecciona la
producción que contiene el token de entrada en el FIRST() donde  es la parte derecha de la
producción. Si hay un conflicto con los lados derechos y el token de entrada, no se puede utilizar el
método.

- El método usa un procedimiento por cada no-terminal, simulando la parte derecha de la

producción. Un no-terminal es la llamada a un procedimiento (derivación de una producción) y un
terminal llama a un proceso de asociación entre él y el símbolo de entrada, si no se puede asociar,
ocurre un error. En caso de que el no-terminal derive a , si el token de entrada no puede usar
ninguna de las partes derechas, se selecciona justamente la producción de  (es decir, no se debe
hacer nada, ya que si existe error será detectado posteriormente).
RECURSIVIDAD IZQUIERDA

Una gramática no debe ser recursiva izquierda para construir un parser recursivo descendente.
Por ejemplo:

A → A
A→ 

Si se usan producciones corno esta, el proceso en computadora entra a un loop sin fin. El proceso
de eliminación es sencillo y se trata de eliminar la recursividad izquierda convirtiéndola a recursividad
derecha:
A → A'

- 27 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

A' → A' | 

Esta regla se puede generalizar como:

Se agrupan todas las producciones de A en la forma:

𝐴 → 𝐴𝛼1 |𝐴𝛼2 | … |𝐴𝛼𝑛 |𝛽1 |𝛽2 | … |𝛽𝑚

donde ninguna  i comienza con A. Después se sustituyen las producciones de A por:

𝐴 → 𝛽1 𝐴′ |𝛽2 𝐴′ | … |𝛽𝑚 𝐴′

𝐴′ → 𝛼1 𝐴′ |𝛼2 𝐴′ | … |𝛼𝑛 𝐴′ | ∈

Existen casos en que la recursión no es inmediata y hay que aplicar otro proceso.
CALCULO DEL CONJUNTO FIRST

Aplíquense las 3 reglas siguientes para todos los símbolos gramaticales (terminales y no-
terminales), hasta que no se puedan añadir más elementos al conjunto.

1.- Si X es un terminal, entonces FIRST(X ) es {X }.

2.- Si X→ es una producción, añadase  al FIRST(X ).

3.- Si X es un no-terminal y además 𝑋 → 𝑌1 𝑌2 𝑌3 … 𝑌𝑘 es una producción, entonces añadase al

FIRST(X ) el FIRST(𝑌1 ) excepto . Si FIRST(𝑌1 ) contiene a  entonces también debe añadirse
FIRST(𝑌2 ) a FIRST(X ) excepto . Si FIRST(𝑌1 ) y FIRST(𝑌2 ) contiene a , deber añadirse
FIRST(𝑌3 ) a FIRST(X ) excepto , y así sucesivamente. Y por último, si ocurre que para toda i
el FIRST(𝑌𝑖 ) contiene a , entonces deber incluirse una sola vez  en FIRST(X).

Una vez comprendidas las reglas anteriores, también se puede calcular el First de cualquier
cadena 𝑋1 𝑋2 𝑋3 … 𝑋𝑛 . Este proceso es similar a la regla 3 mencionada arriba.

Se añade al FIRST(𝑋1 𝑋2 𝑋3 … 𝑋𝑛 ) el FIRST(𝑋1 ) excepto . Si FIRST(𝑋1 ) contiene a  entonces

también debe añadirse FIRST(𝑋2 ) a FIRST(𝑋1 𝑋2 𝑋3 … 𝑋𝑛 ) excepto . Si FIRST(𝑋1 ) y también FIRST(𝑋2 )
contiene a , deber añadirse FIRST(𝑋3 ) a FIRST(𝑋1 𝑋2 𝑋3 … 𝑋𝑛 ) excepto , y así sucesivamente. Y por
último, si ocurre que para i=1,2,...,n el FIRST(𝑋𝑛 ) contiene a , entonces deber incluirse una sola vez 
en FIRST(𝑋1 𝑋2 𝑋3 … 𝑋𝑛 ).
PARSERS CON TABLAS PREDICTIVAS

Estos métodos tienen la ventaja de permitir la generalidad, es decir, se pueden construir

generadores de revisores sintácticos (parsers) en función de una gramática de contexto libre. El
esquema general de funcionamiento es

- 28 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

Entrada a * C + ( 3 * x ) ┴

Pila

X ANALIZADOR Emite un
Y SINTACTICO diagnóstico
┴

TABLA
PREDICTIVA

(Selecciona la
producción
adecuada)

La tabla predictiva es un arreglo matricial que permite seleccionar la produc ción adecuada para ir
asociando los tokens de la cadena de entrada por medio de la pila.

Para la construcción de los parsers con tabla predictiva, es necesario la elaboración de otros
conjuntos, los FOLLOW's.

CALCULO DE CONJUNTOS FOLLOW

Para construir el conjunto FOLLOW( A) para todos los no-terminales A, se aplican las reglas
siguientes hasta que no se pueda añadir nada más a los conjuntos FOLLOW:

1.- Añádase ┴ al FOLLOW(S ) dónde S es el símbolo inicial de la gramática.

2.- Si hay una producción A → B, FOLLOW(B ) contiene a FIRST() excepto .

3.- Si hay una producción A → B o una producción A → B donde FIRST() contenga ;
todo lo que está en FOLLOW(A ) se añade al FOLLOW(B ).
GRAMATICAS LL(1)

Las gramáticas LL(1) son un subconjunto de las gramáticas de contexto libre que cumplen con
que dadas dos producciones distintas de G como A →  | :

1.- Para ningún terminal "a"  y  derivan a la vez cadenas que comienzan con "a".

2.- A lo sumo una de  y  puede derivar .

3.- Si *,  no deriva ninguna cadena que comience con un terminal en el FOLLOW( A ).

La primera L quiere decir "left to right", recorrido de la cadena de izquier da a derecha, y la

segunda L por leftmost derivation", derivaciones por la izquierda. El 1, es porque se utiliza el análisis
de un solo símbolo de entrada a la vez para las decisiones del parser.

Para este tipo de gramáticas se puede construir una tabla predictiva LL(1) con la cual se puede
seleccionar la producción adecuada durante la revisión de una cadena de entrada. La tabla es un

- 29 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

arreglo matricial de 𝑚 × 𝑛 donde los renglones se encabezan con los no-terminales y las columnas con
los terminales inclusive ┴, o viceversa.
CONSTRUCCION DE UNA TABLA LL(1)

Para cada producción A →  de la gramática hacer:

1.- Por cada terminal "a" en el FIRST() añádase A →  a M[A,a].

2.- Si  está en FIRST(), añádase A →  a M[A,b] para cada terminal "b" del FOLLOW( A ). Si
 está en FIRST() y ┴ está en FOLLOW(A ), añádase A →  a M[A,┴].

3. Cada entrada no definida en la tabla es error.

PRUEBA DE UNA CADENA DE ENTRADA CON EL PARSER LL(1)

El parser funciona con una pila, que en un principio contiene en el fondo el símbolo terminal de la
gramática(Ʇ), y en el tope el símbolo inicial de la gramática. La cadena a ser revisada debe tener hasta
el final el símbolo terminal de la gramática. El parser toma el elemento X del tope de la pila, y un
elemento "a" de la cadena a ser revisada, con estos dos elementos el parser decide que acción realizar,
a saber, hay cuatro posibilidades :

1.- Si X=a=┴ el análisis ha terminado y quiere decir que la cadena ha sido revisada con éxito.

2.- Si X=a<>┴ el parser saca a X de la pila y lee el siguiente token de la cadena de entrada.

3.- Si X<>a y X es un terminal hay error.

4.- Si X es un no terminal, se consulta el elemento M[X,a] de la tabla predictiva, es te elemento de

la tabla ser una producción o un error. Si la entrada de la tabla es una producción, por ejemplo,
M[X,a]=X → A + C, se sustituye X por la parte derecha de la producción en orden inverso C + A, de tal
modo que quede A en el tope de la pila. Si M[X,a]=error, el parser llama a una rutina de error.

Pseudocódigo:

a=lee_token()
Repite
pop(X)
Si(a=┴ y X=┴) entonces
Aceptada
Otro
Si(X es terminal) entonces
Si(X=a) entonces
a= lee_token()
otro
Error()
Fin si
otro
Si(M[X,a]=X→Y1 Y2 ... Yk) entonces
Para i= k hasta 1
Push (Yi)
Finpara
otro
Error()
Finsi

- 30 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

Finsi
Hasta (X=┴)

NOTA: Por facilidad de manejo, en la tabla predictiva se guarda con frecuencia solamente un
número que indica la producción por la que hay que reducir en la pila.
RECUPERACION DE ERRORES EN PARSERS LL(1)

Una técnica que pudiera ser útil para la recuperación de los errores en este método, es hacer lo
siguiente:

Se agregan a la tabla las entradas M[A,a]=sinc (sincronización) donde "a" son los elementos de
FOLLOW(A). Si existe colisión con una producción, se prefiere (obviamente) la producción.

La forma de utilizar la tabla es, si M[A,a]=sinc se saca el no-terminal del tope de la pila y se
continúa con el análisis. Si M[A,a] está en blanco, el parser se salta el token de entrada y continua con
el análisis. Utilizando este método hay posibilidad de que si se detecta un error, se ignore (previa
indicación de que ha ocurrido un error), y pueda seguir la revisión. La técnica anterior es heurística,
por lo cual puede variar dependiendo de la gramática, además debemos tener cuidado en que la
técnica no entre a un ciclo sin fin.

Quizás la técnica puede mejorarse si se hace un análisis más a conciencia de los posibles errores
que pueden ocurrir, y con esto, colocar en la tabla en lugar de la palabra "si nc" o dejarla en blanco, la
llamada a un procedimiento específico para recuperar ese error particular y hacer la indicación.
ANALIZADORES SINTACTICOS LR

Otra técnica para la revisión sintáctica, son los analizadores LR que viene del inglés "L -left to
right" que es el recorrido de la cadena de entrada de izquierda a derecha, y la "R-rightmost derivation"
que son derivaciones por la derecha, ya que en este método se parte de las hojas del árbol para llegar
a la raíz (al inverso del LL(1)), y el 1 porque se utiliza un sólo símbolo de entrada a la vez para to mar
las decisiones del parser.

Estos analizadores sintácticos requieren de mayor trabajo y mayor espacio para su

funcionamiento, no obstante, aceptan una gama más amplia de gramáticas. Se verán tres tipos del
método LR.

El esquema de funcionamiento de los parsers LR es el siguiente : Entrada a*C+(3*x)┴:

- 31 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

Entrada a * C + ( 3 * x ) ┴

Pila

Símbolo gramatical Em
Xm ANALIZADOR Emite un
Em-1 SINTACTICO diagnóstico
Xm-1
.
. TABLA LR
Estados .
ACCIO-
E1 GOTO's
NES
X1
E0

La pila contiene las cadenas de elementos intercalados, los 𝑋1 , 𝑋2 , … , 𝑋𝑚 son símbolos gramaticales
(terminales o no-terminales), y los 𝐸0 , 𝐸1 , … , 𝐸𝑚 son símbolos llamados estados.

Como se muestra en la figura la tabla predictiva está formada por dos partes, la de acciones, y la
de goto's que en realidad son transiciones de un DFA que construyen los métodos LR.

La pila se maneja diferente al método LL(1), en un principio contiene en el fondo a 𝐸0 (el estado 0
del DFA), y la cadena de entrada debe tener al final ┴.

Las tres acciones que marca la tabla predictiva son:

1. Shift(𝐸𝑖 ).- Introducción de i en la pila para el estado 𝐸𝑖 .

2. Reduce(j ).- Reducción en la pila por la producción número j.

3. Goto(𝐸𝑖 ).- Transición del DFA en la pila hacia el estado i.

NOTA: Por sencillez, se abrevia la notación como: Shift(𝐸𝑖 )= 𝑆𝑖 , Reduce( j )= 𝑅𝑗 , Goto(𝐸𝑖 )= 𝐺𝑖

La tabla es un arreglo matricial, cuyos renglones son los estados 𝐸1 , 𝐸2 , … , 𝐸𝑚 y cuyas columnas
son el conjunto de elementos terminales inclusive ┴, y elementos no terminales.

El parser decide que hacer tomando en cuenta el siguiente esquema de trabajo:

La pila contiene la configuración

𝐸0 𝑋1 𝐸1 𝑋2 𝐸2 … 𝑋𝑛 𝐸𝑛

Donde el fondo es 𝐸0 y el tope es 𝐸𝑛 .

Sea a el símbolo leído de la cadena de entrada, y sea 𝐸𝑖 el estado en el tope de la pila

1. Si M[𝐸𝑖 , a]= 𝑆𝑗 se introduce a en la pila y después se introduce el nuevo estado j dado 𝑆𝑗 .

2. Si M[𝐸𝑖 , a]= 𝑅𝑗 , la producción j tiene la forma A → , y r es la longitud de  denotadoa como

r=||. El parser saca de la pila 2r elementos quedando en el tope algún estado 𝐸𝑘 , se introduce
en la pila A y se introduce después el nuevo estado p, donde M[𝐸𝑘 , A]= 𝐺𝑝 .

- 32 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

3. Si M[𝐸𝑖 , a]= Aceptar, la revisión ha concluido con éxito.

4. Si la entrada M[𝐸𝑖 , a], está vacía, ha ocurrido un error.

Pseudocódigo:

a=lee_token()
Repite
S=Tope de la pila
Si M[S,a]=Ac entonces
aceptada()
otro
Si M[S,a]=Si entonces
push(a)
push(i)
a=lee_token()
otro
Si M[S,a]=Rj (Rj=A→) entonces
Para k=1 hasta 2*||
pop(e)
Fin para
push(A)
Si M[e,A]=vacio entonces
error()
otro
push(M[e,A])
Finsi
otro
error()
Finsi
Finsi
Finsi
Fin repite

El algoritmo para la revisión de un texto de entrada es el mismo para los tres casos de parser LR,
lo único que varía son las tablas.
PARSER SLR(1)

A continuación se muestra el método para construir una tabla SLR(1) (Simple LR). Pero antes de
continuar se deben conocer algunos otros conceptos.
ITEMS LR(0)

Un item LR(0) es una producción con un punto en alguna posición de la parte derecha. Por
ejemplo la producción A → A+A tiene cuatro items LR(0)

[A →  A + A]

[A → A  + A]

[A → A +  A]

[A → A + A ]

Al caso particular A →, genera un solo ítem, [A → ] . A una serie de ítems LR(0) se le denomina
colección canónica LR(0).

- 33 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

OPERACION DE CERRADURA

Si I es un conjunto de ítems en G se construye cerradura(I) como:

1. Todos los elementos de I están en cerradura(I).

2. Si hay un ítem como [A → B] y B →  es una producción, se añade el ítem [B → ]. Se

repite esta regla hasta que ya no se puedan añadir más ítems.
OPERACION GOTO

La operación GOTO que se escribe como goto(I,X), donde I es un conjunto de ítems y X un

símbolo gramatical, se define como la cerradura del conjunto de todos los ¡tem s [A → X] tales que
[A → X] están en I.

Con las operaciones anteriores se puede encontrar la colección canónica de ítems LR(0), y los
estados del DFA, para posteriormente construir una tabla predictiva. Primero se obtiene a partir de G
una gramática aumentada G', que consiste en agregar una producción al principio y cambiar
consecuentemente el símbolo inicial de la gramática, S' → S. Posteriormente se calcula la cerradura
para S' → S, y se comienzan a realizar las operaciones góto sobre el conjunto encontrado. Ejemplo :

0) F' → F
1) F → f ( x ) = MENOS EXP
2) MENOS → -
3) MENOS → 
4) EXP → # S
5) S → OP EXP
6) S → 
7) OP → -
8) OP → +

TERMINALES={f, (, x, ), =, -, #, +, ┴}

NO TERMINALES = {F', F, MENOS, EXP, S, OP}

0) F' →  F goto(0,F)=1
F →  f ( x ) = MENOS EXP goto(0,f)=2

1) F' → F 

2) F → f  ( x ) = MENOS EXP goto(2,()=3

3) F → f (  x ) = MENOS EXP goto(3,x)=4

4) F → f ( x  ) = MENOS EXP goto(4,))=5

5) F → f ( x )  = MENOS EXP goto(5,=)=6

6) F → f ( x ) =  MENOS EXP goto(6,MENOS)=7

MENOS →  - goto(6,-)=8
MENOS → 

7) F → f ( x ) = MENOS  EXP goto(7,EXP)=9

- 34 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

EXP →  # S goto(7,#)=10

8) MENOS → - 

9) F → f ( x ) = MENOS EXP 

10) EXP → #  S goto(10,S)=11

S →  OP EXP goto(10,OP)=12
S → 
OP →  - goto(10,-)=13
OP →  + goto(10,+)=14

11) EXP → # S 

12) S → OP  EXP goto(12,EXP)=15

EXP →  # S goto(12,#)=10

13) OP → - 

14) OP → + 

15) S → OP EXP 

TABLA SLR(1)

Una vez construido el conjunto canónico, se siguen las reglas:

1. Si goto (i,a)= j, donde a es terminal, M[i,a]= Shift(j).

2. Si goto (i,A)= j, donde A es no-terminal, M[i,A]=Goto(j).

3. Si A →   está en i, M[i,b]=Reduce(j) (reduce por la producción número j), para todo b en el

FOLLOW(A), y A≠S'.

4. Si S' → S  está en i, M[i,┴]=Acceptar.

5. Todas las demás entradas no definidas son error.

Si existen colisiones se dice que la gramática no es SLR.

PARSER LR(1)
ITEMS LR(1)

Para la construcción de la tabla LR(1) se requiere calcular el conjunto canónico de ítems LR(1). Se
modifica la operación de cerradura.

Los ítems del conjunto LR(1) tienen la forma [A → B, a], (tienen el nuevo elemento a llamado
símbolo de anticipación) y la cerradura para un conjunto de ítems I se calcula como:

1. Para cada ítem de la forma [A → B, a] en I, sea B →  una producción, se añade el ítem
[B→ , b] para cada b en FIRST(a). Se repite esta regla hasta que no se pueda añadir nada más.

Para construir el conjunto canónico de ítems LR(1) dada una gramática, primero se calcula la
cerradura para el ítem [S'→ S, ┴], con lo que se crea el primer estado, y posteriormente se comienzan

- 35 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

a hacer las operaciones goto hasta que ya no puedan ser añadidos más ítems.
CONSTRUCCION DE LA TABLA LR(1)

1. Si goto (i,a)= j, donde a es terminal, M[i,a]= Shift(j).

2. Si goto (i,A)= j, donde A es no-terminal, M[i,A]=Goto(j).

3. Si [A → , a] está en i, M[i,a]=Reduce(j) (reduce por la producción j), y A≠S'.

4. Si [S'→ S, ┴] está en i, M[i,┴]=Aceptar.

5. Todas las demás entradas no definidas son error.

Una de las desventajas de este método es que produce tablas predictivas demasiado grandes, por
lo que en ocasiones se utiliza un parser LALR que tiene mayor cobertura que un SLR, y produce tablas
más pequeñas que las LR.
PARSER LALR(1)

Este método se basa en los núcleos de los ítems LR(1), agrupando los núcleos iguales en un solo
estado, para reducir el número de estados. Se buscan los elementos LR(1) con mismos núcleos y se
reemplazan por su unión. El único conflicto posible es el de reducción/reducción, y entonces, se dice
que la gramática no es LALR. Para construir la tabla se realiza el siguiente método. Las siglas del
método quieren decir "look ahead-LR", análisis sintáctico LR con símbolo de anticipación.

1. Constrúyanse el conjunto 𝐶 = {𝐼1 , 𝐼2 , … , 𝐼𝑛 } de ítems LR(1).

2. Búsquense todos los conjuntos con núcleos iguales y sustitúyanse por su unión obteniendo el
nuevo conjunto que llamaremos 𝐶′ = {𝐽1 , 𝐽2 , … , 𝐽𝑚 }. Al realizar la operación goto(J,X)=𝐼𝑚 , J puede
ser la unión de varios conjuntos I, es decir 𝐽 = 𝐼1 ∪ 𝐼2 ∪ … ∪ 𝐼𝑘 , y si m no existe como conjunto
independiente porque m forma parte de alguna unión 𝐿 = 𝐼1 ∪ 𝐼2 … ∪ 𝐼𝑚 ∪ … ∪ 𝐼𝑘 , goto(J,X)=L.

3. Aplíquense todos los pasos utilizados en la construcción de la tabla LR(1). Si existe algún
conflicto, se dice que la gramática no es LALR(1).
TRASLACION DIRIGIDA POR SINTAXIS

NOTACION POSTFIJA.

1. Si E es variable o constante el postfijo de E es E.

2. Si E es una expresión de forma E1 op E2 con op como operador binario, el postfijo de E es

E′1 E′2 op donde E′1 y E′2 son los postfijos de E1 y E2 .

3. Si E es de la forma (E1 ), el postfijo E es el postfijo de E1 .

(9-5)+2 = 9 5 - 2 +

9-(5+2) = 9 5 2 + -

Durante el proceso de traslación, un compilador puede ir almacenando ciertas cantidades que

servir n para la generación de código. En este punto es donde se consideran los atributos asociados
con algún elemento.

Un formalismo para implementar estas actividades se llamado "SYNTAX DIRECTED DEFINITION"

(definición dirigida por sintaxis). Esta especifica los atributos con los componentes sintácticos de
alguna definición.

Una DDS usa una gramática de contexto libre para especificar la estructura de una cadena, con

- 36 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

cada símbolo de la gramática se asocia un conjunto de atributos, y con cada producción de la

gramática, una regla semántica. La gramática y las reglas semánticas forman la SDD. Una translación
es el mapeo de una entrada en una salida por medio de la DDS. Para producir la salida, primero se
construye un árbol de perser para X. Se escribe X.a para denotar el valor del atributo a en el nodo n. El
valor de X.a en el nodo n es calculado por la regla semántica asociada con la X-producción.

Por ejemplo:

PRODUCCIONES REGLA SEMANTICA

EXP → EXP + TERM EXP.a := EXP.a ǁ TERM.a ǁ +

EXP → EXP - TERM EXP.a := EXP.a ǁ TERM.a ǁ -
EXP → TERM EXP.a := TERM.a
TERM → num TERM.a := num.val
TERM → id TERM.a := id.val

Estas reglas semánticas trasladan una expresión en notación infija a notación postfija, el símbolo ǁ
significa concatenación.

Para 9-5+2 se expande el árbol

EXP EXP.a=95-2+

EXP + TERM EXP.a=95- TERM.a=2

EXP - TERM 2 EXP.a=9 TERM.a=5

TERM 5 TERM.a=9

9 9 - 5 + 2

La notación postfija tiene una importante ventaja ya que solo hay una forma de codificarla debi do a la
posición y número de argumentos. La manera de interpretarla siempre es la misma y es muy sencilla.
Se recorre la cadena de izquierda a derecha hasta encontrar un operador, luego se toman los dos
operandos previos al operador encontrado, se evalúa el operador con sus operandos y se sustituyen
por el resultado luego se continúa. Este proceso se repite hasta terminar con todas las evaluaciones.

Ejemplo:

Sea a=5, m=7 y d=3

dia := (1461*a) div 4 + (153*m + 2) div 5 + d

entonces dia=2043

Ahora la notación postfija es:

dia 1461 a * 4 div 153 m * 2 + 5 div d + + :=

Al evaluar de izquierda a derecha:

- 37 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

dia 1461 a * 4 div 153 m * 2 + 5 div d + + :=

dia 7305 4 div 153 m * 2 + 5 div d + + :=
dia 1826 153 m * 2 + 5 div d + + :=
dia 1826 1071 2 + 5 div d + + :=
dia 1826 1073 5 div d + + :=
dia 1826 214 d + + :=
dia 1826 217 + :=
dia 2043 :=

entonces dia=2043

Por ejemplo: ROBOT ( Tarea ).

Procedimiento recursivo para evaluar un árbol con reglas semánticas y atributos.

PROCEDURE VISITA (n:nodo)

inicio
Por cada hijo m del nodo n de izquierda a derecha HACER
VISITA(m)
Evaluar las reglas semánticas para n
fin procedimiento
ESQUEMAS DE TRANSLACION.

Un esquema de translación es una gramática de contexto libre en la cual se introducen

fragmentos de código en la parte derecha de las producciones, prácticamente, es lo mismo que una
DDS, sólo que el orden de evaluación de las reglas semánticas es explícito.

La acción a ejecutar, es simplemente un nodo más en un árbol sintáctico. Cuando una DDS es
"simple" el orden de los no terminales de la gramática conserva su posición, y solamente se añaden
algunos strings adicionales. Una forma sencilla de construir un esquema de translación para una
gramática, es añadir los caracteres agregados de la regla semántica en la DDS. El esquema de
traslación queda:

EXP → EXP + TERM { print '+' }

EXP → EXP - TERM { print '-' }
EXP → TERM
TERM → num { print num.val }
TERM → id { print id.val }

IMPLEMENTACION DE CODIGO INTERMEDIO CON PILA

El front-end de un compilador debe generar código intermedio, es decir, una representación

intermedia del programa fuente. Una forma de implementarlo es mediante una pila. Este esquema
trabaja con un área de memoria para instrucciones y otra reservada para da tos, y todas las
operaciones aritméticas son hechas sobre una pila.

- 38 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

PROGRAMA PILA DATOS

1 mete(5) 16 1 0
2 rvalor(2) 7  tope 2 11
3 opsum 3 7
4 rvalor(3) 4
5 opmul  cp
6
7

En este diseño, las operaciones aritméticas se realizan en forma postfija. La pila y la memoria de
datos se manejan con estas instrucciones:

mete(x) mete x a la pila.

rvalor(x) mete en la pila el contenido de la dirección x del segmento de datos.

lvalor(d(x)) mete en la pila la dirección d(x) del segmento de datos.

saca saca el tope de la pila.

opabs saca el tope de la pila e introduce su valor absoluto.

copia mete una copia del tope de la pila en la pila.

opsum Saca los dos últimos elementos de la pila, los suma y el resultado
lo introduce en la pila. Todos los siguientes trabajan de la misma
manera.

opdif Hace la resta.

opmul Hace la multiplicación.

opcoc Hace la división

opdiv Hace la división entera.

opmod Hace el módulo.

opand Hace la conjunción (0 es falso, no cero es verdadero).

opor Hace la disyunción (0 es falso, no cero es verdadero).

opnot Hace la negación, saca el tope de la pila y si es 0 introduce un 1, y si

es cualquier valor diferente de 0, introduce un 0.

asig el rvalor del tope de la pila es colocado en el lvalor debajo de él,

y los dos elementos son sacados de la pila.

ira(x) Salta a la dirección x del segmento del programa. Es decir IP=x.

irfalso(x) Saca el tope de la pila y si es 0 salta a la dirección x del segmento del

programa. Es decir IP=x.

irverdad(x) Saca el tope de la pila y si es distinto de 0 salta a la dirección x del

segmento del programa. Es decir IP=x.

fin Termina la ejecución del programa.

- 39 - Héctor Torres Aguilar

 Universidad Autónoma del Estado de México
Facultad deIngeniería

El código para una suma como 3 + 5 es:

mete(3)
mete(5)
opsum

Tomando el segmento de datos de arriba, el código para guardar en la dirección 1 el resultado de

la multiplicación de las direcciones 2 y 3 es el siguiente:

lvalor(d(1))
rvalor(2)
rvalor(3)
opmul
asig

Para las expresiones booleanas el valor de 0 es falso y todos los valores diferentes de cero
significan verdadero.

Las comparaciones con los operadores =, <>, >, <, >=, <= se pueden hacer con las operaciones
básicas descritas anteriomente, por ejemplo la igualdad se puede resolver con operaciones aritméticas.

3 <> 1 debe arrojar un valor verdadero es decir, diferente de 0. En tanto que

3 <> 3 debe arrojar un valor igual a 0 que es falso. En tanto que

3 = 1 debe arrojar un 0 porque esto es falso y

3 = 3 debe arrojar algo diferente de cero porque esto es verdadero.

Nos percatamos que si hacemos la resta de los dos elementos que se comparan, siempre nos dará
como resultado un cero si los elementos son iguales, y algo diferente de 0 si son diferentes es decir:

= 0 𝑠𝑖𝑒𝑚𝑝𝑟𝑒 𝑞𝑢𝑒 𝑎 = 𝑏
𝑑𝑎𝑑𝑎 𝑙𝑎 𝑒𝑥𝑝𝑟𝑒𝑠𝑖ó𝑛 𝑎 = 𝑏, (𝑎 − 𝑏) {
≠ 0 𝑠𝑖𝑒𝑚𝑝𝑟𝑒 𝑞𝑢𝑒 𝑎 ≠ 𝑏

Es decir, si hacemos la diferencia (a-b) dado a=b, nos dará falso si son iguales y verdadero si son
diferentes. Por lo que simplemente basta negar el valor. Así la expresión la podemos traducir con
operaciones aritméticas:

𝑎 = 𝑏 ⇒ ∼ (𝑎 − 𝑏)
𝑎 ≠ 𝑏 ⇒ (𝑎 − 𝑏)

De la misma manera se pueden buscar fórmulas para 𝑎 > 𝑏, 𝑎 < 𝑏, 𝑎 ≥ 𝑏 𝑦 𝑎 ≤ 𝑏.

- 40 - Héctor Torres Aguilar