Compiladores

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 200

Compiladores

M. en C. Joel Omar Juárez Gambino


COMPILADORES E INTÉRPRETES

2
Compilador
• Un compilador es un programa que lee
un programa escrito en algún lenguaje
(lenguaje fuente) y lo traduce a un
programa equivalente en otro lenguaje
(lenguaje objeto)

3
Historia de los compiladores

La palabra compilador se atribuye a
Grace Murray Hopper

El concibió la implementación de un
lenguaje de alto nivel como “una
compilación de una secuencia de
subrutinas desde una librería”

Los primeros compiladores tipo traductor
fueron escritos a fines de los 50

4
Historia de compiladores

El lenguaje FORTRAN se considera el primer
lenguaje compilado con exito

El diseño de este compilador lo encabezó John
Backus y su desarrollo tomó 18 años

Existia un gran escepticismo con respecto a
que un lenguaje semejante al inglés pudiera
diseñarse y traducirse en algo que la máquina
pudiera ejecutar eficazmente

“Los verdaderos programadores utilizan el
lenguaje ensamblador”
5
Historia de los compiladores

En la actualidad es posible diseñar e
implementar un compilador mejor y más
rápido que FORTRAN por las siguientes
razones:

Los lenguajes se comprenden mejor

Se han desarrollado herramientas que
facilitan algunas tareas del compilador

Se han desarrollado estructuras de datos
y algoritmos que realizan las tareas que
son comunes a todos los compiladores
6
7
Proceso de compilación

Programa Programa
Compilador
fuente objeto

Errores

8
Proceso de compilación
• Es importante señalar que diferentes
lenguajes de programación requieren
distintos compiladores
• No existen compiladores genéricos
• ¿Qué pasa con CIL?

9
LENGUAJES DE PROGRAMACIÓN

10
Evolución de los LP
• Las computadora son capaces de
ejecutar procedimientos que están
escritos en su lenguaje nativo
• Dicho lenguaje está definido en las
instrucciones que el procesador es capaz
de ejecutar
• Con estos lenguajes se producian
programas gigantescos y con alta
probabilidad de errores
11
Programa en ensamblador
.BEGIN ini
a: .DW 10 ; Variable a
b: .DW 5 ; Variable b
sum: .DW 0 ; Resultado

ini: load a(R0),R1 ; 10 -> R1


load b(R0),R2 ; 5 -> R2
addi R0,#0,R3 ; 0 -> R3
loop: subi R2,#0,R0 ; R2 positivo?
ble fin ; Si <= 0, entonces FIN
add R3,R1,R3 ; R3+10 -> R3
subi R2,#1,R2 ; R2-1 -> R2
br loop ; repetir bucle
fin: store R3,sum(R0) ; R3 -> resultado
.END 12
Evolución de los LP
• Con el paso del tiempo los LP han
evolucionado
• Se acercan cada vez más a los lenguajes
algorítmicos
• Esto obliga a traducir los programas al
lenguaje de las computadoras

13
1. HACER Suma = 0;
2. HACER Valor = 0 ;
3. HACER Elemento = 0 ;
4.
5. LEER Elemento ;
6.
7. ES Elemento < 0 ?
8.   NO:
9.      HACER Suma = Suma + elemento;
10.      ES Elemento > Valor ?
11.         SI: 
12.            HACER Valor = Elemento;
13.         NO:
14.            VOLVER AL PASO 5
15.   SI: 
16.      DESPLEGAR Suma, Valor
17.
18. FIN DE PROCESO

14
Evolución de los LP
• Actualmente los compiladores no
producen programas objetos escritos en
código máquina
• Compilan el programa fuente a un código
intermedio
• Este código intermedio puede ser
interpretado directamente o traducido a
código máquina

15
FUNCIONES DEL COMPILADOR

16
Fases de un compilador
Programa fuente

Analizador léxico

Analizador sintáctico

Analizador semántico
Administrador de la Manejador de
tabla de símbolos errores
Generador de código intermedio

Optimador de código

Generador de código

Programa objeto
17
Analizador léxico
• Lee los caracteres de entrada (programa
fuente)
• Genera como salida una secuencia de
componentes léxicos
• Mediante algunas técnicas descompone
los cadenas en una serie de elementos
fundamentales del lenguaje
– variables, constantes, palabras
reservadas, etc.
18
Analizador léxico
area:=(base∗altura)/2 ;

1.El identificador area


2.El símbolo de asignación :=
3.El símbolo de paréntesis abierto (
4.El identificador base.
5.El signo de multiplicación *
6.El identificador altura
7.El símbolo de paréntesis cerrado )
8.El signo de división /
9.El número 2
19
Analizador sintáctico
• Determina si una cadena de
componentes léxicos puede ser
generada por una gramática
• Agrupa los componentes léxicos en
frases gramaticales que se utilizan para
sintetizar la salida
• Las frases gramaticales se representan
mediante un árbol de análisis sintáctico

20
Analizador sintáctico

21
Analizador sintáctico
• La estructura jerárquica de un programa
normalmente se expresa utilizando reglas
recursivas
• Ejemplo:
1. Cualquier identificador es una expresión
2. Cualquier número es una expresión
3. Si expresión1 y expresión2 son expresiones,
entonces también lo son
• expresión1 + expresión2
• expresión1 / expresión2
• (expresión1)

22
Analizador sintáctico
• Muchos lenguajes definen recursivamente las
proposiciones mediante reglas
• Ejemplo:
1. Si identificador1 es un identificador y expresion2 es
una expresión, entonces
identificador1:=expresión2
es una proposición
1. Si expresión1 es una expresión y proposición2 es
una proposición, entonces
while (expresión1) do proposición2
if (expresión1) do proposición2
son proposiciones

23
Tabla de símbolos
• Estructura de datos que contiene un
registro por cada identificador con campos
específicos para sus atributos
• Permite encontrar rápidamente el registro
de cada identificador
• Se puede almacenar y consultar datos de
ese registro

24
Tabla de símbolos
• Los atributos que comúnmente se
almacenan para un identificador son:
–Memoria asignada
–Tipo
–Ámbito
• Los atributos para un procedimiento:
–Cantidad y tipo de argumentos
–Método de envío de argumentos
–Tipo retornado

25
Tabla de símbolos
• Gran parte de la información almacenada
en la tabla de símbolos se introduce
durante la fase de análisis léxico
• Sin embargo, algunos atributos no se
pueden determinar durante esta fase
–var area, base, altura : real ;
• Las fases restantes complementaran los
atributos restantes de los identificadores de
la tabla de símbolos
26
Análisis semántico
• Revisa el programa en busca de errores
semánticos y reúne información sobre los tipos
• Uno de los errores más comunes revisados por
esta fase es la verificación de tipos
• Esta verificación comprueba si cada operador
tiene los operandos permitidos por la
especificación del lenguaje
int x=4, z;
char y[3]=“abc”
z = x + y;

