WIXLIB

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALESLENGUAJES FORMALES

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALESLENGUAJES FORMALES Todos los derec hos de propiedad intelec tual de esta obra pertenec en en exc lusiva a la UniversidadEuropea de Madrid, S.L.U. Queda terminantemente prohibida la reproduc c ión, puesta a disposic ión delpúblic o y en general c ualquier otra forma de explotac ión de toda o parte de la misma.La utilizac ión no autorizada de esta obra, así c omo los perjuic ios oc asionados en los derec hos depropiedad intelec tual e industrial de la Universidad Europea de Madrid, S.L.U., darán lugar al ejerc ic iode las ac c iones que legalmente le c orrespondan y, en su c aso, a las responsabilidades que de dic hoejerc ic io se deriven.2

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALESLENGUAJES FORMALESÍndicePresentación4¿Cuál fue la necesidad de los lenguajes formales?5Definiciones básicas6Definic ión de los c onc eptos: esenc iales y su notac ión6Operaciones con palabras8Operaciones con lenguajes9Gramáticas formales11Derivaciones y árbol de derivación12Ambigüedad14Eliminar la ambigüedad15Eliminar la rec ursividad a izquierdas15Fac torizar por la izquierda15Clasificación de los lenguajes de programación17Ventajas e inconvenientes de los lenguajes de alto nivel19Resumen203 Univ ersidad Europea de Madrid. Todos los derechos reserv ados.

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALESLENGUAJES FORMALESPresentaciónEl objetivo de este tema es que el estudiantecomprenda la necesidad y el origen de loslenguajes formales, junto con la forma deespecificar una gramática y a reconocer unasentencia, así como a identificar y eliminarambigüedades.El objetivo en este segundo tema es llegar aconocer los siguientes puntos:¿Cuál fue la necesidad de los lenguajesformales?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 lenguajesformales, junto con la jerarquía de Chomsky, lo que permitió abrirse a otro enfoque y llegar a lasolución que tenemos actualmente.4 Univ ersidad Europea de Madrid. Todos los derechos reserv ados.

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALESLENGUAJES 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 fueun verdadero compilador, adolecía de una gran complejidad. Casi al mismo tiempo que JohnBackus inició su compilador, Noam Chomsky empezó con el estudio del lenguaje natural, con laidea de estructurarlo, y consiguió una revolución en este campo.Una de sus muchas aportaciones fue la jerarquía de Chomsky para organizar lasgramáticas formales, entendiéndose por gramática las reglas necesarias paradefinir la estructura de un lenguaje formal.La jerarquía de Chomsky estructura las gramáticas en cuatro niveles, del más genérico y queincluye a los demás (tipo 0) al más específico (tipo 3):Gramáticas tipo 0Sin restricciones. Estas gramáticas tienen que tener en suparte izquierda al menos un símbolo no terminal(posteriormente veremos lo que significa, el concepto desímbolo terminal y no terminal).Gramáticas tipo 1Dependientes del contexto. Se las denomina dependientesdel contexto porque hay que tener en cuenta los símbolosque vienen antes y después del que queremos sustituir (sucontexto).Gramáticas tipo 2Independientesdelcontexto.Generan lenguajesindependientes del contexto y se caracterizan porque enla parte izquierda de una producción solo pueden tenerun símbolo no terminal.Gramáticas tipo 3Expresiones regulares. Estas son las gramáticas másrestrictivas y generan lenguajes regulares. En su parteizquierda tienen solo un no terminal y en su parte derechatienen solo un terminal.A nosotros, como diseñadores de lenguajes formales, nos interesan las gramáticas tipo 2, queson las que nos permiten definir un lenguaje de programación, y las de tipo 3, que nos permitirándefinir 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 vezhayamos definido los conceptos necesarios para entenderlos.Definiremos también a lo largo de esta Unidad la notación básica necesaria que utilizaremos paraespecificar un lenguaje formal.5 Univ ersidad Europea de Madrid. Todos los derechos reserv ados.

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALESLENGUAJES FORMALESDefiniciones básicasUn lenguaje natural es el lenguaje hablado o escrito que tiene como misión principalestablecer 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 loslenguajes de programación, y ejemplo de ellos son:CC JavaEtcDefinición de los conceptos: esenciales y su notaciónCarácter o símboloEs el componente indivisible y elemental con el que secompone un texto. Ejemplos: a, b, 5, [, )Es un conjunto de símbolos. Para los lenguajes formales,utilizamos alfabetos que contienen una cantidad finita desímbolos. Ejemplos:Alfabeto ( ) 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:Palabraabc 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 unaconvenció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 FORMALESLENGUAJES FORMALESLo constituyen todas las palabras que pueden formarsecon símbolos del alfabeto , incluyendo a la palabra vacía(λ). Contiene, por tanto, un número infinito de palabras.Universo de un alfabeto W( )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, ypor tanto, puede ser también infinito. Ejemplo: supongamosel alfabeto 1 (a, b, c, d, e , f, g, h, i).Lenguaje sobre un alfabetoL ( )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 FORMALESLENGUAJES FORMALESOperaciones con palabrasA 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 FORMALESLENGUAJES FORMALESOperaciones con lenguajesComo hemos visto anteriormente un lenguaje es cualquier subconjunto del universode 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). Hayotras operaciones como la potencia, reflexión, resta o complemento que no lasvamos a necesitar.Sean L1 y L2 dos lenguajes sobre un alfabeto , L1 U L2es el lenguaje formado por las palabras de L1 y por laspalabras de L2.Ejemplo: supongamos el alfabeto 1 (a, b, c, d, e, f, g, h,Unióni) 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ónde 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 decirque L2 U L1 daría el mismo resultado.Sean L1 y L2 dos lenguajes sobre un alfabeto , L1. L2 esel lenguaje formado por las palabras de L1 concatenadocon las palabras de L2.ConcatenaciónEjemplo: a partir del alfabeto y los lenguajes descritos en elpárrafo anterior, L 1. L2 {ba, ca, da, fa, ga, ha, aaba,aaca, aada,.}.Cierre Positivo ( )Es el lenguaje formado por todas las palabras que puedenformarse con símbolos del alfabeto , excluyendo lapalabra vacía. Si L2 1 {ba, ca, da, fa, ga, ha}, el cierrepositivo de ese lenguaje será L2 ( 1) {ba, baca, bada,ca, caba, cada, cafa,.}.9 Univ ersidad Europea de Madrid. Todos los derechos reserv ados.

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALESLENGUAJES FORMALESCierre o cerradura deKleene ( *)Es el lenguaje formado por todas las palabras que puedenformarse con símbolos del alfabeto , incluyendo lapalabra 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,.}.ClausuraA 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 FORMALESLENGUAJES FORMALESGramáticas formalesUna gramática formal es una descripción de la estructura de las sentencias queforman un lenguaje, entendiendo por lenguaje, en este contexto, un lenguaje deprogramación.La forma en la que se describe una gramática (G) es mediante cuatro términos: el alfabeto de lossímbolos terminales ( T), el alfabeto de los símbolos no terminales ( N), el axioma o símboloinicial de la gramática (S) y un conjunto de producciones (P). Se denota de la siguiente forma:¿Qué significa cada uno de estos com ponentes?Símbolos terminales ( T): representa al conjunto de palabras reservadas de un lenguaje de programación.Esto incluye los caracteres especiales y los operadores tanto aritméticos como lógicos. Ejemplo: en ellenguaje de programación C: T {main, {, }, #, include, if, then, define, int, float, char, double;, , -, *, , , ,.}. Se denotan con letras minúsculas: Ej: int, float, if.Símbolos no terminales ( N): representa el conjunto de variables que utilizamos en las producciones delas gramáticas como símbolos de transición. Esto incluye el símbolo inicial de la gramática (S) y lasvariables que utilicemos. Se denota con letras mayúsculas y veremos un ejemplo cuando expliquemos lasproducciones.Símbolo inicial (S): es un símbolo no terminal a partir del cual se obtienen todas las palabras del lenguaje yserá el primer símbolo de la gramática G. También se le denomina el axioma de la gramática.Conjunto de producciones (P): es un conjunto de reglas que indica cómo se obtienen las palabras dellenguaje definido por G. Establece las relaciones entre los símbolos terminales y los no terminales.Reglas del conjunto de producciones (P)11 Univ ersidad Europea de Madrid. Todos los derechos reserv ados.

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALESLENGUAJES FORMALESDerivaciones y árbol de derivaciónHemos visto de qué forma se puede especificar una gramática para generar frases de unlenguaje específico, aunque un compilador no se utiliza para generar programas.Un compilador debe revisar los símbolos y las sentencias que se construyen con ellos paradeterminar si pertenecen o no al lenguaje. Por tanto de lo que se trata es de ver cómo, a partir delsímbolo inicial de la gramática se puede derivar una secuencia de símbolos utilizando lasproducciones de esa gramática, y esto se hace mediante derivaciones. Estas derivaciones serepresentan gráficamente mediante un árbol de derivación, también llamado árbol de análisissintáctico.Lo vamos a ir viendo con un ejemplo, para la gramática definida en (1) y con la frase (id * id):12 Univ ersidad Europea de Madrid. Todos los derechos reserv ados.