PDF de programación - Introducción a compiladores y lenguajes formales

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

© Todos los derechos de propiedad intelectual de esta obra pertenecen en exclusiva a la Universidad
Europea de Madrid, S.L.U. Queda terminantemente prohibida la reproducción, puesta a disposición del
público y en general cualquier otra forma de explotación de toda o parte de la misma.

La utilización no autorizada de esta obra, así como los perjuicios ocasionados en los derechos de
propiedad intelectual e industrial de la Universidad Europea de Madrid, S.L.U., darán lugar al ejercicio
de las acciones que legalmente le correspondan y, en su caso, a las responsabilidades que de dicho
ejercicio se deriven.

2

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES



Índice

Presentación

¿Cuál fue la necesidad de los lenguajes formales?

Definiciones básicas

Definición de los conceptos: esenciales y su notación

Operaciones con palabras

Operaciones con lenguajes

Gramáticas formales

Derivaciones y árbol de derivación

Ambigüedad

Eliminar la ambigüedad

Eliminar la recursividad a izquierdas

Factorizar por la izquierda

Clasificación de los lenguajes de programación

Ventajas e inconvenientes de los lenguajes de alto nivel

Resumen

4

5

6

6

8

9

11

12

14

15

15

15

17

19

20

3
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

Presentación

El objetivo de este tema es que el estudiante

comprenda la necesidad y el origen de los
lenguajes formales, junto con la forma de
especificar una gramática y a reconocer una
sentencia, así como a identificar y eliminar
ambigüedades.

El objetivo en este segundo tema es llegar a

conocer los siguientes puntos:

¿Cuál fue la necesidad de los lenguajes

formales?

Definiciones básicas.

Operaciones con palabras.

Operaciones con lenguajes.

Gramáticas formales.

Derivaciones y árboles de derivación.

Ambigüedad.

Eliminación de la ambigüedad.

Clasificación de los lenguajes de programación.

Ventajas e inconvenientes de los lenguajes de alto nivel.

Al inicio veremos un pequeño repaso histórico para entender la motivación de los lenguajes

formales, junto con la jerarquía de Chomsky, lo que permitió abrirse a otro enfoque y llegar a la

solución que tenemos actualmente.

4
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

¿Cuál fue la necesidad de los lenguajes formales?

Allá por 1954, se inició el desarrollo del lenguaje de programación FORTRAN que, aunque fue
un verdadero compilador, adolecía de una gran complejidad. Casi al mismo tiempo que John
Backus inició su compilador, Noam Chomsky empezó con el estudio del lenguaje natural, con la
idea de estructurarlo, y consiguió una revolución en este campo.

Una de sus muchas aportaciones fue la jerarquía de Chomsky para organizar las
gramáticas formales, entendiéndose por gramática las reglas necesarias para

definir la estructura de un lenguaje formal.

La jerarquía de Chomsky estructura las gramáticas en cuatro niveles, del más genérico y que
incluye a los demás (tipo 0) al más específico (tipo 3):

Gramáticas tipo 0

Gramáticas tipo 1

Gramáticas tipo 2

Gramáticas tipo 3

izquierda al menos un símbolo no

Sin restricciones. Estas gramáticas tienen que tener en su
parte
terminal
(posteriormente veremos lo que significa, el concepto de
símbolo terminal y no terminal).

Dependientes del contexto. Se las denomina dependientes
del contexto porque hay que tener en cuenta los símbolos
que vienen antes y después del que queremos sustituir (su
contexto).

del

Generan lenguajes
Independientes
independientes del contexto y se caracterizan porque en
la parte izquierda de una producción solo pueden tener
un símbolo no terminal.

contexto.

Expresiones regulares. Estas son las gramáticas más
restrictivas y generan lenguajes regulares. En su parte
izquierda tienen solo un no terminal y en su parte derecha
tienen solo un terminal.

A nosotros, como diseñadores de lenguajes formales, nos interesan las gramáticas tipo 2, que
son las que nos permiten definir un lenguaje de programación, y las de tipo 3, que nos permitirán
definir cuáles son los caracteres que constituyen las palabras de nuestro lenguaje.

Posteriormente, veremos un ejemplo de cada uno de estos cuatro tipos de gramática, una vez

hayamos definido los conceptos necesarios para entenderlos.

Definiremos también a lo largo de esta Unidad la notación básica necesaria que utilizaremos para
especificar un lenguaje formal.

5
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

Definiciones básicas

Un lenguaje natural es el lenguaje hablado o escrito que tiene como misión principal

establecer la comunicación. Ejemplo de estos lenguajes son: español, inglés,

francés, chino, etc.

Podemos definir un lenguaje formal, además de como una especialización del lenguaje natural,
como el conjunto de palabras que están formadas por caracteres o símbolos, de longitud finita,