27
Etapas del compilador
• En ocasiones el trabajo del compilador
se suele dividir en solo dos fases:
– Fase de análisis. Verifica posibles errores
en diferentes niveles
– Fase de síntesis. construye el programa
objeto a partir de la representación
intermedia

28
Etapa de análisis
• Se suelen identificar las siguientes etapas:
– Análisis lineal. La cadena de caracteres del
programa fuente se leen de izquierda a derecha
y se agrupan en componentes léxico
– Análisis jerárquico. Los componentes léxicos se
agrupan jerárquicamente en colecciones
anidadas con un significado colectivo
– Análisis semántico. Se realizan ciertas revisiones
para asegurar que los componentes de un
programa se ajustan de un modo significativo

29
Etapas de análisis
• Análisis léxico: ¿Cuáles son las “palabras” del
lenguaje?. Las palabras de un lenguaje de
programación reciben el nombre de símbolos o
componentes léxicos (tokens)
• Análisis sintáctico: ¿Cuáles son las “frases” del
lenguaje?. En un lenguaje de programación, las
“frases” son los programas bien construidos
sintácticamente
• Análisis semántico: ¿Qué “significa” cada frase del
lenguaje?. El significado del programa se describe en
téminos de lo que éste hace al ser ejecutado

30
Código intermedio
• Algunos compiladores incluyen una última
etapa que genera un código intermedio
• Este código se considera como un
programa para una máquina abstracta
• Esta representación debe de tener dos
propiedades importantes:
–Fácil de producir
–Fácil de traducir

31
Código intermedio
• Una representación intermedia utilizada es
el código de tres direcciones
• Consiste en una secuencia de
instrucciones, cada una con un máximo de
tres operandos
• Ejemplo:
temp:=entreal(2)
area:=(base∗altura)/2 ; temp2:=id2*id3
temp3:=temp2/temp
id1:=temp3
32
Etapa de síntesis
• Una tarea importante de esta etapa es la
optimización de código
• La optimización trata de mejorar el código
intermedio de modo que el código máquina
se ejecute más rápido
• Existen incluso compiladores que le
dedican mucho tiempo de la compilación a
esta etapa

33
Optimización de código

temp:=entreal(2)
temp2:=id2*id3 temp1:=id2*id3
temp3:=temp2/temp id1:=temp1/2.0
id1:=temp3

34
Generación de código objeto
• Después de la optimización el compilador
traduce las instrucciones a código objeto
• El código objeto generalmente se
representa en lenguaje ensamblador
• Cada una de las instrucciones máquina se
traducen a una secuencia de instrucciones
máquina que ejecutan la misma tarea

35
Generación de código objeto

MOVF id3, R2
temp1:=id2*id3 MULF id2, R2
id1:=temp1/2.0 MOVF #2.0, R1
DIVF R2, R1
MOVF R1, id1

36
area:=(base∗altura)/2 ;

temp:=entreal(2)
temp2:=id2*id3 Verificación de
temp3:=temp2/temp tipos
id1:=temp3

MOVF id3, R2
temp1:=id2*id3 MULF id2, R2
id1:=temp1/2.0 MOVF #2.0, R1
DIVF R2, R1
MOVF R1, id1
37
Agrupamiento de las fases
• Las fases del compilador se pueden
agrupar en:
– Etapa inicial
– Etapa final

38
Etapa inicial
• Comprende las fases que dependen
principalmente del lenguaje fuente
• Las fases de esta etapa son en gran
parte independientes de la máquina
objeto
• Generalmente incluye los análisis léxico,
sintáctico, semántico, generación de la
tabla de símbolos, generación de código
intermedio y manejo de errores
39
Etapa final
• Incluye fases del compilador que
dependen de la máquina objeto
• Estas fases no trabajan con el código
fuente, sino con el código intermedio
• Generalmente incluye la optimización de
código, generación de código, manejo de
errores y operaciones con la tabla de
símbolos

40
Nota libro compiladores (1986)
• “Resulta tentador compilar varios
lenguajes distintos en el mismo lenguaje
intermedio y usar una etapa final común
para las distintas etapas iniciales,
obteniendose así varios compiladores
para una máquina. Sin embargo, dadas
las sutiles diferencias en los puntos de
vista de los distintos lenguajes, sólo se
han obtenido un éxito limitado en ese
aspecto” 41
Pasadas
• Una pasada consiste en la lectura de una archivo
de entrada y la escritura de un archivo de salida
• Normalmente se aplican varias fases de
compilación en una sola pasada
• Siguiendo esta idea se podría traducir
directamente los componentes léxicos a código
intermedio
• Es deseable tener relativamente pocas pasadas,
dado que la lectura y escritura de archivos
intermedios lleva tiempo
• Una solución a estos problemas es el relleno de
42
retroceso (backpatching)
Pasadas

Si se agrupan varias fases dentro de una
pasada, puede ser necesario mantener
el programa completo en memoria

En ocasiones el programa interno puede
ser mayor que el programa fuente o el
programa objeto

El manejo de memoria no es un
problema trivial

43
Pasadas
• El agrupamiento de las fases en una sola
pasada no siempre es posible
• Algunos lenguajes permiten usar variables
antes de declararlas, por lo que no se puede
generar código objeto si no se conocen los
tipos de la variables implicadas
• En las sentencias goto no se puede
determinar la dirección objeto de dichos saltos
hasta haber visto el código objeto implicado y
haber generado el código objeto
correspondiente 44
Pasadas
• Es posible dejar un segmento de la tabla
en blanco para la información que falta y
llenarlo cuando la información esté
disponible
• La generación de código intermedio y
código objeto se puede fusionar en una
sola pasada utilizando la técnica de
relleno de retroceso (backpatching)

45
INTRODUCCIÓN A LOS AUTÓMATAS Y
LENGUAJES

46
Alfabetos
• Es un conjunto no vacio y finito de
símbolos
• Se utiliza el símbolo Σ para denotar un
alfabeto
• Ejemplo:
–Σ = {0,1}
Descripción: El alfabeto Σ consiste en los
dígitos 0 y 1
47
Cadenas o palabras
• Cadena o palabra. Es una secuencia finita de
símbolos
Ejemplo:
C=1010 sobre el alfabeto Σ = {0,1}
• Longitud de cadena. Es el número de símbolos
que tiene una cadena
Ejemplo:
|C|= 4

Cadena vacia. Cadena con 0 ocurrencias de
símbolos. Es denotada por ε
48
Cadenas o palabras
• Sea w=101 y z=111 dos cadenas, se
definen las siguientes operaciones:
– Concatenación de cadenas. La
concatenación de w y z es wz=101111
– Potencia de cadenas ( w k): Denota la
concatenación de k copias de la cadena
w
– Igualdad de cadenas: w y z estas
cadenas son iguales si tienen la misma
longitud y los mismos símbolos en la
49
misma posición
Lenguaje
• Conjunto de cadenas las cuales son
parte de un alfabeto Σ
• Una cadena L sobre un alfabeto Σ no
necesita incluir todos los símbolos de Σ

