ANÁLISIS LEXICOGRÁFICO

Y
SINTÁCTICO DE UN COMPILADOR

Joel Ayala de la Vega Irene Aguilar Juárez José Jair Vázquez Palma
 ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Primera edición 2021

ISBN: 978-607-8435-99-9

Todos los derechos reservados.

© 2021 Joel Ayala de la Vega, Irene Aguilar Juárez y José Jair Vázquez Palma.
Los conceptos expresados en este documento son responsabilidad exclusiva de los autores. Esta
obra cumple con el requisito de evaluación por dos pares de expertos.

Edición y diagramación: Orlanda Patricia Santillán Castillo

Editorial Centro de Estudios e Investigaciones para el Desarrollo Docente. CENID AC es miembro de

la Cámara Nacional de la Industria Editorial Mexicana Socio #3758
Queda prohibida la reproducción o transmisión total o parcial del contenido de la presente obra
mediante algún método sea electrónico o mecánico (INCLUYENDO EL FOTOCOPIADO, la grabación
o cualquier sistema de recuperación o almacenamiento de información), sin el consentimiento por
escrito del editor.

Indexación de Datos
Bases de datos en las que Editorial Centro de Estudios e Investigaciones para el Desarrollo Docente
CENID A.C. está indexada: Dialnet (Universidad de la Rioja)
© 2021 Editorial Centro de Estudios e Investigaciones para el Desarrollo Docente. CENID AC
Av. Acantilado 2880 Int. Mirador de la barranca 43, Col. Bosques el centinela, C.P. 45120, Zapopan, Jal.
Teléfono: 01 (33) 1061 8187 Registro definitivo Reniecyt No.1700205 a cargo de Conacyt.

CENID y su símbolo identificador son una marca comercial registrada.

Impreso en México / Printed in México

Si desea publicar un libro o un artículo de

investigación contáctenos.
ww.cenid.org.mx
[email protected]
 ÍNDICE
INTRODUCCIÓN ………………………………………………........... 5

CAPÍTULO I

Compiladores ………………………………………………........... 6

CAPÍTULO II

Lenguajes formales ………………………………………………........... 13

CAPÍTULO III

Lenguajes regulares …………….........…………………………………........... 18

CAPÍTULO IV

Autómatas de estado finito ..………………………………………………........... 28

CAPÍTULO V

Gramáticas formales ………….........……………………………………........... 56

CAPÍTULO VI

Autómatas tipo pila ………………………………………………........... 77

ÍNDICE

REFERENCIAS ………………………………………………........... 124

ANEXO A ………………………………………………........... 1126

ANEXO B ………………………………………………........... 140

 Introducción 5

El desarrollo de los compiladores facilitó el uso masivo de las computadoras digitales por-
que ofreció al público general los medios amigables para incursionar en la codificación de
aplicaciones informáticas útiles en cualquier área de estudio humano. Sin los compiladores
el desarrollo de los programas informáticos hubiera quedado en el dominio de pocas per-
sonas especialistas y no se hubieran aprovechado las computadoras de la forma masiva

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

que vemos actualmente. Después de más de sesenta años de avances en el estudio de la
computación, el análisis de los compiladores sigue siendo un área de estudio necesaria en
la formación de los profesionistas de la computación.

Aunque es muy probable que los profesionistas del cómputo no tengan que enfrentar el reto
de desarrollar o mantener un compilador durante su vida profesional, el estudio de las bases
teóricas de estos programas informáticos facilita que los alumnos comprendan con mayor
profundidad la aplicación de la teoría de autómatas y leguajes formales, la aplicación de las
estructuras de datos complejas, las técnicas de programación estructurada y el desarrollo
de software.

Este libro, en concreto, está constituido en seis capítulos en los que se explican los funda-
mentos teóricos del funcionamiento de un compilador, de ahí que haya sido diseñado para
ser utilizado como fuente de consulta en un curso semestral de compiladores. En síntesis,
en el capítulo I se describe el proceso de la compilación y sus fases, mientras que en el
capítulo II se explica la teoría de los lenguajes formales. En el capítulo III se analizan las
bases teóricas de los lenguajes regulares y sus operaciones, y en el capítulo IV se analiza la
teoría de autómatas de estado finito y su relación con el análisis lexicográfico. En el capítulo
V se describen las gramáticas formales en general y las gramáticas libres de contexto en
particular, así como su utilidad en el análisis sintáctico de un compilador. Finalmente, en el
capítulo VI se analizan los autómatas tipo pila y los diferentes tipos de analizadores. Como
estrategia didáctica se presenta el anexo A, el cual constituye un ejemplo de la codificación
de un analizador sintáctico ascendente donde se colocan los diagramas de flujo y el código
en lenguaje C indicando la forma en que se puede programar una pila de apuntadores para
la construcción del árbol en forma ascendente para que el alumno analice la aplicación de
los analizadores SLR. Por último, en el anexo B se ofrece el código completo.
 6 CAPÍTULO I.
COMPILADORES

INTRODUCCIÓN

Un compilador es, en pocas palabras, un traductor que usa como entrada un leguaje de alto
nivel y da como resultado otro lenguaje aproximado al lenguaje máquina. El lenguaje de
programación C, por ejemplo, se compila comúnmente a un lenguaje ensamblador, el cual
es convertido en lenguaje máquina por un ensamblador.
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Un compilador efectúa solo la traducción (no ejecuta el programa), mientras que el progra-
ma objeto que resulta después de la compilación será directamente ejecutable.

COMPILACIÓN

Se denomina compilación al proceso de traducir un programa fuente a código máquina; un

compilador estándar emplea típicamente dos pasos sobre el programa fuente: analizar y
sintetizar (Lemone, 1991). En el primero descompone el programa en los componentes que
lo construyen y obtiene cierta información. En el segundo genera un programa objeto a partir
de la información recogida.

Si decidimos tomar las definiciones análisis y síntesis literalmente, tenemos que el análisis
se lleva a cabo mediante tres etapas:

1. Análisis lexicográfico.
2. Análisis sintáctico.
3. Análisis semántico.

La síntesis se desarrolla mediante cuatro etapas:

1. Generador de código intermedio.

2. Optimización de código.
3. Enlazador.
4. Generación de código.

Interactuando directamente con el proceso de compilación, encontramos al administrador

de la tabla de símbolos y al manejador de errores, los cuales proporcionan una ayuda auxi-
liar al compilador para llevar a cabo su tarea (figura 1.1).
 Figura 1.1. Etapas del proceso de compilación (Google imágenes)
7

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

A continuación, se describirá brevemente cada una de las etapas del compilador.

ANÁLISIS LEXICOGRÁFICO

El objetivo del analizador lexicográfico es examinar cada una de las palabras contenidas
en un programa de un lenguaje de programación específico. El analizador lexicográfico —
también conocido como scanner— lee carácter por carácter hasta formar una palabra que
puede ser uno de los siguientes elementos:

• identificadores,
• delimitadores,
• símbolos de operadores,
• números,
• palabras clave,
• palabras pregonadas (palabras opcionales que se insertan en los
enunciados para mejorar la legibilidad),
• espacios en blanco,
• comentarios, etc.

Todos con alguna relación entre sí (tokens). Cada token es una secuencia de caracteres
 8 tratados como una entidad, y son la entrada para la siguiente etapa del compilador.

El modelo básico que se usa para proyectar analizadores léxicos es el autómata de estados
finitos. Se utilizará al lenguaje C estándar para indicar un error lexicográfico. Si se escribe
la función principal como:

mein

se tiene un error lexicográfico, ya que lo correcto sería:

main

Si la palabra está bien escrita, el compilador reconoce la palabra y la envía como token al
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

analizador sintáctico.

ANÁLISIS SINTÁCTICO

Solo como ejemplo se utilizará el español para mostrar la forma en que funciona el anali-
zador sintáctico. En español, un error sintáctico sería:

con juega la pelota la niña

Obsérvese que cada palabra está bien escrita, por lo que en esta oración se tienen seis
tokens:

• token 1 “con” puede ser representado con una “c”,

• token 2 “juega” puede ser representado con una “j”,
• token 3 “la” puede ser representado con una “l”,
• token 4 “pelota” puede ser representado con una “p”,
• token 5 “la” puede ser representado con una “l”,
• y token 6 “niña” que puede ser representado con una “n”.

Véase que cada palabra está bien escrita (análisis lexicográfico), pero no tiene una estruc-
tura sintáctica definida (en este ejemplo la palabra a analizar por el analizador sintáctico
sería “cjlpln”, el analizador léxico envía un token “c” al analizador sintáctico y es aceptado,
el siguiente token que llega del analizador lexicográfico es una “j”, en este momento el ana-
lizador sintáctico no lo reconoce y produce un error sintáctico).

Las oraciones correctas serían las siguientes: “la niña juega con la pelota”, “la pelota juega
con la niña”, “con la pelota juega la niña” o “con la niña juega la pelota”. Estas cuatro oracio-
nes están bien definidas sintácticamente, por lo que las posibles palabras para el análisis
sintáctico serían “lnjclp” o “lpjcln” o “clpjln” o “clnjlp”.
Para el analizador sintáctico un programa escrito en un lenguaje de programación imperati-
9
vo, sin importar lo grande que sea, es una palabra para reconocer, donde cada token que le
llega representa un símbolo de tal palabra.

El analizador sintáctico (también conocido como parser) recibe como entrada los tokens que
le pasa el analizador léxico, comprueba que lleguen en el orden correcto (definido por el
lenguaje) e identifica las estructuras de programa (enunciados, declaraciones expresiones,
etc.). El analizador sintáctico se alterna con el análisis lexicográfico hasta que llega el fin del
programa, por lo que se crea un ciclo de la siguiente forma:

• Primero. El analizador lexicográfico lee una palabra del programa que debe

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

revisar. Si la palabra es incorrecta, el analizador lanzará un error lexicográ-
fico; si no es así, la palabra revisada se transforma en un token que será
enviado al analizador sintáctico.
• Segundo. El token es revisado por el analizador sintáctico: si el token cum-
ple con la propiedad del lenguaje, es aceptado como parte de la palabra del
analizador sintáctico; si no, marca un error sintáctico.
• Tercero. Si el token es aceptado, se llama a una rutina que permite colocarlo
como parte de un árbol conocido como árbol sintáctico.

Al terminar de analizar la palabra del analizador sintáctico, y si esta es correcta, se ha logra-

do crear un árbol sintáctico (conocido en inglés como parser tree).

Se utilizará el lenguaje C estándar para indicar un error sintáctico si se escribe una repeti-
ción, utilizando el comando “for” de la siguiente forma:

for (i<10; i++; i=0)

Es posible que no se haya roto ninguna regla lexicográfica, pero sí una sintáctica, ya que
los elementos dentro del paréntesis no tienen el orden adecuado (como primer elemento
el inicio del contador; como segundo elemento la condición de continuidad, y como tercer
elemento el incremento o decremento del contador). La sentencia correcta sería:

for (i=0; i<10; i++)

ANÁLISIS SEMÁNTICO

Siguiendo con el español, un error semántico sería:

La pelota juega con la niña.

Obsérvese que cada palabra está bien escrita (análisis lexicográfico) y bien colocada (sin-
10 tácticamente hablando), pero no tiene un sentido apropiado (al menos que se esté en el
mundo de los Tiny Tunes), por lo que presenta un problema semántico.

Al mismo tiempo que se realiza el análisis sintáctico se va creando el árbol sintáctico. Si la

palabra está bien escrita, se tiene completo un árbol sintáctico que se puede recorrer en
postorden para realizar dos tareas en específico:

• Crear el código intermedio.

• Revisar si existe un error semántico.

Se mostrará un ejemplo por medio del lenguaje de programación C para comprender mejor
el análisis semántico:
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

#include <stdio.h>
main(){
int i, *ptr;
i=10;
ptr=i;
}

Produce el siguiente error (compilado en dev-c, figura 1.2):

Figura 1.2. Error de tipo de dato en Dev-C

El programa está bien escrito tanto en forma lexicográfica como sintáctica. Al recorrer el ár-
bol sintáctico, se puede observar que en la línea 5 se tiene un error de tipo, ya que se indica
una conversión inválida de tipos de “entero a entero”. En tal línea (“ptr=i;”) se está tratando
de dar a la variable “ptr” un valor entero cuando espera una variable tipo apuntador de ente-
ro. Esto se puede observar solo hasta que el árbol sintáctico esté creado.
El programa correcto es:
11
#include <stdio.h>
main(){
int i, *ptr;
i=10;
ptr=&i;
}

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

donde a “ptr” se le asigna una dirección de memoria.

GENERACIÓN DE CÓDIGO INTERMEDIO

Después de los análisis sintáctico y semántico, el árbol sintáctico se recorre en postorden

para generar un código intermedio en ensamblador.

OPTIMIZACIÓN DE CÓDIGO

El analizador semántico produce ordinariamente como salida el programa ejecutable tradu-

cido en algún código intermedio. A partir de esta representación interna, las generaciones
de código pueden crear el código objeto de salida con el formato apropiado. Sin embargo,
es posible realizar mejoras en el código intermedio; la optimización de código intermedio
es independiente del lenguaje fuente y del lenguaje objeto, este suele incluir algoritmos de
optimización que dependen del compilador.

ENLAZADOR

Permite formar un solo programa a partir de varios archivos de código máquina relocaliza-
ble. Estos archivos pueden haber sido el resultado de varias compilaciones distintas, y al-
gunos de estos pueden ser librerías del sistema que pueden utilizarse en programas fuente
(ejemplo de esto son todos los archivos que se localizan en el subdirectorio “include” de
cualquier compilador en C, como “stdio.h”, “stdlib.h”, etc.).
12 GENERADOR DE CÓDIGO

En esta parte, el código intermedio optimizado es traducido a una secuencia de instruccio-

nes en ensamblador o en código máquina del procesador que nos interese.

Después de que se ha optimizado el programa traducido en la representación interna, se

debe transformar en los enunciados en lenguaje ensamblador, código de máquina u otra
forma de programa objeto que va a construir la salida de la traducción.

Este proceso implica dar formato apropiado a la salida con base en la información que
contiene la representación interna del programa (Cueva Lovelle, 2001; Dean, 2001; Proces-
sadors de llenguatge II, 25 de marzo de 2020). El código de salida puede ser directamente
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

ejecutable o puede haber otros pasos de traducción por seguir: por ejemplo, ensamblador o
vinculación y carga (en el caso de Java y otros lenguajes compilados-interpretados, se crea
un código de bytes que será interpretado por una máquina virtual).

ADMINISTRADOR DE LA TABLA DE SÍMBOLOS

Un compilador necesita guardar y usar la información de los objetos que va encontrando en

el texto fuente, la cual se almacena en una estructura de datos interna (tabla de símbolos).
El compilador debe desarrollar funciones para manipular esta tabla, cuyos accesos deben
ser rápidos (Processadors de llenguatge II, 25 de marzo de 2020).
 CAPÍTULO II. 13
LENGUAJES FORMALES

INTRODUCCIÓN

Existen dos tipos básicos y reconocidos de lenguajes: los lenguajes naturales o semánticos
y los lenguajes formales. El origen y desarrollo de los primeros —como el castellano, el
inglés o el francés— es natural, es decir, sin el control de ninguna teoría. Las teorías de len-

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

guajes naturales y las gramáticas fueron establecidas a posteriori, esto es, después de que
el lenguaje había madurado. Por otro lado, los lenguajes formales —como las matemáticas
y la lógica— fueron desarrollados a priori generalmente a través del establecimiento de una
teoría que les otorgó sus bases.

El conflicto que se tiene con un lenguaje semántico es su ambigüedad, ya que una palabra,
frase u oración puede tener en un momento dado más de un significado, dependiendo del
contexto en el que se esté hablando (p. ej., La planta de los pies y La planta de un edificio).

En cambio, el lenguaje formal no tiene el problema de interpretación semántica. Así, la ecua-

ción ax2 + bx + c = 0 tiene el mismo significado en cualquier lugar, de ahí que se puedan
explicar fenómenos científicos sin conflictos de interpretación.

Otra ventaja de los lenguajes formales es el manejo de los espacios abstractos. Esta capaci-
dad permite la exploración de nuevos espacios, lo cual es realizado por los matemáticos. La
creación de nuevos espacios permite elaborar herramientas para que la ciencia comunique
sus hallazgos sin ambigüedades.

Los lenguajes formales se pueden dividir en dos grupos: los que permiten expresar un
espacio continuo (donde el cálculo infinitesimal es el rey), y los que permiten expresar un
espacio discreto (p. ej., la teoría de grafos, la lógica, la teoría de distribuciones de probabi-
lidad discretas, la teoría de conjuntos, etc.). Dentro de los lenguajes que se localizan en el
espacio discreto están aquellos que estudian la forma en que se concatenan las palabras
que cumplen una cierta propiedad. La gran ventaja de los lenguajes formales es que permi-
ten expresar un algoritmo sin el problema de la ambigüedad. En este punto nace una nueva
disciplina matemática conocida como teoría de la computación.

Teoría de la computación. Es el estudio matemático de las máquinas com-

putacionales y sus capacidades, por lo que se debe desarrollar un modelo
14 para los datos que manipulan las computadoras. Se adoptó la opción mate-
máticamente conveniente de representar datos mediante cadenas de símbo-
los (Lewis y Papadimitriou, 1998).

Este fue el punto de partida de los lenguajes de programación, los cuales sirvieron para
expresar un algoritmo por medio de un lenguaje formal y ejecutarlo para ver y analizar su
comportamiento.

El desarrollo de los computadores en la década de los cuarenta tuvo un gran auge en el

campo de la computación, ya que se tuvo una nueva maquetación de memoria al poder
cargar los programas a la memoria principal, lo cual permitía interpretar el conjunto de ins-
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

trucciones de manera más rápida y eficiente (Moral Callejón, s. f.). Posteriormente, surgió la
introducción de lenguajes de programación de alto nivel, lo que propició reglas sintácticas
y semánticas más rígidas, concretas y bien definidas que fueron útiles para apegarse aún
más al lenguaje natural, aunque con un control más riguroso, lo que dio paso a la construc-
ción de gramáticas y reglas del lenguaje.

Así, se tiene a la teoría de la computación como una herramienta matemática que permite
dar un rigor más amplio al diseño de lenguajes de programación, además de desarrollar las
bases necesarias para la construcción de gramáticas y autómatas, aunque vale señalar que
su origen se encontró afuera del vasto campo de las ciencias de la computación, es decir, la
lingüística (Cueva Lovelle, 2001).

En efecto, el campo de las ciencias de la computación comenzó a emplear estos concep-

tos de gramáticas y lenguajes formales luego de diversas publicaciones de Avram Noam
Chomsky, un célebre lingüista y matemático que permitió definir la sintaxis y la semántica
del lenguaje natural.

En 1956, Chomsky creó una jerarquía en la cual se observan cuatro tipos de lenguajes (en
este escrito se analizarán los lenguajes del tipo 3 y 2. Si se desea conocer los lenguajes del
tipo 1 y 0, se recomienda leer cualquier libro sobre teoría de la computación; ver figura 2.1),
lo que posibilitó que surgiera uno de los primeros lenguajes de programación de alto nivel
implementado por gramáticas libres de contexto: ALGOL 60 (Cueva Lovelle, 2001), donde
se observa un diseño más riguroso de algoritmos de traducción y compiladores (Quiroga
Rojas, 2008).
 Figura 2.1. Jerarquía de Chomsky (Google imágenes)
15

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

La teoría de la computación —sin la intención de su creador— resultó tener una relación
muy fuerte y sorprendente con la teoría de autómatas y la computabilidad, pues los lengua-
jes propuestos por Chomsky tenían una equivalencia entre las máquinas abstractas, donde
a partir de restricciones de las gramáticas les corresponde un tipo de máquina abstracta
(Ibarra Florencio, 2011).

DEFINICIÓN DE LENGUAJE FORMAL

En matemáticas, lógica y las ciencias computacionales, un lenguaje formal es un conjunto

de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (con-
junto de caracteres) finito (Quiroga Rojas, 2008). Informalmente, el termino lenguaje formal
es utilizado para referirse a la formalización de un lenguaje al cual le precede una teoría,
previamente establecida, que le permite mantener una sintaxis y una semántica bien forma-
das, lo que le brinda una consistencia más elocuente a las “oraciones” que llegan a formarse
(Polanco Fernández, 2000). A continuación, se darán algunas definiciones generales sobre
lenguajes formales:

Alfabeto (). Al igual que todo lenguaje, la base de un lenguaje formal es un alfabeto, el cual
se define como un conjunto finito y no vacío de símbolos, denotado por el símbolo Σ. A con-
tinuación, se muestran algunos ejemplos de alfabetos:

Se usará la letra ( ) como un simbolo que pertenece a un alfabeto ( ).

Cadena. Una cadena o palabra (ω) es una serie arbitraria de símbolos que pertenecen a un
alfabeto, unidos por concatenación; por ejemplo, aaabbbccc es una cadena. Al no tener un
16 tamaño u orden específico, puede definirse simplemente que ω es una cadena o palabra.
De igual forma, existe la cadena vacía, representada con el símbolo ξ (ξ no es el espacio
en blanco. Se puede comentar que una palabra “ab” puede represe también como “ξaξbξ”,
ambas cadenas son equivalentes).

