PDF de programación - Procesadores del lenguaje

Procesadores del lenguaje

Pau Arlandis Martínez

Introducción
Un compilador es un programa que traduce un lenguaje (código fuente de otro programa) de
código en otro texto en lenguaje objeto.

Compilador

Fase de análisis => Procesador de
lenguaje

Fase de síntesis

Análisis léxico

Generador de código

Análisis sintáctico

Optimizador

Programa

objeto

Análisis semántico

Generador de código intermedio

Control de errores

Tabla de símbolos



Programa



fuente



Mensajes

de error



Este es el esquema básico de un compilador, veámoslo por partes:

Fase de análisis
En la fase de análisis se estudia el lenguaje del programa fuente, errores, elementos de
interés… Esta fase también se denomina procesador del lenguaje y es lo que vamos a ver en
esta asignatura. La fase de análisis se describe en tres subfases:

Análisis léxico
Se encarga de analizar los elementos más pequeños de un texto que tienen sentido por sí
mismas.

Análisis sintáctico
Se encarga de analizar la estructura de un texto.



1

Análisis semántico
Se encarga de estudiar el significado de todos los elementos dentro del texto.



Ejemplo

Texto Fuente
límite := largo * alto – 1

Analizador léxico
El analizador léxico estudia carácter a carácter conociendo las estructuras mínimas que tienen
sentido por sí mismas. A estas se las denomina Tokens.

límite := largo * alto – 1



‘l’ no tiene
sentido en
sí mismo.

‘lar’ no tiene
sentido en sí
mismo.

‘*’ SÍ tiene
sentido

‘alto’ SÍ tiene
sentido

Texto resultado
Identificador1/op.asignación1/identificador2/op.
aritmética1/identificador3/op.aritmético2/constante_entera1/

A grandes rasgos este sería el resultado del analizador. Cada token necesitaría más
información pero eso lo veremos más adelante.

Analizador sintáctico
Estudia la estructura de la secuencia de tokens para conocer si es una estructura permitida o
no lo es.

En el ejemplo:



2

Árbol resultado
Resulta entonces en un árbol sintáctico donde se detalla la estructura de la sentencia:



Este árbol es la entrada del analizador semántico que estudia si la sentencia (estructuralmente
correcta) tiene sentido en el lenguaje.

Analizador Semántico
Este analizador hace anotaciones en el árbol sintáctico comprobando tipos, variables
definidas,…

Por ejemplo:



3



Control de errores
Cada fase de análisis tiene sus propios errores:

 Errores léxicos: Se utilizan operadores inexistentes o palabras mal formadas  limi?te

, */

 Errores sintácticos: Se estructuran mal los tokens, de forma incorrecta o confusa 

id1 op.asig id2 cte_entera

 Errores semánticos: La estructura de tokens elegida es correcta pero no tiene sentido

 id1(Entero) op.asig expr(real)

Todos estos errores se analizan en el control de errores.

Tabla de símbolos
La tabla de símbolos es una colección de símbolos que utiliza nuestro texto para almacenar
información de cada token. El procesador del lenguaje interactúa con ella para almacenar y
consultar su contenido.

Estos 5 módulos de la fase de análisis son, básicamente, los temas y el contenido de la
asignatura. Para completar la información, introduzcamos también el contenido de la fase de
síntesis.



Fase de síntesis
Una vez resuelta sin errores la fase de análisis comienza la fase de síntesis que será la
encargada de construir el texto objeto del texto fuente que hemos utilizado. La fase de síntesis
se subdivide en tres módulos:

Generador de código intermedio
Este es el primer paso, su misión consiste en facilitar la traducción del lenguaje fuente al
lenguaje objeto traduciendo el primero a un lenguaje intermedio. Utiliza el árbol anotado de la
fase de análisis.

Su otra misión es muy útil para reutilizar módulos ya que podemos traducir muchos lenguajes
al mismo lenguaje intermedio.

En el ejemplo:

C.I 

temp1 := id2*id3



temp2:= 1

temp3:=temp1-temp2

id1:=temp1

Optimizador
El lenguaje resultante del generador de código intermedio (CI) suele ser demasiado
redundante y poco eficiente ya que traducen paso a paso el árbol semántico sin fijarse en



4

pasos anteriores. Por ello es necesario el optimizador, para convertir el CI en un lenguaje
eficiente:

O.C.  temp1 := id2*id3



id1 := temp1 – 1

Generador de código
El último paso del proceso de síntesis es muy similar al primero, el generador de código se
encarga de traducir el CI optimizado resultado del proceso anterior, que es más fácil que el
lenguaje inicial, en código ensamblador de muy bajo nivel.

En el ejemplo:

G.C.  move id2, r1

mul

id3, r1

sub

#1, r1

move r1, id1



Lenguajes y gramáticas

Repaso de la teoría de lenguajes

 Alfabeto: Conjunto finito de símbolos.

(a-z, A-Z)

o String o cadena: Cualquier secuencia de símbolos de un alfabeto.

hola





Longitud: Número de caracteres de una cadena.


hola  4

 Cadena vacía: Cadena con longitud 0, denominada λ.


Lenguaje: Conjunto de cadenas válidas formadas por un determinado alfabeto.



o Válido: Cumple unas determinadas reglas.



 Gramática: Especificación precisa y formal de todas las cadenas válidas para un