50
Lenguaje
• Ejemplos:
– El conjunto de todas las cadenas que
consisten en n 0's seguida de n 1's para
n≥0
– El conjunto de cadenas formadas por 0's
y 1's en cualquier posición con igual
número de repeticiones cada uno
– El lenguaje vacio ∅
– El lenguaje que consiste solo en la
51
cadena vacia {ε}
Lenguajes
• Un lenguaje es un conjunto de cadenas
de un alfabeto fijo
• Hay varias operaciones importantes que
se pueden aplicar a los lenguajes
• Para el análisis léxico son interesantes
principalmente la unión, la concatenación
y la cerradura

52
Operaciones sobre los
lenguajes

53
Ejemplo
• Sea L el conjunto {a,b,...,z} y D el
conjunto {0,1,...,9}, al aplicar las
operaciones se forman los siguientes
lenguajes
• LυD
• LD
4
L
+
D
• L*
54
• L(L υ D)*
Expresiones regulares
• Es una notación utilizada para
especificar patrones
• Una expresión regular se construye a
partir de expresiones regulares más
simples utilizando un conjunto de reglas
definitorias
• Cada expresión regular r representa un
lenguaje L(r)

55
Expresiones regulares
• Las siguientes reglas definen las expresiones
regulares del alfabeto Σ
1. ε es una expresión regular designada por
{ε}, el conjunto que contiene la cadena vacía
2. Si a es un símbolo de Σ , entonces a es una
expresión regular designada por {a}; por
ejemplo el conjunto que contiene la cadena
a. Aunque usa la misma notación para las 3,
técnicamente la expresión regular a es
distinta de la cadena a o del símbolo a.
56
Expresiones regulares
1. Suponiendo que r y s sean
expresiones regulares representadas
por los lenguajes L(r) y L(s), entonces:
• (r) | (s) es una expresión regular
representada por L(r) υ L(s)
• (r)(s) es una expresión regular
representada por L(r)L(s)
• (r)* es una expresión regular
representada por (L(r))*
• (r) es una expresión regular
57
representada por L(r)
Expresiones regulares
• Se pueden evitar los paréntesis
innecesarios en las expresiones
regulares si se adoptan las siguientes
convenciones
1. El operador unario * tiene la mayor pr y es
asociativo por izquierda
2. La concatenación tiene la segunda mayor
precedencia y es asociativa por izquierda
3. | tiene la menor precedencia y es
asociativo por izquierda 58
Expresiones regulares
• Siguiendo las convenciones anteriores
– (a)|((b)*(c)) es equivalente a
– a|b*c
• ¿Qué conjunto de cadenas se forman
con esa expresión?

59
Ejemplo
• Sea Σ = {a,b}, definir el conjunto de
cadenas que especifican las siguientes
expresiones regulares
1. a|b
2. (a|b)(b|a)
3. a*
4. (a|b)*
5. a|a*b

60
Expresiones regulares
• Si dos expresiones regulares r y s
representan al mismo lenguaje, se dice
que r y s son equivalentes (r = s)
– (a|b) = (b|a) ¿?
• Son varias las leyes algebraicas que
obedecen las expresiones regulares y
pueden ser usadas para transformar
dichas expresiones a otras equivalentes

61
Propiedades algebraicas

62
Definiciones regulares
• Por conveniencia de notación es
deseable dar nombres a las expresiones
expresiones regulares
• Se pueden definir nuevas expresiones
regulares utilizando dichos nombres
como si fueran símbolos
• A esta operación se le conoce como
definición regular

63
Definiciones regulares
• Si Σ es un alfabeto de símbolos básicos,
entonces una definición regular es una
secuencia de definiciones
• Ejemplo:
letra → A|B|...|Z|a|b|...|z
dígito → 0|1|...|9
• ¿Cómo se definirían los identificadores
en C?
64
Abreviatura en la notación

Uno o más casos. El operador unitario postfijo +
significa “uno o más casos de”. La expresión regular a +

representa al conjunto de todas las cadenas de una o


más a. El operador + tiene la misma precedencia y
asociatividad que el operador *

Cero o un caso. El operador unitario postfijo ? significa
“cero o un caso de”. La notación r? es una abreviatura
de r | ε

Clase de caracteres. Una clase abreviada de carácter
como [a-z] designan la expresión regular a|b|...|z.
Utilizando clase de caracteres, se puede definir los
identificadores como cadenas generadas por la
expresión regular [A-Za-z][A-Za-z0-9]* 65
Conjuntos no regulares
• Las expresiones regulares se utilizan para
describir un número fijo o no especificado de
repeticiones de una determinada construcción
• En general fallan al describir construcciones
equilibradas o anidadas
• Por ejemplo:
– Conjunto de cadenas con parentesis equilibrados
– {wcw | w es una cadena de símbolos a y b}

66
Conjuntos no regulares
• Para especificar este tipo de conjuntos
se utiliza una gramática independiente
(libre) del contexto
• Para reconocer una cadena de está
gramática se utiliza un autómata de pila
(push-down)

67
Teoría de Autómatas
• La teoría de autómatas estudia dispositivos de
cómputo abstractos
• En la época de 1930, antes de que existieran las
computadoras, Alan Turing inicio el estudio de
máquinas abstractas
• Dichas máquinas tenían todas las capacidades
de las computadoras actuales
• El estudio pretendía describir con precisión lo
que estos dispositivos podían y no podían hacer

68
Teoría de Autómatas
• Las conclusiones obtenidas por Turing aplican no
solamente a sus máquinas abstractas (máquinas
de Turing), sino a las computadoras de hoy en
día
• Entre 1940 y 1950 se realizó el estudio unas
máquinas simples llamadas autómatas finitos
(AF)
• Estos autómatas pretendían modelar el
funcionamiento del cerebro
• Los autómatas se han aplicado en muchas áreas
de la computación donde han sido muy útil

69
Aplicaciones de los autómatas
1. Software para diseño y verificación del
comportamiento de circuitos digitales
2. Software para analizar grandes cantidades de
texto, para encontrar palabras, frases, y otros
patrones
3. Software para la verificación de cualquier tipo
de sistema que requiera un número finito de
estados distintos, por ejemplo, protocolos de
comunicación
4. Analizador léxico de un compilador típico

70
Definición informal de los AF
• Un AF es un diagrama de transiciones, el
cual cuenta con un conjunto de estados
definidos
• La transición de un estado a otro se realiza
como respuesta a una entrada externa

71
Elementos de una AF
• Un estado

• Estado de inicio

• Estado de aceptación

• Una transición a

72
Ejemplo

73
Ejemplo

74
Ejemplo
• Si se tiene el siguiente alfabeto ∑ = {0,1}
diseñar un autómata finito que acepte la
cadena 01

75
Estado de aceptación
• Un AF acepta una cadena w si se pueden
seguir las etiquetas de los arcos con los
símbolos de la cadena w desde el estado
de inicio hasta su estado de aceptación
• En caso de hacer el seguimiento de los
símbolos y no llegar a un estado de
aceptación la cadena no es valida