Longitud de una cadena. La longitud de una cadena w sobre , |w|, es el número de sím-
bolos que tiene la cadena. Todo símbolo del alfabeto es una palabra o cadena sobre dicho
alfabeto. La cadena vacía ( ) es una palabra sobre cualquier alfabeto.

Concatenación. Sean “x” y “y” cadenas sobre , la concatenación de “x” con “y” es la ca-
dena “z” que se obtiene al añadir la cadena “x” a la palabra “y”.
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

• Notación: z=xy,

Ejemplo; x=“porta”, y=“equipaje”, entonces z=xy=“portaequipaje”.

• Longitud resultante de una concatenación de palabras: |xy|=|x|+|y|.

• identidad respecto a la concatenación: | |=0
• Operación no conmutativa:
• Operación asociativa: x(yz)=(xy)z
• Potencia: Sea x una cadena sobre ,

• Reversa: Sea x una cadena sobre ,

La reversa se deshace a sí misma: (XR)R = X.

Lenguaje (L). Es un conjunto finito o infinito de palabras o cadenas que cumplen con una
propiedad. Los siguientes son ejemplos de lenguajes:
Con base en las definiciones anteriores, se puede indicar que existe un espacio o universo
17
U infinito de lenguajes. No todos los lenguajes que se encuentran en este universo son de
interés para la teoría de los lenguajes formales, cuyo objetivo es investigar si existe un orden
dentro de ese universo para estudiar las diversas propiedades con las cuales se pueden
calificar como interesantes (Baliri, 2014).

Una de las maneras de determinar si un lenguaje es de interés o no es observando si sigue

alguna pauta regular en la construcción de las cadenas. De esta forma, se puede determinar
que el lenguaje es razonable de estudio, ya que se puede definir una periodicidad, aunque
tal vez el lenguaje L4 no lo sea.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

El segundo punto para determinar si un lenguaje es de interés consiste en representar la
disposición de recursos que podrían determinar si una cadena dada pertenece o no a un
lenguaje determinado. Este par de connotaciones permite definir los dos objetivos principa-
les de las dos grandes disciplinas matemáticas que dan orden y sentido al universo de los
lenguajes formales: la teoría de los lenguajes formales y la teoría de la complejidad compu-
tacional (Baliri, 2014).

La teoría de los lenguajes formales estudia los lenguajes prestando atención úni-
camente a sus propiedades estructurales para definir clases de complejidad es-
tructural y establecer relaciones entre las diferentes clases.

La teoría de la complejidad computacional estudia los lenguajes prestando aten-

ción a los recursos que utilizaría un dispositivo mecánico para completar un
procedimiento de decisión, definiendo así diferentes clases de complejidad com-
putacional y las relaciones que existen entre ellas.
18 CAPÍTULO III.
LENGUAJES REGULARES

El estudio de los lenguajes formales es bastante amplio y complejo. Dentro de esta clasi-
ficación, el lenguaje regular obtiene su nombre por la regularidad o por la repetición de un
mismo componente, es decir, se tiene una precepción intuitiva del lenguaje (Quiroga Rojas,
2008).

Los lenguajes regulares contienen una estructura más simple dentro de la jerarquía de
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Chomsky; una de las características más relevantes de los lenguajes regulares es la depen-
dencia lineal que poseen sus cadenas, es decir, la presencia de un símbolo u otro en una
posición determinada de la cadena depende exclusivamente del símbolo que lo precede
inmediatamente.

Un ejemplo de un lenguaje regular se logra apreciar en el Lenguaje L1.

En este ejemplo se observa la simple repetición de la cadena ab hasta un número infinito o

finito de veces, lo que define la regularidad de este tipo de lenguajes. De lo demostrado
anteriormente nace un punto de vista práctico, donde los lenguajes regulares son utilizados
para especificar la construcción de analizadores léxicos (programas dedicados al análisis
de texto y obtener lexemas o unidades léxicas que existen dentro del mismo texto) (Dean,
2001).

Un lenguaje L es regular si, y solo si, se cumple al menos una de las siguientes condiciones:

• L es finito.

• L es la unión o la concatenación de otros lenguajes regulares R1 y R2,

L = R1 U R2 o L = R1R2, respectivamente.

• L es la cerradura de Kleene de algún lenguaje regular, L = R* (se hace un

estudio más detallado de los operadores en las siguientes páginas).

Esta definición permite la creación de expresiones basadas en la notación de conjuntos que

son representados en los lenguajes regulares.
EXPRESIONES REGULARES
19
Las expresiones regulares surgen como una forma de enunciar los lenguajes regulares; di-
cho en otras palabras, son un metalenguaje. Este tipo de expresiones no son propiamente
de los lenguajes regulares; de igual forma, sirven para representar otro tipo de lenguajes
y son una forma de entrada de datos y reconocimiento por parte de los autómatas finitos
(Cueva Lovelle, 2001).

Como se mencionó en la sección anterior, un lenguaje regular puede ser representado por la
notación de conjuntos, pero es mejor el manejo de una notación en la que al representar un
lenguaje se haga con simple texto (cadenas de caracteres). De esta manera, el representar

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

un lenguaje regular sería simplemente mediante palabras de un lenguaje (Ibarra Florencio,
2011). Una de las grandes ventajas con las que cuentan las expresiones regulares —y que
un autómata no puede llegar a ofrecer— se halla en la forma declarativa que poseen para
expresar las cadenas que desean ser aceptadas; una ventaja adicional es que se puede
convertir a una máquina (autómata finito), la cual puede automáticamente decidir si una ca-
dena (palabra) pertenece o no al lenguaje denotado por la expresión regular (Vilca Huayta,
2008). Por lo tanto, las expresiones regulares son una gran forma de representar datos en
muchos sistemas de procesamiento de este tipo de información. Algunos ejemplos de sis-
temas de este tipo son:

• Comandos de búsqueda tales como el comando grep de UNIX o comandos

equivalentes para localizar cadenas en los exploradores web o en los sis-
temas de formateo de texto. Estos emplean una notación de tipo expresión
regular para describir los patrones que el usuario desea localizar en un
archivo.
• Generadores de analizadores léxicos, como JLex o JFLex. Un analizador
léxico es el componente de un compilador que divide el programa fuente en
unidades lógicas o sintácticas formadas por uno o más caracteres que tie-
nen un significado. Entre las unidades lógicas o sintácticas se incluyen las
palabras clave (p. ej., while), identificadores (p. ej., cualquier letra seguida
de cero o más letras y/o dígitos) y signos como + o =.

Las expresiones regulares representan patrones de cadenas de caracteres. Un patrón es

una regla que describe el conjunto de lexemas que pueden representar a un determinado
componente léxico (token) en los programas fuente. En la tabla 3.1 se muestran ejemplos
de componentes léxicos con su lexema y la descripción informal del patrón, es decir, la regla
que describe el conjunto de lexemas. El patrón para el componente léxico const de la tabla
3.1 es simplemente la cadena sencilla const que deletrea la palabra reservada.
20 Tabla 3.1. Ejemplos de componentes léxicos
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Una expresión regular r se encuentra completamente definida mediante el conjunto de ca-

denas con que concuerda. Este conjunto se denomina lenguaje generado por la expresión
regular y se escribe como L(r); aquí lenguaje se utiliza para definir a un conjunto específico
de cadenas. Una expresión regular r también contendrá símbolos del alfabeto; en una ex-
presión regular todos los símbolos indican patrones. También una expresión regular r puede
abarcar caracteres especiales llamados metacaracteres y, por lo general, no pueden ser
caracteres legales en el alfabeto.

Hay dos tipos de expresiones regulares: las expresiones regulares atómicas y las expresio-
nes regulares compuestas. Cada tipo posee tres subtipos.

La sintaxis y la denotación de las expresiones regulares atómicas son:

• Sea α, tal que a ∑, es una expresión regular, entonces L (α) = {a}.

• La cadena vacía ξ es una expresión regular, entonces L (ξ) = {ξ}.
• El conjunto vacío Φ es una expresión regular, entonces L (Φ) = {}.

(El lenguaje vacío no contiene palabra alguna, por lo que ).

La sintaxis y la denotación de las expresiones regulares compuestas son:

• (r1r2) es una expresión regular, entonces L (r1r2) = L (r1) · L (r2).

• (r1 U r2) es una expresión regular, entonces L (r1 U r2) = L (r1) U L (r2).
• (r)* es una expresión regular, entonces L ((r)*) = (L (r)) *

OPERACIONES CON LAS EXPRESIONES REGULARES

Como se demostró, la definición de expresión regular explota la propiedad única de los

lenguajes regulares, según la cual cualquier lenguaje regular puede expresarse como la
concatenación, unión o clausura de dos o más lenguajes regulares por la propiedad basada
21
en la notación de conjuntos (Baliri, 2014).

UNIÓN

Unión de lenguajes. Si L1 y L2 son lenguajes, la unión de L1 y L2 es ,

donde cada lenguaje está definido sobre el mismo alfabeto. (Cueva Lovelle, 2001). Esto
queda a denotar que el conjunto resultante de la unión es aquel conjunto que contiene las
cadenas pertenecientes a los lenguajes L1 y L2, indistintamente uno de otro. Por lo tanto, si
tenemos que L1={001,101,111} y L_2={ξ,001,000,010}, entonces:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

.

Otro ejemplo se aprecia a continuación, donde L1={ab,c,df} y L2={xy,ab,je}. Entonces:

CONCATENACIÓN

Concatenación de lenguajes. Si L1 y L2 son lenguajes, la concatenación de L1 y L2 es

, donde cada lenguaje está definido sobre el mismo
alfabeto. Se denomina concatenación de lenguajes a todas las cadenas formadas concate-
nando una palabra del primer lenguaje con una del segundo lenguaje (Cueva Lovelle, 2001).

La concatenación es el conjunto de cadenas que pueden llegar a formarse al tomar cual-

quier cadena de L1 y concatenándola con cualquiera de L2, obteniendo así una nueva ca-
dena resultante, donde la primera posición pertenece al primer lenguaje, el segundo al si-
guiente y así sucesivamente. Para definir con un operador la concatenación se hace uso
del operador punto (·) o de la omisión de algún operador para darla a denotar (Hopcroft,
Motwani y Ullman, 2007).

Para demostrar su funcionamiento, se tiene L1 ={001,10,111} y L2={ξ,01} . Entonces:

L1 L2 o L1L2={001,10,111,00101,1001,11101}.

Como podemos observar, las tres primeras cadenas son pertenecientes al lenguaje L1 y las
consiguientes son la concatenación de L1 con L2. La razón de las tres primeras cadenas se
debe a una de las propiedades de las expresiones regulares, la cual mantiene toda cadena
sin alteración alguna al ser concatenada a la cadena vacía (Navarrete Sánchez et al., 2008).

Un operador particular de la concatenación es la potencia. La potencia marca el número de

veces que se concatenará un elemento elevado a la potencia indicada. Por ejemplo, an se
define como el elemento “a” concatenado n veces, esto es, a3 equivale a concatenar a “a”
22 tres veces (aaa), a1 es equivalente de concatenar a “a” solo una vez (a), a0 es equivalente a
concatenar a “a” cero veces (ξ).

OPERADORES POTENCIA DE UN LENGUAJE

• Cerradura positiva (+). La cerradura positiva se define como la unión de una o

más potencias de una cadena de L1 en un alfabeto. El resultado contiene todas las
cadenas, con excepción de la cadena vacía ξ. Se denota como . (Padilla
Beltrán, 2006). Desde un punto de vista estricto, se define como la potencia i-ésima
de un lenguaje, concatenándolo consigo mismo i-veces. Para demostrarlo, se tiene
el siguiente ejemplo:
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Si L1 ={a} entonces L1+, tendremos:

Desglosándolo:

Así sucesivamente hasta llegar al infinito o a la cantidad de concatenaciones desea-

das, siempre comenzando desde n=1.

• La clausura de Kleene (*). Dado un lenguaje L, se obtiene un nuevo lenguaje L*, al

igual que la cerradura positiva de un lenguaje representa el conjunto de cadenas que
se pueden formar tomando cualquier número de cadenas de L. Por tanto, se define
como (Cueva Lovelle, 2001). Como puede apreciarse, su funciona-
miento es idéntico al de la cerradura positiva, con la diferencia de que aquí sí se toma
en cuenta la cadena vacía (ξ) y comenzando n = 0.

La clausura de Kleene toma su nombre de quien ideó la notación para las expresio-
nes regulares, Stephen Cole Kleene (1909-1994), quien de igual forma dio pauta a la
existencia de este operador (Hopcroft, Motwani y Ullman, 2007).

Como ejemplo, si se tiene L1={a} entonces L1*, tendremos:

Habitualmente, desglosando cada cadena y tomando en cuenta que siempre la pri-

mera cadena es la cadena vacía (ya que a0=ξ).

Por ello, cualquier subconjunto de ∑* será llamado lenguaje. Así, ∑, Φ, ∑* son lenguajes.
En este punto, definiendo la clausura de Kleene se puede dar una definición de lenguaje
23
formal:

Para los propósitos computacionales, P es una expresión matemática bien formada o una
descripción adecuada de las cadenas en un lenguaje donde se puede dar un procedimiento
sistematizado para decidir si dada una cadena w tiene la propiedad P. De esta forma, uno
debe concretarse a definir un “procedimiento sistematizado” o “algoritmo”.

Un algoritmo puede ser descrito como una finita secuencia de instrucciones en forma pre-
cisa que, cuando se confronta con una pregunta de algún tipo y ejecutado con los pasos

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

indicados, en forma invariable terminará, tarde o temprano, con la respuesta correcta.

Un ejemplo de una propiedad que no cumple con algún procedimiento sistematizado es:

El ejemplo describe en forma adecuada la cadena del lenguaje, pero no tiene en general un
procedimiento o algoritmo en el que pueda indicar si la cadena w pertenece o no al lenguaje.
Obsérvese que no existe restricción en el tamaño de la cadena.

Un lenguaje se puede expresar en forma explícita mediante un ordenamiento lexicográfi-

co (equivalente a un diccionario). Por ejemplo:

se ordena en forma lexicográfica:

L={ξ,0,00,11,000,011,101,110,0000,0011,0101,1001,1010,1100,…}

siendo el conjunto infinito.

Este lenguaje también se puede expresar en forma implícita. Siendo este lenguaje regular,
su expresión regular es:

L=0*(10*10*)*

Para comprender mejor la expresión regular se mostrarán las primeras cuatro cadenas indi-
cadas en el orden lexicográfico:
{ξ} => 00( )0
{0}=> 01( )⁰
{00} => 02( )⁰
{11} => 00 ( )1 = ξ(0⁰10⁰10⁰)
24 La generación de una cadena más grande sería:

{00010010110010001000} => 03()³=000(10²10)(10⁰10²)(10³10³)

Otros ejemplos de lenguajes regulares son:

Ejemplo 3.1. L= {w {0,1}* │w tiene dos o tres ocurrencias de unos, la primera y la segunda
no son consecutivas}

En un orden lexicográfico el lenguaje se expresa como:

L= {101,0101,1010,1011,…}
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

En forma implícita, la expresión regular puede ser:

L= 0*10*010*(10* ξ)

Por ello, una expresión que puede describir a un lenguaje solo con los operadores { ,
*}, combinados con un alfabeto , se considera expresión regular.

Ejemplo 3.2. L={ w {a,b}* │w finaliza con una a}

En un orden lexicográfico el lenguaje se expresa como:

L={a,aa,ba,aaa,aba,baa,bba,…}

La expresión regular del lenguaje se puede expresar como:

L=(a b)*a

Ejemplo 3.3. L={w {a,b,c}* │w no tiene la subcadena ac}

En un orden lexicográfico el lenguaje se expresa como:

L={ξ,a,b,c,ab,bc,cb,abc,bca,bcc,…}

La expresión regular del lenguaje se puede expresar como:

L=c*(a bc*)*

Ejemplo 3.4. L= {w {0,1}* │w no tiene la subcadena 111}.

Por tanto, en un orden lexicográfico el lenguaje se expresa como:

L={ ξ,0,1,00,01,10,11,000,001,010,100,011,101,110,0000,0001,0010,0100,1000, 0011,010

1,0110,1001,1010,1100,…}

La expresión regular del lenguaje se expresa como:

L=0* 0*(1 11) (00*(1 11))*0*

Ejemplo 3.5. L= {w {0,1} *│w forma el conjunto de cadenas que constan de ceros y números
25
1 alternos}.

En orden lexicográfico, el lenguaje se puede expresar como:

L= { ξ, 0, 1, 01, 10, 010, 101, 0101,1010, 10101,01010,…}

La expresión regular del lenguaje se expresa como:

L=(01)* U (10)* U 0(10)* U 1(01)*

Ejemplo 3.6. L= {w {0,1} *│w forma el conjunto de cadenas que comienzan con un 0 segui-
do de cualquier cantidad de números 1}.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

En orden lexicográfico, el lenguaje se puede expresar como:

L= {0, 01, 011, 0111, 011111, 01111, 01111,…}

La expresión regular es:

L=0 1*

Ejemplo 3.7. L= {w {a, b} *│w forma las cadenas de letras a y b que contienen una cantidad
impar de letras b}.

En orden lexicográfico, el lenguaje se puede expresar como:

L= {b, ab, ba, aab, aba, baa, bbb, aaab,aaba, abaa, ba³, bbba,bbab,babb,abbb,…}

En el primer ejemplo se colocó el leguaje cuya propiedad era par de unos. Tomando eso en
cuenta, se puede definir a impar o non como par más uno, a la a la expresión regular anterior
solo se incluye al final una b cumpliendo con dicha propiedad:

L=a*(ba*ba*)*ba*

Ejemplo 3.8. L= {w {a, b} *│w forma las cadenas de letras a y b que nunca contienen tres
letras b seguidas}.

En orden lexicográfico, el lenguaje se puede expresar como:

L= { ξ, a, b, bb, aa, ba, ab,a³, aab,aba,baa, bba,bab, abb,a⁴,aaab,aaba,abaa,ba³,…, bbaa,…,

bbabbaabbab, …}

La expresión regular es:

(a U ba U bba)* (ξ U b U bb)

Ejemplo 3.9. L={w {0,…,9,E,.,+,-} | w es una notación científica normalizada}

26 Una notación científica normalizada tiene una mantisa y un exponente. La mantisa tiene las
siguientes reglas.

• Se tiene en forma opcional un signo positivo o signo negativo.

• La parte entera puede tener opcionalmente un digito y debe ser el cero.
• En la parte fraccional debe tener al menos un dígito.
• En la parte fraccional, el primer dígito después del punto decimal, debe ser
mayor de uno.
• En el exponente es opcional tener un signo positivo o negativo.
• El exponente debe ser siempre un número entero.
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

• En el exponente debe aparecer al menos un dígito.

De esta forma, ejemplos de cadenas permitidas en el lenguaje son:

+.999E+99 0.567E89 -.876E-99 +0.87E4

Algunos ejemplos de cadenas no permitidas en el lenguaje son:

+.089E66 9.99E4 0.66E -.66E+

Si Σ1={0,…,9} y
Σ2= Σ1-{0}

El lenguaje visto en un ordenamiento lexicográfico se observa de la siguiente forma:

Como ejemplo, un número indicado en forma general en el orden lexicográfico puede ser:

Pero , ya que existe un cero después del punto.

La expresión regular puede quedar de la siguiente forma:

Por tanto, un lenguaje es regular si puede ser descrito por medio de una expresión regular.

Desafortunadamente no se pueden describir por medio de una expresión regular lenguajes

tan simples como:

Realizando un orden lexicográfico del lenguaje, se tiene:

L={ab,aabb,aaabbb,aaaabbbb,aaaaabbbbb,…}
27
Este lenguaje tiene un algoritmo sencillo para poder definir si alguna palabra pertenece o
no a tal lenguaje, pero no tiene una regularidad (esto es, se debe tener el mismo número de
letras a con respecto a las letras b). Un lenguaje regular con el operador Kleene similar será:

L2=a*b*

El orden lexicográfico es:

L2={ ξ,a,b,aa,ab,bb,aaa,aab,abb,bbb,…}

Véase que el operador Kleene no permite realizar una contabilidad de letras a con respecto

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

a las letras b (por lo que L1 L2). De esta forma, el lenguaje L1 no es regular.

PROPIEDADES DE LOS LENGUAJES REGULARES

Las expresiones regulares toman varias de las propiedades que la notación de conjuntos
posee, ya que están basadas en el álgebra de conjuntos, pero con sus debidas variedades.
Tomamos que α y β son expresiones regulares equivalentes, por lo tanto, α = β y L (α) =
L (β). A continuación, se enumeran algunas de las propiedades más recurrentes de las
expresiones regulares (Navarrete Sánchez et al., 2008). Recordando que Φ es el conjunto
vacío y ξ es la cadena vacía.
28 CAPÍTULO IV.

AUTÓMATAS DE ESTADO FINITO

INTRODUCCIÓN

En los capítulos anteriores se definió el lenguaje formal desde un punto de vista informático.
Para estudiar en profundidad tales lenguajes se requieren dos herramientas que apoyen
dicha labor:
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Gramática. Es aquel componente matemático que permite crear todas y cada

una de las cadenas que pertenecen al lenguaje.

Autómata. Es aquel componente matemático que permite indicar si una cade-

na dada pertenece o no a un lenguaje específico.