determinado alfabeto. Definen y especifican un lenguaje. Se denomina como una 4-
tupla (N, T, P, S) donde:

o N: Símbolos no terminales (símbolos auxiliares)
o T: Símbolos terminales (alfabeto del lenguaje). Una cadena solo puede estar

compuesta de símbolos terminales.

o P: Reglas de producción. Antecedente  Consecuente.
o S: Elemento de N, llamado axioma, que es el generador de todas las cadenas,

es el primer antecedente.

Ejemplo: G1(N={A}; T={0,1}; P



; ; j; ; S={A})

A  0A
A  1A
A  0

5

A 0

A  0A  00

A  1A  10A  100

Jerarquía de Chomsky

Entonces:
L(G1) = { C/ A *C} = {0,1}*0

 Tipo 0 (sin restricciones) = Las reglas de producción pueden ser de cualquier tipo. α 

β α,βϵ{N U T}*


 Tipo 1 (dependientes del contexto) = αAβ  αϒβ

AϵN ϒϵ{N U T}*



 Tipo 2 (Independientes del contexto) = Aϒ



 Tipo 3 (gramáticas regulares) = AaB ; A a aϵT BϵN

Nos interesan en esta asignatura.

L(G0)

L(G1)



Las gramáticas de tipo 2 las usaremos en el
análisis sintáctico.

L(G2)

L(G3)

Para el análisis léxico utilizaremos gramáticas de
tipo 3 (regulares)



R. por la izquierda
B  Bα
Ejemplo:

BB1



BB1B11

Existen analizadores sintácticos incompatibles con esta recursividad por eso debemos crear
una gramática equivalente sin recursividad por la izq.

Eliminación Recursividad por la izquierda
A  Aα
A  β A  βA’
A’α A’αA’ Tras β hay tantos α como se quiera
A  β
Mantenemos las



producciones normales


β

Aα  βα

Aαα  βαα

Aααα  βααα


β
βA’  βα
βA’  βαA’  βαα
βA’  βαA’  βααA’  βααα

Introducimos un símbolo N auxiliar y se elimina la
recursividad por la izquierda.

A  B



6

Factorizar por la izquierda
A  1B Existen
A αβ

A  αϒ

A  1C



A  αA’
A’  β
A’  ϒ


Gramática ambigua
Una gramática es ambigua si existen dos formas diferentes de generar una misma sentencia,
una misma cadena. Los procesadores del lenguaje no son compatibles con las G. ambiguas.
Ejemplo:

1. S  if E then S
2. S  if E then S else S
3. S  P

y en el lenguaje aparece:



if e1 then if e2 then P1 else P2

de forma:

S 1 if e1 then S 2 if e1 then if e2 then P1 else S 3 if e1 then if e2 then P1 else P2

pero:

S 2 if e1 then S else S 1 if e1 then if e2 then S else S 3 if e1 then if e2 then P1 else S 3 if
e1 then if e2 then P1 else P2

Hemos llegado a la misma cadena mediante dos caminos generadores. Esta es una gramática
ambigua. Ningún analizador sintáctico permite una gramática ambigua ya que esta generaría
distintos árboles y, por tanto, distintos códigos objeto.



Ejercicio

E  E + T

E  T
T  T*F
F  a
F  (E)
T  F
Es una gramática recursiva por la izquierda. Elimina dicha recursividad.



7

Análisis léxico

El analizador léxico simplifica el trabajo al Analizador sintáctico agrupando todas aquellas
cadenas que tienen la misma estructura sintáctica. Por ejemplo, si recibe la cadena límite el A.
léxico debe saber que esto es un identificador a nivel sintáctico y así con cada uno de los
tokens.



Funciones del Analizador léxico

Leer los caracteres del TF.

 Manejar el fichero del texto fuente (TF).

 Enviar al Analizador sintáctico un token.
 Eliminar del TF todo lo que sea superfluo. Por ejemplo: comentarios, espacios en

blanco, saltos de línea…

 Detectar errores léxicos. Es decir, secuencias de caracteres que no corresponden a

ningún token. Por ejemplo:

o 10,00,0  Número mal formado
o 7a8  Error léxico
o año, alá  Caracteres incorrectos en la mayoría de compiladores.

Imposibilidad de formar un token

 Relacionar los errores con su posición en el TF.
 Pre procesar el TF (macros)


Interactuar con la tabla de símbolos.

Definiciones

Token (componente léxico)
Cada uno de los elementos del lenguaje que estamos identificando que tienen sentido o
significado por sí mismos. Es un conjunto mínimo de caracteres. Ejemplo:

limite := 100



if a = 3 then



Es un solo token ya que
‘:’ o ‘=’ no tienen
sentido aquí en sí
mismas.

Este ‘=’ sí tiene sentido
aunque vaya solo.



8



Todo token tiene algunos componentes importantes:

Lexema
Es el conjunto de caracteres que forman un token. Ejemplo:

límite (6 caracteres) en un identificador.

Patrón
La regla que describe como un determinado lexema se asocia a un determinado token.
Ejemplo:

“Secuencia alfanumérica (sin espacios ni signos de puntuación) que empieza por una letra” en
un identificador.

Tipos de token
Existen algunos tipos básicos que apa