76
Autómatas finitos
• Un AF puede ser determinista (AFD) o no
determinista (AFN)
• El “no determinismo” se refiere a que un estado
puede tener más de una transición para el mismo
símbolo de entrada
• Tanto los AFN como los AFD pueden reconocer
con precisión los conjuntos regulares, por lo
tanto ambos pueden reconocer lo que denotan
las expresiones regulares

77
Autómata finito no determinista
Es un modelo matemático formado por:
1. Un conjunto de estados S
2. Un conjunto de símbolos de entrada Σ (el
alfabeto de los símbolos de entrada)
3. Una función de transición “mueve” que
transforma pares estado-símbolo en conjuntos
estados
4. Un estado So que se considera el estado de
inicio (o inicial)
5. Un conjunto de estados F considerados como
estados de aceptación (o finales)
78
Ejemplo de un AFN
• Autómata que acepta cualquier cantidad
de 0’s y 1’s y termina con un 0

79
Ejemplo AFN

(a|b)*abb

80
Ejemplo AFN
En el ejemplo anterior podemos identificar
los siguientes elementos del AFN
1. Conjunto de estados S={0,1,2,3}
2. Alfabeto Σ = {a,b}
3. Estado inicial S0=0
4. Conjunto de estados aceptación F={3}

81
Tabla de transiciones
La función de transición se puede especificar
mediante una tabla de transiciones

82
Tabla de transiciones
• La tabla de transiciones es una alternativa
sencilla de implementar un autómata
• En esta tabla existirá una fila por cada
estado
• Y una columna por cada símbolo de
entrada, incluyendo ε de ser necesario

83
Transiciones vacías
• Los AFN permiten transiciones de ε
• Ejemplo:

aa*|bb*

84
Ejercicios
Dado el alfabeto Σ={0,1} diseñar los autómatas
que reconozca las siguientes cadenas
1. Cadenas que contengan cualquier cantidad de
0’s y 1’s y que terminen con la subcadena 00 o
11
2. Cadenas que contengan a la subcadena 010
3. Cadenas que solo contienen una cantidad par
de 0’s consecutivos
Cadenas que solo contienen una cantidad impar
de 1’s consecutivos
85
Ejercicios
1. Todas las cadenas que contienen solo
pares consecutivos de 0’s o 1’s o ambos
2. Todas las cadenas de 0’s y 1’s que no
contienen la subcadena 001
3. Todas las cadenas de 0’s y 1’s con al
menos un número par de dígitos 0
consecutivos

86
Ejercicios
Construir un autómata que reconozca las
siguientes cadenas
1. Todas las cadenas de letras que contienen las
5 vocales en orden
2. Comentarios que consisten en una cadena
encerrada entre /* y */ sin ningún */ intermedio
3. Todas las cadenas de 0’s y 1’s con al menos
un número impar de dígitos 1 consecutivos

87
Paso de una ER a un AFN
• El algoritmo esta dirigido por la sintaxis en el
sentido de que utiliza la estructura sintáctica de
la expresión regular para guiar el proceso de
construcción
• Los casos del algoritmo siguen a los casos de la
definición de una expresión regular
• Cada paso del algoritmo introduce a lo sumo dos
nuevos estados, por lo tanto el AFN resultante
tendrá a lo más el doble de estados que
símbolos y operadores que hay en la ER

88
Algoritmo
(construcción de thompson)

Entrada: Una expresióbn regular r en una
alfabeto Σ

Salida: un AFN n que acepte L(r)

Reglas:
1.Para ε, construir el AFN

i es un nuevo estado de inicio y f es un nuevo


estado de aceptación

89
Algoritmo
(construcción de thompson)
1. Para a de Σ, construir el AFN

1. Supongase que N(s) y N(t) son AFN para


las ER s y r
a) Para la ER s | r, construyase el AFN
compuesto N(s | r)

90
Algoritmo
(construcción de thompson)
a) Para la ER rs, construyase el AFN
compuesto N(rs)

4. Para la ER r*, construyase el AFN


compuesto N(r*)

91
92
Ejemplo

Construya el AFN a partir de la expresión
regular (a|b)*abb

93
Ejercicios

a|a*b

(ab)+ab

(a|b)*(a|b)+

94
Autómata finito determinista
Es un caso especial de un AFN en el cual:
• Ningún estado tiene una transición ε, es
decir una transición con la entrada ε
• Para cada estado S y cada símbolo de
entrada a, hay a lo sumo una arista
etiquetada a que sale de S

95
Autómata finito determinista
• Un AFD tiene a lo sumo una transición desde
cada estado con cualquier entrada
• Cada entrada en la tabla de transiciones es un
solo estado
• Los AFD y los AFN son capaces de reconocer
las mismas cadenas
• Debido a las diferencias entre los AFD y AFN,
dos autómatas que reconocen la misma cadena
pueden ser distinto (estados y transiciones)

96
Ejemplo AFD
(a|b)*abb

97
Ejemplo AFD
(a|b)*abb

98
AFN y AFD
• Los autómatas no deterministas pueden moverse
a dos estados distintos leyendo el mismo
símbolo
• Esto produce ambigüedad y esta situación es
difícil de simular en un programa de
computadora
• Otro problema que se presenta son las
transiciones de cadena vacía, ya que estas
permiten estar en varios estados sin leer un
símbolo
• Es más sencillo convertir un AFN a un AFD que
realizar una simulación de su comportamiento
99
Conversión de un AFN a AFD
• La idea general de la transformación de un
AFN a un AFD es que cada estado de un
AFD utiliza un estado para localizar todos
los posibles estados en los que puede
estar el AFN después de leer los símbolos
de entrada

100
Operaciones para la conversión

101
Algoritmo
(construcción de subconjuntos)
• Entrada: Un AFN N
• Salida: Un AFD D que acepta el mismo lenguaje
• Método: El algoritmo construye una tabla de
transiciones tranD para D. Cada estado del AFD
es un conjunto de estados del AFN y se
construye tranD de modo que D simulará “en
paralelo” todos los posibles movimientos que N
puede realizar con una cadena de entrada
• El algoritmo usa las operaciones descritas
anteriormente para construir los subconjuntos

102
Algoritmo
Al inicio, cerradura-ε (So) es el único estado
dentro de estadosD y no está marcado;
mientras haya un estado no marcado T en estadosD
hacer
marcar T;
para cada símbolo de entrada a hacer
U := cerradura-ε (mueve(T,a));
si U no está en estadosD entonces
añadir U como estado no marcado a estadosD;
tranD[T,a]:=U
fin
fin