La palabra autómata hace alusión a imitar las funciones propias de un ser vivo, de una ma-
nera más elocuente y enfocada, al movimiento. Dentro del campo de procesadores, com-
piladores e intérpretes, el movimiento no es el campo fundamental que se estudia y ma-
neja, ya que se evoca más a la simulación de procesos para transformar información. Un
autómata dentro del campo de los compiladores, procesadores, intérpretes (por mencionar
algunos) recibe información que es codificada en cadenas de símbolos, y el autómata (que
es un dispositivo que manipula las cadenas de símbolos) produce otro tipo de cadenas
de símbolos para la salida de datos (Isasi Viñuelas, Martínez Fernández y Borrajo Millán,
1997). El resultado obtenido no solo depende del último símbolo, sino de toda la secuencia
de caracteres o cadena de símbolos secuencial que se introdujo; esta definición se atribuye
a un tipo de autómata llamado máquinas secuenciales.

La teoría de autómatas tiene su origen en el campo de la ingeniería eléctrica (Navarrete

Sánchez et al., 2008) por el matemático norteamericano Claude Elwood Shannon (1916-
2001), quien estableció las bases para la aplicación de la lógica matemática a los circuitos
combinatorios y secuenciales. Esto, posteriormente, permitiría a Huffman en 1954 dar inicio
a los circuitos secuenciales y utilizar los conceptos estado de un autómata y tabla de transi-
ción. De esta manera, Shannon fue desarrollando y formalizando la teoría de las máquinas
secuenciales y de los autómatas finitos (1956) (Quiroga Rojas, 2008). Retomando lo ante-
riormente mencionado, se puede definir el concepto fundamental estado de un autómata.

Estado de un autómata. Es toda aquella información necesaria en un momento determina-

do para deducir cuál será el símbolo de salida dado un símbolo de entrada en ese momento.
Dentro de la teoría de autómatas, existen diversos tipos:
1. Autómatas finitos deterministas (AFD).
29
2. Autómatas finitos no deterministas (AFND).
3. Autómatas finitos no deterministas con transición . (AFND- ).
4. Autómatas tipo pila.
5. Autómatas lineales.
6. Máquinas de Turing determinísticas.
7. Máquinas de Turing no determinísticas.

De esta forma, la jerarquía de Chomsky se observa en la tabla 4.1:

Tabla 4.1. Jerarquía de Chomsky (Google imágenes)

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

En otras palabras, conocer el estado del autómata significa determinar todo el historial de
símbolos de entrada que ha tenido; asimismo, el estado inicial es el estado en recibir el pri-
mero de los símbolos de entrada.

AUTÓMATA DE ESTADO FINITO

La representación gráfica de un autómata de estado finito se puede realizar por medio de un

diagrama de Moore (figura 4.1):
30 Figura 4.1. Elementos gráficos de un autómata de estado finito
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Para aclarar más el tema de autómatas se tiene el siguiente ejemplo, donde se usa un len-
guaje regular, se muestra su expresión regular y posteriormente se implementa un autómata
con su grafo correspondiente, forma más común para representarlo dentro del campo de las
ciencias de la computación.

Ejemplo 4.1. Obtener un autómata que acepta el lenguaje L= {w {0,1} *| w tiene par de
ceros}.

Se usará el ordenamiento lexicográfico para comprender mejor el lenguaje descrito en el

ejemplo 4.1:

L={ξ,1,11,00,111,100,010,001,0⁴,0²1²,0101,0110, 1001,1010,1²0²,1⁴,…}

Obsérvese que se acepta la cadena vacía por la inexistencia de ceros (0/2=0 con residuo
cero, el exponente cero es par, por lo que 00= )

Una forma de representar el lenguaje es por medio de una expresión regular:

L=1*(01*01*)*

Utilizando los elementos que se muestran en la figura 4.1, se forma el autómata. La opera-
ción Kleene permite añadir o no la cadena o caracteres a los que afecta. En la figura 4.2, en
la transición de q0 a q0 se realiza con la lectura del símbolo “1”, representando el operador
Kleene (la transición marca que se pueden leer los números 1 que se deseen desde la ca-
dena vacía); lo mismo sucede con la transición de q1 a q1 con la lectura del símbolo “1”.
La transición q0 a q1 se realiza leyendo un cero de la cadena (en este caso se ha leído un
impar de ceros). La transición de q1 a q0 se realiza leyendo un cero (en este caso se han
leído un par de símbolos “0”); q0 es tanto estado inicial como estado final, se justifica que
sea estado final, ya que la cadena vacía también pertenece al lenguaje.
31
Figura 4.2. Diagrama de autómata

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

AUTÓMATAS FINITOS DETERMINÍSTICOS (AFD)

Un autómata finito determinístico es un modelo matemático con un sistema que recibe pará-
metros de entrada y posee salidas discretas, como se mencionó antes, poseyendo de igual
forma un conjunto de estados o configuraciones internas. Los autómatas finitos son capaces
de reconocer solamente un determinado tipo de lenguajes, llamados lenguajes regulares,
que pueden ser caracterizados también mediante un tipo de gramáticas denominadas gra-
máticas regulares o por medio de expresiones regulares (Moral Callejón, s. f.).

Los autómatas finitos determinísticos (AFD) se utilizan generalmente para analizar cadenas
de caracteres y verificar si pertenecen o no a un determinado lenguaje regular; asimismo,
son empleados como analizadores en la traducción de algoritmos para los ordenadores.
Este tipo de analizadores son mayormente conocidos como analizadores lexicográficos.

Un AFD se define matemáticamente como una quíntupla:

M=(Q,∑,s,F,δ):

• Un alfabeto de entrada ∑
• Una colección finita de estados Q.
• Un estado inicial s.
• Una colección de estados finales o de aceptación F.
• Una función, subconjunto del producto cruz , que determina el úni-
co estado siguiente para el par (q_i,σ) correspondiente al estado actual y la entrada.

El nombre determinista proviene de la forma como está definida la función de transición,

es decir, si en un instante t se encuentra en el estado qi y lee el símbolo a, entonces, en el
instante t+1, se cambia al siguiente estado qj, el cual se conoce con seguridad. Descrito
en otras palabras, se define como δ(qi,σ)=qj. (Quiroga Rojas, 2008).
32 Ejemplo 4.2. Considerando el lenguaje regular A = c* (abc* )*. Dada una cadena ω, verificar
que ω pertenece a A.

Realizando un ordenamiento lexicográfico del lenguaje, se tiene:

A={ξ,c,ab,cc,abc,cab,ccc,abab,ccab,cabc,abcc,…}

Como ejemplo, la palabra “abcccababab” se crea de la siguiente forma:

{abcccababab}=>c⁰()⁴=(abc³)(abc⁰)(abc⁰)(abc⁰)
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Para dar solución al Ejemplo 4.2 no solamente se deben verificar los caracteres pertene-
cientes a ω, sino que también se deben vislumbrar sus posiciones. Por ejemplo, la cadena
abc5 se encuentra en A, pero cabac3 no lo está. Para ello, se construye un diagrama que
permita determinar los distintos miembros del lenguaje.

De esta forma, y siguiendo con el Ejemplo 4.2, se obtiene el autómata mostrado en la Figura
4.3.

Figura 4.3. Grafo resultante del Ejemplo 4.2

La tabla de donde se muestra la función de transiciones es una donde las filas son el con-
junto de estados y las columnas las entradas con las que cuenta el autómata. De esta forma,
un autómata representado mediante el diagrama de Moore puede ser presentado como una
tabla de transiciones y viceversa.

Para el Ejemplo 4.2 se obtiene una tabla de transiciones, pero primeramente es necesario
identificar el alfabeto que acepta el autómata. Como puede observarse, es posible obtener
todos los elementos de la quíntupla mencionada con anterioridad para definir el autómata y
la tabla de transiciones. El autómata acepta un alfabeto de entrada , los estados
son Q={q0,q1,q2,q3}, el estado inicial s={q0} y los estados finales F={q0,q2}. Posterior a ello, es
posible conseguir la tabla de estados (tabla 4.2).
 Tabla 4.2. Tabla de estados resultante perteneciente a la figura 4.3
33

Como se observa, el conjunto de transiciones es el subconjunto del producto cruz del nú-

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

mero de estados que se tiene con respecto al alfabeto, para así obtener la transición a cada
estado, mediante cada símbolo.

Un AFD es inicializado con la entrada de una palabra ω de la siguiente manera:

1. ω es agregada al inicio de la lista de entrada separando de esta forma cada

carácter de manera individual.
2. El apuntador de lectura del AFD apunta al símbolo más a la izquierda de ω.
3. El estado actual será q0.

Ejemplo 4.3. Considerando el lenguaje regular:

L={w=(a,b)*| w tiene las letras a que se deseen, pero al menos una a al final de la cadena.
Las subcadenas de letras b, si las hay, serán continuas e impares}

Por ende, el orden léxico gráfico será:

L={a,aa,ba,aaa,baa,aba,a⁴,ba³,abaa,aaba,aaaba,bbba,…}

La expresión regular perteneciente al lenguaje será:

Algunos ejemplos de la creación de cadenas que pertenecen al lenguaje por medio de la

expresión regular son:
34 Recordando que a+=a*-{ }, por lo que un ordenamiento lexicográfico de este operador será:

a+={a,aa,aaa,a⁴,a⁵,...}

El autómata resultante que reconoce el lenguaje está presente en la Figura 4.4.

Figura 4.4. Autómata resultante del ejemplo 4.3

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Retomando la figura 4.4, se tiene a modo de ejemplo la cadena aaaba. De esta forma, y con
lo anteriormente mencionado, es retomar el símbolo más a la izquierda para poder inicializar
el autómata; entonces se inicia con el carácter <<a>> (figura 4.5).

Figura 4.5. Caracterización de la cadena aaaba

Una vez que el autómata ha iniciado, comienza su ejecución tras el siguiente ciclo:

1. Se lee el símbolo actual, que es la cabecera de la pila de lectura. Si el cabe-

zal apunta al vacío, entonces el AFD finaliza aceptando la palabra si, y solo
si, el estado actual es el final.
2. Se calcula el estado siguiente con base en el estado y símbolo actual según
la tabla de transiciones, obteniendo de esta forma la siguiente ecuación:

δ(estado actual,simbolo actual)=estado siguiente.

Para el Ejemplo 4.3 se obtiene la tabla de transición 4.3.

 Tabla 4.3. Tabla de transiciones resultante del autómata del Ejemplo 4.3
35

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

3. El apuntador de lectura se mueve a la siguiente posición hacia la derecha.
4. El estado siguiente pasa a ser el estado actual y se regresa al paso 1.

Figura 4.6. Con base en el algoritmo mostrado, va cambiando el apuntador hasta finalizar
la palabra ω

Como muestra la Figura 4.6, el apuntador se va desplazando hasta finalizar la palabra se-
gún las transiciones y los estados determinados dentro del autómata hasta finalizar y acep-
tar la cadena.

AUTÓMATAS FINITOS NO DETERMINISTAS (AFND)

Una de las diferencias fundamentales entre las diversas clases de autómatas mencionadas
se halla en si dicho control o manejo de estados es determinista o no determinista. El no
determinismo es esencialmente la habilidad de cambiar de estado en una forma que es
parcialmente determinado por el estado actual y el símbolo de entrada. Esto es, se
permiten diferentes posibles caminos para realizar la transición a uno de los estados dada
la combinación del estado actual y el símbolo de entrada. Las posibles transiciones se cla-
sifican en:
36 1. Dado un símbolo de entrada, la transición permite trasladarse a uno de los posibles ca-
minos.

2. Se realiza la transición del estado qi al estado qj sin lectura de símbolo de la cadena de

entrada (conocido como AFND- ξ .
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

3. Para realizar una transición se requiere leer más de un símbolo de entrada.

El siguiente ejemplo muestra mejor estos tres criterios (Lewis y Papadimitriou, 1998):

L(G)= (ab aba)*

El ordenamiento lexicográfico de tal lenguaje es:

L={ξ,ab,aba,abab,ababa,abaab,…}

Para el primer caso el autómata no determinístico se observa en la figura 4.7, donde el no

determinismo se aprecia en el estado q1, ya que al leer el símbolo b se tiene la opción de
transitar hacia el estado q0 o el estado q2.
 Figura 4.7
37

Para el segundo caso, el autómata no determinístico se observa en la figura 4.8. Obsérvese

que estando en el estado q2, se puede transitar al estado q0 sin leer el símbolo o al leer el
símbolo a.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Figura 4.8

Para el tercer caso, el autómata no determinístico se observa en la figura 4.9. En este caso,
no se sabe si se tienen que leer dos o tres símbolos para realizar la transición del estado
q0 al estado q0. Esto es, si se tiene la cadena que pertenece al lenguaje “ababab” y se leen
primero tres caracteres, se realiza sin problema la primera transición, quedando el resto de
la cadena “bab”, en este momento sin importar si se leen dos o tres símbolos va a marcar
un error. Véase que el aceptar o rechazar una cadena correcta depende del número de ca-
racteres que se lean en cada transición.

Figura 4.9

Por ello, se puede diseñar más de un autómata no determinístico que acepte las cadenas
de un lenguaje regular.
38 El no determinismo logra definir un lenguaje de una forma más rápida y sencilla, a diferencia
de un autómata determinístico. Una de las ventajas sobre los autómatas no determinísticos
es que permiten diseñar soluciones más flexibles dentro de los problemas presentados a
los lenguajes de alto nivel, pero es muy difícil de programar. El autómata determinístico a
veces no es fácil de diseñar, pero es fácil de programar (Hopcroft, Motwani y Ullman, 2007).

Ejemplo 4.4. Dado el lenguaje regular:

Se muestra que el autómata de la Figura 4.10 acepta las cadenas generadas por tal expre-
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

sión regular. Su tabla de transiciones se enseña en la tabla 4.4.

En la tabla de transiciones obtenida por el ejemplo 4.4 es posible apreciar que en algunas de
las transiciones de los estados existe más de una transición con un solo símbolo; esta parte
viene a definirse como el no determinismo de esta clase de autómatas (Navarrete Sánchez
et al., 2008), ya que —como hemos de recordar— un AFD se caracteriza por tener una sola
transacción por un símbolo de entrada determinado.

Figura 4.10. AFND del ejemplo 4.4

Tabla 4.4. Tabla de transiciones correspondiente a la Figura 4.10

A pesar de ser autómatas, en ocasiones complejos, es un concepto útil para probar teore-
mas y simplificar descripciones. Ahora bien, un lenguaje regular que es aceptado por un
AFND también es aceptado por un AFD (Campos, 1995).
Los autómatas no determinísticos con transición de cadena vacía son parte de la familia de
39
los AFND, con sus mismas propiedades y características; la diferencia recae en sus transi-
ciones entre un estado a otro, ya que estas pueden ser realizadas sin la necesidad de con-
sumir alguna entrada de un carácter como tal (Dean, 2001). Este tipo de transiciones son
representadas por la cadena vacía (ξ). Al igual que los AFD, los AFND, los AFND- ξ son una
quíntupla que difiere de los demás en la función de transición y en la habilidad que poseen
de permitir una cantidad variada de caminos a elegir con base en el estado en el que se
encuentran y el símbolo de entrada que se tenga (Lewis y Papadimitriou, 1998); los AFND-,
a diferencia de los AFND (que también permiten la transición a varios estados con un solo
carácter) permiten dicha transición con base en el carácter nulo o cadena vacía (Hopcroft,

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Motwani y Ullman, 2007).

Este tipo de transiciones vacías o nulas dan una nueva capacidad y versatilidad a los au-
tómatas. Si se tiene una transición nula, el autómata puede quedarse en el estado actual o
cambiar a algún otro estado que permita llegar a él sin la necesidad de consumir algún ca-
rácter como entrada. La Figura 4.11 muestra un autómata, por el cual dos de sus transicio-
nes son mediante el vacío y cuentan con transiciones con caracteres con un valor no nulo.

Figura 4.11. Representación de un AFND- ξ para L(G)=0*1*2*

Como se mencionó con anterioridad, y como sucede con los AFND, la tabla de transiciones
es distinta a los demás. La diferencia recae en que dentro de los caracteres del lenguaje
aceptado existe el símbolo ξ, de esta forma también se toman en cuenta aquellos cambios
de estado que sean representados por el vacío. Aunque parece un cambio muy simple, lle-
va una gran funcionalidad porque permite la lectura de diversos caracteres y un camino de
inicio a fin, con espacios invisibles que no contribuyen o afectan a la cadena de entrada. El
Ejemplo 4.5 enseña el uso de los AFND-ξ de una manera práctica.

Ejemplo 4.5. Un autómata, que acepte la notación de punto flotante:

1. Primero se espera un signo +, - (opcional).

2. Posteriormente se podrá leer una subcadena de dígitos (opcional).
3. Se lee un punto decimal (opcional).
4. Al final se lee otra subcadena de dígitos (al menos un digito).
40 5. La subcadena del punto 2 o del punto 4 pueden llegar a ser vacías, aunque
al menos una de las dos subcadenas debe tener dígitos.

Un orden lexicográfico será:

L={σ, .σ, + σ, +. σ, σ.σ, + σ.σ,…}

donde σ {0,1,…,9}
Figura 4.12. Autómata resultante del Ejemplo 4.5 usando la cadena vacía en las
transiciones de un estado a otro para obtener una solución congruente
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Como se aprecia en la Figura 4.12 la primera transición mostrada (de q0 a q1) se logra con
el símbolo “+”, con el símbolo “–” o mediante el consumo de la cadena vacía (mejor dicho,
sin el consumo de algún carácter), lo cual es redituable ante ciertos casos y permite resolver
el ejercicio propuesto de manera temporal, pues al mismo tiempo presenta otro problema.
En el estado q1 se tiene que decidir si se mantiene en el estado q1 o se tiene que realizar
una transición a q3 por medio de un símbolo σ {0, 1,…,9}. El problema recae en el uso de
los tipos de autómatas ante una máquina de estados, ya que las máquinas de estados solo
aceptan AFD; por ello, y como se ha venido comentando, el no determinismo es una manera
fácil de dar solución a diversos problemas, pero también una solución óptima en diversos
casos como el presentado con anterioridad. Resumiendo:

Hay que recordar que todo autómata del tipo AFND, sin importar a cuál familia pertenezca,
puede ser transformado en un AFD.

TRANSFORMACION DE UN AFND O AFND-ξ A AFD

La transformación de un AFND o AFND- ξ a AFD lleva a cabo el siguiente algoritmo aquí

presentado, tomando en cuenta que M=(Q,∑,S,F,δ) es un AFND y para hacerlo determinís-
41
tico es necesario construir un autómata M'=(Q',∑,S',F',δ) equivalente a M. El algoritmo de
transformación es el siguiente:

• Si una transición se realiza con la lectura de más de un símbolo, se forman los

mecanismos de transición y estados necesarios para que cada transición se realice
con un símbolo de entrada de la palabra por examinar. Ejemplo:

Teniéndose la transición no determinista de un autómata determinado:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

se transforma a una transición determinista:

• Transición con cadena vacía. Se crea una función de transición vacía en la que se
sabe, a partir de un estado, todos los estados a los que uno puede llegar de forma
directa con la transición de cadena vacía (sin leer algún símbolo de entrada). Para
observar mejor esto se usará el autómata de la figura 4.13:

Figura 4.13
42 En un ordenamiento lexicográfico, las cadenas que acepta el autómata son:

L={ξ,aa,ba,bb,aab,baa,bab,bba,bbb,aabb,baab,babb,bbaa,bbab,b4,…}

Las que no acepta el autómata son:

L {ab,aba,abb,a⁴,a³b,aaba,abaa,abab,abba,ab³,ba³,aaba…}

Por lo que:

L={w {a,b}*|w no tiene restricción con las b. Pero si existen, solo habrá dos a con-
catenadas o una a precedida de una b}
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

El análisis lexicográfico sirve para observar las cadenas que debe aceptar o rechazar
el autómata determinístico.

Obsérvese que a partir de q0 uno puede transitar al mismo estado q0, a los estados q1,
q3 y q4 sin leer un símbolo de entrada. De esta forma, la función E(qi), Empty, se forma
con el conjunto de estados en los que se puede transitar sin leer símbolo de entrada.

E(q0)={q0, q1, q3, q4}

Por tanto, se requiere obtener la función E(qi) de cada uno de los estados involucra-
dos en el autómata no determinístico:

• Estado inicial. El estado inicial del AFD es E(q0), llamándose el nuevo estado ‘S’,
Start. Este nuevo estado determinístico contendrá, como parte de él, al conjunto de
estados del autómata no determinístico.

En este caso:

• Transiciones por realizar. El interior de cada estado de un AFD estará formado

por un conjunto de estados del AFND. Las transiciones de un estado de un AFD se
determinarán dependiendo de las transiciones que marcan cada uno de los estados
del AFND que son parte del conjunto interno del estado del AFD. Cada transición
determinística de un AFD será la unión de la función vacío de todas las transiciones
 de los estados del AFND del conjunto que formó el AFD. El paso 4 se repetirá hasta
43
que no exista una transición más.

Para el caso del estado inicial, este se formó con E(q0) = {q0,q1,q3,q4}, por lo que se
analizarán la transiciones del AFND para cada uno de los estados antes indicados.
El resultado para la letra a es:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

• Estado final. En el AFD, un estado final del AFD será aquel donde se tenga en su
interior un conjunto de estados del AFND en el cual uno de sus elementos sea estado
final.

A continuación, se muestran las transiciones realizadas en el paso cuatro del algoritmo y en