que a su vez forman parte de un alfabeto finito. Con los lenguajes formales construimos los

lenguajes de programación, y ejemplo de ellos son:

C

C++

Java

Etc

Definición de los conceptos: esenciales y su notación

Carácter o símbolo

Es el componente indivisible y elemental con el que se
compone un texto. Ejemplos: a, b, 5, [, )

Alfabeto (∑)

Palabra

Es un conjunto de símbolos. Para los lenguajes formales,

utilizamos alfabetos que contienen una cantidad finita de

símbolos. Ejemplos:

∑1 = (a, b, c, d, e, f, g, h, i).

∑2 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).

∑3 = El alfabeto del lenguaje de programación C.

Es una secuencia finita de símbolos de un alfabeto ∑.

Ejemplos:

abc → es una palabra definida sobre ∑1.

12 → es una palabra definida sobre ∑2.

main → es una palabra definida sobre ∑3.

Palabra vacía (λ)

Es una palabra que no contiene símbolos (es una
convención similar al número 0 en matemáticas).

6
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

Universo de un alfabeto W

(∑)

Lenguaje sobre un alfabeto
L (∑)

Lo constituyen todas las palabras que pueden formarse

con símbolos del alfabeto ∑, incluyendo a la palabra vacía

(λ). Contiene, por tanto, un número infinito de palabras.
Ejemplo: supongamos el alfabeto ∑1 = (a, b, c, d, e , f, g,
h, i).

El universo de ese alfabeto sería: W (∑1) = {λ, a, aa, ba,
ab, ac, ca, de,...}.

Es cualquier subconjunto del universo de ese alfabeto, y

por tanto, puede ser también infinito. Ejemplo: supongamos
el alfabeto ∑1 = (a, b, c, d, e , f, g, h, i).

Posibles lenguajes de ese alfabeto podrían ser:

L1∑1 = {λ, aa, bb, cc, dd}.

L2∑1 ={ba, ca, da, fa, ga, ha}.

7
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

Operaciones con palabras

A partir de las palabras y de las operaciones que vamos a ver se pueden construir otras palabras.

Estas operaciones son: concatenación, potencia y reflexión.

8
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

Operaciones con lenguajes

Como hemos visto anteriormente un lenguaje es cualquier subconjunto del universo
de un alfabeto L (∑), y las operaciones que nos interesan sobre un lenguaje son:
unión, concatenación, clausura positiva y la clausura o (cierre de Kleene). Hay
otras operaciones como la potencia, reflexión, resta o complemento que no las
vamos a necesitar.

Sean L1 y L2 dos lenguajes sobre un alfabeto ∑, L1 U L2
es el lenguaje formado por las palabras de L1 y por las
palabras de L2.

Ejemplo: supongamos el alfabeto ∑1 = (a, b, c, d, e, f, g, h,
i) y dos lenguajes de ese alfabeto podrían ser: L1∑1 = {λ,
aa, bb, cc, dd} y L2∑1 = {ba, ca, da, fa, ga, ha}. La unión
de L1 con L2 sería:

L1 U L2 = {λ, aa, bb, cc, dd, ba, ca, da, fa, ga, ha},
que cumple con la propiedad conmutativa, es decir
que L2 U L1 daría el mismo resultado.

Sean L1 y L2 dos lenguajes sobre un alfabeto ∑, L1. L2 es
el lenguaje formado por las palabras de L1 concatenado
con las palabras de L2.

Ejemplo: a partir del alfabeto y los lenguajes descritos en el
párrafo anterior, L1. L2 = {ba, ca, da, fa, ga, ha, aaba,
aaca, aada,...}.

Es el lenguaje formado por todas las palabras que pueden
formarse con símbolos del alfabeto ∑, excluyendo la
palabra vacía. Si L2∑1 = {ba, ca, da, fa, ga, ha}, el cierre
positivo de ese lenguaje será L2 (∑1)+ = {ba, baca, bada,
ca, caba, cada, cafa,...}.

Unión

Concatenación

Cierre Positivo (∑+)

9
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

Cierre o cerradura de
Kleene (∑*)

Es el lenguaje formado por todas las palabras que pueden
formarse con símbolos del alfabeto ∑, incluyendo la
palabra vacía, que siempre será parte del cierre. Si L2∑1
= {ba, ca, da, fa, ga, ha}, el cierre de ese lenguaje será L2
(∑1)* = {λ, ba, baca, bada, ca, caba, cada, cafa,...}.

Clausura

A la operación de cierre también se le denomina clausura en distintos libros de texto.

10
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

LENGUAJES FORMALES

Gramáticas formales

Una gramática formal es una descripción de la estructura de las sentencias que

forman un lenguaje, entendiendo por l