103
Construcción de estadoD
Para construir estadosD y tranD se siguen los siguientes
pasos:
• Cada estado de D corresponde a un conjunto de estados
del AFN en los que podría estar N después de leer
alguna secuencia de símbolos de entrada, incluidas
todas las transiciones ε anteriores a la lectura
• El estado de inicio de D es cerradura-ε(So)
• Se añaden los estados y las transiciones a D utilizando
el algoritmo anterior
• Un estado de D es de aceptación si es un conjunto de
estados del AFN que contenga al menos un estado de
aceptación de N
104
Cálculo de cerradura-ε
Meter todos los estados T en pila;
Inicializar cerradura-ε (T) a T;
mientras pila no este vacia hacer
sacar t, el elemento tope de pila;
para cada estado u con una arista desde t a u
etiquetada con ε hacer
si U no está en cerradura-ε (T) entonces
añadir u a cerradura-ε (T);
Meter u en pila;
fin
fin
fin

105
Análisis léxico

106
Analizador léxico
• Lee los caracteres de entrada y genera
como salida una secuencia de
componentes léxicos
• Otras tareas del analizador léxico:
– Eliminar comentarios, tabulaciones,
espacios en blanco y saltos de línea
– Relacionar los errores con las lineas del
programa fuente

107
Fases del analizador léxico
• En algunas ocasiones los analizadores
léxicos se dividen en dos fases:
– Fase de examen: Encargada de eliminar
espacios en blanco, tabuladores, etc.
– Fase de análisis: Reconoce los
componentes léxicos

108
Interacción entre analizadores
• Los componentes identificados por el
analizador léxico son utilizados por el
analizador sintáctico
• Esta interacción se logra convirtiendo al
analizador léxico en una subrutina del
analizador sintáctico

109
Interacción entre analizadores

Componente léxico

Programa Analizador Analizador


fuente léxico sintáctico

Obtén el siguiente componente


léxico

Tabla de símbolos

110
Interacción entre analizadores
• Los componentes léxicos producidos se
pueden conservar en un buffer hasta ser
consumidos por el analizador sintáctico
• El analizador léxico no puede avanzar
mientras el buffer este lleno
• El analizador sintáctico no puede
continuar cuando e buffer está vacio

111
Interacción entre analizadores
• Es importante separar las etapas de
análisis léxico y sintáctico
– Diseño claro y sencillo
– Mejorar eficiencia (manejo de buffers)
– Mejorar transportabilidad (identificación
de símbolos que no son parte del
alfabeto)

112
Análisis de cadenas
• Componente léxico. Cadenas que el
analizador léxico es capaz de identificar
y agrupar de acuerdo a un significado
colectivo
• Patrón. Reglas mediante las cuales se
describen los componentes léxicos
• Lexema. Secuencia de caracteres en el
programa fuente con la que concuerda el
patrón para un componente léxico
113
Ejemplos

114
Componentes léxicos
• En la mayoria de los lenguajes de
progamación se consideran
componentes léxicos:
– Palabras clave
– Operadores
– Identificadores
– Constantes
– Signos de puntuación (coma, punto y
coma, paréntesis, etc.)
115
Palabras reservadas
• En algunos lenguajes ciertas cadenas
tienen un significado predefinido
• Esas cadenas se reservan para usos
exclusivo del lenguaje y el usuario no las
puede modificar
• Si dichas palabras no se reservan el
analizador léxico tendrá la tarea de
distinguir entre palabras reservadas e
identificadores
116
Ejemplo
• En el lenguaje PL/I las palabras clave no
son reservadas y se pueden complicar
muchos las proposiciones
    IF THEN THEN THEN = ELSE
    ELSE ELSE = THEN

117
Atributos de los componentes
léxicos
• Algunos patrones describen a más de un
lexema, por ejemplo, el patrón de
identificador
• Por lo que varios lexemas pueden
concordar con un mismo patrón
• Bajo estas circunstancias el analizador
léxico debe proporcionar información
adional sobre el lexema

118
Atributos de los componentes
léxicos
• Los componentes léxicos influyen en las
decisiones del análisis sintáctico
• Los atributos influyen en la traducción de
los componentes léxicos
• En la práctica los componentes léxicos
suelen tener un solo atributo, el
apuntador al registro de la tabla de
símbolos donde se especifican sus
atributos
119
Ejemplo
perímetro = lado * 2
• Secuencia de parejas
<identificador, apuntador>
<op_asignacion, >
<identificador, apuntador>
<op_multiplicacion, >
<num_entero, valor entero 2>

120
Errores léxicos
• Son pocos los errores que pueden ser
detectados durante esta etapa
• Un error detectado en esta etapa es
cuando no se encuentra un patrón que
describa a una cadena del programa
fuente
• Estos errores deben ser manejados
correctamente por el compilador para
poder continuar con el análisis
121
Errores léxicos
• Existen varias estrategias que el
compilador puede tomar para manejar el
problema:
– Borrar caracteres extraños hasta
reconocer un componente
– Insertar un carácter faltante
– Reemplazar un carácter incorrecto por
otro correcto
– Intercambiar dos caracteres adyacentes
122
Implementación del analizador
léxico

123
Aspectos prácticos de la
implementación
• Principio de máxima longitud
–Se da prioridad al componente léxico de
máxima longitud. Por ejemplo: <> se interpreta
como el operador “distinto de”, en vez de
“menor que” y “mayor que”

124
Aspectos prácticos de la
implementación
• Palabras reservadas e identificadores
–El patrón que define a un identificador también
se aplica a una palabra reservada, por lo tanto
antes de determinar el tipo de componente
léxico la cadena se busca en una tabla
previamente inicializada con las palabras
reservadas del lenguaje

125
Gramáticas

126
127
Gramáticas
• Las gramáticas describen lenguajes
• Los lenguajes naturales son descritos por una
gramática que agrupa palabras en categorías
sintácticas tales como sujeto, predicados,
verbo, etc.
• Una gramática impone una estructura a las
sentencias en el lenguaje
• Una gramática G, define un lenguaje L(G)
mediante la definición de un mecanismo para
derivar todas las cadenas de un lenguaje
128
Gramáticas libres de contexto
• Una gramática libre de contexto es un
cuarteto
G = (V,T,P,S)
• Donde:
V.- Conjunto de Variables
T.- Conjunto de Terminales
P.- Conjunto de Reglas de Producción
S.- Símbolo inicial de la gramática
129
Ejemplo
• La siguiente gramática describe el
lenguaje de todas las cadenas de ceros
y unos que son palíndromos
G = ({A}, {0,1},P,A)

A → 0A0 Derivemos la cadena 001100


A → 1A1
A ⇒ 0A0⇒ 00 A 00 ⇒ 001 A100 ⇒ 001100
A → 0∣1∣ε

130
Gramática libre de contexto
• En 1957 Noam Chomsky empleo una
notación denominada producciones para
definir la sintaxis del inglés (también
aplicable al español)
• Los términos oración, frase sustantiva,
frase verbal, etc,, más otras reglas
describen un conjunto pequeño
oraciones en español