la figura 4.14 se enseña el AFD.

Nota: El autómata de la figura 4.13 se analizó con las palabras que acepta y no acepta. El
siguiente punto es observar si el AFD transformado cumple también con el mismo análisis
lexicográfico; si no es así, la traducción fue incorrecta.
44 Figura 4.14. AFD resultante del AFND de la figura 4.13

Ejemplo 4.6. Crear un AFD de la siguiente expresión regular:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Para dar solución al autómata presentado fue eficiente el generar un autómata del tipo
AFND-ξ que se muestra en la figura 4.15. En este caso, se crean dos autómatas: el primero
acepta la cadena aa*, el estado inicial se conecta con tal autómata por medio de una transi-
ción cadena vacía al estado q1, y el autómata que acepta la cadena (ab)*(ba)* que se une el
estado inicial con la transición vacío a q2.

Figura 4.15. AFND del ejemplo 4.6

El primer paso dentro del algoritmo (de transformación de un AFND-ξ a AFD) consiste en
separar todas aquellas transiciones que contengan más de un solo carácter. Esto para po-
der obtener una propiedad de unicidad entre transición de un estado a otro. La figura 4.16
muestra el autómata bajo la unicidad de transiciones.

Primer paso. Unicidad de transiciones de un estado a otro.

Figura 4.16. Autómata resultante al aplicar la unicidad de transiciones

Segundo paso. Consiste en obtener una tabla de transiciones de todas aquellas que pue-
45
den ser logradas mediante la cadena vacía. Cabe aclarar que estas transiciones incluyen
todos y cada uno de los estados, ya que para llegar a cada estado por sí mismo, puede ser
realizado mediante el vacío; por lo tanto, todos los estados poseen una transición mediante
el vacío. La tabla 4.5 muestra la función vacío.
Tabla 4.5. Tabla de transiciones resultante de todas aquellas realizadas mediante la
cadena vacía

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Tercer paso. Obtener el nuevo estado inicial del AFD.

Cuarto paso. Consiste en obtener todos los demás estados con base en los caracteres
pertenecientes al lenguaje para conseguir las nuevas transiciones del AFD. El comienzo
va con base en el nuevo estado inicial S, donde debe obtenerse el nuevo estado según el
conjunto de estados de transición por el cual está formado y formando los nuevos estados
sucesivamente.

Como se puede notar en las funciones anteriores, se han obtenido dos nuevos conjuntos
de estados {q3,q4 } y {q5 }, que dan lugar a Q1 y Q2, respectivamente. De esta forma, se van
a ir formando los nuevos estados y transiciones; si alguno de estos conjuntos de estados
pertenecientes al autómata no determinístico vuelve a presentarse en alguna función, no se
genera un nuevo estado en el autómata determinístico, se indica que regresa al estado ya
existente.
46
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Como se puede apreciar en este último caso, se repite nuevamente un conjunto que apare-
ció como resultado con anterioridad. Como se comentó, no se genera un nuevo estado, sino
que se retoma al ya generado.
Véase que ya no existen nuevos estados para procesar, por lo que se pasa a construir el
47
nuevo autómata. Como se mencionó, el nuevo estado inicial es la función vacía del estado
inicial del autómata no determinístico, y para los estados finales se aplica la misma con-
jetura, haciendo estado final del autómata determinístico a todo conjunto de estados que
contenga un estado final del autómata no determinístico.

Una vez cotejados todos los estados y transiciones, se obtiene el autómata mostrado en la
Figura 4.17. De esta manera, se obtiene el nuevo autómata del tipo AFD.

Figura 4.17. Autómata resultante del algoritmo de transformación

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

ANALIZADOR LEXICOGRÁFICO

Un analizador lexicográfico (en inglés scanner) es la primera fase de un compila-

dor, consistente en un programa que recibe como entrada el código fuente de otro programa
(secuencia de caracteres) y produce una salida compuesta de tokens (componentes léxi-
cos) o símbolos. Estos tokens sirven para una posterior etapa del proceso de traducción, lo
que constituye la entrada para el analizador sintáctico (en inglés parser).

La especificación de un lenguaje de programación a menudo incluye un conjunto de reglas

que definen el analizador lexicográfico. Estas reglas consisten comúnmente en expresio-
nes regulares que indican el conjunto de posibles secuencias de caracteres que definirá a
un token o lexema.

En algunos lenguajes de programación es necesario establecer patrones para caracteres

especiales (como el espacio en blanco, tabuladores y saltos de línea) que la gramática pue-
da reconocer sin que constituya un token en sí.
48 Esta etapa está basada usualmente en una máquina de estados finitos y contiene la infor-
mación de las posibles secuencias de caracteres que puede conformar cualquier token que
sea parte del lenguaje (las instancias individuales de estas secuencias de caracteres
son denominadas lexemas). Por ejemplo, un token de naturaleza entero puede contener
cualquier secuencia de caracteres numéricos (Universidad Autónoma del Estado de Hidalgo
[UAEH], 16 de mayo de 2019).

A su vez, el analizador realiza funciones secundarias dentro del compilador en la interfaz del
usuario, como son:

• Eliminar comentarios del programa fuente.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

• Eliminar caracteres como espacios en blanco, caracteres TAB y de nueva

línea (retorno de carro).
• Dentro del analizador es posible generar un contador que muestre el nú-
mero de líneas total del programa o el número de línea en donde se podría
generar un posible error.

Dentro del proceso de un compilador existen tres razones importantes para separar el aná-
lisis léxico del análisis sintáctico:

• Permite tener un diseño sencillo, es decir, separa el análisis léxico del sin-
táctico, lo que por lo general permite simplificar algunas fases posteriores
a estas, ya que con la separación se da origen a un lenguaje más claro y
comprensible.
• Se mejora la eficiencia del compilador. Al tener por separadas ambas fases
permitirá también tener procesos independientes en cada una de ellas. Por
lo tanto, el tiempo que el procesador consume leyendo el programa fuente y
dividirlo en componentes léxicos se puede sustituir con manejo de técnicas
especiales como los buffers.
• La transportabilidad del compilador. Se sabe que cada alfabeto tiene pecu-
liaridades de entrada, entre muchas otras anomalías únicas; estas peculia-
ridades se pueden limitar al analizador léxico para tener una representación
única para los caracteres o cadenas que cumplan con ciertos rubros para
descartarlos o simplemente separarlos.

Para tener una mejor comprensión de lo que es un analizador lexicográfico y cómo se reali-
za, podemos ejemplificarlo de la siguiente manera.

En general, hay un conjunto de cadenas de entrada para las cuales se produce como salida
un componente léxico o token; a este proceso podemos llamar patrón. Se dice que cada
patrón debe coincidir con un componente del conjunto; entonces, un lexema es una secuen-
cia de caracteres, un elemento del léxico con significado referencial en el programa fuente,
49
es decir, aporta a la palabra una idea comprensible con la que concuerda el patrón para un
componente léxico.

Un ejemplo de un lenguaje regular con su autómata finito podrá ser:

L={if, is, for}

El autómata se observa en la figura 4.18:

Figura 4.18

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

La tabla 4.6 muestra el mismo autómata tabulado, lo que se conoce como tabla lexicográfi-
ca. Obsérvese que cada letra del alfabeto se tiene que traducir a un elemento del índice de
la columna y cada fila representa a un estado del AFD.
Tabla 4.6. Tabla lexicográfica
50 En este caso, la idea es tener un archivo en el cual estén las palabras que acepta un anali-
zador lexicográfico. En el ejemplo, la tabla marca el -1 como error y termina el analizador o
se reinicia el estado a cero. Si se llega al estado 7, 8 o 9, la palabra es aceptada y se reinicia
el estado a cero para analizar otra palabra hasta llegar al EOF. Por ejemplo, la figura 4.19
muestra un posible archivo con los siguientes datos, donde ‘\t’ es el tabulador, ‘\n’ es el salto
de línea y EOF es el EndOfFile.
Figura 4.19. Un supuesto archivo con las palabras “for, if, for, is” separados con caracteres
especiales
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

En la primera línea un tabulador muestra la palabra for, tres espacios en blanco y un salto
de línea. En la línea dos se muestran la palabra if, dos tabuladores, la palabra for y un salto
de línea. En la línea tres solo se tiene un salto de línea. En la línea cuatro se tienen dos
espacios en blanco, la palabra is y la marca de fin de archivo (EOF), por lo que el analizador
reconocerá a cada una de las palabras hasta leer el EOF (EndOfFile).

En la parte superior de la tabla lexicográfica se tienen números de equivalencia con respec-

to al alfabeto, esto es, si se lee una ‘f’, su equivalente será el cero, para tener una equiva-
lencia directa con las letras que llegan y el número de columna que corresponda a la tabla
lexicográfica. La función de equivalencia en lenguaje de programación C quedaría de la
siguiente forma:

int transforma(char c){

int x;
switch(c){
case ‘f’: x=0; break;
case ‘i’: x=1; break;
case ‘o´:x=2; break;
case ‘r’:x=3; break;
case ‘s’: x=4; break;
case ‘ ‘:
 case ‘\t’:
51
case ‘\n’
case (char)-1: x=5; break; //EOF
default: x=-1; break;
}
return x;
}

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Se realiza el llenado de la tabla lexicográfica utilizando la propiedad mediante la cual un
pase de parámetros de una matriz se realiza por referencia. Por ello, la función en lenguaje
de programación C quedaría de la siguiente forma:

void Llena_Tabla(int M[7][6]){

int i,j:
for (i=0;i<7;i++)
For (j=0;j<6;j++)
M[i][j]=-1;
M[0][0]=4; M[0][1]=1; M[0][5]=0;
M[1][0]=2; M[1][4]= 3;
M[2][5]=7;
M[3][5]=8;
M[4][2]=5;
M[5][3]=6
M[6][5]=9;
}
52 Así, la función principal podría quedar en pseudocódigo de la siguiente forma:

…
Int A[7][6];
Edo=0;
Llena_Tabla(A);
Realiza{
c=lee_caracter_de_archivo();
x=Transforma(c);
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Si (x== -1){
Escribe(“La letra no pertenece al alfabeto”);
Break;
}
Edo=A[Edo][x];
Si (Edo ==-1){
Escribe(“Error, la palabra no es reconocida”);
Break;
}
Si (Edo>6)
Edo=0; // Se reconoce una palabra correcta y se inicia la lectura de
//una nueva palabra
}mientras(c!=EOF);
}
…

EJEMPLOS DE LENGUAJES QUE NO SON ACEPTADOS POR UN AFD

Ejemplo 4.7: L={w {id, +,*,(,),$}* | w realiza operaciones matemáticas simples con el ope-
rador aditivo, el operador multiplicativo y el operador de agrupación}

Para este lenguaje se colocará un símbolo de fin de cadena que será ‘$’.

El orden lexicográfico de tal lenguaje es:

L={$, id$,(id)$,id+id$,id*id$,(id+id)$,…}
La gramática regular que podría producir todas las cadenas del lenguaje es:
53
L(G)= {(* id {+ U * U ξ } { id U ξ } )* {+ U * U ξ } }* $

(En este ejemplo se utilizan las llaves como operador de agrupación, ya que los paréntesis
pertenecen al propio lenguaje por analizar).

Algunos ejemplos de cadenas aceptadas son:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Para una mejor comprensión, el AFND propuesto queda de la siguiente forma:

L(M):

Una simulación de la ejecución del autómata se muestra en la tabla 4.7:

Tabla 4.7
54 Pareciera ser correcta la expresión regular, por ende, el autómata; desgraciadamente un
autómata finito tiene ciertas restricciones. Por ejemplo, en la tabla 4.8 se acepta la cadena:

id+((id$

Tabla 4.8
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Por ende, la expresión regular no representa en su totalidad al lenguaje y el autómata no

tiene la capacidad de reconocer solo a las cadenas que pertenecen al lenguaje, particular-
mente, el balancear en forma correcta los paréntesis, además de no introducir la capacidad
de dar la prioridad relativa a los operadores. Para eso, se requiere un elemento matemático
más poderoso que se estudiará en los siguientes capítulos.

Ejemplo 4.8. Realizar la expresión regular y el autómata finito de los siguientes lenguajes.
En el lenguaje L1, para poder escribir la expresión regular y el autómata finito se requirieron
55
un finito número de elementos, por lo que el lenguaje es regular.

El lenguaje L2 requiere un infinito número de elementos (por ejemplo, un infinito número de

estados en el AFND), por lo que el lenguaje no es regular, es un lenguaje libre de contexto.
Obsérvese la pequeña diferencia entre los dos lenguajes.

Teorema. Un lenguaje es regular si y solo si es aceptado por un autómata de estado

finito.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

56 CAPÍTULO V.

GRAMÁTICAS FORMALES

INTRODUCCIÓN

En esta sección se explican, de forma general, las gramáticas formales y, de manera parti-
cular, las gramáticas libres de contexto, sobre las cuales se basa el análisis sintáctico.

Recordando el capítulo de los lenguajes regulares, las expresiones regulares permiten una
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

repetición no contable de caracteres, el análisis de la cadena es lineal y no existe una res-

tricción de la repetición. Obsérvese el ejemplo 5.1.
Ejemplo 5.1. Para el siguiente lenguaje:

L= {w(a,b)*|w tiene un número indeterminado de letras a y después un número indetermi-

nado de b}

El ordenamiento lexicográfico del lenguaje queda de la siguiente forma:

L={ξ,a,b,aa,bb,ab,aaa,bbb,abb,aab,aaa,bbb,…}

donde L(G)=a*b*

L(M):

Sin embargo, una expresión regular no puede representar el siguiente lenguaje:

L= {w (a,b)*|anbn, n≥0}

donde el ordenamiento lexicográfico del lenguaje queda de la siguiente forma:

L={ξ,ab,aabb,aaabbb,aaaabbbb,…}

Este lenguaje requiere una contabilidad de letras a y posteriormente compararla con una
contabilidad de letras b.

Las gramáticas libres de contexto tienen esta y otras virtudes que permiten realizar el análi-
sis sintáctico de un lenguaje imperativo.

DEFINICIÓN DE GRAMÁTICAS

Se utilizará el alfabeto griego para expresar una cadena de caracteres pertenecientes a

algún alfabeto. El símbolo del alfabeto griego incluye a la cadena vacía.
57
Se usará la notación Bacus Naur (Bacus Naur Form, BNF), la cual es un metalenguaje para
describir lenguajes formales.

John Backs, un diseñador de lenguajes de programación de IBM, adoptó las reglas genera-
tivas de Chomsky para describir la sintaxis del nuevo lenguaje de programación IAL, cono-
cido en la actualidad como ALGOL 58 (1959).

Peter Naur, en su reporte sobre ALGOL 60 de 1963, identificó la notación de Backus como
la forma normal de Backus (Backus Normal Form), y la simplificó para usar un conjunto de
símbolos menor; no obstante, a sugerencia de Donald Kunth, su apellido fue agregado en

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

reconocimiento a su contribución, por lo que la palabra normal fue reemplazada por Naur.

Para definir gramática primero se determinará lo que es una regla en el campo de los len-
guajes formales.

• Regla. Expresión de la forma:

α→β

Tanto α como β son cadenas de símbolos en donde pueden aparecer elementos del alfabeto
Σ (llamados constantes o símbolos terminales) o símbolos nuevos (denominados variables
o símbolos no terminales). El símbolo “” representa producción. Por lo tanto, la expresión
anterior puede leerse como “alfa produce a beta”, es decir, en la cadena donde aparezca la
subcadena que representa “alfa” se reemplaza por la subcadena que representa a “beta”.
Por ende, una gramática, básicamente, es un conjunto de reglas.

DEFINICIÓN DE GRAMÁTICA

Una gramática es una cuádrupla de la forma:

G=(V,T,S,P)

donde

• Conjunto finito de símbolos no-terminales V.

• Conjunto finito de símbolos terminales T.
• Símbolo inicial y pertenece a V, S.
• Conjunto de producciones o reglas de derivación P.

De esta forma, la gramática de los lenguajes formales está formada con símbolos del voca-
bulario terminal . Este tipo de vocabulario se define por enumeración de los símbolos termi-
nales (Cueva Lovelle, 2001).
58 El vocabulario no-terminal V es el conjunto de símbolos introducidos como elementos au-
xiliares para poder definir la gramática. No figuran en la sentencia establecida y es definido
por enumeración de los símbolos no-terminales (Cueva Lovelle, 2001).

El símbolo inicial S es un símbolo no-terminal, el cual da inicio a aplicar las reglas de la gra-
mática para obtener las distintas cadenas del lenguaje (Cueva Lovelle, 2001).

Las producciones P son el conjunto de reglas que deben aplicarse desde el símbolo inicial
para obtener las cadenas del lenguaje. El conjunto se define con base en las enumera-
ciones de las distintas producciones, en forma de reglas o mediante un metalenguaje, por
ejemplo, BNF (Backus Naur Form) o EBNF (Extended Backus Naur Form) (Cueva Lovelle,
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

2001).

JERARQUÍA DE LAS GRAMÁTICAS

En 1956, Noam Chomsky publica Three models for the description of language, un trabajo
en el que se describen las propiedades de los tipos de lenguajes formales y correspondien-
tes gramáticas en relación con su complejidad computacional.

Chomsky definió cuatro tipos de gramáticas en función de sus reglas de derivación. Su

clasificación inicia con el tipo de gramáticas que pretenden ser universales, y aplicando las
debidas restricciones a sus reglas de derivación es como se obtienen los otros tres tipos de
gramáticas (Cueva Lovelle, 2001).

La Figura 5.1 muestra la clasificación de lenguajes determinada por Chomsky dentro del
universo de los lenguajes.

Figura 5.1. Clasificación de lenguajes según Chomsky (imagen de Google)

Gramática tipo 0

También llamadas gramáticas no restringidas o gramáticas con estructura de frase, son un

tipo de gramáticas más generales, por lo que también adquieren el nombre de gramáticas
sin restricciones. Esto quiere decir que las producciones pueden ser de cualquier tipo per-
59
mitido (Navarrete Sánchez et al., 2008).

Las gramáticas de tipo 0 son de la forma:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Es decir, la única restricción se halla en que no puede haber reglas de la forma:

ξ→β

donde ξ es la cadena vacía.

Este tipo de gramáticas generan lenguajes recursivamente enumerables que son aceptados
en la máquina de Turing (recuérdese que el autómata puede ser del tipo determinístico o no
determinístico) (Padilla Beltrán, 2006).

Gramática tipo 1

También son conocidas como sensibles al contexto y sus reglas de producción son de la
forma:

Generalmente, son llamadas sensibles al contexto porque se puede reemplazar por siem-
pre y cuando se esté en el contexto α…β.. Por lo tanto, las producciones de tipo:

S→γ

Son aceptadas siempre y cuando no pertenezca a la parte derecha de ninguna de las reglas
de producción (recuérdese que S es el símbolo de inicio) (Navarrete Sánchez et al., 2008).

Otra forma de ver las reglas de producción es especificando que una variable A puede ser
reemplazada por γ en una derivación directa, cuando A aparezca en el contexto de α y β.
60 Por esta última característica son llamadas sensibles al contexto (Navarrete Sánchez et al.,
2008). Cabe aclarar que en este tipo de producciones en la parte izquierda siempre tienen
una longitud menor o igual que en la parte derecha, pero nunca mayor; por lo tanto, es una
gramática no contráctil. La única excepción presente es el caso ya visto:

S→γ

Gramática tipo 2

Se denominan gramáticas libres de contexto. Estas solo permiten tener un símbolo no-ter-
minal en la parte izquierda de su producción, mientras que en la parte derecha puede ser
una combinación entre terminales y no-terminales, es decir, son de la forma:
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Las producciones obtenidas por este tipo de gramáticas son aceptadas por los autómatas
de tipo pila. Se denominan libres de contexto porque pueden cambiar A por α, independien-
temente del contexto en que aparezca (Padilla Beltrán, 2006).

Gramática tipo 3

También llamadas regulares, comienzan sus reglas de producción por un símbolo terminal,
el cual puede llegar a ser seguido por un símbolo no-terminal.

Existen dos tipos:

Lineales por la derecha. Todas sus producciones son de la forma A→bC

donde

Lineales por la izquierda. Todas sus producciones son de la forma A→Cb

donde

Este tipo de lenguajes tiene un símbolo no-terminal en el lado izquierdo de la producción,

mientras que en el lado derecho debe contener una cadena formada por símbolos termina-
les y no-terminales. Como máximo debe tener un no-terminal, el cual debe estar del lado
61
derecho o izquierdo de la cadena (Padilla Beltrán, 2006).

Se pueden generar todas y cada una de las palabras de un lenguaje regular utilizando gra-
máticas regulares. Para verificar si una palabra pertenece a un lenguaje regular se requiere
de un autómata finito.

Se pueden generar todas y cada una de las palabras de un lenguaje libre de contexto utili-
zando gramáticas libres de contexto. Para reconocer si una palabra pertenece a un lenguaje
libre de contexto se requiere de un autómata tipo pila.

Se pueden generar todas y cada una de las palabras de un lenguaje sensible al contexto

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

utilizando gramáticas sensibles al contexto. Para reconocer si una palabra pertenece a un
lenguaje sensible al contexto se requiere de una máquina de Turing.

Como es posible apreciar, y según lo mencionado hasta el momento, los diferentes tipos
de autómatas (sean determinísticos o no-determinísticos) aceptan alguno de los tipos de
lenguajes manejados por Noam Chomsky, dentro de los cuales se han basado los análisis
lexicográficos y sintácticos que han permitido y han dado paso a la resolución de diversos
problemas presentes dentro del mundo de la computación, y más apegados a los compi-
ladores que permiten el interactuar con los ordenadores con base en instrucciones en un
lenguaje más comprensible para todos, y no solo según aquel que la máquina comprende.

El principal objetivo de Chomsky y su jerarquía era demostrar que los dos primeros tipos de
gramáticas son incapaces de dar cuenta, de manera simple y general, de la complejidad de
las lenguas naturales (Gallego, 2008).

GRAMÁTICAS REGULARES

Las gramáticas regulares son aquellas reconocidas por un autómata finito; el lado derecho
de la producción debe contener símbolos terminales y un símbolo no terminal (solo uno) a
la izquierda o derecha de la producción.

Como ya se comentó, existen dos tipos de gramáticas regulares:

• Lineales a la derecha: En el lado derecho de las producciones el símbolo no termi-

nal aparece a la derecha del símbolo terminal, ejemplo:

L={w {a,b}* | w tiene par de letras a}

El orden lexicográfico del lenguaje es:

L={ξ,b,bb,aa,bbb,aab,aba,baa,…}
62 La expresión regular que representa el lenguaje es:

L(G)=b*(ab*ab*)*

La gramática regular lineal por la derecha se define como:

G={{A,B,C,D},{a,b},{A},P}
P:
A→bA|B|ξ
B→aC
C→bC|aD
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

D→bD|E
E→B|ξ

Por medio de esta gramática se producirá la cadena “baababa”.

A→bA→bB→baC→baaD→baabD→baabE→baabB→baabaC→baababC→ baaba-
baD→baababaE→ baababa ξ

(En este ejemplo se ve claramente la producción lineal de una gramática regular).

Obsérvese lo siguiente:

B→bB| ξ es equivalente al operador Kleene star ( b* )

• Lineales a la izquierda: En el lado derecho de las producciones el símbolo no termi-
nal aparece a la izquierda del símbolo terminal, ejemplo:

L= {a,b}*|w tiene solo cadenas de letras a o solo cadenas de b}

L={ ξ,a,b,aa,bb,aaa,bbb,…}

La expresión regular queda de la siguiente forma:

L(G)=a* Ub*

La gramática regular lineal por la izquierda se define como:

G={{S,A,B},{a,b},S,P}

P:

S→A|B|ξ

A→Aa| ξ

B→Bb| ξ
Obsérve que la producción S → A|B equivale al operador en una expresión regular.
63
Otro ejemplo es:

L=(ab U aba)*

donde la cadena abababa se produce de la siguiente forma:

{abababa}=> ()3=(ab)(ab)(aba)

Las reglas de producción de la gramática lineal derecha quedan de la siguiente forma:

P:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

A->B|C|ξ
B->abB|A
C->abaC|A

La cadena anterior se crea de la siguiente forma:

A->B->abB->ababB->ababA->ababC->abababaC->abababaA->abababa ξ

Como se observó, las gramáticas regulares son las gramáticas más laxas de la clasificación
de gramáticas dada por Chomsky.

GRAMÁTICAS LIBRES DE CONTEXTO

Las gramáticas libres de contexto fueron muy importantes para los compiladores en los
años cincuenta y sesenta, y aún en la actualidad tienen una gran importancia en los ámbitos
de XML y DTD (Document Type Definition).

Una gramática libre de contexto es un conjunto formado por cuatro partes “G = {V, T, S, P}”,
donde:

• P son las producciones que la forma F  α, donde F es un carácter del alfabeto no

terminal y α un conjunto de símbolos tanto terminales como no terminales o cadena
vacía.

Algunos libros de teoría de computación colocan un quinto símbolo:

Σ = T V, donde T= Σ – V o V = Σ – T. Las gramáticas libres de contexto, grosso modo,

permiten:

1) Analizar lenguajes que tienen un balance de caracteres.