131
<oración> →<frase sustantiva><frase verbal>
<frase sustantiva> →<artículo><frase sustantiva> | <sustantivo><adjetivo>
<frase verbal> →<verbo><adverbio>
<artículo> →<un | el>
<adjetivo> →<pequeño>
<sustantivo> →<niño>
<verbo> →<corrió>
<adverbio> →<rápidamente>

132
Ejemplo
<oración>

<frase sustantiva> <frase verbal>

<artículo> <frase sustantiva> <verbo> <adverbio>

<sustantivo <adjetivo>
>

<El> <niño> <pequeño> <corrio> <rápidamente>

133
Forma Backus-Naur (BNF)
• El metalenguaje BNF es una forma de
especificar lenguajes libres de contexto
• Fue creado por John Backus y Peter
Naur como una forma de describir la
sintaxis del lenguaje de programación
Algol

134
Ejemplo
Gramatica para definir una expresión aritmética
consistente solo en la suma y multiplicación

<expresión> ::= <expresión> + <término> | <término>


<término> ::= <término> * <factor> | <factor>
<factor> ::= (<expresión>) | <nombre> | <entero>
<nombre> ::= <letra> | <nombre><letra> | <nombre><dígito>
<entero> ::= <dígito> | <entero><dígito>
<letra> ::= A | B | ... | Z
<dígito> ::= 0 | 1 | 2 | ... | 9

135
Análisis sintáctico

136
Análizador sintáctico
• El analizador sintáctico obtiene una cadena de
componentes léxicos del analizador léxico y
comprueba si la cadena puede ser generada
por la gramática del lenguaje fuente
• El analizador sintáctico informará de cualquier
error de sintaxis
• También debería recuperarse de los errores
que ocurren frecuentemente para poder
continuar procesando el resto de la entrada

137
Árbol de
Component Representación
análisis
e léxico intermedia
Programa Analizador Analizador sintáctico Resto de la
fuente léxico sintáctico etapa inicial
Obtén el siguiente
componente léxico

Tabla de
símbolos

138
Análisis sintáctico
• Los métodos empleados por los compiladores se
clasifican generalmente en ascendentes y
descendentes
• Los analizadores sintácticos descentes
construyen árboles de análisis sintáctico desde
arriba (la raíz) hasta abajo (las hojas)
• Los analizadores sintácticos ascendetes
comienzan en las hojas y terminan en la raíz
• En ambos casos, se examina la entrada de
izquierda a derecha, un símbolo a la vez
139
Análisis sintáctico
• Los métodos descendentes y
ascendentes más eficientes trabajan sólo
con subclases de gramáticas
• Varias de estas subclases, como las
gramáticas LL y LR, son lo
suficientemente expresivas para
describir la mayoria de las
construcciones sintácticas de los
lenguajes de programación
140
Árboles sintácticos y
derivaciones
• De las derivaciones hechas por izquierda y por
derecha se puede producir un árbol de análisis
sintáctico
• Este árbol se define como G = (V,T,P,S) y cumple con
las siguientes propiedades:
– Cada nodo tiene una etiqueta
– La raíz tiene etiqueta S
– La etiqueta de los nodos que no son hojas debe estar
en V, y las de las hojas en T
– Si un nodo n tiene etiqueta A, y los nodos n1, ..., nm
son sus hijos (de izquierda a derecha), con etiquetas
respectivamnete A1, ..., Am, entonces A → A1 ,. .. Am ∈ P
141
Árboles sintácticos y
derivaciones
• Al efectuar un recorrido en orden del
árbol de derivación recuperamos la
cadena a partir de la cual se construyo
dicho árbol
• De esta forma el problema de analizar
una cadena consiste en construir el árbol
de derivación a partir del producto de
este

142
Gramáticas ambiguas
• Es importante señalar que una frase
puede generar más de un árbol de
análisis sintáctico
• Este problema se le denomina
gramáticas ambiguas
• Una gramática es ambigua si produce
más de un árbol de análisis sintáctico
para una frase (derivación izquierda y
derecha)
143
Gramáticas ambiguas
• La mayoria de los compiladores no pueden
trabajar con gramáticas ambiguas
• No podrían determinar de manera exclusiva
que árbol de análisis sintáctico seleccionar
para una frase
• Los compiladores que manejan estas
gramáticas implementan reglas que desechan
árboles de análisis sintáctico indeseables,
dejando solo un árbol para cada frase

144
Ejemplo
1. E→E + E Derivar la cadena:
x+y*x
2. E→E * E
3. E→x E E
4. E→y
E E

x + y * x x + y * x

145
Gramáticas ambiguas
• Existen dos formas para evitar las
gramáticas ambiguas
– Tranformar la gramática
– Establecer precedencias entre
operadores y de asociatividad

146
Gramáticas ambiguas
• La transformación de la gramática agrupa
todos los operadores de igual precedencia en
grupos y asocia a cada uno una regla
• De esta forma los que tienen menor
precedencia aparecen más cercanos al
símbolo de inicio
• Esto conlleva el aumento de la complejidad y
del árbol sintáctico generado
• La gramática deja de ser intuitiva

147
Ejemplo
1. E→E + E 1.exp → exp + term | term
2.term → term * factor | factor
2. E→E * E 3.factor → (exp) | x | y
3. E→x
4. E→y x + (y * x)
exp → exp + term → term + term
→ factor + term → x + term
→ x + factor → x + (exp)
→ x + (term) → x + (term * factor)
→ x + (factor * factor)
→ x + (y * factor)
→ x + (y * x)
148
Análisis sintáctico predictivo
La selección de una producción para un no
terminal puede implicar un proceso de prueba
y error
• En caso de que no se pueda generar el árbol
que concuerde con la cadena de entrada, se
retrocede para hacer otro intento de
producción
• Un analizador sintáctico que no requiere
retroceso es el analizador sintáctico predictivo

149
Análisis sintáctico predictivo
• El análisis sintáctico descendente recursivo es
un método descendente en el que se ejecuta
un conjunto de procedimientos recursivos para
procesar la entrada
• Una forma especial de este análisis es
denominado análisis sintáctico predictivo
• El análisis sintáctico predictivo utiliza un
símbolo de preanálisis para determinar sin
ambigüedad la producción que genera la
cadena deseada
150
Gramáticas recursivas
• Es posible que una analizador sintáctico descendente
recursivo entre en un ciclo infinito
• El problema se presenta con producciones recursivas del
tipo
expr → expr + término
• El símbolo situado más a la izquierda del lado derecho es el
mismo que el no terminal del lado izquierdo de la
producción
• Debido a que el símbolo de preanálisis cambia solo cuando
coincide un terminal del lado derecho y la producción inicia
con el no terminal expr, no se realiza ningún cambio en la
entrada entre llamadas recursivas, entrando a un ciclo
infinito
151
Gramáticas recursivas
• Las gramáticas pueden ser recursivas
por izquierda o por derecha
• Los analizadores sintácticos requieren
que la gramatica este libre de
recursividad

152
Gramáticas recursivas por
izquierda
• Una gramática es recursiva por izquierda
si tiene un no terminal A tal que existe
una derivación A ⇒ Aα para alguna cadena
α
• Ejemplo:
βααα
A→Aα
A → Aα → Aαα
A→β → Aααα → βααα

153
Algoritmo para eliminar la
recursividad izquierda
1) Se agrupan las producciones de A en la
forma
A → Aα 1∣Aα 2 ∣.. .∣Aα m∣β 1∣β 2∣. . .∣β n

1) Se sustituyen las producciones de A por:


A → β 1 A'∣ β 2 A' ∣. ..∣ β n A'
A' → α 1 A'∣α 2 A'∣. . .∣α m A' ∣ε

154
Algoritmo para eliminar la
recursividad izquierda
A → Aα A → βA'
→β A' → αA' | ε

βααα
A → βA'
→ βαA'
→ βααA'
→ βαααA'
→ βααα 155
Ejemplo
E→E+T|T E → TE'
T→T*F|F E'→ +TE' | ε
F → (E) | id T → FT'
T' → * F' | ε
F → (E) | id

156
Factorización
• En ocasiones un símbolo no terminal
genera más de una producción y no esta
claro cual es mejor opción para el
análisis
• Se pueden reescribir las producciones
para retrasar la desición hasta haber
visto lo suficiente de la entrada como
para elegir la opción correcta
• Esta técnica se conoce como
factorización 157
Factorización
• La factorización por izquierda es una
transformación gramatical adecuada
para el análisis sintáctico predictivo
• La factorización izquierda ayuda a
seleccionar una de varias producciones
con prefijo común

158
Algoritmo para realizar la
factorización izquierda
• Para cada no terminal A, encuentrese el
prefijo α más largo común a dos o más
de sus alternativas

159
Algoritmo para realizar la
factorización izquierda
• Si α≠ε es decir, existe un prefijo común
no trivial, sustitúyanse todas las
producciones de A, A → αβ 1∣αβ 2 ∣.. .∣αβ n∣γ,
donde γ representa todas las
alternativas que no comienzan con α,
por
A → αA'∣γ
A' → β 1∣ β 2∣. ..∣ β n

160
Algoritmo para realizar la
factorización izquierda
• Esta transformación se aplica hasta que
no haya dos alternativas para un no
terminal con un prefijo común

161
Ejemplo

A → αβ 1∣αβ 2 A → αA'
A' → β 1∣β 2

P → iE+P∣iE+PeP∣a P → iE+PP' ∣a
E →b P → eP∣ε
E →b

162
Análisis sintáctico descendente
• El análisis sintáctico descendente es un
método que intenta encontrar una
derivación por la izquierda para una
cadena de entrada
• El árbol de análisis sintáctico generado
por este método es construido desde la
raíz, creando los nodos del árbol en pre-
orden

163
Ejemplo
S → cAd
Dada la gramática
A → ab∣a
y la cadena w=cad
• Primero se utiliza el nodo etiquetado como S
y un apuntador a la izquierda que apunta a C,
el primer símbolo de w
• Después se utiliza la primera producción de
S para expandir el árbol
164
Ejemplo
• En cada nueva producción se intentará
emparejar la hoja situada más a la izquierda,
con el símbolo apuntado por w
• Si se encuentra una concordancia entonces se
avanza el apuntador al siguiente símbolo de w
• En caso de que no exista concordancia, se
indica el fallo y se regresa al no terminal
anterior para verificar si existe otra alternativa
de reescritura

165
Ejemplo
S → cAd
A → ab∣a
S S S

c A d c A d c A d

a b a

166
Análisis sintáctico predictivo
• Si se diseña una gramática eliminando
su recursión izquierda y factorizando por
izquierda se puede obtener una
gramática que puede utilizar un
analizador sintáctico descendente
recursivo que no necesite retroceso
• Este analizador se conoce como
sintáctico predictivo

167
Analizador sintáctico predictivo
• Para construir un analizador sintáctico
predictivo se debe conocer dado el
símbolo actual a de entrada y el no
terminal A a expandir, cual de las
alternativas de producción A → α 1∣α 2∣. ..∣α
esn
la única alternativa que da lugar a una
cadena que comience con a

168
Diagramas de transiciones para
analizadores sintácticos predictivos
• Al igual que existen diagramas de
transiciones para un analizador léxico,
también se puede crear un diagrama de
transiciones como plan para un
analizador sintáctico predictivo

169
Diagramas de transiciones para
analizadores sintácticos predictivos
• Existen varias diferencias entre los
diagramas del analizador léxico y el
sintáctico
– En un analizador sintáctico existe un
diagrama para cada no terminal
– Las etiquetas de las aristas son
componentes léxicos y no terminales

170
Ejemplo
• Para cada no terminal se hace los
siguiente:
1) Crear un estado inicial y un estado final
2) Para cada producción A → x 1∣x 2 ∣.. .∣x n
crear un camino desde el estado inicial al
estado final, con aristas etiquetadas con
x 1 ,x 2 , . .. ,x n

171
Ejemplo
E → TE' id + id
E'→ +TE' | ε
T → FT'
T' → * FT' | ε
F → (E) | id

172
Análisis sintáctico predictivo no
recursivo
• Los algoritmos recursivos generalmente
ocupan más recursos (memoria y
procesamiento) que los iterativos
• Se puede construir un analizador
sintáctico predictivo no recursivo
manteniendo explicitamente una pila, en
vez de hacerlo implicitamente con las
llamadas recursivas

173
Análisis sintáctico predictivo no
recursivo
• El problema clave durante el análisis
sintáctico predictivo es determinar la
producción que debe aplicarse a un no
terminal
• El analizador sintáctico no recursivo
busca la producción que debe aplicarse
en una tabla de análisis sintáctico

174
Modelo del analizador sintáctico
predictivo no recursivo
Entrada a+b$ buffer

Pila X Programa
Y para análisis Salida
Z sintáctico
$ predictivo

Tabla de análisis
sintáctico M 175
Componentes del analizador
sintáctico predictivo no recursivo
• Buffer de entrada: contiene la cadena que se va a
analizar, seguida de un símbolo $, un símbolo
utilizado como delimitador derecho para inidicar el
fin de la cadena de entrada
• Pila: contiene una secuencia de símbolos
gramaticales con $ en la parte de abajo, que
indica la base de la pila. Al principio, la pila
contiene el símbolo inicial de la gramática encima
de $
• Tabla de análisis sintáctico: es una matriz
bidimensional M [A, a], donde A es un no terminal,
y a es un terminal o el símbolo $ 176
Algoritmo de análisis sintáctico
predictivo no recursivo
• Entrada: una cadena w y una tabla de
análisis sintáctico predictivo no recursivo
• Salida: si w está en L(G), una derivación
por la izquierda de w; de lo contrario una
indicación de error