2) Poder llevar una prioridad relativa con respecto a los operadores aritmé-
ticos que pertenecen un lenguaje en particular, si estos existen.
64 Para comprender mejor la idea del balance de caracteres se tiene el ejemplo 5.2.

Ejemplo 5.2. Dado el siguiente lenguaje, hacer su gramática libre de contexto.

L={w {(,)}*|w tiene los paréntesis balanceados en forma algebraica}

Un análisis lexicográfico del lenguaje nos permite observar que las siguientes palabras son
válidas:

L={ ξ,(), ()(), (()),()()(),(())(), ()(()),. . . , ()(())(())(),….}

Palabras que no pertenecen al lenguaje pueden ser:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

{(,), )(, ((, )), ()(, ()), …} L

La gramática es la siguiente:
G={S,{(,)},S,P}
P:

S→ξ

S→ SS

S→(S)

La producción continua S → SS permite crear paréntesis concatenados. Por ejemplo:

S->SS->SSS->(S)SS->(S)(S)S->(S)(S)(S)->()()()()

La producción continua S → (S) permite crear paréntesis anidados. Por ejemplo:

S->(S)->( (S) )->(( (S) ))->((()))

Otra forma de representar las reglas de producción es por medio de un árbol de derivación,
el cual para la gramática dada con la palabra ()((())())() se muestra en la figura 5.2:

Figura 5.2. Árbol de derivación del ejemplo 5.2

En este ejemplo se observa el balance que existe entre los paréntesis que abren y que
65
cierran, lo cual es imposible para una gramática regular. Esta gramática sencilla nos repre-
senta, en forma general, la estructura de un lenguaje imperativo. Obsérvese la figura 5.3:

Figura 5.3. Una suposición de bloques de un lenguaje imperativo cualquiera

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Lo que representa la figura 5.3 puede ser el esqueleto de un programa cualquiera, y con
imaginación nos muestra el inicio y fin de una función. Dentro de la función se tiene un while
y dentro del while un if y un for. Esto nos da una simple cadena representada de la siguiente
forma:

{{{}{} }}

Como se puede apreciar en este simple ejemplo, un programa de lenguaje imperativo, sin
importar lo grande que sea, solo forma una palabra perteneciente a un lenguaje libre de
contexto.

Recursividad

Si se piensa que un lenguaje de programación permite crear un número infinito de progra-

mas, se podría creer que haría falta una infinidad de reglas para una especificación sintác-
tica. No obstante, hay un concepto que permite reconocer infinitos lenguajes con un finito
número de reglas: recursividad.

La recursividad se expresa por medio de una o más reglas no recursivas que son la base
y una o más reglas que son recursivas, las cuales permiten hacer crecer la estructura del
lenguaje aplicándose a sí mismas una y otra vez.

Una gramática se llama recursiva si es de la forma:

A→αAβ

donde α y β es una cadena con terminales y no terminales. Pueden ser la misma cadena
vacía. Si α es la cadena vacia, se conoce como recursividad hacia la izquierda. Si β es la ca-
66 dena vacía, entonces se conoce como recursividad hacia la derecha (Ruiz Catalán, 2010).

Tipos de gramáticas libres de contexto

Las gramáticas libres de contexto pueden ser recursivas ambiguas o recursivas tanto iz-
quierdas como derechas. Para explicar tales gramáticas se utilizará como ejemplo el si-
guiente lenguaje:

L={w {id,+}*|w forma cadenas de expresiones algebraicas correctas}

donde el orden lexicográfico es:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

L={id,id+id,id+id+id,…}

GRAMÁTICA RECURSIVA AMBIGUA

Se dice que una gramática es recursiva ambigua cuando existe una cadena ∑* que tenga
más de un árbol de derivación, es decir, una cadena se puede generar a su vez por más de
un árbol de derivación.

Para el lenguaje anterior la gramática libre de contexto es:

G={E,{id,+},E,{E → E+E|id}

En la figura 5.4 se muestran dos casos de derivación de la cadena id1 +id2 + id3 para ejem-
plificar el caso de derivación ambigua.

Figura 5.4. Dos derivaciones de la cadena id1 +id2 + id3 por una gramática
recursiva ambigua

La generación del árbol es fácil, pero no mantienen ninguna prioridad de operadores. Al

recorrer el árbol en postorden se tienen diferentes formas de evaluación de la misma expre-
sión. Si se utiliza una pila de datos para evaluar las expresiones, la evaluación del primer
árbol se realiza de la siguiente forma:
1. Introducir id0 y posteriormente id1 a la pila.
67
2. Se obtiene la suma de los dos últimos elementos que están en pila.

R0=id0+id1

Y se introduce R0 a la pila.

3. Se introduce id2 a la pila.

4. Se obtiene la suma de los dos últimos elementos localizados en pila.

R1=R0+id2
5. Se coloca R1 en pila.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Como resultado de estas operaciones, se realiza la suma de id0 a id2.
Ahora veamos la evaluación del segundo árbol:

1. Se introducen al árbol id0 id1 id2.

2. Se realiza la suma de los dos elementos que están en tope de pila

R0=id1 + id2.

3. El resultado R0 se guarda en pila.

4. Se realiza la suma de los dos elementos que se guardan en tope de pila

R1=id0 + R0.
5. El resultado R1 se guarda en tope de pila.

Para el caso de la suma, en la prioridad relativa, al encontrarse más de una suma en la

expresión se realizará la evaluación de izquierda a derecha. El primer árbol obedece a la
prioridad antes indicada, pero el segundo árbol no la obedece, ya que la suma la realiza de
derecha a izquierda. Como se puede observar, una gramática ambigua produce más de una
forma de evaluar una expresión, lo que genera un conflicto de prioridades.

Por ello, una gramática libre de contexto recursiva ambigua no sirve para desarrollar un
compilador en forma eficiente.

GRAMÁTICA RECURSIVA DERECHA

Para restringir el número de opciones para derivar una cadena la gramática libre de contexto
tiene dos tipos de derivaciones: la derivación a la izquierda siempre reemplaza la variable
más a la izquierda por uno de los cuerpos de sus producciones, sin embargo, la derivación
a la derecha reemplaza la variable más a la derecha por uno de sus cuerpos de sus produc-
ciones
68 Un ejemplo de gramática recursiva derecha será:

ET+E
ET
Tid

En la figura 5.5 se observa el árbol de derivación para la cadena id0 + id1 + id2 + id3+id4:

Figura 5.5. Creación de árboles de una gramática recursiva derecha

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Si se recorre el árbol de una gramática recursiva derecha en postorden, el resultado es el

siguiente:

Id0 id1 id2 id3 id4++++

Otra forma de revisar la prioridad relativa es transformar una operación en postorden a

inorden. Al tenerse una notación en postorden, para transformarse en inorden, se recorren
todos los identificadores hasta hallar al primer operador. Al localizar el primer operador se
colocará en inorden en el primer identificador que se localice a la izquierda colocándose un
paréntesis que envuelve al operador y los dos operandos circunstantes. Se repite el proce-
so hasta que no haya operadores por examinar. En tal caso, de la expresión en postorden
id0id1id2id3id4++++ se transforma a inorden de la siguiente forma:
id0id1id2(id3+id4)+++
id0id1(id2+(id3+id4))++
id0 (id1+(id2+(id3+id4)))+
id0+(id1+(id2+(id3+id4)))

La primera operación por realizar será la que tenga el paréntesis más anidado; por lo tanto,
la primera suma será id3+id4. Posteriormente, ese resultado se sumará a id2, su resultado
acumulado se sumará a id1 y al final el resultado se sumará a id0. Obsérvese que las opera-
ciones se realizarán de derecha a izquierda.
Al momento de hacer la ejecución de la expresión en postorden no se mantiene la prioridad
69
de la suma de la evaluación de izquierda a derecha.

Enseguida se muestra un ejemplo sencillo de una gramática recursiva izquierda:

EE+T
ET
Tid

En la figura 5.6 se observa el árbol de derivación para la cadena id0 + id1 + id2 + id3+id4.

Figura 5.6. Creación de árboles de una gramática recursiva izquierda

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Si se recorren los árboles de una gramática recursiva izquierda en postorden, el resultado
es el siguiente:

id1id2+id3+id4+
Al transformar la expresión a inorden queda de la siguiente forma:
(id1+id2)id3+id4+
((id1+id2)+id3)id4+
((id1+id2)+id3)+id4

Realizando las operaciones con respecto al paréntesis más anidado, se tienen las siguien-
tes sumas: primero se evalúa id1+id2. A este resultado se le suma id3, y después se le suma
id4, con lo cual se obtienen las operaciones de izquierda a derecha.

Al momento de hacer la ejecución de la expresión en postorden, se mantiene la prioridad de

la suma de la evaluación de izquierda a derecha. Por tanto, en compiladores se emplea la
recursividad izquierda para mantener la prioridad de los operadores.

De esta forma una gramática libre de contexto recursiva izquierda tiene dos ventajas con
respecto a una expresión o gramática regulares:
70 • Permite generar todas las cadenas del tipo anbn o estructura semejante,
como ya se comentó anteriormente.
• Permite el manejo de las prioridades relativas de los operadores
algebraicos.

Para una mayor comprensión de las prioridades relativas se realizará el ejemplo 5.3 con una
gramática clásica que aparece en todos los libros que versan sobre compiladores; en este
ejemplo se manejan los operadores de suma, multiplicación y agrupación.

Ejemplo 5.3. Realizar la gramática del siguiente lenguaje:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

donde P es:

E E+T
E T
T T*F
T F
F (E )
F id

Las prioridades absolutas de los operadores involucrados en la gramática antes indicada

son:

Primero. El operador de agrupación (los paréntesis).

Segundo. Los operadores multiplicativos (*, /, %).

Tercero. Los operadores aditivos (+,-).

Sin embargo, las prioridades relativas se definen conforme a:

• El operador de agrupación. Se observará que entre mayor prioridad tenga el

operador más profundo se localiza en las reglas de producción.
• Si existen dos operadores de la misma prioridad en forma continua, se rea-
lizan las operaciones de izquierda a derecha. Por ejemplo, id1 + id2 + id3,
primero se realizará la operación id1 + id2 y el resultado se sumará a id3.

Un ejemplo de la prioridad relativa se muestra en la figura 5.7:

 Figura 5.7. Prioridades relativas para expresión id0+(id1+id2)*id3
71

Obsérvese que la prioridad relativa indica que primero se debe sumar id1 con id2. Posterior-
mente, ese resultado se debe multiplicar con id3 y al final este total se debe sumar a id0. En
un árbol sintáctico, entre mayor prioridad relativa tenga el operador más profundo se encon-

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

trará en el árbol. En la figura 5.8 se observa el árbol sintáctico de la expresión anterior con
la gramática del ejemplo 5.3:

Figura 5.8. Árbol recursivo izquierdo de la figura 5.7

La expresión, al recorrer el árbol en postorden, queda de la siguiente forma:

id0 id1 id2 + id3 * +

Véase que en la notación en postorden no requiere de paréntesis y la prioridad de los ope-

radores se mantiene. En este caso, simulando una pila de datos, las operaciones quedan
de la siguiente forma:

Introducir a pila id0.

Introducir a pila id1.
Introducir a pila id2.
72 Sumar dos elementos en tope de pila y colocar el resultado en tope de pila

Introducir a pila id3.

Multiplicar dos elementos en tope de pila y colocar el resultado en tope de pila.

Sumar dos elementos en tope de pila y colocar el resultado en tope de pila. Ejecutando las
instrucciones, la pila se comporta de la siguiente manera:
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Con el lenguaje y la gramática recursiva izquierda del ejemplo 5.3, se muestra la prioridad
relativa, el árbol sintáctico y su operación en postorden.

Ejemplo 5.4. Otra expresión algebraica se muestra a continuación en la figura 5.9:

Figura 5.9. Prioridades relativas para expresión: id0*((id1+id2)*id3)

donde su árbol sintáctico se muestra en la figura 5.10.

Figura 5.10. Árbol sintáctico de la figura 5.9

Al recorrer el árbol sintáctico en postorden se obtiene la siguiente expresión:
73
Id0 id1 id2 + id3 * *

La simulación por medio de una pila de la expresión en postorden queda de la siguiente

forma:

Introducir a pila id0.

Introducir a pila id1.
Introducir a pila id2.

Sumar dos elementos en tope de pila y colocar el resultado en tope de pila.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Introducir a pila id3.

Multiplicar dos elementos en tope de pila y colocar el resultado en tope de pila.

Multiplicar dos elementos en tope de pila y colocar el resultado en tope de pila. La simula-
ción de las operaciones de la pila queda de la siguiente forma:

Ejemplo 5.5. Teniendo la siguiente gramática libre de contexto:

PROGRAMA → procedimiento ENCABEZADO CUERPO
ENCABEZADO → IDENTIFICADOR es
CUERPO → DECLARACIONES BLOCK
DECLARACIONES → IDENTIFICADOR: entero; DECLARACION
| IDENTIFICADOR: entero;
BLOCK → begin ENUNCIADOS end.
ENUNCIADOS → ENUNCIADO;
| ENUNCIADO; ENUNCIADOS
ENUNCIADO → ENUNCIADO_ASIGNACION
| ENUNCIADO_FOR
| ENUNCIADO_IF
| ENUNCIADO_INPUT
| ENUNCIADO_OUTPUT
| ENUNCIADO_NULO
ENUNCIADO_ASIGNACIONIDENTIFICADOR := EXPRESION
74 ENUNCIADO_FOR → for IDENTIFICADOR in CONSTANT to CONSTANT
loop
ENUNCIADOS
endloop
ENUNCIADO_IF → if EXPRESION then ENUNCIADOS
else ENUNCIADOS
endif
ENUNCIADO_INPUT → input (IDENTIFICADOR)
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

ENUNCIADO_OUTPUT → output (IDENTIFICADOR)

ENUNCIADO_NULO → ξ
EXPRESION → EXPRESION ADD_OP TERM | TERM
TERM → TERM MULT_OP FACTOR | FACTOR
FACTOR → IDENTIFICADOR | ( EXPRESION)| CONSTANT
IDENTIFICADOR → a|b|c|d|…|z
ADD_OP → +|-
MULT_OP →*|/
CONSTANT → DIGITO | DIGITO CONSTANT
DIGITO → 0|1|2|3|…|9

Hacer el parser y recorrerlo en postorden para el siguiente programa:

Procedimiento a es
b:entero;
c:entero;
begin
input(b);
input( c );
c=b*c*(b-c);
output ( c );
end.

Primero se realiza una tabla de equivalencias y se transforma la gramática para que la es-
critura del árbol sea más ligera.
 75

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

P→ pEC

EN →I es

C→DB

D →I ; en ; D | I : en;

B → b E’s e.

E’s → E | E; E’s

E→ E_A | E_F | E_IF | E_IN | E_O | E_N

E_A→ I := EX

E_FOR→ f I i CONST t CONST l E’s el

E_IF→ if EX th E’s ee E’S ei

E¬_IN→in( I )

E_O→o ( I )

E_N→ξ
76 EX→ EX A T | T

T→TMF|F

F → I | ( EX) | CONST

I→a|b|c|d|…|z

A→ +|-

M → *|/

CONST → DIG | DIG COST

DIG → 0|1|2|3|…|9
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Con la gramática reducida, el parser queda de la siguiente forma:

Figura 5.11. Árbol sintáctico del código indicado en el ejemplo 5.5

Al recorrer en postorden, el programa queda de la siguiente forma:

p id es id : en ; id : en ; b in id ; in id ; c := id id + o id e.

Para el analizador sintáctico cada token es una letra de su abecedario y el programa com-
pleto es una palabra de su lenguaje.
 CAPÍTULO VI. 77
AUTÓMATAS TIPO PILA

INTRODUCCIÓN

En el capítulo sobre gramáticas, específicamente en torno a las gramáticas libres de contex-

to se indicaron dos ideas muy importantes:

• Pueden crear todas las cadenas del tipo anbn.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

• Una gramática recursiva izquierda permite manejar las prioridades relativas
de los operadores algebraicos.

Para poder manejar estos dos elementos se requiere un autómata de estado finito con ca-
pacidad de memoria. Esta memoria puede manejarse como una pila. Por ejemplo, para el
lenguaje:

Como se observó anteriormente, su gramática es simple:

S→aSb|ξ

Su autómata es un poco más complejo, ya que no es la expresión regular.

a *b *

El autómata para la expresión regular se muestra en la figura 6.1:

Figura 6.1. Autómata finito para la expresión regular a*b*

El autómata no puede determinar cuántas letras b con respecto a las a han llegado; sin em-
bargo, ¿qué sucede si al autómata le colocamos una memoria de tipo pila?

En la tabla 6.1 se muestra una simulación con el autómata y una memoria tipo pila:
78 Tabla 6.1. Autómata de la figura 6.1 usando una pila como memoria de apoyo
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Como se observa, la estrategia es la siguiente: por cada a que se lea de la cadena, se co-
loca en la pila. Por cada b que se lea de la cadena, se revisa si existe una a en la pila para
su eliminación. Al momento de leer todos los elementos de la cadena, si la pila está vacía,
indica que la cadena estuvo balanceada de letras b con respecto a las a. A este autómata
se le llamará tipo pila.

Del lenguaje se puede derivar cantidad de lenguajes que tienen una pro-
piedad semejante. Una estrategia para poder obtener el autómata tipo pila es realizar un
análisis relajado de una expresión regular (en este caso, fue a*b*) proponiéndose un AFD,
después se analiza del uso de la pila para cumplir con el balance solicitado de elementos.

Lema. Cada lenguaje libre de contexto es aceptado por un autómata tipo pila (Lewis y
Papadimitriou, 1998).

DEFINICIÓN DE UN AUTÓMATA TIPO PILA

Un autómata tipo pila es una 6-tupla, de la forma AP=(Q,Σ,Γ,Δ,q0,F).. Cada elemento se

define como:

• Q es el conjunto finito de estados.

• Σ es el alfabeto finito de entrada de la cadena.
• Γ es el alfabeto que pertenece a la pila.
• Δ es la función de transición.
• q0 es el estado inicial.
• F es el conjunto de estados finales.

La función de transición se define como se muestra en la figura 6.2.

 Figura 6.2. Definición de la función de transición en los autómatas tipo pila
79

Los autómatas tipo pila son básicamente un autómata finito con control sobre los elementos

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

de entrada y sobre la pila (o stack) que posee una capacidad infinita; de igual forma, los
lenguajes generados por las gramáticas libres de contexto son aceptados en los autómatas
tipo pila (Campos, 1995).

Los autómatas tipo pila o AP son autómatas finitos que pueden ser determinísticos o no
determinísticos con transición ξ. El hecho de tener una pila dentro de un autómata permite
dar la capacidad de “recordar” toda la información que pasa a través del mismo autómata.
Una de las desventajas presentes en los AP recae en la misma capacidad que tiene de
almacenar de forma infinita información dentro de la pila, ya que solo puede acceder a la
información disponible en su pila según esta sea manipulada. Al ser una pila una estructura
del tipo LIFO (last-in, first-out), solo podrá manipular el último elemento que accedió al AP.

De manera informal, es posible interpretar un AP como un dispositivo, como se muestra en

la figura 6.3. En dicha imagen se logra leer claramente la funcionalidad de un simple autó-
mata finito, donde se tiene una entrada de datos, un control de entrada de datos, el cual lee
el dato que accedió y valida si es aceptado o no dentro de la máquina. Dentro de los AP lleva
una máquina de estados apilada, la cual define la próxima transición con base en el estado
actual (Hopcroft, Motwani y Ullman, 2007).

Figura 6.3. Autómata tipo pila es un autómata finito con una estructura de datos de pila
80 En los AP se tiene el siguiente comportamiento:

• Consume el símbolo de entrada en la transición. Si se llega a utilizar el sím-

bolo ξ, no se consume ningún símbolo.
• Pasa al nuevo estado, el cual puede o no ser el mismo que el estado ante-
rior.
• Reemplaza el símbolo de la parte superior de la pila con cualquier cadena.
La cadena puede ser desde la cadena vacía.

Los AP, al igual que los autómatas finitos, poseen una notación gráfica, donde en cada nodo
existe una transición del tipo “ω/α/β”:
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

• ω es la entrada de caracteres que consume el autómata.

• α es lo que va a salir de la pila.
• β es lo que va a entrar a la pila.

La figura 6.4 muestra un ejemplo en las diversas variaciones que existen en los tipos de
transición de cada autómata y cómo varían en los que son del tipo pila.

Figura 6.4. Diferencia gráfica en las transiciones de un autómata finito y un

autómata tipo pila

Los AP, al igual que los autómatas finitos, poseen estados finales, los cuales permiten distin-
guir que la palabra de entrada es aceptada correctamente. Para que una palabra de entrada
sea aceptada debe cumplir las siguientes condiciones:

• La palabra debe haber sido consumida en su totalidad.

• El AP debe encontrarse en un estado final.
• La pila debe estar vacía.
Ejemplo 6.1. Se tiene el lenguaje L={anbn |n≥1}
81
donde un orden lexicográfico es:

L={ab, aabb, a3b3, a4b4,…}

En primer lugar, se puede señalar que con este lenguaje es casi imposible intentar construir
un autómata finito, ya que estos no cuentan con la capacidad para contar el número de
elementos que son insertados. Por ello, es necesario hacer uso de un AP. Una vez aclara-
do, véase el grafo resultante de AP, el cual se muestra en la figura 6.5. El autómata que se
visualiza no es la solución final, ya que hace falta definir las entradas y salidas de la pila.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Figura 6.5. Primer esquema del autómata para el ejemplo 6.1

Una vez que se tiene este esquema, es necesario tener en cuenta cuáles serán los elemen-
tos que entrarán al autómata, qué se espera que exista en la pila y cuál sería el resultado
final en la pila. Como es posible apreciar, se tienen los estados q0 y q1, donde q1 además de
ser el último estado, también es el estado de aceptación de la cadena.

Con este esquema de los AP es necesario tener en cuenta la pila en todo momento; para
ello, se debe mantener un identificador, el cual nos dé el estado actual de la pila, cuando se
encuentre vacía. Este identificador se definirá como cadena vacía. De esta forma, es posible
comenzar con la construcción del autómata.

Para este tipo de autómatas, su función va con base en la pila; por ello, y a partir del ejem-
plo, es necesario verificar y validar el estado de la pila para utilizar la siguiente transición,
ya que estas dependen del estado actual de la pila. El autómata se muestra en la figura 6.6.
82 Figura 6.6. Autómata tipo pila para el ejemplo 6.1
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Como ejemplo, se tratará de validar la cadena “aabb”. Como el primer elemento en entrar
a la pila es una a, se tiene en cuenta que la pila en ese momento está vacía. La figura 6.7
muestra el comportamiento tras la entrada del primer elemento al AP.

Figura 6.7. Reacción del autómata tipo pila luego de introducir el primer elemento

Si se vuelve a introducir otra "a", la pila queda como se muestra en la figura 6.8.

Figura 6.8. Movimientos realizados en la pila tras la introducción de otro elemento

Como se aprecia, el estado de la pila comienza a cambiar según el número de elementos
83
que se introduzcan a ella y sigue apilándolos mientras más "a" sean introducidas. Pero
ahora, si se lee una “b", el procedimiento cambia, ya que se debe verificar que en la pila
exista algo más que un elemento vacío, y con base en el ejemplo que estamos trabajando,
se espera que exista una “a" dentro de la pila. El procedimiento se muestra en la figura 6.9,
donde por cada lectura de una “b", en la pila debe encontrarse una ”a", la cual es eliminada
de la pila.

Figura 6.9. Al introducir un elemento a la pila, una se saca de la pila

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Con la transición que se mencionó anteriormente, ahora se encuentra el autómata en el
estado q2, el cual es el estado final y el estado de aceptación de la cadena. Como se apre-
cia, aún se cuenta con un elemento en la pila tras el ejercicio que se está llevando a cabo
y, como se mencionó con anterioridad, el estado de aceptación solo es válido hasta que se
hayan consumido todos los elementos de la cadena y que la pila se encuentre vacía.

Si recordamos, el lenguaje marca que debe ser el mismo número de entradas de a y b; por
ello, en el estado final es necesario aplicar el mismo criterio de la transición anterior. De esta
forma, se obtiene el resultado mostrado en la figura 6.10.

Figura 6.10. Resultado final de la pila y el autómata

84 Ya logramos visualizar el funcionamiento de los AP, los cuales se encuentran ampliamente
relacionados con los lenguajes libres de contexto (LLC), ya que los AP aceptan exactamente
a los LLC. La prueba de lo mencionado se divide en dos partes:

• Si la máquina (M) es un AP, entonces el lenguaje que acepta M (L(M)) es

un LLC.
• Si L es un LLC, entonces hay un AP (M) tal que L(M) = L.

Para el mismo ejemplo 6.1, la función de transiciones para L(M) —con base en la función
definida en la figura 6.2 donde se define aquel estado en que se encuentra el autómata, qué
carácter va a ser leído, el elemento a sacar de la pila, el nuevo estado al cual va a pasar y
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

el nuevo elemento a introducir en la pila— será:

Un ejemplo del manejo de la pila es:

Ejemplo 6.2. Dado el siguiente lenguaje, mostrar su gramática y su autómata:

Para una mayor comprensión del lenguaje, se muestra su ordenamiento lexicográfico:

L={c,aca,bcb,aacaa,abcba,bacab,bbcbb,…}

La gramática es:

G=(S →,{a,b,c},S ,{S → aSa, S → bSb,S → c})

Como ejemplo, usando la gramática se creará la cadena “abcba”:

S → aSa → a bSb a → abcba.

La máquina, matemáticamente hablando, queda de la siguiente forma:
85

La misma máquina vista de forma gráfica se muestra en la figura 6.11.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Figura 6.11. La máquina vista en forma gráfica del ejemplo 6.2

Ejemplo 6.3. Dado el siguiente lenguaje, mostrar su gramática y su autómata:

Un ordenamiento lexicográfico quedaría de la siguiente forma:

L={ξ,aa,bb,aaaa,abba,baab,bbbb,…}

La gramática es:

G=(S,{a,b,c},S,{S → aSa, S → bSb,S →ξ})

La máquina, matemáticamente hablando, queda de la siguiente forma:

86 La misma máquina vista de forma gráfica se muestra en la figura 6.12.

Figura 6.12. La máquina vista en forma gráfica del ejemplo 6.3

Ejemplo 6.4. Dado el siguiente lenguaje, mostrar su gramática y su autómata:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Un ordenamiento lexicográfico quedaría de la siguiente forma:

L={ξ,a,b,aa,bb,,aaa,bbb,aba,bab,aaaa,abba,baab,bbbb,…}

Esta sería la definición de un palíndromo, es decir, aquella palabra o expresión que se lee
igual de izquierda a derecha y viceversa. Por ejemplo, en lenguaje español la siguiente ora-
ción forma un palíndromo:

Se observa que la máquina es no determinística. Existe no determinístico en el paso 1, 2, 3,

4 y 5. Un autómata determinístico para el lenguaje del ejemplo 3 y ejemplo 4 es la máquina
de Turing.

La misma máquina vista en forma gráfica se muestra en la figura 6.13.

 Figura 6.13. La máquina vista en forma gráfica del ejemplo 6.4
87

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Equivalencia. En este escrito se definirá equivalencia como el algoritmo que permite tra-
ducir un elemento de un tipo a otro elemento de otro tipo. En este caso, se puede decir que
una gramática es equivalente a un autómata si existe el algoritmo que permita traducir la
gramática a un autómata específico. En particular, a partir de una gramática libre de contex-
to se pueda construir un autómata tipo pila.

Hasta este momento se ha visto que a partir de una gramática recursiva izquierda se puede
construir un árbol sintáctico utilizando las prioridades relativas de los operadores aritmé-
ticos. Para la construcción automática del árbol se requiere un autómata tipo pila. Ahora
bien, utilizado la idea de equivalencia se puede construir un algoritmo para producir el árbol
sintáctico a partir de una gramática libre de contexto recursiva izquierda que permita trans-
formar la gramática en un autómata tipo pila.

El árbol sintáctico se puede construir de dos formas. Lo común es construir el árbol a partir
de la raíz a las hojas (en forma descendente o top-down). La otra forma es antinatura, esto
es, construir el árbol de las hojas a la raíz (en forma ascendente o bottom-up).

AUTÓMATAS TIPO DESCENDENTE (TOP-DOWN)

El algoritmo de transformación más sencillo es el siguiente: sea G=(V,T,S,P) una gramática

libre de contexto, se puede construir un autómata tipo pila M tal que L(M)=L(G). La máquina
por construir tiene solo dos estados (p y q) y permanece en el estado q después del primer
movimiento. El autómata se define como M=({p,q},σ,{ σ,S},Δ,p,q), donde Δ tiene las siguien-
tes transiciones:

(p,ξ,ξ)(q,S)

(q,ξ,A)(q,α) para cada regla A→ α en R.

(q, σ, σ)(q,ξ) para cada σϵΣ

88 Ejemplo 6.5. Para ver el funcionamiento de este algoritmo de transformación se mostrará
con el siguiente lenguaje visto en una sección anterior:
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

La cadena aabcbaa es aceptada por M a través del siguiente esquema de movimientos de

la tabla 6.2:

Tabla 6.2. Transiciones para la cadena aabcbaa utilizando el autómata del ejemplo 6.5

En la tabla 6.2 se observa que las transiciones 2, 3 y 4 producen un autómata no determinís-

tico, ya que no se sabe cuál de las decisiones tomar teniendo a S en tope de pila: producir
aSa o bSb o ξ.

La tarea de reconocer a un lenguaje libre de contexto en una forma determinística que pro-
duce el árbol sintáctico es algo sumamente importante y es un reto. A un autómata tipo
pila determinístico se le conoce como analizador. Naturalmente, no todos los lenguajes
libres de contexto pueden tener un analizador.
Un analizador descendente es aquel autómata tipo pila determinístico que crea un árbol
89
sintáctico de raíz a las hojas. Tal analizador se logra observando el siguiente elemento para
ser analizado, y dependiendo de ello se realiza la transición.

Ejemplo 6.6. Dado el siguiente lenguaje, desarrollar la gramática y el autómata a partir de

la gramática señalada. Posteriormente, construir un analizador descendente utilizando la
propiedad de observar el siguiente elemento para ser analizado.

Su gramática es conocida.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

L(G): S→aSb|ξ

Por lo que L(M):

M1=({p,q},{a,b},{a,b,s},Δ,p,{q})

donde Δ={(p,ξ,ξ)(q,S), (q, ξ,S)(q,aSb), (q, ξ,S)(q, ξ), (q,a,a)(q, ξ), (q,b,b)(q, ξ)}

En esta máquina, las transiciones en negrita son no determinísticas, ya que teniendo a S en

tope de pila, no se sabe si producir aSb o ξ.

Para observar hacia adelante (look ahead) se deben introducir más estados que permitan
hacer un autómata determinístico, donde se pueda decidir con el símbolo de la cadena por
leer y el símbolo que está en tope de pila la transición que se debe realizar. Además, se
requiere un símbolo especial que indique el fin de cadena ($), por lo que la palabra, en este
caso, queda como w$. Así, el analizador descendente queda de la siguiente forma:
90 En la tabla 6.3 se realizará una simulación con la siguiente cadena: ab$

Tabla 6.3. Usando el analizador descendente del ejemplo 6.6, se analiza la cadena ab$
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

El no determinismo se rompe con el estado qa y qb. Solo en el estado qa y S en tope de pila

se permite la producción S → aSb, y solo con qb y S en tope de pila se permite la producción
S → ξ, por lo que ambos estados permiten una observación hacia adelante (hacer un look
ahead), rompiendo el no determinismo.

No todo lenguaje libre de contexto tiene un autómata determinístico descendente vía una
observación hacia adelante, incluso para lenguajes libres de contexto no ambiguos. Algunos
lenguajes no son amigables para hacer un analizador descendente por razones que son
superficiales y pueden ser removidas con pequeños cambios en la gramática.

Ejemplo 6.7. Recordemos el lenguaje libre de contexto que representa a un álgebra ele-
mental con los operadores de agrupación, la multiplicación y la suma, siendo esta gramática
recursiva izquierda:

G=({E,T,F},{id,*,+,(,)}, E,{ E→ E+T, E→T,T→T*F,T→F,F→(E),F→id})

Utilizando el algoritmo de transformación sencillo, la máquina queda de la siguiente forma:

El no determinismo se muestra al observar que al tener E o T o F en tope de pila, se tienen
91
dos posibles derivaciones para cada una de las no terminales indicadas anteriormente. En
la tabla 6.4 se realizará una simulación con la siguiente cadena: id0+id1*id2.

Tabla 6.4. Simulación de la cadena id0+id1*id2 usando el AP del ejemplo 6.7

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

En esta gramática no se puede usar la estrategia look ahead. Observemos la gramática del
ejemplo 6.6. Al estar en el estado qa y al tener a S en tope de pila, la derivación es S → aSb,
por lo que se elimina a S del tope de pila y en el tope de pila queda una a (es decir, un ele-
mento del alfabeto terminal), permitiendo saber lo que se realizará en el siguiente paso (look
ahead). En el ejemplo 6.7, al derivar E→E+T, al sacar a E del tope de pila e introducir E+T,
el elemento que queda en tope de pila de nuevo es E (es decir, un elemento del alfabeto no
terminal recursivo); esta recursión puede producir una ramificación infinita.

Aplicando el siguiente algoritmo de transformación, se rompe la recursividad izquierda, lo

que permite realizar la estrategia look ahead.

Heurística para producir una gramática no recursiva izquierda

Sea A→Aα1,..., A→Aαn, y A→β1,..., A→βm son todas las reglas con A al lado izquier-
do de la producción y las β’ no inician con A y n>0. Entonces, reemplazar estas reglas
por A→β1A’,..., A→βmA’, A’→α1A’,..., A’→αnA’, y A’→ξ, donde A’ es una nueva no terminal
(Lewis y Papadimitriou, 1998).

Para las dos reglas gramaticales, la transformación queda de la siguiente forma:

E→E+T
E→T
92 Realizando equivalencias, E es equivalente a A, +T es equivalente a α (E → E+T equivale a
A → A α) y T es equivalente a β (E→T es equivalente a A→β). Por lo tanto, la primera parte
queda como E → TE’. Y la segunda parte queda como
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

En la figura 6.14 se muestra un árbol sintáctico con la siguiente expresión y la gramática no

recursiva izquierda obtenida de la transformación id0*(id1+id2).
Figura 6.14. Árbol sintáctico sin recursividad izquierda
El analizador descendente queda de la siguiente forma:
93

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

En la tabla 6.5 se realizará la simulación del autómata con la siguiente cadena: id0*(id1+id2)$.
Tabla 6.5. Simulación del autómata con la cadena id0*(id1+id2)$
94 Véase que el autómata determinístico produce el árbol sintáctico (parser tree).

Existen varios algoritmos para transformar una gramática libre de contexto a un autómata
tipo pila, pero su coste computacional es elevado (del orden de n3). Por lo tanto, existen
algoritmos más eficientes para ciertas gramáticas libres de contexto. En la siguiente sección
se observará un algoritmo que permite crear una tabla sintáctica para una gramática no
recursiva izquierda.

ANALIZADOR PREDICTIVO NO RECURSIVO LL(1)

Una gramática cuyo tabla analizadora no tenga entradas de definición múltiple se dice que
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

es LL(1). La primera L se refiere a la lectura de la entrada de izquierda a derecha (scanning

the input from left to right), la segunda L por producir una derivación más a la izquierda (for
producing a leftmost derivation), y el “1” por usar un símbolo de entrada para look ahead en
cada paso al hacer una decisión en el analizador. Una gramática del tipo LL(1) tiene varias
propiedades. Gramáticas no ambiguas o gramáticas recursivas izquierdas pueden ser LL(1).

Es posible construir un analizador predictivo no recursivo manteniendo una pila o stack. El

problema clave durante el análisis predictivo es determinar la producción que se debe apli-
car para una no terminal. El analizador no recursivo de la figura 6.15 revisa la producción
que debe ser aplicada en una tabla analizadora.

Figura 6.15. Modelo de un analizador no recursivo predictivo

Un analizador predictivo dirigido por una tabla tiene una entrada, una pila, una tabla anali-
zadora y una cadena de salida. La entrada contiene a la cadena que debe ser analizada,
seguida por un $ indicando fin de cadena. La pila contiene una secuencia de símbolos de
la gramática. El primer símbolo por introducir a la pila es $, seguido del símbolo no terminal
de inicio. La tabla analizadora es una tabla bidimensional M[A,a], donde A es una letra del
abecedario no terminal y a es una terminal o el símbolo $.
El analizador es controlado por un programa que se comporta con el siguiente algoritmo:
95
El programa considera a X el símbolo en el tope de la pila, y a el símbolo de la entrada a
analizar. Estos dos símbolos determinan la acción que va a realizar el analizador. Existen
tres posibilidades:

1. Si X=a=$, el analizador termina con éxito.

2. Si X=a=$, el analizador saca a X del tope de pila y el programa avanza al
siguiente símbolo por analizar en la entrada.
3. Si X es no terminal, el programa consulta a la tabla analizadora con los
parámetros M[X,a]. Si M[X,a]={X → UVW}, el analizador reemplaza a X en

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

el tope de la pila por UVW (con U en el tope de la pila); de otra manera, si
M[X,a]=error, el analizador llama una rutina de recuperación de error.

Del ejemplo 6.7 se obtuvo una gramática no recursiva predictiva izquierda. Su tabla analiza-
dora se muestra a continuación:

Tabla 6.6. Tabla analizadora del ejemplo 6.7

En la tabla 6.7 se realizará una simulación con la cadena de entrada id*(id+id)$, el algoritmo
que permite realizar las transiciones apropiadas a partir de la tabla analizadora y la pila.
Obsérvese que al inicio el stack contiene el $ y el símbolo no terminal de inicio E.
96 Tabla 6.7. Simulación de la tabla 6.6 y la cadena id*(id+id)$
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR
En la tabla 6.8 se muestra otro ejemplo con la cadena ((id0*id1+id2)*id3)+id4$:
97
Tabla 6.8.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

98 CREACIÓN DE UNA TABLA ANALIZADORA DESCENDENTE

Para crear una tabla analizadora descendente predictiva se requieren dos pasos:

1. A partir de un nodo en general del árbol sintáctico, se trata de saber cuáles son
los símbolos terminales que pueden aparecer a la izquierda. A esa función se le
conocerá como FIRST(). A partir de un nodo en general, se tratará de saber cuá-
les son los símbolos terminales que pueden aparecer a la derecha. A esta función
se le conocerá como FOLLOW() (el dominio de estas funciones es el alfabeto de
los símbolos terminales, por lo que se espera que cada función FIRST() o FO-
LLOW() tenga un subconjunto de tales elementos). Véase la figura 6.16.
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

2. A partir de estas dos funciones, se sigue un algoritmo para indicar cuáles son
las derivaciones que se deben obtener en forma determinista utilizando como
información al elemento que se localiza en tope de pila y el símbolo de entrada
por analizar.

Figura 6.16. Dominio de la función First() y de la función Follow()

A continuación, se explican las funciones First() y Follow().

Función First( )
Para calcular la función First() se usa el siguiente algoritmo:
Si x es un terminal, entonces First (x) ← { x }
Entendiendo que "ξ" se considera la cadena vacía. Si x →ξ, entonces agregar
ξ al First(x). (First(X) ←{ξ}).
Si X es una no terminal y:
X→Y1 Y2 . . . Yk
Y1→Z1 Z2 . . . ZT
Z1->W1W2..
 Entonces First(X) ← First(Y1) ← First(Z1)<-First(W1)
99
Ejemplo 6.8. Para mostrar el algoritmo de la función First() se tomará como ejemplo una
gramática izquierda no recursiva:
E→TE’
E’→+TE’
E’-> ε
T→FT’

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

T’→*FT’| ε
F→( E ) | id

Para crear los First() solo se aplican las reglas del procedimiento anterior, desglosando los
resultados:
Del paso 2.
First(E’)←{ ε}
First(T’) ←{ ε}

Del paso 3 se obtiene:

First(E) ← First(T) ← First(F) ←{id,(}
First(T’) ←{*}
First(E’) ←{+}

Agregando todos los elementos del paso 2 y del paso 3 se obtiene:

First(E) ←{id, (}
First(T) ←{id,(}
First(F) ←{id,(}
First(F) ←{id, (}
First(T’) ←{ ε, *}
First(E’) ← { ε, +}
100 Función Follow()
Como en el procedimiento FIRST(), para realizar un correcto desarrollo del FOLLOW se
debe seguir este algoritmo:
1) FOLLOW ( E )←{ $ } // donde E es el no-terminal inicial.
2) Si existe una producción A→αBβ, donde toda letra griega indica una subca-
dena de terminales y no terminales incluyendo la cadena vacía, entonces FOLLOW(-
B)←FIRST(β) –{ξ}
3) Si existe
a) A→ αB
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

a) A→αBβ donde {ξ} FIRST(β)

Entonces FOLLOW(B) ←FOLLOW(A)

Ejemplo 6.9. Ejemplo de FOLLOW(). Usando la gramática y el FIRST() del ejemplo 6.8,
encontrar la función FOLLOW().
Ejemplo 6.10. Obtener el FIRST( ) y FOLLOW( ) de la siguiente gramática.
101

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

ALGORITMO PARA CREAR UNA TABLA ANALIZADORA DESCENDENTE

Se puede usar el siguiente algoritmo para construir una tabla analizadora predictiva para
una gramática G. La idea detrás del algoritmo es la siguiente: suponga A→α es una produc-
ción con a en el FIRST(α). Entonces el analizador puede expandir A por α cuando el símbolo
de entrada es a. Ocurre una complicación cuando α =ξ, o α ξ. En este caso, A se debe
expandir por α si el símbolo de entrada se localiza en FOLLOW(A), o si el signo $ ha sido
alcanzado y $ se localiza en FOLLOW(A).

Algoritmo:

1)Para cada producción A→α de la gramática, hacer paso 2 y paso 3.

2)Para cada terminal a en FIRST(α), adisionar A→α a M[A,a].

3)Si ξ se localiza en FIRST(α), añadir A→α a M[A,b] para cada terminal

b en FOLLOW(A). Si ξ está en FIRST(α) y $ se localiza en FOLLOW(A),
adicionar A→α a M[A,$].

4)Cada entrada indefinida en M se marcará como error.

102 Ejemplo 6.11. Hacer la tabla analizadora descendente para la siguiente gramática.
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR
Ejemplo 6.12. Obtener la tabla analizadora descendente de la siguiente gramática y probar-
103
la con la cadena zandoryx$ (Catalán, 2010).

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

104 De esta forma se obtiene la tabla 6.9.
Tabla 6.9

La tabla 6.10 muestra el funcionamiento del analizador sintáctico descendente de la tabla

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

6.9 utilizando la cadena zandoryx$.

Tabla 6.10

El árbol sintáctico se muestra en la figura 6.17:

Figura 6.17. Árbol sintáctico de la tabla 6.10
Ejemplo 6.13. Desarrollar un analizador LL(1) de la siguiente gramática:
105

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

La tabla analizadora descendente se muestra en la tabla 6.11:

Tabla 6.11

La transición M[S’,e] contiene dos transiciones S’→ξ y S’→eS, por la transición FO-
LLOW(S’)={e,$} la gramática es ambigua y la ambigüedad se manifiesta en escoger, el else
(e) o cadena vacía. Ya que la tabla contiene entradas multidefinidas, la gramática no es
LL(1).
106 AUTÓMATA TIPO ASCENDENTE (BOTTOM-UP)

La idea es construir el autómata de las hojas a la raíz, método conocido como bottom-up.

El algoritmo de transformación más sencillo es el siguiente: sea G=(V,T,S,P) una gramática

libre de contexto, se puede construir un autómata tipo pila M tal que L(M)=L(G). La máquina
por construir tiene solo dos estados (p y q) y permanece en el estado p hasta que se llega
al símbolo de inicio para cambiar al estado q. El autómata se define como M=({p,q}, σ,{
σ,S},Δ,p,q) donde Δ tiene las siguientes transiciones:
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Ejemplo 6.14. Con el autómata ascendente no determinístico mostrado arriba hacer la tabla
de transiciones con la cadena id0+id1*id2.
En la tabla 6.12 se muestran las transiciones.
107
Tabla 6.12

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Claramente se observa que el autómata es no determinístico, ya que en cada reducción no
se sabe si se debe sacar de la pila uno o tres símbolos, o seguir leyendo símbolos del alfa-
beto (en este caso), además de no saber cuántos símbolos leer.

CREANDO UN AUTÓMATA DETERMINÍSTICO ASCENDENTE

Para construir un autómata práctico para L(G) se debe crear un autómata determinístico
que acepte L(G)$. A diferencia de un autómata descendente, no se dará un procedimiento
sistemático, sino que se colocarán las bases heurísticas que permiten tal tarea.

Primero se necesita saber el camino para determinar los dos tipos básicos de movimientos,
esto es:

• Leer el siguiente símbolo de la cadena y colocarlo en la pila (Shift) o

• Realizar una reducción de una regla gramatical en la pila (A →α). En otras
palabras, eliminar un determinado número de elementos del tope de la pila
(α) e introducir un símbolo no terminal a la pila (A) de acuerdo con alguna
de las reglas de la gramática.
108 Esto se realiza observando dos elementos de información:

• el siguiente símbolo por leer de la cadena, llamado “b”,

• y el símbolo en el tope de la pila, llamado “a” (el símbolo “a” podría ser no
terminal).

La decisión entre leer un símbolo de la cadena (Shift) o una reducción (sacar α elementos
de la pila) se realiza entre una relación , conocida como relación de pre-
cedencia. Si (a,b) P, entonces habrá una reducción; de otra forma, habrá un Shift con
“b”. Intuitivamente, (a,b) P significa que existe una derivación a la derecha de la forma
ya que se está reconstruyendo la derivación de la derecha hacia atrás,
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

esto hace sentido reducir la regla A→γa donde se observa que “a” inmediatamente precede
a “b”. Existen caminos sistemáticos para calcular la relación de precedencia para decidir
entre un shift o una reducción.

Ejemplo 6.15. Dada la siguiente gramática, mostrar la tabla de precedencia y realizar una
simulación de su funcionamiento.

En la tabla 6.13 se muestra la precedencia para la gramática del ejemplo 6.15.

Tabla 6.13. Tabla de precedencia ((a,b) P)

La tabla 6.13 solo indica si se realiza una reducción o una lectura, pero no cuál reducción
debe efectuarse. La tabla 6.14 muestra un ejemplo utilizando la tabla 6.3. Las reducciones,
en este momento, se realizan de manera intuitiva.
 Tabla 6.14. Simulación del uso de la tabla 6.13 de precedencia
109

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Ahora se debe confrontar el siguiente origen del no determinismo: ¿cuál de las reglas se
debe de reducir en la pila? Por ejemplo, la pila guarda la siguiente cadena F*T+E y se debe
hacer una reducción, la cual puede ser T → F o T → T*F. La heurística marca que se reduz-
ca la regla de mayor tamaño, en este ejemplo sería T → T*F. Obsérvese en la tabla 6.14 que
las reducciones de mayor tamaño se marcaron en negrita itálica.

Con la tabla de precedencia y al reducir escoger la regla de mayor tamaño (si se tiene en
pila) se puede construir un autómata determinístico que analice L(G)$. Un detalle: el autó-
mata debe censar el final de la pila, por lo que se coloca un símbolo especial # en el inicio de
la pila para cualquier computación. En el ejemplo 6.16 se muestra el autómata ascendente
determinístico para la gramática indicada en el ejemplo 6.15.
110 Ejemplo 6.16. Máquina determinística ascendente mostrando la heurística con operadores
de precedencia y reducción de la regla de mayor tamaño.
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

De esta forma se han mostrado dos reglas heurísticas para crear un autómata determinís-
tico ascendente:

1. El uso de la relación de precedencia para decidir si se almacenará en la pila

el símbolo por analizar de la palabra o reducir una regla gramatical.
2. Cuando existe duda de cuál de las reglas reducir, se hará con la de mayor
tamaño | α |. Esta regla no siempre es adecuada. Las gramáticas en las que
trabaja se conocen como gramáticas de precedencia débil (weak preceden-
ce grammars). En la práctica, varias gramáticas son o pueden ser converti-
das a gramáticas de precedencia débil (Lewis y Papadimitriou, 1998).

Ejemplo 6.17. Mostrar una simulación con el autómata del ejemplo 6.16.

En la tabla 6.15 se muestra una simulación del funcionamiento del autómata determinístico
ascendente antes descrito.
 Tabla 6.15. Simulación con una cadena de caracteres con un autómata
111
ascendente determinístico

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Construcción de la tabla analizadora LR
En esta sección se presentan las técnicas para crear un analizador sintáctico descendente
que puede ser usado para analizar una gran cantidad de gramáticas libres de contexto. La
técnica es llamada analizador LR(K): L es un escaneo de izquierda a derecha (left to right
scanning) de la entrada, la R por construir una derivación más a la derecha en reversa (ri-
ghtmost derivation in reverse) y la K por el número de símbolos de entrada con los que se
puede usar la técnica look ahead y realizar decisiones en el análisis. Cuando K es omitido,
se supone igual a uno. Un analizador LR es atractivo por las siguientes razones:
112 • Puede ser construido para reconocer virtualmente todos los lengua-
jes de programación en los cuales han sido escritos por una gramática
libre de contexto.
• Es el método general en el cual no se usan técnicas con retorno hacia atrás
con lectura-reducción (nonbacktracking shift-reduce)
• La clase de gramáticas que puede analizar usando métodos LR es un su-
perconjunto de la clase de gramáticas que pueden ser analizadas con ana-
lizadores predictivos.
• Un analizador LR puede detectar un error sintáctico lo más
temprano posible.
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

El único inconveniente de este método es que se requiere mucho trabajo para construir un
analizador LR a mano para una gramática de un lenguaje de programación. Por eso, se
requieren herramientas especiales como Lex (lexicografical analyzer) y YACC (yet another
compile compiler) que realizan el análisis lexicográfico y el análisis sintáctico (ambos se
pueden interconectar).

Existen tres algoritmos para crear una tabla LR:

• SLR. Simple LR. Es el más sencillo de los tres, pero el que tiene menos po-
der de construcción, ya que no llega a reconocer algunas gramáticas libres
de contexto donde otros métodos llegan a tener éxito.
• LR. Es el algoritmo más poderoso, pero a la vez el más costoso.
• LALR. Look Ahead LR. Tiene un costo intermedio entre los dos anteriores.
Trabaja en la mayoría de las gramáticas de los lenguajes de programación
y, con un poco de esfuerzo, puede ser implementado eficientemente.

En este escrito se muestra solo el algoritmo SLR.

ANALIZADOR SLR
La construcción de la tabla analizadora SLR se basa en un autómata finito. El autómata se
construye bajo el concepto de los “ítems” (o símbolo por analizar). Un ítem es una regla de
la gramática que tiene un punto en algún lugar de la producción, por lo que el elemento por
analizar es el que se encuentra a la derecha del ítem.

Como ejemplo se coloca la siguiente producción:

A→XYZ

Tal producción tiene cuatro ítems:

A→.XYZ
A→X.YZ
113
A→XY.Z
A→XYZ.

La producción A → ε genera solo un ítem:

A →. ε

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Uso de los ítems para construir el autómata
Para crear todos los estados del autómata se utiliza una operación de cerradura que permi-
te tener todas las posibles ramificaciones a partir de un ítem dado (Cerradura (I)). En una
gramática dada G, la cerradura (I) es el conjunto de elementos construido a partir de I bajo
las siguientes reglas:

1. Cada ítem de I se añade a la Cerradura(I).

2. Si A→α.Bβ se localiza en Cerradura(I) y B→ γ es una producción de la
gramática, entonces añadir B→ γ. a la Cerradura(I) si aún no se localiza
ahí. Se aplica esta regla hasta que no se puedan añadir más elementos a
Cerradura(I)
3. La operación Ir_a (I,x), donde I es un conjunto de ítems y x es un símbolo
de la gramática. Se define Ir_a(I,x) como la cerradura del conjunto de todos
los elementos { A→αx.β} tal que { A→α.xβ} esté en I.

Por ello, la construcción del conjunto de elementos C es la colección canónica (regular)

producida por LR(0). Para construir el conjunto de elementos se tiene el siguiente algoritmo:

C= Cerradura({S’ → .S}) // Donde S’ es el estado inicial

Repetir

Para cada conjunto I en C y cada símbolo en la gramática X tal que ir_a (I,X) no esté
vacío y no esté en C, realizar:

Añadir ir_a (I,X) a C

hasta que no se puedan añadir conjuntos de elementos a C.

La siguiente gramática del tipo SLR o LR(0) se utilizará como ejemplo tanto para la genera-
ción del conjunto de cerradura de ítems como para mostrar el algoritmo para crear una tabla
sintáctica SLR:
114 P={
(0) E’E
(1) E E + T
(2) ET
(3) T T * F
(4) TF
(5) F (E)
(6) F id
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

}
donde E indica expresión, T indica término, F indica factor e id indica identificador.
Con el algoritmo dado se genera el conjunto C(I)={I1, . . . ,I11} de la siguiente forma:
Utilizando la función Ir_a( ), se crea el autómata de la figura 6.18:
115
Figura 6.18. Autómata generado por el algoritmo de los ítems

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Algoritmo para construir la tabla sintáctica SLR
Basándose en el autómata para construir la tabla sintáctica ascendente SLR, se aplica el
siguiente algoritmo:

// El símbolo Sj (Shiftj) indica recorrer al siguiente símbolo a analizar y pasar al j-simo estado
del autómata.

//La indicación reduce A→ α indica que se reducirá la regla indicada.

//El signo $ se utilizará como delimitador de cadena.

1. C es la colección canónica del conjunto de ítems.

2. Del estado Ii, las acciones se determinan bajo los siguientes criterios:
a) Si {A→α.aβ} Ii e Ik=Ir_a(Ii, a), entonces M[i,a]=Sk (“a” es una terminal)
b) Si {A→α.} Ii, entonces M[i,a]= reduce A→α para a Follow(A)
A

(A no puede ser S’)

c) Si {S’→S.} Ii, entonces M[i,$]=acc.

Si existe un conflicto, entonces la gramática no puede ser SLR.

3. Si Ik=Ir_a(Ii,A), entones M[i,A]=k.

4. Toda entrada no definida en (2) y (3) es error.
5. El estado inicial del analizador es S’→S.
116 Con el algoritmo dado se mostrará paso a paso la construcción de la tabla sintáctica SLR:

Paso 2a

Se toma en cuenta la transición con elementos terminales del autómata finito. Por lo tanto,
las transiciones son las siguientes:

M[0,(]=S4 M[0,id]=S5 M[1,+]=S6 M[2,*]=S7 M[4,(]=S4 M[4,id]=S5

M[6,(]S4 M[6,id]=S5 M[7,(]=S4 M[7,id]=S5 M[8,)]S11 M[8,+]=S6 M[9,*]=S7

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Paso 2b

Para desarrollar el paso 2b se requiere aplicar la función Follow(); ver ejemplo 6.10, que-
dando el siguiente resultado:

Follow ( E ) ← {$, +, )}

Follow (T) ← {*,$,+,)}

Follow (F) ← {*, $, +, )}

Además, se requiere todo ítem que llegó al final de la producción. A continuación, se mues-
tran los ítems que cumplen con tal condición:

{E’→E.} I1

{E→T.} I2

{T→F.} I3

{F→id.} I5

{E→E+T.} I9

{T→T*F.} I10

{F→(E).} I11

M[2,+]=r2 M[2,)]=r2 M[2,$]=r2 M[3,+]=r4 M[3,)]=r4 M[3,$]=r4 M[3,*]=r4

M[5,+]=r6 M[5,)]=r6 M[5,$]=r6 M[5,*]=r6 M[9,+]=r1

M[9,)]=r1 M[9,$]=r1 M[10,+]=r3 M[10,)]=r3 M[10,$]=r3 M[10,*]=r3

M[11,+]=r5 M[11,)]=r5 M[11,$]=r5 M[11,*]=r5

 117
En este caso, r2 indica reducir la regla gramatical número dos.

Paso 2c

{E’→E.} I1

M[1,$]=acc.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Paso 3

Del autómata finito se toma en cuenta la transición con elementos no terminales. Por lo tan-
to, las transiciones son las siguientes:

M[0,E]=1 M[0,T]=2 M[0.F]=3 M[4,E]=8 M[4,T]=2 M[4,F]=3

M[6,T]=9 M[6,F]=3 M[7,F]=10

Obteniéndose la tabla sintáctica 6.16:

Tabla 6.16. Tabla sintáctica SLR
118 Algoritmo para el uso de la tabla sintáctica SLR
En la figura 6.19 se muestra de forma general la estrategia de la pila utilizando la tabla sin-
táctica adecuadamente:

Figura 6.19. Manejo de la pila por medio de una Tabla sintáctica LR(K)
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

donde

• Cada Xi en la pila es un símbolo de la gramática.

• Cada Si en la pila es un estado del autómata.
• La combinación del estado en tope de pila y el símbolo de entrada a analizar sirven
para indexar a la tabla y producir una decisión Shift/Reduce (leer elemento de cade-
na/Reducir regla gramatical).

De esta forma:
ip.- Al inicio apunta al primer símbolo de la palabra por analizar (w$).
S.- Es el estado del tope de pila.
a.- Es el símbolo apuntado por ip.

Por tanto, el algoritmo para el uso de la tabla sintáctica SLR es:

Repite

Si M[S,a]=Shift S, entonces:

Colocar a ‘a’ y después a ‘S’ en tope de pila.

Si no, Si M[S,a]=reduce A→ α.

Sacar 2*| α | símbolos del tope de pila.

S’ es el nuevo estado en el tope de pila.

 Colocar ‘A’ en el tope de pila.
119
Colocar M[S’,A] en tope de pila.

Si no, Si M[S,a]=acc

Retornar con éxito

Si no

Llamar a rutina de error( )

En la tabla 6.17 se muestra un ejemplo utilizando el algoritmo para el uso de la tabla sintác-

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

tica:
Tabla 6.17. Iteraciones para el ejemplo id1 * (id2 + id3)$

El autómata permite crear el árbol de forma ascendente. Cada reducción permite ir creando
una rama o unir ramas hacia la raíz. Por lo tanto, las acciones para crear el árbol se hacen
en cada una de las reducciones. Las reducciones se localizan en las iteraciones 2, 3, 7, 8, 9,
12, 13, 14, 16, 17 y 18 realizándose las conexiones entre ramas de derecha a izquierda. En
la figura 6.20 se observa con claridad este aspecto mostrando cada una de las reducciones.
120 Algorítmicamente hablando, se requiere una pila de apuntadores donde se va guardando
el apuntador a cada una de las ramas creadas, por lo que la figura 6.20 también muestra el
funcionamiento de la pila de apuntadores. Obsérvese que al momento de unir dos ramas,
estas se escogen con respecto a los dos apuntadores que están en tope de pila (véanse las
iteraciones 14 y 17).

Figura 6.20. Creación del árbol sintáctico en forma ascendente utilizando

como auxiliar las iteraciones marcadas en la tabla 6.17 en las iteraciones 2, 3,
7, 8, 9, 12, 13, 14, 16, 17 y 18 y su recorrido en postorden
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR
121

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

122 La tabla 6.18 muestra otro ejemplo utilizando el analizador SLR que se enseña en la tabla
6.16. La figura 6.21 evidencia la creación del árbol en forma ascendente utilizando una pila
de apuntadores como auxiliar.

Tabla 6.18
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR
 Figura 6.21. Creación del árbol sintáctico en forma ascendente utilizando las iteraciones