177
Apuntar al primer símbolo de w$
Repetir 
  Sea x el símbolo de la cima en la pila y a el símbolo apuntado
  Si x es un terminal o $ entonces
    Si x = a entonces
      Extraer x de la pila y avanzar al siguiente símbolo
    Si no
      Error()
  Si no /* x no es terminal */
    Si M [x,a] = x → y1y2...yk entonces
      Extraer x de la pila
      Meter yk, yk­1, ..., y1 en la pila, con y1 en la cima
    Else
      Error()
    Fin si
Hasta x = $ /* la pila está vacia */

178
Tabla de análisis sintáctico
E → TE'
E'→ +TE' | ε
T → FT'
T' → * F' | ε
F → (E) | id

179
Cálculo de conjuntos primero y
siguiente
• Las funciones primero y siguiente,
permiten rellenar siempre que sea
posible, las entradas de una tabla de
análisis sintáctico predictivo
• También se pueden utilizar los conjuntos
de componentes léxicos devueltos por la
función siguiente como componentes
léxicos de sincronización durante la
recuperación de errores en modo pánico
180
Conjunto primero
• Si α es una cadena de símbolos
gramaticales, se considera primero (α)
como el conjunto de terminales que
inician las cadenas derivadas de α
• Para calcular primero (x) para todos los
símbolos gramaticales x, aplíquense las
reglas siguientes hasta que ya no se
puedan agregar terminales o ε a ningún
conjunto primero
181
Conjunto primero
1. Si x es terminal, entonces primero (x) es {x}
2. Si x → ε es una producción, entonces añádase ε a
primero (x)
3. Si x es no terminal entonces se analizan todas las
reglas de producción con x en la izquierda de la forma:
x → y1 y 2 y 3 . .. y k
donde y k puede ser un terminal o no terminal
Para cada producción realizar las siguientes acciones:

182
Conjunto primero
– Añadir primero ( y 1) - {ε} a primero (x)
– Si ε está en primero ( y 1 ), entonces añadir
primero ( y 2 ) - {ε} en primero (x)
– Si ε está en primero ( y 3), entonces añadir
primero ( y 2) en primero(x)
– ...
– Si ε está en primero ( y i ) para 1≤i≤k (todas
sus producciones del lado derecho)
entonces poner ε dentro de primero (x)

183
En resumen...
• Añádase a primero ( x 1 x 2 x 3 . .. x n ) todos los
símbolos distintos de ε primero ( x 1)
• Si ε está en primero( x 1) añádase también los
símbolos distintos de ε de primero( x 2)
• Si ε está tanto en primero( x 1) como en
primero(x 2) añádase también los símbolos
distintos de ε de primero(x 3), y así
sucesivamente
• Por último, añádase ε a primero( x 1 x 2 x 3 . .. x n) si
para toda i primero( )xcontiene
i ε
184
Siguiente
• Para un no terminal A, siguiente(A) es el
conjunto de terminales que pueden
aparecer inmediatamente a la derecha
de A en alguna derivación parcial
• Por ejemplo:
– El terminal t está en siguiente(A) si
s → ...At... donde t es un terminal

185
Siguiente
1. Si A es el no terminal inicial, poner $ en
siguiente(A)
2. Encontrar las producciones con A en el lado
derecho
– Para cada producción x → αAβ , poner
primero ( β ) - {ε} en siguiente (A)
– Si ε está en primero( β) entonces poner
siguiente(X) en siguiente(A)
– Por cada producción x → αA, poner
siguiente (X) en siguiente(A)
186
Ejemplo
Primero (E) = {(, id}
E → TE'
Primero (E') = {+, ε}
E'→ +TE' | ε
Primero (T) = {(, id}
T → FT'
Primero (T') = {*, ε}
T' → * FT' | ε
Primero (F)= {(, id}
F → (E) | id
Siguiente (E) = {$, )}
Siguiente (E') = {$, )}
Siguiente (T) = {+, ), $}
Siguiente (T') = {+, ), $}
Siguiente (F) = {+, *, ), $}
187
Ejemplo

188
Ejercicio
L→L+E
L→E
E → (L)
E→a

189
Gramáticas LL(1)

Se puede aplicar el algoritmo de construcción
de tabla de análsis sintáctico para cualquier
gramática

Sin embargo, para algunas gramáticas la tabla
puede tener algunas entradas con definiciones
múltiples

Por ejemplo si la gramática es recursiva por
izquierda o ambigua, entonces la tabla tendrá
al menos una entrada con definición múltiple

190
Ejemplo
P → iEtPP' | a
P'→ eP' | ε
E→b

191
Gramática ambigua

La gramática anterior es ambigua y la
ambigüedad se manifiesta en la elección de la
producción que se va a utilizar cuando se
encuentra una e (else)

Ninguna gramática ambigua o recursiva por la
izquierda puede ser LL (1)

192
Recuperación de errores en el
análisis sintáctico predictivo
• Durante el análisis sintáctico predictivo
se detecta un error cuando:
– el terminal de la cima de la pila (tope) no
concuerda con el siguiente símbolo de
entrada
– Cuando el no terminal A esta en la cima
de la pila, a es el siguiente símbolo de
entrada, y la entrada M[A,a] de la tabla
de análisis sintáctico está vacia

193
Recuperación de errores en el
análisis sintáctico predictivo
• La recuperación en modo de pánico se
basa en la idea de saltarse símbolos de
la entrada hasta que aparezca un
componente léxico que pertenezca a un
conjunto seleccionado de componentes
léxicos de sincronización

194
Recuperación de errores en el
análisis sintáctico predictivo
• Para generar los componentes léxicos
de sincronización se aplica el siguiente
procedimiento:
– Se colocan todos los símbolos de
siguiente (A) dentro del conjunto de
sincronización para el no terminal A
• Si se saltan componentes léxicos hasta
encontrar un elemento de siguiente (A) y
se saca a A de la pila, es probable que
el análisis sintáctico pueda continuar
195
Aplicación del algoritmo
• Si el analizador sintáctico busca la entrada
M[A,a] y ve que está en blanco, debe saltarse
el símbolo de entrada a
• Si la entrada es sinc, se saca el no terminal de
la cima de la pila para continuar el análisis
• Si un componente léxico de la cima de la pila
no concuerda con el símbolo de entrada,
entonces se saca el componente léxico de la
pila, como ya se ha mencionado

196
Ejemplo
Primero (E) = {(, id}
E → TE'
Primero (E') = {+, ε}
E'→ +TE' | ε
Primero (T) = {(, id}
T → FT'
Primero (T') = {*, ε}
T' → * FT' | ε
Primero (F)= {(, id}
F → (E) | id
Siguiente (E) = {$, )}
Siguiente (E') = {$, )}
Siguiente (T) = {+, ), $}
Siguiente (T') = {+, ), $}
Siguiente (F) = {+, *, ), $}
197
Ejemplo

198
Ejemplo

id*+id)

199
Ejercicios
S → SS+ S → S+S
S→ SS* S→ SS
S→a S → (S)
S → S*
aa+a*
S→a
(a+a)*a

200

También podría gustarte