1-3, 6-8, 12-14, 17,18, 21-23, 25,26, 29-31, 33-35 de la tabla 6.16
123

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Siendo el recorrido en postorden id0 id1 id2 id3 id4 *+ id5 * + +.
124 REFERENCIAS

Aho, A and Ullman, J. (1978). Principles of compiler design. Wilmington, Delawere, USA:
Addison-Wesley.

Baliri, S. (2014). Teoría de lenguajes formales: una introduccion para lingüistas. España:
Universidad Autónoma de Barcelona.

Campos, A. (1995). Teoría de autómatas y lenguajes formales. Chile: Pontificia Universidad

Catolica de Chile.
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Cueva Lovelle, J. M. (2001). Lenguajes, gramáticas y autómatas. España: Universidad de

Oviedo.

Dean, K. (2001). Teoría de autómatas y lenguajes formales. Madrid: Prentice Hall.

Gallego, Á. J. (2008). La jerarquía de Chomsky y la facultad del lenguaje: consecuencias

para l7a variación y la evolución. Teoema, 27(2), 47-60.

Hopcroft, J., Motwani, R. y Ullman, J. (2007). Introduccion a la teoría de autómatas, lengua-

jes y computación. Madrid: Pearson Educación.

Ibarra Florencio, N. (2011). Tipos de lenguajes formales. México: Universidad Nacional

Autónoma de México. Recuperado de http://www.comunidad.escom.ipn.mx/genaro/
Papers/Veranos_McIntosh_files/lenguajesNivardo.pdf

Isasi Viñuelas, P., Martínez Fernández, P. y Borrajo Millán, D. (1997). Lenguajes, gramáticas
y autómatas: un enfoque práctico. Madrid: Pearson Educación.

Lemone, K. (1991). Fundamentos de compiladores. Cómo traducir al lenguaje de computa-

dora. México: CECSA.

Lewis, H. and Papadimitriou, C. (1998). Elements of the theory of computation. New Jersey:
Prentice Hall.

Moral Callejón., S. (s. f.). Teoría de autómatas y lenguajes formales. Universidad de Grana-
da.

Navarrete Sánchez, I., Cárdenas Viedma, M. A., Sánchez Álvarez, D., Botia Blaya, J. A.,
Marín Morales, R. y Martínez Bejar, R. (2008). Teoría de autómatas y lenguajes for-
males. España: Universidad de Murcia.

Padilla Beltrán, P. G. (2006). Lenguajes y álgebra de eventos regulares. México: Instituto

Politecnico Nacional. Recuperado de http://delta.cs.cinvestav.mx/~mcintosh/comun/
 summer2006/algebraPablo_html/intro.html
125
Polanco Fernández, D. F. (2000). Evaluación y mejora de un sistema automático de análisis
sintagmático (proyecto de fin de carrera). Universidad Politécnica de Madrid,
Escuela Técnica Superior de Ingeniería de Telecomunicaciones. Departamento
de Ingeniería Electrónica.

Processadors de llenguatge II (25 de marzo de 2020). Universitat Pumpeu Fabra. Recupe-

rado de https://www.upf.edu/pro/es/2014/3371/12470.html

Quiroga Rojas, E. A. (2008). Autómatas y lenguajes formales. Bogota: Universidad Nacional

Abierta y a Distancia.

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Ruiz Catalán, J. (2010). Compiladores. Teoría e implementación. Ciudad de México: Alfao-
mega.

Universidad Autónoma del Estado de Hidalgo [UAEH] (16 de mayo de 2019). Función del
analizador léxico. Centro de Innovación para el Desarrollo y la Capacitación en Mate-
riales Educativos. Recuperado de http://cidecame.uaeh.edu.mx/lcc/mapa/PROYEC-
TO/libro32/21_funcin_del_analizador_lxico.html

Vilca Huayta, O. A. (2008). Expresiones regulares y autómatas finitos. Chile. Recuperado de

https://www.yumpu.com/es/document/read/28532329/expresiones-regulares-y-auta-
matas-finitos
126 ANEXO A

EXPLICACIÓN DE LA PROGRAMACIÓN DE UN ÁRBOL

SINTÁCTICO ASCENDENTE

Introducción

En este anexo se muestra la programación del árbol sintáctico ascendente. Toda la progra-
mación se realizó en lenguaje estándar C para que se pueda recrear en cualquier computa-
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

dora que tenga un compilador C. Para el entendimiento del programa se requieren conoci-
mientos de memoria dinámica y haber tenido un curso de estructuras de datos en el cual se
haya programado al menos un árbol binario.

El programa completo que muestra el analizador sintáctico ascendente se localiza en el

anexo B.

Analizador lexicográfico

Para la programación del árbol sintáctico ascendente se utilizará la siguiente gramática:

P={
(0) E’E
(1) E E + T
(2) ET
(3) T T * F
(4) TF
(5) F (E)
(6) F id

(Aho y Ullman, 1978).

Se observará que las palabras que debe reconocer el analizador lexicográfico son:

L= {+, *, (,), id}

Por tanto, el analizador lexicográfico es, en este caso, muy simple y al reconocer una pala-
bra retorna por cada palabra válida un número que representa en este caso un token para el
analizador sintáctico. Se observará que por cada token reconocido se invoca al analizador
sintáctico para ver si dicho token corresponde sintácticamente a una letra de la palabra que
127
analizará el analizador sintáctico.

En la figura A.1 se observa su diagrama de flujo y programación del analizador lexicográfico.

Figura A.1. Tabla lexicográfica

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Analizador sintáctico ascendente

Se programará el analizador sintáctico ascendente SLR de la tabla 6.16, donde se modifica-

ron las acciones por realizar en números para una mayor facilidad del programador. La tabla
A.1 muestra los cambios respectivos:

• Para los subíndices de las columnas a cada elemento terminal o no terminal

se le adjudica un entero positivo como subíndice.
• Los Shift se introdujeron como decenas.
• La reducción de alguna regla se introdujo por medio de las centenas.
• Los saltos a algún estado se colocaron por medio de las unidades.
128 Tabla A.1. Tabla sintáctica modificada para una mayor facilidad en la programación
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

La figura A.2 muestra la programación de la tabla sintáctica:

Figura A.2. Diagrama de flujo y programación de la tabla sintáctica ascendente

Para poder realizar el árbol se requirieron tres estructuras:
129
La que soporta la pila del analizador sintáctico:
struct nodo{
int dato;
nodo * siguiente;
};

La que soporta la pila de apuntadores para crear el árbol sintáctico:

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

struct nodo2{
void * p;
nodo2 * siguiente;
};

Y la estructura misma del árbol sintáctico:

struct nodo1{
char dato;
nodo1 * izq;
nodo1 * der;
};

Para manejar ambas pilas a la vez se utilizó un apuntador bidimensional tipo void:

void * p[2];

Donde:

El apuntador p[0] se encarga de apuntar a la pila que producen las iteraciones que indica la
tabla sintáctica ascendente.

p[1] apunta a una pila de apuntadores que permite crear el árbol ascendente donde cada
elemento en la pila de apuntadores apunta a una rama que permitirá crear el árbol sintáctico
de las hojas a la raíz.
130 En la figura A.3 se muestra la función que permite definir las acciones dependiendo de la
consulta a la tabla sintáctica (si se lee otro carácter de la cadena por analizar o se realiza
una reducción a una regla determinada).

Figura A.3. Función sintáctico()

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR
Como se observa, la función sintáctico() invoca las siguientes funciones:
131
Shift(). Permite leer otro elemento del archivo y pasar al estado indicado en la tabla sintác-
tica.

Reduce(). Realiza la operación reducción indicada en el algoritmo para el uso de la tabla

sintáctica SLR (capítulo 6). En la figura A.4 se muestra la función shift():
Figura A.4. Función shift()

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

La función shift() invoca a la función crea(). La función crea() sirve para colocar un elemento
en la pila del autómata. En la figura A.5 se muestra la función crea():

Figura A.5. Función que permite crear un elemento en pila del analizador sintáctico

La función más interesante es reduce() y se muestra en la figura A.6. En tal función, la varia-
ble w es el número de regla para reducir. Se observará que en las reglas 1, 3 y 5 se deben
de reducir seis elementos. En la pila del analizador sintáctico se procede como sigue:
132 • Se coloca un ciclo for para eliminar n elementos de la pila (si el número de
regla es impar, se eliminan 6 elementos de pila; si el número de regla es
par, se eliminan 2 elementos de tope de pila) y se utiliza la función elimina()
para tal propósito.
• Se invoca a la función tope() para observar lo que existe en tope de pila y
se guarda en la variable z.
• Posteriormente se invoca la función crea() dos veces: la primera para intro-
ducir la reducción ‘A’ de la regla A→ α y la segunda para introducir a pila el
elemento indicado por la tabla sintáctica (tsin[z][A]).
• Para las reglas 1 y 3 se invoca la función enlaza(), ya que se tienen que
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

enlazar dos ramas (E->E+T o T->T*F).

• Para las 2, 4 y 6 se invoca la función creaA(), que permite crecer un ramal
en particular (el que esté en tope de pila de apuntadores).
 Figura A.6. Función que permite realizar la operación de reducción
133

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

134 La función enlaza() permite realizar la conexión de dos ramas (observar figura A.7).

Figura A.7. Función que permite conectar a dos ramas independiente

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR
Para la pila del árbol sintáctico se invoca la función creaA(), en el cual puede realizar uno
135
de los dos pasos:

Si es una hoja (el elemento a analizar es una “i”), se crea un nodo para tal elemento, se crea
otro nodo para el elemento ‘F’, se conectan entre sí y se guarda el apuntador de ‘F’ a pila
de apuntadores.

O si la reducción se une a la rama que está apuntando en el tope de pila (observar figura
A.8).
Figura A.8. Formación de un ramal del árbol

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

136 La función que controla las llamadas continuas del analizador lexicográfico y sintáctico se
observa en la figura A.9.
Figura A.9. El do…while que controla la invocación al analizador lexicográfico y analizador
sintáctico
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR
La figura A.10 enseña la función que permite mostrar lo que existe en el tope de la pila del
137
analizador sintáctico.

Figura A.10. Función que muestra el tope de pila

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

La figura A.11 muestra la función que elimina un elemento del tope de pila del analizador
sintáctico.

Figura A.11. Función que elimina un elemento de pila del analizador sintáctico
138 La función que enseña el contenido en pila del analizador sintáctico se muestra en la figura
A.12.

Figura A.12. Función que muestra el contenido en pila de un analizador sintáctico

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

En la figura A.13 se muestra la función que recorre en postorden el árbol sintáctico.

Figura A.13. Función que muestra el árbol sintáctico en postorden

139

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

140 ANEXO B

PROGRAMA COMPLETO DEL ANALIZADOR SINTÁCTICO ASCENDENTE

# include <stdio.h>
# include <stdlib.h>

//pila sintáctica
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

struct nodo{
int dato;
nodo * siguiente;
};

// el árbol
struct nodo1{
char dato;
nodo1 * izq;
nodo1 * der;
};
//pila para crear el árbol
struct nodo2{
void * p;
nodo2 * siguiente;
};
int tope(void*);
void mostrar(void *);
void * elimina(void *);
void *crea(void *, int);
int transforma (char);
int tablasin(int[][9]);
void sintactico(void **, int, int, int[][9]);
void *shift(void*, int, int);
141
void reduce(void**, int , int [][9]);

//Funciones para crear el árbol

void *creaA(void *, char );
void * enlaza(void *, char );
void muestraA(nodo1*);

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

main(){
void * p[2];
p[0]=p[1]=NULL;
p[0]=crea(p[0],0);
int tsin[12][9],x,y;
tablasin(tsin); //observará que el parámetro es un arreglo, por lo que se envía por referencia.
char caracter;
int edo;
FILE* fichero;
fichero = fopen(“prueba1.txt”, “r”);
if (fichero==NULL){
fputs (“File error”,stderr); exit (1);
}
printf(“Analizador Léxico y Sintáctico COMELI.\n “);
printf(“iniciamos\n”);
//observará que el parámetro es un arreglo, por lo que se envía por referencia. T_lexico() sólo
llena el arreglo t_l
do{
caracter = fgetc(fichero);
y=transforma(caracter);
if (y==6)
break;
edo=tope(p[0]);
142 printf(“caracter=> %c, y=>%d, edo=>%d\n”,caracter,y,edo);
edo=tsin[edo][y];
printf(“Edo=%d\n”,edo);
if (edo<0){
printf(“ERROR SINTÁCTICO”);
break;
}
else
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

sintactico(p,edo,y,tsin);

}while (y<5);
if (y==6)
printf(“Error lexicográfico, no se reconoce la palabra=>%c”,caracter);
getchar();
}

void sintactico(void ** p, int edo, int y, int tsin[][9]){

int z;
nodo2 *aux;
nodo1 *r;
if (edo <100) //Hay un shift
p[0]=shift(p[0],y,edo);
else{ // hay una reducción
while(edo>100){
reduce(p,edo,tsin);
printf(“Después de Reducción\n”);
mostrar(p[0]);
z=tope(p[0]);
edo=tsin[z][y]; //Reviso el nuevo estado guardado en tope de
//pila con el elemento leído para ver si se repite
 // la reducción
143
if (edo==1000){
printf(“TERMINO CON EXITO\n\n”);
printf(“El arbol es:\n”);
aux=(nodo2*)p[1];
r=(nodo1*)aux->p;
muestraA(r);
break;

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

}
else if (edo <100 && edo >-1) //Hay un shift
p[0]=shift(p[0],y,edo);
else if (edo<0)
printf(“ERROR SINTÁCTICO”);
}
}
}

void*shift(void *p, int y, int edo){

p=crea(p,y);
p=crea(p,edo-10);
printf(“\nShift =>%d\n”,y);
mostrar(p);
putchar(‘\n’);
return p;
}
void reduce(void **p, int edo, int tsin[][9]){
int w=edo-100,z;
if (w%2==1){
for (int k=0;k<6;k++) //ELIMINO SEIS ELEMENTOS
p[0]=elimina(p[0]);
144 printf(“Reducción de seis elementos\n”);
mostrar(p[0]);
putchar(‘\n’);
z=tope(p[0]); //TOMO LO QUE HAY EN TOPE DE
// PILA
if(w==1){ //reduce E->E+T
p[0]=crea(p[0],6);//INTRODUCIR LA
//REDUCCIÓN (EN ESTE
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

// CASO 6 ME
// REPRESENTA A “E”)
z=tsin[z][6]; //Reviso el elemento a introducir a
//tope de pila
p[0]=crea(p[0],z);//introduzco el elemento a
//tope de pila
printf(“llamo a enlaza con +\n”);
p[1]=enlaza(p[1], ‘+’);
}
else if(w==3){ //reduce T->T*F
p[0]=crea(p[0],7);
z=tsin[z][7];
p[0]=crea(p[0],z);
printf(“Llamo a enlaza con *\n”);
p[1]=enlaza(p[1], ‘*’);
}
else{ //REDUCE F->(E)
p[0]=crea(p[0],8);
z=tsin[z][8];
p[0]=crea(p[0],z);
p[1]=creaA(p[1],’F’);
}
 }
145
else{
for (int i=0;i<2;i++) //ELIMINO DOS ELEMENTOS
p[0]=elimina(p[0]);
z=tope(p[0]);
printf(“Reducción de dos elementos\n”);
mostrar(p[0]);
putchar(‘\n’);

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

if (w==2){ //E->T
p[0]=crea(p[0],6);
z=tsin[z][6];
p[0]=crea(p[0],z);
p[1]=creaA(p[1],’E’);
}
else if (w==4){ //T->F
p[0]=crea(p[0],7);
z=tsin[z][7];
p[0]=crea(p[0],z);
p[1]=creaA(p[1],’T’);
}
else if (w==6){ //F->ID
p[0]=crea(p[0],8);
z=tsin[z][8];
p[0]=crea(p[0],z);
p[1]=creaA(p[1],’i’);
}

}
}
int transforma (char c){ //equivalente a la tabla lexicográfica
146 int x;
if (c>=’a’ && c<=’z’)
x=0;
else
switch(c){
case ‘+’:x=1;break;
case ‘*’:x=2;break;
case ‘(‘:x=3;break;
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

case ‘)’:x=4;break;
case ‘$’:x=5;break;
default:x=6;
}
return x;
}
int tablasin(int x[][9]){
for(int i=0;i<12;i++)
for (int j=0;j<9;j++)
x[i][j]=-1;
x[0][0]=15; //S5
x[0][3]=14; //S4
x[0][6]=1; // IR AL ESTADO 1
x[0][7]=2; // IR AL ESTADO 2
x[0][8]=3; // IR AL ESTADO 3
x[1][1]=16; //S6
x[1][5]=1000; //ACC
x[2][1]=102; // REDUCE E->T
x[2][2]=17; //S7
x[2][4]=102; // REDICE E->T
x[2][5]=102; // REDICE E->T
x[3][1]=104; // REDUCE T->F
x[3][2]=104; // REDUCE T->F
147
x[3][4]=104; // REDUCE T->F
x[3][5]=104; // REDUCE T->F
x[4][0]=15; //S5
x[4][3]=14; //S4
x[4][6]=8; // IR AL ESTADO 8
x[4][7]=2; // IR AL ESTADO 2
x[4][8]=3; // IR AL ESTADO 3

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

x[5][1]=106; // REDUCE F->ID
x[5][2]=106; // REDUCE F->ID
x[5][4]=106; // REDUCE F->ID
x[5][5]=106; // REDUCE F->ID
x[6][0]=15; //S5
x[6][3]=14; // S4
x[6][7]=9; // IR AL ESTADO 9
x[6][8]=3; // IR AL ESTADO 3
x[7][0]=15; // S5
x[7][3]=14; // S4
x[7][8]=10; // IR AL ESTADO 10
x[8][1]=16; // S6
x[8][4]=21; // S11
x[9][1]=101; // REDUCE E->E+T
x[9][2]=17; // S7
x[9][4]=101; // REDUCE E->E+T
x[9][5]=101; // REDUCE E->E+T
x[10][1]=103; // REDUCE T->T*F
x[10][2]=103; // REDUCE T->T*F
x[10][4]=103; // REDUCE T->T*F
x[10][5]=103; // REDUCE T->T*F
x[11][1]=105; // REDUCE F->(E)
148 x[11][2]=105; // REDUCE F->(E)
x[11][4]=105; // REDUCE F->(E)
x[11][5]=105; // REDUCE F->(E)
}
void *crea(void *p, int x){
nodo *q,*aux;
q=(nodo*)malloc(sizeof(nodo));
q->dato=x;
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

q->siguiente=NULL;
if(p==NULL) //La pila está vacía
p=q;
else{
q->siguiente=(nodo*)p;
p=q;
}
return(p);
}

void * elimina(void * s){

nodo *p,* aux;
if(s==NULL)
printf(“\npila vacia\n”);
else{
p=(nodo*)s;
s=p->siguiente;
free(p);
}
return(s);
}
void mostrar(void *p){
149
nodo *s;
s=(nodo *)p;
if (p==NULL)
printf(“PILA VACIA”);
else{
if(s->siguiente!=NULL)
mostrar(s->siguiente);

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

printf(“%d..”,s->dato);
}
}

int tope(void* p){

nodo *q=(nodo*)p;
printf(“\nEn tope %d\n”,q->dato);
return q->dato;
}

//------------------------------------------------
//FUNCIONES PARA CREAR EL ÁRBOL

void *creaA(void *p, char x){

nodo1 *q, *aux; //apuntador a nodo de árbol
nodo2 *q1,*aux1; //apuntador a pila para crear el árbol
if (x==’i’){//en este caso, se considera que el identificador es una hoja del árbol.
//crear el nodo para el identificador y preparo el terreno para el Factor
aux=(nodo1*)malloc(sizeof(nodo1));
aux->dato=x;
x=’F’;
printf(“\n\tSe crea rama => %c\n”,aux->dato);
150 aux->izq=aux->der=NULL;
q1=(nodo2*)malloc(sizeof(nodo2));
q1->p=aux;
q1->siguiente=NULL;
if (p==NULL)
p=q1;
else{
q1->siguiente=(nodo2*)p;
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

p=q1;
}
}
//se crea el una parte de la rama del árbol
q=(nodo1*)malloc(sizeof(nodo1));
q->dato=x;
printf(“\n\tGuardo un %c\n\n”,q->dato);
q->der=NULL;
aux1=(nodo2*)p;
aux=(nodo1*)aux1->p;
q->izq=aux;
aux1->p=q;
p=aux1;
return(p);
}

void * enlaza(void * p, char x){

nodo1 * q,*q1;
nodo2 * aux,*aux1,*aux2;
//se crea nodo que enlaza dos ramas
q=(nodo1*)malloc(sizeof(nodo1));
151

ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

152

ANÁLISIS LEXICOGRÁFICO
ANÁLISIS LEXICOGRÁFICO Y SINTÁCTICO DE UN COMPILADOR

Y
SINTÁCTICO DE UN COMPILADOR

Se termino de imprimir en octubre 2021 en los

talleres de Editorial Centro de Estudios e
Investigaciones para el Desarrollo Docente. CENID AC
Av. Acantilado 2880 Int. Mirador de la barranca 43, Col.
Bosques el centinela, C.P. 45120, Zapopan, Jal.
Teléfono: 01 (33) 1061 8187
Tiraje: 1000