analisis sintactico ii

DEPARTAMENTO DE MATEMATICAS CUADERNO DIDACTICO N 61

ANALISIS SINTACTICO EN PROCESADORES DE LENGUAJE

Juan Manuel Cueva Lovelle Catedrtico de E.U. de Lenguajes y Sistemas Informticos Departamento de Matemticas Universidad de Oviedo 2 Edicin Oviedo, Abril 1995

Anlisis sintctico en procesadores de lenguaje

1 INTRODUCCIONEl anlisis sintctico (parser en lengua inglesa) toma los tokens que le envia el analizador lxico y comprueba si con ellos se puede formar alguna sentencia vlida del lenguaje. Recurdese que se entiende por sintaxis como el conjunto de reglas formales que especifican como se construyen las sentencias de un determinado lenguaje. La sintaxis de los lenguajes de programacin habitualmente se describe mediante gramticas libres de contexto (o gramticas tipo 2) utilizando algn tipo de notacin. Por ejemplo las notaciones BNF y EBNF. Esta especificacin ofrece numerosas ventajas a los diseadores de lenguajes y a los escritores de compiladores: Una gramtica da una especificacin sintctica precisa, y fcil de comprender, de un lenguaje de programacin. Para ciertas clases de gramticas se puede construir automticamente un analizador sintctico, que determina si un programa est bien construido. Como beneficio adicional, el proceso de construccin del analizador sintctico puede revelar ambigedades sintcticas y otras dificultades para la construccin del parser que de otra forma no seran detectadas en la fase de diseo inicial de un lenguaje y que podran se arrastradas a su compilador. Una gramtica bien diseada da una estructura al lenguaje de programacin que se utiliza en la traduccin del programa fuente en cdigo objeto correcto y para la deteccin de errores. Existen herramientas que a partir de la descripcin de la gramtica se puede generar el cdigo del analizador sintctico. Los lenguajes de programacin despus de un periodo de tiempo, adquieren nuevas construcciones y llevan a cabo tareas adicionales. Estas nuevas construcciones se pueden aadir ms fcilmente al lenguaje cuando hay una implementacin basada en una descripcin gramatical del lenguaje. El papel del analizador sintctico dentro de un procesador de lenguaje puede representarse segn el esquema de la figura 1.Manejo de errores

token programa fuente Analizador lxico pide siguiente token Analizador sintctico rbol sintctico Analizador semntico representacin intermedia

Tabla de smbolos

Figura 1: Interfaces del analizador sintctico

2 GRAMATICAS LIBRES DE CONTEXTOHabitualmente las estructura sintctica de los lenguajes de programacin se especifica sintcticamente mediante gramticas libres de contexto o de tipo 2.

2.1 Derivaciones y rboles sintcticosAnalizar sintcticamente una cadena de tokens es encontrar para ella un rbol sintctico o derivacin, que tenga como raz el smbolo inicial de la gramtica libre de contexto y mediante la aplicacin sucesiva de sus reglas de derivacin se pueda alcanzar dicha cadena como hojas del rbol sintctico. En caso de xito la sentencia pertenece al lenguaje generado por la gramtica, y puede proseguirse el proceso de compilacin. En caso contrario, es decir cuando no se encuentra el rbol que genera dicha gramtica, se dice entonces que la sentencia no pertenece al lenguaje, y el compilador emite un mensaje de error, pero el proceso de compilacin trata de continuar. Algunos compiladores paran el proceso de compilacin cada vez que encuentran un error, en ellos es necesario realizar tantas compilaciones como errores tendra el programa fuente.

2.1.1 Ejemplo: gramtica de expresiones aritmticasSupongamos que se desea construir una gramtica G={VN, VT, S, P} que describe un lenguaje basado en la utilizacin de expresiones aritmticas con sumas, diferencias, productos, divisiones, potenciacin, parntesis, y menos unario. Este lenguaje tambin permitir el uso de constantes e identificadores de variables. La gramtica est compuesta por un vocabulario terminal

-1-


VT formado por los smbolos de los operadores, parntesis y los tokens constante e identificador. El vocabulario no terminal VN slo contendr el smbolo no terminal . El smbolo inicial S tambin ser . La gramtica G queda tal y como se muestra a continuacin: VT= {+, *, /, ^, (, ), -, identificador, constante} VN= { } S= Las reglas de produccin P que en un principio representaran al lenguaje se muestran a continuacin numeradas del (1) al (9). La numeracin se utilizar para indicar la regla que se aplica en cada derivacin. (1) ::= + (2) ::= * (3) ::= - (4) ::= / (5) ::= ^ (6) ::= - (7) ::= ( ) (8) ::= identificador (9) ::= constante Sea la expresin - ( a * 9 ) se desea saber si pertenece o no al lenguaje, para lo cual se pretende alcanzar a partir de derivaciones desde el smbolo inicial de la gramtica, construyndose el rbol sintctico de la figura 2. El rbol sintctico no indica el orden seguido para alcanzar la cadena incognita. Para indicar el orden de aplicacin de las derivaciones con las que se construy el rbol se muestran las derivaciones siguientes, sealando encima de la flecha el nmero de la regla aplicada: - -() -( * ) -( identificador * ) -(identificador * constante) El analizador lxico se encarga de reconocer los smbolos terminales, as tambin indica que a es un identificador y que 9 es una constante.(6) (7) (2) (8) (9)

-

(

)

*

identificador

constante

a

9

Figura 2: Arbol sintctico de -(a*9)

2.2 Derivaciones ms a la izquierda y ms a la derechaLas reglas de derivacin que se aplican desde el smbolo inicial hasta alcanzar la sentencia a reconocer, pueden reemplazar los smbolos no terminales tomando el de ms a la izquierda (derivaciones ms a la izquierda) o tomando el no terminal de ms a la derecha (derivaciones ms a la derecha).

-2-


Habitualmente se trabaja con derivaciones ms a la izquierda. Se puede demostrar que todo rbol de anlisis sintctico tiene asociado una nica derivacin izquierda y una nica derivacin derecha. Sin embargo una sentencia de un lenguaje puede dar lugar a ms de un rbol de anlisis sintctico tanto por la derecha como por la izquierda.

2.2.1 EjemploSea la gramtica de contexto libre G= (VN, VT, S, P) para al generacin de expresiones aritmticas donde VN= {S, T, F}, VT= {a, b, +, *, (, )} y las reglas de produccin P son: (1) S S+T (2) ST (3) T T*F (4) TF (5) F (S) (6) F (a) (7) F (b) Determinar los rboles sintcticos ms a la izquierda y ms a la derecha que reconocen la cadena a*(a+b). Para determinar el rbol ms a la izquierda se parte del smbolo inicial S y en la variable parse se van poniendo las producciones aplicadas, utilizando nmeros para indicar los cdigos de cada regla aplicada. Siempre se expansiona el no terminal ms a la izquierda en el rbol hasta alcanzar un smbolo terminal. En las figuras siguientes se observa como se alcanza el rbol ms a la izquierda aplicando las producciones por el rden indicado por los nmeros 23465124647.

S

S

S

Tparse= 2

T T *parse= 23

T F T Fparse= 234

*

F

S

S

S

T T F aparse= 2346

T F T F aparse= 23465

T F T ) F a * ( F S ) T

*

* (

S

S +parse= 234561

-3-


S

S

S

T T F a * ( F S ) T T F a

T * ( F S ) T T F a

T * ( F S ) T

S + Tparse= 2346512

S + T Fparse= 23465124

S + T F aparse= 234651246

S

S

T T F a * ( F S ) T F T F a

T * ( F S ) T F b

S + T F a

S + T F a

parse= 2346512464

parse Izdo= 23465124647

Para obtener el rbol ms a la derecha se parte del smbolo inicial S y se van aplicando las producciones de forma que se eligen en primer lugar las expansiones del smbolo no terminal ms a la derecha en el rbol. As en la variable produccin utilizada (p.u.) se van colocando los nmeros de las producciones utilizadas. En las figuras siguientes puede observarse el orden de sustitucin hasta alcanzar el rbol ms a la derecha representado por los nmeros 23514724646.

-4-


S

S

S

Tproduccin utilizada= 2

T T *p.u.= 23

T F T * ( F S )

p.u.= 235

S

S

S

T T * ( F S ) T T

T * ( F S ) T Fp.u.= 23514

T T * ( F S ) T F bp.u.= 235147

S +p.u.= 2351

S +

S +

S

S

S

T T * ( F S ) T F bp.u.= 2351472

T T * ( F S ) T F b T

T * ( F S ) T F b

S + T

S + T Fp.u.= 23514724

S + T F ap.u.= 235147246

-5-


S

S

T T F * ( F S ) T F b T F a

T * ( F S ) T F b

S + T F ap.u.= 2351472464

S + T F a

p.u.= 23514724646

Puede observarse que los rboles finales alcanzados son los mismos aunque por distintos caminos. En general puede ocurrir que el rbol ms a la izquierda y el rbol ms a la derecha no sea el mismo, dando lugar a problemas de ambigedad tal y como se estudia en el apartado 2.4.

2.3 RecursividadLas reglas de produccin de una gramtica estn definidas de forma que al realizar sustituciones dan lugar a recursividades. Entonces se dice que una regla de derivacin es recursiva si es de la forma:A A

Si es nula, es decir A A se dice que la regla de derivacin es recursiva a izquierda. De la misma forma A A es recursiva a derecha (vase figura 3).

A A A A

A A A A

Recursividad a Izquierda

Recursividad a Derecha

Figura 3: Recursividad a izquierdas y a derechas

-6-


Los analizadores sintcticos que trabajan con derivaciones ms a la izquierda deben de evitar las reglas de derivacin recursivas a izquierda, pues entraran en un bucle infinito.

2.3.1 EjemploSea la gramtica siguiente que describe nmeros enteros e identificadores: | | | sus rboles sintcticos son los de la figura 4.

Figura 4: Arboles sintcticos recursivos

2.4 Gramticas ambiguasUna sentencia generada por una gramtica es ambigua si existe ms de un rbol sintctico para ella. Una gramtica es ambigua si genera al menos una sentencia ambigua, en caso contrario es no ambigua. Ntese que se llama a la gramtica ambigua y no al lenguaje que genera dicha gramtica. Hay muchas gramticas equivalentes que pueden generar el mismo lenguaje, algunas son ambiguas y otras no. Sin embargo existen ciertos lenguajes para los cuales no pueden encontrarse gramticas no ambiguas. A tales lenguajes se les denomina ambiguos intrnsecos. Por ejemplo el lenguaje {xi, yj, zk / i=j o j=k} es un lenguaje ambiguo intrnseco. El grado de ambigedad de una sentencia se caracteriza por el nmero de rboles sintcticos distintos que la generan. La ambigedad de una gramtica es una propiedad indecidible, lo que significa que no existe ningn algoritmo que acepte una gramtica y determine con certeza y en un tiempo finito si la gramtica es ambigua o no.

2.4.1 EjemploSea la gramtica de manejo de expresiones mostrada en el apartado 2.1.1. Se puede comprobar que la sentencia: 5-C*6 tiene dos derivaciones ms a la izquierda diferentes, y cuyos rboles sintcticos tambin son diferentes. - constante- 5-* 5-identificador* 5-C*constante 5-C*6EXP EXP constante 5 EXP EXP * EXP constante 6EXPconstante identificador

* -* constante-* 5-identificador* 5-C*constante 5-C*6EXP EXP * EXP EXP constante 6

identificador c

identificador constante

5

c

Figura 5: Arbol 1

Figura 6: Arbol 2

El rbol de anlisis sintctico de la figura 5 refleja la precedencia habitual de Matemticas de la operacin sustraccin sobre la multiplicacin. Mientras que en el rbol de la figura 6 no se respeta esta precedencia.

-7-


2.5 Conversin de gramticas ambiguas en no ambiguasSe ha indicado anteriormente que la propiedad de ambigedad es indecidible, es decir, no existe ni puede construirse un algoritmo que, tomando una gramtica en BNF, determine con certeza, y en plazo finito de tiempo, si es ambigua o no. Sin embargo, se han desarrollado las condiciones que, de cumplirse, garantizan la no ambigedad, aunque en caso de que no se cumplan no puede afirmarse nada. Son condiciones suficientes pero no necesarias. As, las gramticas del tipo LL(k) y LR(k), que se estudiarn en otros apartados siguientes a ste, son no ambiguas, pero una gramtica que no sea LL(k) ni LR(k) no puede decirse que sea ambigua. Una gramtica ambigua produce problemas al analizador sintctico, por lo que interesa construir gramticas no ambiguas. Sin embargo, en algunos lenguajes de programacin, la ambigedad sintctica existe y se deber eliminar con consideraciones semnticas.

2.5.1 Ejemplo: representacin de los arrays y llamada de funcionesLa representacin de los elementos de un array en los lenguajes PL/I y FORTRAN da lugar a ambigedades, pues se puede confundir la llamada a una funcin con un elemento de un array. As la expresin M(I,J,K) es ambigua, puede considerarse como el elemento Mi,j,k del array, y tambin la llamada a la subrutina M con los parmetros I,J,K. Si la declaracin de variables de tipo array o de funciones es obligatoria, tambin se resuelve la ambigedad, en caso contrario han de tenerse en cuenta consideraciones semnticas. Los lenguajes Pascal, C, C++, y Algol 60 resuelven esta ambigedad empleando corchetes para representar los arrays. El lenguaje FORTRAN no tiene declaracin obligatoria de variables ni de subrutinas, pero resuelve la ambigedad obligando a declarar las funciones no estndar. La llamada a subrutinas no constituye ambigedad pues se deben hacer con la sentencia CALL. El lenguaje PL/I resuelve la ambigedad con la declaracin obligatoria de todas las variables.

2.5.2 Ejemplo: else danzante o ambiguoUna sentencia alternativa simple es de la forma siguiente: ::= if then | if then else | otra_sentencia Puede darse el caso de que la sentencia que va despus del then sea otra sentencia alternativa, es decir se produce una sentencia if-then-else anidada de la forma: if E1 then if E2 then S1 else S2 En este caso se produce una ambigedad pues la parte correspondiente al else puede asociarse a dos if, lo que da lugar a dos rboles sintcticos, que se muestran en las figuras 7 y 8.

IF E1 THEN IF E2 THEN S1 ELSE S2

Figura 7: Arbol 1, el else se asocia con el if anterior ms cercano

-8-


IF

E1

THEN

IF

E2

THEN

S1

ELSE

S2

Figura 8: Arbol 2, el else se asocia con el primer if

La mayor parte de los lenguajes de programacin con sentencias condicionales de este tipo utilizan el primer rbol sintctico (fig. 7), es decir utilizan la regla el else se empareja con el if anterior ms cercano. Esta regla elimina la ambigedad y se puede incorporar a la gramtica. Se construye una gramtica equivalente que elimine la ambigedad. La idea es que una sentencia que aparezca entre un THEN y un ELSE debe estar emparejada, es decir no debe terminar con un THEN sin emparejar seguido de cualquier sentencia, porque entonces el ELSE estara obligado a concordar con este THEN no emparejado. As sentencia emparejada tan solo puede ser una sentencia alternativa IF-THEN-ELSE que no contenga sentencias sin emparejar o cualquier otro tipo de sentencia diferente de la alternativa. La nueva gramtica equivalente ser la siguiente: ::= | ::= IF THEN ELSE | OTRA_SENTENCIA ::= IF THEN | IF THEN ELSE El problema del if-then-else se volver a tratar en el apartado 5.4.5.2.1.

2.5.3 Ejemplo: definicin de precedencia y asociatividadUna de las principales formas de evitar la ambigedad es definiendo la precedencia y asociatividad de los operadores. As el lenguaje C est basado en el uso intensivo de operadores, con una definicin estricta de las precedencias y asociatividades de cada uno de ellos. Volvamos otra vez a la gramtica de expresiones ya utilizada en los ejemplos 2.1.1 y 2.4.1. Dicha gramtica era ambiga debido a problemas de precedencia y asociatividad de sus operadores. En este ejemplo se mostrar como se refleja la precedencia y asociatividad en la gramtica para evitar la ambigedad. Se define el orden de precedencia de evaluacin de las expresiones y los operadores. A continuacin se presenta el orden de precedencia de mayor a menor precedencia: 1) 2) 3) 4) ( ) identificadores constantes - (menos unario) ^ (potenciacin) */

5) + La asociatividad se define de forma diferente para el operador potenciacin que para el resto de los operadores. As el operador ^ es asociativo de derecha a izquierda: a ^ b ^ c = a ^ (b ^ c) mientras que el resto de los operadores binarios sern asociativos de izquierda a derecha, si hay casos de igual precedencia.

-9-


a-b-c= (a-b)-c a+b-c= (a+b)-c a*b/c= (a*b)/c Estas dos propiedades, precedencia y asociatividad, son suficientes para convertir la gramtica ambigua basada en operadores en no ambigua, es decir, que cada sentencia tenga slo un rbol sintctico. Para introducir las propiedades anteriores de las operaciones en la gramtica se tiene que escribir otra gramtica equivalente en la cual se introduce un smbolo no terminal por cada nivel de precedencia.

2.5.3.1 Nivel de precedencia 1Se introduce el no terminal para describir una expresin indivisible, y con mxima precedencia, por lo tanto ::= ( ) | identificador | constante

2.5.3.2 Nivel de precedencia 2Se introduce el no terminal , que describe el menos unario y el no terminal de precedencia superior. ::= - |

2.5.3.3 Nivel de precedencia 3El siguiente no terminal que se introduce es que describe los operadores del siguiente nivel de precedencia. ::= ^ | Hay que sealar que el orden es fundamental. As ^ obliga a expresiones del tipo a ^ b ^ c a agruparse como a ^ (b ^ c) siendo su rbol sintctico el representado en la figura 9.

^

^

identificador

a

identificador

b

identificador

cFigura 9:Arbol de a^b^c

- 10 -


2.5.3.4 Nivel de precedencia 4El siguiente no terminal que se introduce es , que es una secuencia de uno o ms factores conectados con operadores de nivel de precedencia 4, es decir: multiplicacin y divisin. ::= * | / | El orden de esta produccin obliga a que expresiones del tipo: a * b / c signifique (a * b) / c

2.5.3.5 Nivel de precedencia 5Por ltimo se introduce el no terminal que representar a conectado a otro con operadores de menor precedencia: adicin y sustraccin. ::= + | - |

2.5.3.6 Gramtica equivalente no ambiguaEntonces la nueva gramtica no ambigua ser GNA= (VN, VT, S, P) donde: VN= {, , , , } VT= {identificador, constante, (, ), ^, *, /, +, -} S= y las producciones P: + | - | ::= * | / | ::= ^ | ::= - | ::= ( ) | identificador | constante Entonces el rbol sintctico de la sentencia a * c + d ^ 4 se muestra en la figura 10. Sin embargo esta gramtica es recursiva a izquierdas, este inconveniente se resolver en el ejemplo del apartado 5.4.5.2.2. ::=

- 11 -


identificador aFigura 10:Arbol de a*c+d^4

+

^ constante 4

*

identificador c identificador d

2.6 Gramticas limpias y gramticas suciasLas gramticas de los lenguajes de programacin estn formadas por un conjunto de reglas BNF, cuyo nmero suele ser bastante amplio, lo cual incide en la ocultacin de distintos problemas que pueden producirse, tales como tener reglas que produzcan smbolos que no se usen despus, o que nunca se llegue a cadenas terminales. Todo esto se puede solventar realizando la transformacin de la gramtica inicial "sucia" a una gramtica "limpia". A continuacin se formalizarn estos conceptos por medio de definiciones. Smbolo muerto: es un smbolo no terminal que no genera ninguna cadena de smbolos terminales. Smbolo inaccesible: es un smbolo no terminal al que no se puede llegar por medio de producciones desde el smbolo inicial. Smbolo extrao: se denomina as a todo smbolo muerto o inaccesible. Gramtica sucia: es toda gramtica que contiene smbolos extraos. Gramtica limpia: es toda gramtica que no contiene smbolos extraos. Smbolo vivo: es un smbolo no terminal del cual se puede derivar una cadena de smbolos terminales. Todos los smbolos terminales son smbolos vivos. Es decir son smbolos vivos lo que no son muertos. Smbolo accesible: es un smbolo que aparece en una cadena derivada del smbolo inicial. Es decir, aquel smbolo que no es inaccesible.

2.7 Limpieza de gramticasEn el apartado anterior se han definido algunos problemas que pueden presentarse en una gramtica. Por lo tanto es norma general que toda gramtica en bruto ha de limpiarse con el objetivo de eliminar todos los smbolos extraos. Existen algoritmos para depurar y limpiar las gramticas sucias. El mtodo consiste en detectar en primer lugar todos los smbolos muertos, y a continuacin se detectan todos los smbolos inaccesibles. Es importante seguir este orden, puesto que la eliminacin de smbolos muertos puede generar nuevos smbolos inaccesibles. Los algoritmos que se utilizan en la limpieza de gramticas se basan en los teoremas que se enunciarn a continuacin sobre los smbolos vivos y los smbolos accesibles.

- 12 -


2.7.1 Teorema de los smbolos vivosSi todos los smbolos de la parte derecha de una produccin son vivos, entonces el smbolo de la parte izquierda tambin lo es. La demostracin es obvia. Este teorema se utiliza para construir algoritmos de deteccin de smbolos muertos. El procedimiento consiste en iniciar una lista de no terminales que sepamos a ciencia cierta que son smbolos vivos, y aplicando el teorema anterior para detectar otros smbolos no terminales vivos para aadirlos a la lista. Dicho de otra forma, los pasos del algoritmo son: 1) Hacer una lista de no-terminales que tengan al menos una produccin sin smbolos no terminales en la parte derecha. 2) Dada una produccin, si todos los no-terminales de la parte derecha pertenecen a la lista, entonces podemos incluir al no terminal de la parte izquierda. 3) Cuando no se puedan incluir ms smbolos mediante la aplicacin del paso 2), la lista contendr todos los smbolos vivos, el resto sern muertos.

2.7.2 EjemploSea la gramtica expresada en BNF: ::= a | d ::= b ::= e | de ::= g | h ::= f ::= t | v Determinar los smbolos muertos. Se aplican los pasos: 1) Confeccin de la lista: slo hay un smbolo no terminal con el cual comenzar la lista. 2) Aplicando el teorema 2.7.1 se incluyen en la lista por el siguiente orden: 3) No se puede aplicar el teorema ms veces, por lo tanto la lista de smbolos vivos est completa y los smbolos y son no terminales muertos.

2.7.3 Teorema de los smbolos accesiblesSi el smbolo no terminal de la parte izquierda de una produccin es accesible, entonces todos los smbolos de la parte derecha tambin lo son. La demostracin es obvia. El teorema se puede utilizar para construir algoritmos, consistiendo stos en el siguiente procedimiento: se hace una lista inicial de smbolos no terminales que se sabe a ciencia cierta que son accesibles, y usando el teorema 2 para detectar nuevos smbolos accesibles para aadir a la lista, hasta que no se pueden encontrar ms. Los pasos a seguir son: 1) Se comienza la lista con un nico no terminal, el smbolo inicial. 2) Si la parte izquierda de la produccin est en la lista, entonces se incluyen en la misma a todos los no terminales que aparezcan en la parte derecha. 3) Cuando ya no se puedan incluir ms smbolos mediante la aplicacin del paso 2), la lista contendr todos los smbolos accesibles, y el resto ser inaccesible.

2.7.4 EjemploSea la siguiente gramtica en BNF:

- 13 -


::= a | ::= c d ::= e | f ::= g | h t ::= x | y | z Determinar los smbolos inaccesibles Aplicando los pasos: 1) Confeccin de la lista: 2) Aplicacin del teorema 2.7.3: 3) No se puede aplicar ms veces el paso, luego la lista de smbolos accesibles est completa, y los no terminales inaccesibles son:

2.7.5 Anlisis automtico de la limpieza de gramticasLos algoritmos de limpieza de gramticas son fciles de programar, y comprueban si las gramticas son limpias. El primer paso para el tratamiento de cualquier gramtica es la eliminacin de los smbolos extraos. En la Universidad de Oviedo se ha desarrollado un analizador de gramticas LL(1), que toma como entrada una gramtica descrita en el formato BNF sin la opcin alternativa e indica si la gramtica es LL(1) o no sealando las reglas de la gramtica que se lo impiden. El primer paso de este analizador es verificar si la gramtica es limpia, as la gramtica de los ejemplos anteriores debe introducirse en el formato siguiente:::= ::= ::= ::= ::= ::= ::= ::= ::= ::= A C D E F G H T X Y Z

El analizador indica que la gramtica no es limpia. En el men correspondiente se puede obtener la relacin de smbolos no accesibles: NOTER3 y NOTER4.

2.8 Capacidad de descripcin de las gramticas libres de contextoLa sintaxis de la mayora de los lenguajes de programacin, tales como ALGOL 60, FORTRAN, C, C++ y Pascal no se puede describir completamente por gramticas libres de contexto. Por este motivo, la definicin sintctica de los lenguajes de programacin viene dada habitualmente en dos partes. La mayor parte de la sintaxis se describe por gramticas libres de contexto, especificadas en notacin BNF o EBNF. El resto de la sintaxis, que no se puede describir por medio de gramticas libres de contexto, se presenta como un aadido en lenguaje natural, y se trata en el compilador en la parte de anlisis semntico. Tambin se amplian las gramticas libres de contexto con atributos, condiciones y reglas semnticas, con el objeto de definir las especificaciones semnticas.

2.8.1 Ejemplo: llamada a funcionesEn la llamada a procedimientos o subrutinas se ha de comprobar que el nmero de argumentos debe de coincidir con el nmero de parmetros ficticios. Esto no lo pueden describir las gramticas libres de contexto. Esta verificacin se suele hacer en la fase de anlisis semntico. Otra solucin es la que utiliza el lenguaje C ANSI obligando a utilizar la definicin de funciones prototipo.

- 14 -


3 FORMAS NORMALES DE CHOMSKY Y GREIBACHSucede con frecuencia en lingstica matemtica, que en algunas ocasiones es imprescindible que las gramticas se hallen dispuestas de una forma especial. Es decir, se trata de obtener una gramtica equivalente, que genera el mismo lenguaje, pero que debe cumplir unas especificaciones determinadas. A continuacin se muestran las dos formas normalizadas ms frecuentes, que se emplean en los lenguajes formales y sus aplicaciones.

3.1 Forma Normal de Chomsky (FNC)Una gramtica se dice que est en la Forma Normal de Chomsky si sus reglas son de una de estas formas: A BC Aa Siendo A, B, C no terminales y a un terminal.

3.1.1 Teorema de la forma normal de ChomskyToda gramtica libre de contexto sin la cadena vaca tiene una gramtica equivalente cuyas producciones estn en la Forma Normal de Chomsky.

3.1.2 EjemploSea la gramtica G= ( VN={S, A, B}, VT={a, b}, P, S) cuyas producciones son: S bA | aB A bAA | aS | a B aBB | bS | b encontrar una gramtica equivalente en FNC. En primer lugar las reglas pueden reescribirse: (1) (2) (3) (4) (5) (*) (6) (*) (7) (8) S bA S aB A bAA A aS Aa B aBB B bS Bb Solamente las sealadas con (*) estn en forma FNC. La produccin (1) puede sustituirse por dos: S CbA Cb b Igualmente la (2) puede sustituirse por S CaB Ca a Las producciones (3) y (4) se sustituyen por A CbD1 A CaS y la (6) y la (7) por B CaD2 D2 BB B CbS Entonces la gramtica equivalente en FNC es: D1 AA

- 15 -


S CbA S CaB A CaS A CbD1 Aa B CbS B CaD2 Bb D1 AA D2 BB Ca a Cb b

3.2 Forma Normal de Greibach (FNG)Se dice que una gramtica est en la Forma Normal de Greibach si sus reglas de produccin son de la forma: A a Aa donde A es un no terminal, a es un terminal y es una cadena compuesta por terminales o no terminales.

3.2.1 Teorema de la forma normal de GreibachTodo lenguaje de contexto libre sin la cadena vaca puede ser generado por una gramtica cuyas reglas de produccin son de la forma A a Aa donde A es un no terminal, a es un terminal y es una cadena de terminales y n terminales.

3.2.2 EjemploLa gramtica dada en el ejemplo 3.1.2. S bA | aB A bAA | aS | a B aBB | bS | b

4 RELACIONES BINARIASEl concepto de relacin es uno de los ms elementales de la Matemtica. La idea que se tiene de relacin en la vida real es la asociacin de entes con alguna caracterstica en comn. Slo se considerarn relaciones binarias, es decir, aquellas que se establecen entre un par de objetos. En este apartado se formalizar el concepto de relacin, vindose dos mtodos para representarlas: mediante matrices y mediante grafos.

4.1 Definicin de relacin binariaSea un conjunto X= {x, y, ...} se dice que dos elementos estn relacionados xRy por medio de la relacin R, si cumplen una determinada propiedad dada por R. El conjunto de pares relacionados est definido por el producto escalar de XX con la relacin R.

4.2 Representacin mediante grafosUna relacin binaria se puede representar mediante un grafo de la siguiente forma, si xRy entonces se representa el grafo de de la figura 11.x y

Figura 11: Grafo de una relacin binaria

- 16 -


4.3 Representacin mediante matricesLa relacin en un conjunto X se puede representar mediante una matriz cuadrada A de dimensin cardinal(X), cuyos elementos son booleanos (o su representacin por ceros y unos) de forma que:aij =

1 si xi Rx j (est relacionado) 0 si xi Rx j (no est relacionado)

R1 x1 x2 ... xn

x1 0 0 ... 0

x2 0 1 ... 1

... ... ... ... ...

xn 1 0 ... 0

4.4 Ejemplo de relaciones binarias en gramticas libres de contextoSea la gramtica G= (Vn, Vt, S, P) donde: Vt= {a, b, +, (, ), } Vn= {E, 1, 1, P, P, S} S= smbolo inicial P: las reglas de produccin ::= ::= + | ::= ::= | ::= a | b | ( ) ::= A continuacin se definen dos relaciones: la relacin de dependencia simple y la relacin de dependencia a izquierdas. Representar los grafos y determinar las matrices de ambas relaciones.

a) Relacin de dependencia simpleSe dice que Vn y V (siendo V = Vn Vt ) estn relacionadas por una relacin de dependencia simple Rs si 12/1, 2 V *

El grafo y la matriz de la relacin de dependencia simple son los que se muestran en la figura 12.Vn Rs S E 1 0 1 1 0 0 0 0 0 0 0 0 0 1 P P 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 a 0 0 0 0 0 1 0 0 0 0 0 0 b 0 0 0 0 0 1 0 0 0 0 0 0 ( 0 0 0 0 0 1 0 0 0 0 0 0 Vt ) 0 0 0 0 0 1 0 0 0 0 0 0 + 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

a ( bVn

S E 1 P a b ( ) +

0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 1 0 0 0 0 0 0

1 0 P 0

+ )Vt

Figura 12: Grafo de la relacin de dependencia simple

b) Relacin de dependencia a izquierdasSe dice que Vn y V cumplen RI si y solamente si aparece como primer smbolo (distinto de la cadena vaca) en una produccin de la gramtica en la que es la parte izquierda. Es decir RI 12 p donde p 0,1, 2, , p Vn , V *, 1 , 2 , 3 , , p .* * *

- 17 -


En la figura 13 se representa el grafo y la matriz de la relacin de dependencia a izquierdas.Vn RI S E 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 P P 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 a 0 0 0 0 0 1 0 0 0 0 0 0 b 0 0 0 0 0 1 0 0 0 0 0 0 ( 0 0 0 0 0 1 0 0 0 0 0 0 Vt ) 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

aVn

S E 1 P a

1 0 P 0

b

+ )

(Vt

b ( ) +

Figura 13: Grafo y matriz de la relacin de dependencia a izquierdas

4.5 Producto de relacionesDadas dos relaciones R y P definidas en el mismo conjunto, se define una nueva relacin Q, llamada producto de R y de P, a la siguiente:cQd cRe y ePd

4.5.1 EjemplosRelacin SER PADRE DE#2 #2 Producto SER SUEGRO DE Relacin SER CONYUGE DE #2 a c ES PADRE de c a ES CONYUGE de b ES SUEGRO DE b

4.5.2 Propiedades del producto de relaciones El producto de relaciones tiene la propiedad asociativa. P (QR) = (PQ) R Empleando el producto de una relacin, se define potencia de una relacin R como:R1 R R 2 RR R 3 RRR R n R n 1R = RR n 1n > 1

Se define R0 como la relacin de identidad, es decir, si a R0 b si y slo si

a=b

4.5.3 Algoritmo para calcular el producto de relacionesDado que las relaciones se representan por matrices booleanas, una forma de calcular el producto de relaciones es por medio del producto booleano de matrices. As se define producto de dos relaciones representadas por las matrices A y B a otra matriz C resultado del producto booleano de las dos anteriores. C=A*B

4.5.3.1 Algoritmo en PascalDado que las matrices que representan una relacin slo estn compuestas por 0 y 1, la matriz producto se puede calcular por el siguiente fragmento de programa Pascal, siendo n el tamao de la matriz.

- 18 -


FOR j:= 1 TO n DO FOR i:= 1 TO n DO IF A[i,j]=1 THEN (* Bucle para inspeccionar la fila j de la matriz B si y solo si A[i,j]= 1 *) FOR k:=1 TO n DO IF B[j,k]=1 THEN C[i,k]:= 1 (* si y solo si A[i,j]=B[j,k]=1 *)

4.6 Relacin reflexivaUna relacin R se dice que es reflexiva, si se cumple que para todo x xRx La matriz de una relacin reflexiva tiene la diagonal principal con unos.

4.6.1 EjemploLa relacin menor o igual es reflexiva con el conjunto de los nmeros reales.

4.7 Relacin simtricaUna relacin R se dice que es simtrica, si se cumple para todo x e y quexR y yRx

La matriz de una relacin simtrica es simtrica respecto de la diagonal principal.

4.7.1 EjemploLa relacin igual es simtrica con los nmeros reales.

4.8 Relacin transitivaSe dice que una relacin R es transitiva si se cumple quexR y entonces xRz xRz

4.8.1 EjemploLa relacin MENOR QUE es transitiva en el conjunto de los nmeros reales.

4.9 Relacin de equivalenciaUna relacin aplicada a un conjunto que sea simultaneamente reflexiva, simtrica y transitiva se denomina una relacin de equivalencia.

4.9.1 Ejemplos de relaciones de equivalenciaRelacin Igualdad Semejanza Tener el mismo n de patas Tener el mismo n de letras Acabar con la misma letra Tiene el mismo resto que Aplicada al conjunto Nmeros Tringulos Animales Palabras Palabras Enteros

4.9.2 Propiedad de las relaciones de equivalenciaLas relaciones de equivalencia dividen al conjunto al que se aplican en clases de equivalencia, de forma que los elementos del conjunto slo se relacionan con los de su clase de equivalencia, y slo con ellos.

4.9.2.1 Ejemplo de clases de equivalenciaLa relacin ser de la misma paridad clasifica a los enteros en dos clases de equivalencia: pares e impares.

- 19 -


4.10 Relacin irreflexivaUna relacin es irreflexiva si para todos los elementos del conjunto se cumple xR x

4.10.1 EjemploRelacin mayor que en el conjunto de los nmeros reales.

4.11 Relacin antisimtricaUna relacin es antisimtrica si para todos los elementos del conjunto se cumple xRyyR x

4.11.1 EjemploRelacin mayor que en el conjunto de nmeros reales.

4.12 Inclusin de una relacinSe dice que una relacin P incluye a otra relacin R, si aRb implica necesariamente aPb.

4.12.1 EjemploLa relacin menor o igual incluye la relacin menor en el conjunto de los nmeros reales.

4.13 Transpuesta de una relacinLa transpuesta de una relacin R es otra relacin Q denominada TRANSPUESTA(R) tal que Q= TRANSPUESTA(R) si cQd dRc

4.13.1 Ejemplosa) En el conjunto de los nmeros reales, la relacin TRANSPUESTA("mayor que") es "menor que". b) La relacin TRANSPUESTA("ser hijo de") es "ser padre de".

4.14 Cierre transitivo de una relacinSea un conjunto finito X, que contiene n elementos, y una relacin R en X, que permite obtener las relaciones Rm (m= 1, 2,...). Se puede construir una relacin R+ en X denominada cierre transitivo de R en x y dada porR+ = R R2 R3

Naturalmente, esta construccin necesitar solamente un nmero finito de potencias de R para ser calculada, y se puede realizar fcilmente usando la representacin matricial de R y la multiplicacin booleana de estas matrices.

4.14.1 Teorema del cierre transitivo de una relacinEl cierre transitivo R+ de una relacin R en un conjunto finito X es transitivo. Es decir, para cualquier otra relacin transitiva P en X tal que R P , se puede afirmar que R + P . En este sentido R+ es la relacin transitiva ms pequea contenida en R.

4.14.2 Algoritmo de WarshallEl cierre transitivo de la matriz de relacin, se puede calcular fcilmente por medio del siguiente algoritmo debido a Warshall. A continuacin se muestra una implementacin en Pascal. Toma la matriz A(n,n) de la relacin R, y determina la nueva matriz A+(n,n) de la relacin R+.FOR j:= 1 TO n DO FOR i:= 1 TO n DO IF a[i,j]= 1 THEN FOR k:= 1 TO n DO IF a[j,k]=1 THEN a[i,k]:= 1 (* si y solo si a[i,j]= a[j,k]= 1 *)

- 20 -


4.14.3 EjemploCalcular la matriz de la relacin cierre transitiva de la relacin de dependencia a izquierdas, que se defini en el ejercicio 4.4. Aplicando el algoritmo de Warshall se obtiene la matriz siguiente:Vn R+

Vt a 1 1 0 1 1 1 0 0 0 0 0 0 b 1 1 0 1 1 1 0 0 0 0 0 0 ( 1 1 0 1 1 1 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

S E 1 1 P P 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0

S 0 E 0 Vn 1 0 1 0 P 0 P 0 a b Vt ( ) + 0 0 0 0 0 0

A la vista de la matriz anterior, se puede construir la siguiente tabla: Smbolos Smbolos terminales no terminales por los que se accede desde el no terminal de la izquierda S....................................................................... a, b, ( E....................................................................... a, b, ( 1....................................................................... + 1....................................................................... a, b, ( P...................................................................... a, b, ( P....................................................................... a, b, (

4.15 Cierre reflexivo transitivo de una relacinSe llama cierre reflexivo transitivo de una relacin R a otra relacin R* tal queaR *b a = b si y slo si o + aR b

Es decir, es una extensin del cierre transitivo, de la forma:R+ = R0 R2 R3

Para realizar el cierre reflexivo transitivo de una matriz que representa una relacin R, se puede emplear el algoritmo de Warshall con una modificacin, que consiste en obligar a todos los trminos de la diagonal principal a que sean la unidad. A continuacin se muestra el algoritmo de Warshall modificado para el cierre reflexivo transitivo de una relacin (en Pascal):FOR j:= 1 TO n DO BEGIN FOR i:= 1 TO n DO IF a[i,j]= 1 THEN FOR k:= 1 TO n DO IF a[j,k]= 1 THEN a[i,k]:= 1 (* si y solo si a[i,j]= a[j,k]= 1 *) a[j,i]:= 1 (* esta modificacin *) END;

- 21 -


5 ANALISIS SINTACTICO DESCENDENTEEl anlisis sintctico (en ingls parser) es la fase del procesador de lenguaje que toma como entrada un conjunto de tokens enviados por el analizador lxico (scaner) y determina si con ellos puede formar una instruccin del lenguaje. Para verificar si una instruccin pertenece al lenguaje construye el rbol sintctico de la instruccin a partir de los tokens recibidos y que constituirn las hojas del rbol sintctico. Si el analizador sintactico no puede formar una sentencia produce un mensaje de error, tratando de indicar las causas por las cuales no puede formar la sentencia. Existen dos tipos bsicos de analizadores sintcticos para las gramticas libres de contexto: los descendentes (top-down) y los ascendentes (bottom-up). Los ascendentes intentan construir el rbol desde las hojas hasta la raz, mientras que los descendentes comienzan por la raz y bajan hasta las hojas. Uno de los mtodos de reconocimiento para las gramticas de contexto libre son los analizadores sintcticos descendentes o tambin llamados predictivos y orientados hacia un fin, debido a la forma en que trabajan y construyen el rbol sintctico. Los analizadores sintcticos descendentes son lo que construyen el rbol sintctico de la sentencia a reconocer de una forma descendente, comenzando por el smbolo inicial o raz, hasta llegar a los smbolos terminales que forman la sentencia. El anlisis descendente es un procedimiento que crea objetivos y subobjetivos al intentar relacionar una sentencia con su entorno sintctico. Al comprobar los subobjetivos, se verifican y descartan las salidas falsas y las ramas impropias hasta que se alcanza el subobjetivo propio que son los smbolos terminales que forman la sentencia. El procedimiento de anlisis, en cada encuentro con la estructura sintctica, tiene que examinar los subobjetivos. Si se cumplen los subobjetivos requeridos, entonces, por definicin, se logra el objetivo de mayor rango. En caso contrario, se descarta dicho objetivos superior. Esta secuencia de comprobar, descartar y por ltimo efectuar los objetivos, se programa hacia abajo siguiendo el rbol sintctico hasta que todas las componentes bsicas se hayan acumulado en componentes de nivel superior o hasta que se compruebe que la sentencia es errnea. Los algoritmos que realizan el anlisis descendente deben de cumplir al menos dos condiciones: a) el algoritmo debe saber en todo momento dnde se encuentra dentro del rbol sintctico; y b) debe poder elegir los subobjetivos (es decir la regla de produccin que aplicar). Histricamente, los compiladores dirigidos por sintaxis, en la forma de anlisis recursivo descendente fue propuesta por primera vez en forma explcita por Lucas (1961), para describir un compilador simplificado de ALGOL 60 mediante un conjunto de subrutinas recursivas, que correspondan a la sintaxis BNF. El problema fundamental para el desarrollo de este mtodo fue el retroceso, lo que hizo que su uso prctico fuera restringido. La elegancia y comodidad de la escritura de compiladores dirigidos por sintaxis fue pagada en tiempo de compilacin por el usuario. La situacin cambi cuando comenz a realizarse anlisis sintctico descendente sin retroceso, por medio del uso de gramticas LL(1), obtenidas independientemente por Foster (1965) y Knuth (1967). Generalizadas posteriormente por Lewis, Rosenkrantz y Stearns en 1969, dando lugar a las gramticas LL(k), que pueden analizar sintcticamente sin retroceso, en forma descendente, examinando en cada paso todos los smbolos procesados anteriormente y los k smbolos ms a la derecha.

5.1 El problema del retrocesoEl primer problema que se presenta con el anlisis sintctico descendente, es que a partir del nodo raz, el analizador sintctico no elija las producciones adecuadas para alcanzar la sentencia a reconocer. Cuando el analizador se da cuenta de que se ha equivocado de produccin, se tienen que deshacer las producciones aplicadas hasta encontrar otras producciones alternativas, volviendo a tener que reconstruir parte del rbol sintctico. A este fenmeno se le denomina retroceso, vuelta atrs o en ingls backtracking. El proceso de retroceso puede afectar a otros mdulos del compilador tales como tabla de smbolos, cdigo generado,... Teniendo que deshacerse tambin los procesos desarrollados en estos mdulos.

5.1.1 Ejemplo de retrocesoPara explicar mejor el problema del retroceso, se estudiar el siguiente ejemplo, donde se utiliza la gramtica G=(VN, VT, S, P) donde: VN={, , } VT={module, d, p, ;, end} S= las reglas de produccin P son las siguientes:

- 22 -


::= module ; end ::= d | d; ::= p | p; Se desea analizar la cadena de entrada siguiente: module d ; d ; p ; p end. A continuacin se construye el rbol sintctico de forma descendente: a) Se parte del smbolo inicial. b) Aplicando la primera regla de produccin de la gramtica:

module

; Figura 14

end

c) Aplicando las derivaciones ms a la izquierda, se tiene que: c1) module es un smbolo terminal, que coincide con el primero de la cadena a reconocer. c2) se deriva con la primera alternativa.

module

; dFigura 15

end

Se comprueba que el nuevo terminal generado d coincide con el segundo token de la cadena de entrada. c3) ; coincide con el tercer token de la cadena de entrada. c4) Se deriva con la primera alternativa.

module

; dFigura 16

end

p

y se llega a un terminal que no es el que tiene la cadena. c4.1) Se deriva con la segunda alternativa.

- 23 -


module

; end d pFigura 17

;

Se observa que el siguiente terminal generado, tampoco coincide con el token de la cadena de entrada. Entonces el analizador sintctico debe de volver atrs, hasta encontrar la ltima derivacin de un no terminal, y comprobar si tiene alguna alternativa ms. En caso afirmativo se debe de elegir la siguiente y probar. En caso negativo, volver ms atrs para probar con el no terminal anterior. Este fenmeno de vuelta atrs es el que se ha definido anteriormente como retroceso. Si en este proceso de marcha atrs se llega al smbolo inicial o raz, se tratara de una cadena errnea sintcticamente. Dado que no se ha encontrado el terminal de la cadena de entrada, se ha de volver atrs hasta el no-terminal analizado anteriormente, que en este caso es , es decir, se pasa a c2) y en vez de tomar la primera alternativa se toma la segunda alternativa. c2.bis)

module

; d ; Figura 18

end

Llegados a este punto, tambin se debe de retroceder en la cadena de entrada hasta la primera d, ya que en el proceso de vuelta atrs lo nico vlido que nos ha quedado del rbol ha sido el primer token module. c2bis1.1) Si se deriva nuevamente con la primera alternativa, se tiene

module

; d ; dFigura 19

end

c3.bis) En este momento se tienen reconocidos los primeros 5 tokens de la cadena. c4.bis) Se deriva el no terminal , con la primera alternativa, y el rbol resultante se muestra en la figura 20. Se ha reconocido el sexto token de la cadena (p).

- 24 -


module

; d ; dFigura 20: Reconocimiento de module d ; d ; p ...

end

p

c5) El siguiente token de la cadena es ;, mientras que en el rbol se tiene end, por lo tanto habr que volver atrs hasta el anterior no terminal, y mirar si tiene alguna otra alternativa. c4bisbis) El ltimo no terminal derivado es , si se deriva con su otra alternativa se tiene el rbol de la figura 21. Con esta derivacin se ha reconocido la parte de la cadena de entrada module d;d;p;

module

; d ; d p ;

end

Figura 21: Reconocimiento de module d ; d ; p ; ...

c4bisbis.1) Se deriva con la primera alternativa y se obtiene el rbol sintctico de la figura 22, reconocindose module d ; d ; p ; p...

module

; d ; d p ;

end p

Figura 22: Reconocimiento de module d ; d ; p ; p end

c5bis) El rbol sintctico de la figura 22 ya acepta el siguiente token de la cadena (end) y por tanto la cadena completa. Puede concluirse, que los tiempos de reconocimiento de sentencias de un lenguaje pueden dispararse a causa del retroceso, por lo tanto los analizadores sintcticos deben eliminar las causas que producen el retroceso.

5.2 La recursividad a izquierdasSe dice que una gramtica tiene recursividad a izquierdas ("left-recursive"), si existe un no terminal A, tal que para algn V * existe una derivacin de la forma:A A+

donde el signo + encima de la flecha indica que al menos existe una produccin.

- 25 -


Si el analizador sintctico toma el primer no terminal (el ms a la izquierda), el rbol sintctico es el de la figura 23. La recursividad a izquierdas deja al analizador sintctico en un bucle infinito, ya que al expandir A, se encontrara con otro A, y as sucesivamente, sin avanzar en la comparacin del token de entrada. Es preciso eliminar la recursividad a izquierdas con tcnicas que se estudiarn ms adelante.

A A A A AFigura 23: Recursividad a izquierda

5.2.1 Ejemplo de recursividad a izquierdasSea la gramtica G= (VN, VT, S, P) donde VN= {A, S}, VT= {a, b, c}, y las reglas de produccin P son las siguientes: S aAc A Ab | el lenguaje reconocido por esta gramtica es L= {abnc / n0}. Supongamos que el analizador sintctico desea reconocer la cadena: abbc, se obtienen los rboles sintcticos de la figura 24. No saliendo el analizador sintctico de este bucle.(1) (2) (3) (4) (5)

S a

S A c a A

S A b A c a A

S A b b A A b c a A

S A b b c

Figura 24: Bucle infinito tratando de reconocer abbc.

a) Una forma de resolver este problema es volviendo a escribir la segunda produccin de la gramtica de esta otra manera:A | Ab

entonces se construyen los rboles sintcticos que se muestran en la figura 25.

- 26 -


(1)

(2)

(3)

(4)

(5)

S a

S A c a

S A c a A

S A b A c a A

S A b b c

Figura 25: Reconocimiento de la cadena abbc.

b) Otra forma de resolver el problema es cambiando en la regla conflictiva el orden Ab a bA, que a su vez cambia la gramtica, pero se obtiene una gramtica equivalente, es decir que genera el mismo lenguaje.A bA |

Para reconocer abbc se obtienen los rboles sintcticos de la figura 26.(1) (2) (3) (4) (5)

S a

S A c a b

S A A c a b

S A A b A c a b

S A A b A c

Figura 26: Reconocimiento de la cadena abbc.

No siempre es tan fcil eliminar la recursividad a izquierdas, en el apartado 5.4.5 Transformacin de gramticas, se estudian otros mtodos para eliminar la recursividad a izquierdas.

5.3 Anlisis sintctico descendente con retrocesoLa forma en que se hace el anlisis descendente con retroceso ya se ha visto en el ejemplo del apartado 5.1, aqu se expone el algoritmo general para construir un analizador sintctico descendente con retroceso.

5.3.1 Algoritmo de anlisis sintctico descendente con retroceso1.- Se colocan las reglas de la gramtica segn un orden preestablecido para cada uno de los no terminales de la que est compuesta. 2.- Se comienza la construccin del rbol sintctico a partir del smbolo inicial, y aplicando las siguientes reglas en forma recursiva. Al nodo en proceso de expansin en un determinado momento se le llamar nodo activo. 3.- Cada nodo activo escoge la primera de sus alternativas posibles, por ejemplo, para el no terminal A con la reglaA x1x2xn crea n descendientes directos, y el nodo activo en ese momento pasa a ser el primer descendiente por la izquierda. Cuando se deriven todos los descendientes, pasar a ser nodo activo el ms inmediato derecho de A susceptible de ser derivado. En el caso de que la regla fuese:A x1 | x2 | | xn se elegir en un principio la alternativa de ms a la izquierda. 4.- Si el nodo activo es un terminal deber entonces compararse el smbolo actual de la cadena a analizar con dicho nodo. Si son iguales se avanza un token de entrada y el nuevo smbolo actual ser el situado ms a la derecha del terminal analizado.

- 27 -


Si no son iguales se retrocede hasta un nodo no terminal y se reintenta eligiendo la siguiente alternativa. Si an as no existe ninguna alternativa posible se retrocede al no terminal anterior, y as sucesivamente. Si se llega al smbolo inicial la cadena no pertenece al lenguaje.

5.3.2 CorolarioUna gramtica de contexto libre, que es una gramtica limpia y no es recursiva a izquierdas, para cualquier cadena de smbolos de su alfabeto terminal existe un nmero finito de posibles anlisis a izquierda desde el smbolo inicial para reconocerla o no. A partir de todo lo expresado anteriormente, se pueden construir analizadores sintcticos descendentes con retroceso. Su principal problema es el tiempo de ejecucin.

5.4 Anlisis descendente sin retrocesoPara eliminar el retroceso en el anlisis descendente, se ha de elegir correctamente la produccin correspondiente a cada no terminal que se expande. Es decir que el anlisis descendente ha de ser determinista, y slo se debe de dejar tomar una opcin en la expansin de cada no terminal.

5.4.1 Gramticas LL(k)Las gramticas LL(k) son un subconjunto de las gramticas libres de contexto. Permiten un anlisis descendente determinista (o sin retroceso), por medio del reconocimiento de la cadena de entrada de izquierda a derecha ("Left to right") y que va tomando las derivaciones ms hacia la izquierda ("Leftmost") con slo mirar los k tokens situados a continuacin de donde se halla.

5.4.1.1 Teorema de la no ambigedad de las gramticas LL(k)Toda gramtica LL(k) es no ambigua. Demostracin: Por definicin de gramtica LL(k).

5.4.1.2 TeoremaUna gramtica LL(k) no es recursiva a izquierdas. Demostracin: Por definicin de gramtica LL(k).

5.4.2 Gramticas LL(1)Antes de definir completamente las gramticas LL(1), se definirn otros tipos de gramticas ms sencillas que son LL(1). La introduccin de estas gramticas permitir una aproximacin paso a paso hacia la definicin completa de las gramticas LL(1).

5.4.2.1 S-gramticasLas S-gramticas son un subconjunto muy restringido de las gramticas LL(1), debido a dos condiciones muy fuertes. Una S-gramtica es una gramtica libre de contexto que debe complir las siguientes dos condiciones: 1) Todas las partes derechas de cada produccin comienzan con un smbolo terminal. 2) Si dos producciones tienen la misma parte izquierda, entonces su parte derecha comienza con diferentes smbolos terminales. Es decir las distintas producciones de cada no terminal A VN , deben comenzar por distinto smbolo terminal. As si se tienen la producciones del no terminal A: A a11 | a22 | | am m se debe cumplir que ai a j i j ai VT i V * 1i m La primera condicin es similar a decir que la gramtica est en la Forma Normal de Greibach (FNG), excepto que los terminales de comienzo de la parte derecha de cada produccin, pueden estar seguidos por simbolos no terminales y/o terminales. La segunda condicin ayudar a escribir los analizadores sintcticos descendentes sin retroceso (o deterministas), ya que permitirn siempre elegir la derivacin correcta, con slo mirar un token hacia adelante.

5.4.2.1.1 Corolario de la definicin de S-gramticasToda S-gramtica es LL(1), la inversa no es cierta. Toda S-gramtica es una gramtica LL(1) dado que una vez que analiza un token es posible determinar que regla de produccin se debe aplicar.

- 28 -


5.4.2.1.2 Contraejemplo de S-gramticaSea la gramtica: (1) a (2) b (3) b (4) b a No es una s-gramtica, ya que la parte derecha de la produccin (2) no comienza por un terminal como exige la primera condicin. Adems las producciones (3) y (4) no cumplen la segunda condicin.

5.4.2.1.3 Ejemplo de S-grmticaSea la gramtica: a b b b a b Obviamente es una s-gramtica, y por tanto es una gramtica LL(1).

5.4.2.1.4 Ejemplo de S-gramticaSea la gramtica: p q a b x a d y Obviamente es una s-gramtica, y por tanto es una gramtica LL(1).

5.4.2.2 Conjunto de smbolos iniciales o cabeceraSe define el conjunto de smbolos iniciales o cabecera (en ingls FIRST) de un smbolo no terminal A, como los smbolos terminales que pueden aparecer en primer lugar de cualquier cadena generada por A. La definicin anterior se puede expresar como:INICIALES(A) = {x/A x siendo x VT}

Otra forma de definir el conjunto iniciales, es por medio de la relacin PRIMERO. Se define la relacin PRIMERO, de la forma siguiente "Dos smbolos A y x estn relacionados por la relacin binaria primero, y se escribe A PRIMERO x si y slo si existe una regla de produccin de la gramtica de la forma: A x...". El cierre transitivo de la relacin primero sera A PRIMERO+ x si y slo si existe una cadena de reglas de produccin de la forma: A A1 A1 A2 ........ AN x Lo que implica que A PRIMERO+ x si A x A partir del cierre transitivo de la relacin PRIMERO se puede definir el conjunto de smbolos iniciales de un no terminal A como:INICIALES(A) = {x/(A, x) PRIMERO +, x VT}+

Tambin puede extenderse la definicin de conjunto de INICIALES de un smbolo no terminal a conjunto de INICIALES de una cadena de smbolos V .

- 29 -


5.4.2.2.1 Ejemplo de clculo del conjunto de InicialesSea la gramtica S S# S ABe A dB A aS Ac B AS Bb INICIALES(A)={d, a, c}, pues existen las reglas: A dB A aS Ac INICIALES(S)=INICIALES(A)={d, a, c}, pues existen las reglas: S S# S ABe INICIALES(B)=INICIALES(A) {b} ={d, a, c, b}.

5.4.2.3 Gramticas LL(1) simplesLas gramticas LL(1) simples son un subconjunto de las gramticas LL(1), con las dos restricciones siguientes: No se permiten smbolos no terminales que deriven a vacio. Es decir no se permiten producciones vacas o reglas-, cuya parte derecha es la cadena vaca . Las distintas producciones de cada no terminal A VN A 1 | 2 | | n deben cumplir los conjuntos INICIALES(1), INICIALES(2),..., INICIALES(n ) son disjuntos entre s, es decir INICIALES(i ) INICIALES(j ) = i j

5.4.2.3.1 Corolario de las gramticas LL(1) simplesToda gramtica LL(1) simple es LL(1), la inversa no es cierta

5.4.2.3.2 Teorema de equivalencia entre las gramticas LL(1) y las S-gramticasDada una gramtica LL(1) simple siempre es posible encontrar una S-gramtica equivalente.

5.4.2.3.3 Ejemplo de gramtica LL(1) simpleSea la gramtica cuyas reglas de produccin son: S S# S ABe A dB A aS Ac B AS Bb Se desea verificar si es o no LL(1) simple. a) Dadas las producciones A dB | aS | cINICIALES(dB) INICIALES(aS) = {d} {a} = 0 INICIALES(dB) INICIALES(c) = {d} {c} = 0 INICIALES(aS) INICIALES(c) = {a} {c} = 0

b) Dadas las producciones B AS | b

- 30 -


INICIALES(AS) INICIALES(b) = {a, c, d} {b} = 0

Luego esta gramtica es LL(1) simple.

5.4.2.3.4 Ejemplo de gramtica LL(1) simpleSea la gramtica cuyas de reglas de produccin son: (0) (1) (2) (3) (4) # a b d c c

Claramente es una gramtica LL(1) simple, que permite reconocer una cadena sin retroceso. As con esta gramtica se desea reconocer la cadena: aabccd#. Realizando derivaciones ms a la izquierda se obtiene: # aa # aab # aabcc # aabccd# siendo el rbol sintctico el que se muestra en la figura 27.

a a b c c dFigura 27: Reconocimiento sin retroceso de aabccd#

#

5.4.2.4 Conjunto de smbolos seguidores o siguientesDada una gramtica libre de contexto con un smbolo inicial S, para un smbolo no terminal A, se dice que el conjunto de smbolos SEGUIDORES(A) es el conjunto de smbolos terminales que pueden seguir inmediatamente a una cadena derivada de S. La definicin formal se puede expresar de la siguiente forma:SEGUIDORES(A) = {a/S A , , (VT VN)*, A VN, a INICIALES()}

Los smbolos seguidores o siguientes (en ingls se denominan FOLLOW) de un smbolo no terminal tambin se pueden definir como los smbolos iniciales del smbolo que le sigue.

5.4.2.4.1 Ejemplo de clculo del conjunto de SeguidoresSea la gramtica: ::= module end ::= d ::= | ; ::= p ::= | ; Clculo del conjunto de seguidores del smbolo no terminal A. module d end INICIALES () = { p }- 31 -Anlisis sintctico en procesadores de lenguajeClculo de los smbolos seguidores de module p end SEGUIDORES()= { end }5.4.2.5 Conjunto de smbolos DirectoresLos smbolos directores (en ingls SELECT) de una produccin como su nombre indica son los que dirigen al analizador sintactico para elegir la alternativa adecuada, se pueden definir como el conjunto de smbolos terminales que determinarn que expansin de un no terminal se ha de elegir en un momento dado, con solo mirar un smbolo hacia adelante. La definicin formal se puede enunciar de la siguiente forma, dada una produccin A donde A es un smbolo no terminal, y es una cadena de smbolos terminales y no terminales. Entonces se define conjunto de smbolos directores SD(A,) de una produccin A como: INICIALES() si es no anulable SD(A, ) INICIALES() SEGUIDORES(A) si es anulable5.4.2.5.1 Ejemplo de clculo del conjunto de smbolos DirectoresSea la gramtica: es anulable, luego: SD (,) = INICIALES() SEGUIDORES () = { p } = { p } b) Calcular el conjunto de smbolos directores de la produccin: < A > ; < DECLARACIONES > SD(, ; ) = { ; } ::= module end ::= d ::= | ; ::= p ::= | ; ::= a) Calcular el conjunto de smbolos directores de la produccin: < A >< vaco >5.4.2.6 Definicin del las gramticas LL(1)La condicin necesaria y suficiente para que una gramtica limpia sea LL(1), es que los smbolos directores correspondientes a las diferentes expansiones de cada smbolo no terminal sean conjuntos disjuntos. La justificacin de esta condicin es simple. La condicin es necesaria, puesto que si un smbolo aparece en dos conjuntos de smbolos directores, el analizador sintctico descendente no puede decidir (sin recurrir a informacin posterior) qu expansin aplicar. La condicin es suficiente, puesto que el analizador siempre puede escoger una expansin como un smbolo dado, y esta alternativa ser siempre correcta. Si el smbolo no est contenido en ninguno de los conjuntos de los smbolos directores, la cadena de entrada no pertenecer al lenguaje y se tratar de un error.5.4.3 Condiciones de las gramticas LL(1)La definicin original dada por D.E. Knuth, de gramticas LL(1) consta de cuatro condiciones equivalentes a la definicin dada en el epgrafe anterior.5.4.3.1 Primera condicin de KnuthNo se permitirn producciones de la forma A Adonde A VN y V *. Esta condicin equivale a no admitir la recursividad a izquierdas.*5.4.3.2 Segunda condicin de KnuthLos smbolos terminales que pueden encabezar las distintas alternativas de una regla de produccin deben formar conjuntos disjuntos. Es decir, si- 32 -Anlisis sintctico en procesadores de lenguajeA B | C*A, B, C VN , V *no debe ocurrir queB dS C d* *d VT S, V *Esto implica que en todo momento, el smbolo terminal que estamos examinando seala sin ambigedad, que alternativa se ha de escoger sin posibilidad de error y, en consecuencia, sin retroceso.5.4.3.2.1 Tercera condicin de KnuthSi una alternativa de una produccin de un smbolo no terminal origina la cadena vaca, los smbolos terminales que pueden seguir a dicho no-terminal en la produccin donde aparezca, han de formar un conjunto disjunto con los terminales que pueden encabezar las distintas alternativas de dicho terminal. Expresado de otra forma, sea la cadena A1... A2... A3A4A5 y sea A3 el smbolo que se est analizando, adems se tienen las producciones:A3 ax | A4 A3a yDado que A3 puede derivar a la cadena vaca, puede darse el caso de que: INICIALES(A3)= { a } INICIALES(A4)= { a } y no puede determinarse si se ha de elegir la produccin de A3 o de A4.5.4.3.2.2 Cuarta condicin de KnuthNingn smbolo no terminal puede tener dos o ms alternativas que conduzcan a la cadena vaca. Esta condicin deriva de la anterior. As por ejemplo no se permite:X A |B A |C B |D5.4.4 Algoritmo de decisinExiste un algoritmo diseado por Lewis et al. [LEWI76, pg. 262-276], traducido y adaptado por Snchez Dueas et al. [SANC84, pg 86-95], que permite decidir si una gramtica es o no LL(1). Es decir, si con el diseo de una gramtica para un lenguaje de programacin, se puede construir un analizador sintctico descendente determinista, con solo examinar el siguiente token de entrada. Los distintos pasos del algoritmo se encaminan a construir los conjuntos de smbolos directores para cada expansin de un smbolo no terminal, y aplicar la condicin necesaria y suficiente para que la gramtica sea LL(1). Para construir los conjuntos citados se ejecutan los siguientes pasos: PASO 1: Encontrar los smbolos no terminales y producciones que sean anulables. PASO 2: PASO 3: PASO 4: PASO 5: PASO 6: PASO 7: PASO 8: PASO 9: Construccin de la relacin EMPIEZA DIRECTAMENTE CON. Calcular la relacin EMPIEZA CON. Calcular el conjunto de INICIALES de cada no terminal. Calcular el conjunto de INICIALES de cada produccin. Construccin de la relacin ESTA DIRECTAMENTE SEGUIDO POR. Construccin de la relacin ES FIN DIRECTO DE. Construccin de la relacin ES FIN DE. Construccin de la relacin ESTA SEGUIDO POR.PASO 10: Calcular el conjunto de SEGUIDORES de cada no terminal anulable. PASO 11: Calcular el conjunto de SIMBOLOS DIRECTORES.- 33 -Anlisis sintctico en procesadores de lenguajePASO 1: Encontrar los smbolos no terminales y producciones anulablesConsiste en aplicar un algoritmo que comprueba qu no terminales generan la cadena vaca. El algoritmo se basa en utilizar un vector cuyos ndices son elementos no terminales, y los elementos del vector solamente pueden tomar estos tres valores: - SI (el smbolo no terminal SI genera ) - NO (el no terminal NO genera ) - INDECISO (no se sabe si genera ) Los pasos del algoritmo son: 1.- Inicializar todos los elementos del vector con INDECISO. 2.- Efectuar las siguiente acciones en la primera pasada de la gramtica: a) Si una produccin de un no terminal es la cadena vaca, el correspondiente elemento del vector toma el valor SI, y se eliminan de la gramtica todas las producciones de dicho no terminal. b) Se eliminan de la gramtica todos los no terminales cuyas producciones contengan un smbolo terminal. Si la accin elimina todas las producciones de un no-terminal su correspondiente valor del vector toma el valor NO. 3.- En este momento, la gramtica est limitada a las producciones cuya parte derecha contiene slo smbolos no terminales. En las siguientes pasadas se examinan cada uno de los smbolos de la parte derecha. a) Si para un no terminal de la parte derecha su elemento en el vector vale SI, se elimina ese smbolo de la parte derecha. Si este deja como parte derecha la cadena vaca, el elemento correspondiente del vector al no terminal de la parte izquierda toma el valor SI, y se eliminan todas las producciones correspondientes a dicho no terminal. b) Si para un no terminal de la parte derecha su elemento del vector vale NO, se elimina la produccin. Si todas las producciones de un no terminal se eliminan de esta manera, su entrada en el vector toma el valor NO. 4.- Si durante una pasada completa de la gramtica no se cambia ninguna entrada del vector, y existen todava elementos del vector con el valor INDECISO, termina el algoritmo y la gramtica no es LL(1). Si una gramtica no pasa de este primer paso, es a la vez recursiva a izquierdas y sucia. a) Es sucia ya que existen producciones que constan slo de smbolos no terminales que no pueden generar cadenas compuestas slo por terminales. Es decir, hay smbolos no terminales muertos. b) Es recursiva a izquierdas, puesto que son un conjunto finito y an quedan los elementos del vector como INDECISOS, por tanto, los miembros ms a la izquierda deben de formar un bucle. Si la gramtica es limpia, siempre se podr generar un vector cuyos ndices son los no terminales y los elementos son todos SI o NO.5.4.4.1.1 Ejemplo de clculo de los smbolos anulablesSea la gramtica G= (VT, VN, P, S) donde: VN= {, , , , } VT= {+, id} S= y las reglas de produccin P son: ::= ::= ::= ::= ::= + | + | id Se trata de aplicar el algoritmo expuesto en el epgrafe anterior. 1. Construccin del vector cuyos ndices son no terminales, y se inicializa a indeciso.- 34 -Anlisis sintctico en procesadores de lenguaje IND IND IND IND INDFigura 28: vector de los smbolos no terminales inicializados a INDECISO2. a) La produccin ::= , hace que el elemento correspondiente a tome el valor SI en el vector, y se eliminan todas las producciones de que en este caso slo es una. IND SI IND IND INDFigura 29: vector de smbolos no terminalesEn la gramtica slo quedan las producciones: ::= + | + |id ::= ::= ::= b) Se eliminan de la gramtica los no terminales cuyas producciones tengan un smbolo terminal. En este caso es el , y su correspondiente elemento del vector toma el valor NO. NO SI IND IND INDFigura 30: vector de smbolos no terminalesEn la gramtica slo quedan las producciones: ::= ::= ::= 3. En este momento slo hay producciones cuya parte derecha slo contiene smbolos no terminales. Se examina a continuacin cada uno de los smbolos de la parte derecha de cada produccin: a) Se toma la produccin B:= dado que ya tiene el valor si se elimina con lo que queda la gramtica: := := := el vector no sufre cambios. b) Se toma la produccin ::= y dado que tiene valor NO, se elimina la produccin, y en el vector el elemento correspondiente a toma el valor NO y la gramtica queda: := := NO SI IND IND NOFigura 31: vector de smbolos no terminales4. Si se da otra pasada a la gramtica, el vector no cambia, y quedan y como indecisos. Luego la gramtica es sucia y recursiva a izquierdas como puede observarse. Tambin se puede utilizar el programa analizador de gramticas LL(1), en el cual la gramtica debe introducirse en el formato siguiente pues no admite el smbolo alternativa.- 35 -Anlisis sintctico en procesadores de lenguaje ::= ::= ::= ::= ::= ::= ::= + + id DE DE DE DE DE SIMBOLOS SIMBOLOS SIMBOLOS SIMBOLOS SIMBOLOS INDECISOS: B C ANULABLES: A NO ANULABLES: D E MUERTOS: B C NO ACCESIBLES: DEl resultado que se obtiene en el programa es:RELACION RELACION RELACION RELACION RELACIONPASO 2: Construccin de la relacin EMPIEZA DIRECTAMENTE CONSe define que A EMPIEZA DIRECTAMENTE CON B, si derivando A se puede obtener B como principio de cadena derivada de A. Los no terminales anulables se reemplazan por el vaco. A VN y B V+. Es decir, si y slo si existe una produccin de la forma A B siendo: A VN una cadena anulable, es decir que puede derivar a vacio B V+ una cadena cualquiera5.4.4.2.1 Ejemplo de clculo de la relacin EMPIEZA DIRECTAMENTE CONSea una gramtica elemental del lenguaje MUSIM. ::= ::= ::= ::= ::= ::= ::= . | | | = + | - | * | / | % | () | | R W dgito letra_minscula ::= ::= ::= ::= ::= ::= ::= ::=Determinar la relacin EMPIEZA DIRECTAMENTE POR. empieza directamente por empieza directamente por empieza directamente por empieza directamente por empieza directamente por empieza directamente por empieza directamente por ; +- 36 -Anlisis sintctico en procesadores de lenguaje * / % empieza directamente por ( empieza directamente por R empieza directamente por W empieza directamente por dgito empieza directamente por letra_minscula Esta relacin se puede representar mediante la siguiente matriz EMPIEZA DIRECTAMENTE CON. empieza directamente por empieza directamente porASIGNACION BLOQUE CONSTANTE ESCRITURA EXPRESION FACTOR LECTURA MAS_FACTORES MAS_TERMINOS OTRA_SENTENCIA PROGRAMA SENTENCIA TERMINO VARIABLE R W % ( * + . / ; = ) dgito letra_minscula ASIGNACION BLOQUE CONSTANTE ESCRITURA EXPRESION FACTOR LECTURA MAS_FACTORES MAS_TERMINOS OTRA_SENTENCIA PROGRAMA SENTENCIA TERMINO VARIABLE R W % ( * + . / ; = ) dgito letra_minscula 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Matriz "EMPIEZA DIRECTAMENTE CON"PASO 3: Construccin de la relacin EMPIEZA CONSe define que A EMPIEZA CON B si y slo si existe una cadena derivada de A que empiece con B. Tambin se admite que A EMPIEZA CON A. Se puede demostrar que la relacin EMPIEZA CON es el cierre reflexivo transitivo de la relacin EMPIEZA DIRECTAMENTE CON. Para determinar la nueva matriz de relacin se puede utilizar el algoritmo de Warshall modificado (apartado 4.15).5.4.4.3.1 Ejemplo de clculo de la relacin EMPIEZA CONContinuando con el ejemplo del paso anterior (apartado 5.4.4.2.1), se obtiene la matriz EMPIEZA CON aplicando el algoritmo de Warshall modificado.- 37 -Anlisis sintctico en procesadores de lenguajeASIGNACION BLOQUE CONSTANTE ESCRITURA EXPRESION FACTOR LECTURA MAS_FACTORES MAS_TERMINOS OTRA_SENTENCIA PROGRAMA SENTENCIA TERMINO VARIABLE R W % ( * + . / ; = ) dgito letra_minscula1 1 1 11 1 1 1PASO 4: Clculo del conjunto de smbolos INICIALES de cada no terminalSe pueden calcular por el mtodo visto en los apartados anteriores (5.4.2.2), o tomando los smbolos terminales marcados con un 1 en cada fila de la matriz de la relacin EMPIEZA CON.5.4.4.4.1 Ejemplo de clculo del conjunto de smbolos INICIALES de cada no terminalContinuando con el ejemplo de los apartados anteriores se obtiene: INICIALES( )= { letra_minscula } INICIALES( ) = { R W letra_minscula } INICIALES( ) = { dgito } INICIALES( ) = { W } INICIALES( ) = { ( dgito letra-minscula } INICIALES( ) = { ( dgito letra_minscula } INICIALES( ) = { R } INICIALES( ) = { % * / } INICIALES( ) = { + - } INICIALES( ) = { ; } INICIALES( ) = { R W letra_minscula } INICIALES( ) = { R W letra_minscula } INICIALES( ) = { ( dgito letra_minscula } INICIALES( ) = { letra_minscula }PASO 5: Clculo de los conjuntos INICIALES de cada produccinSe calculan los conjuntos de INICIALES de la cadena formada por la parte derecha de cada produccin.ASIGNACION BLOQUE CONSTANTE ESCRITURA EXPRESION FACTOR LECTURA MAS_FACTORES MAS_TERMINOS OTRA_SENTENCIA PROGRAMA SENTENCIA TERMINO VARIABLE R W % ( * + . / ; = ) dgito letra_minscula 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Matriz "EMPIEZA CON"- 38 -Anlisis sintctico en procesadores de lenguaje5.4.4.5.1 Ejemplo de clculo de los smbolos INICIALES de cada produccinContinuando con los ejemplos anteriores se obtiene: INICIALES( = ) = { letra_minscula } INICIALES( ) = { R W letra_minscula } INICIALES( dgito ) = { dgito } INICIALES( W ) = { W } INICIALES( ) = { ( dgito letra_minscula } INICIALES( ( ) = { ( } INICIALES( ) = { letra_minscula } INICIALES( ) = { dgito } INICIALES( = o Es una estructura (similar a la union de C) en la que se indican los tipos de los distintos valores que van a pasar por la pila del analizador generado (yyparse) durante el anlisis sintctico, es decir, los tipos de los valores semnticos de los tokens y no terminales que intervienen en la gramtica. Por ejemplo:%union { tipo1 tipo2 tipo3 }nombre1; nombre2; nombre3;indica que la pila de yyparse contendr valores de los tipos tipo1, tipo2 y tipo3, que ocuparn los campos nombre1, nombre2 y nombre3 de la unin respectivamente. Esto pasa al fichero de salida transformado en:typedef union { tipo1 nombre1; tipo2 nombre2; tipo3 nombre3; } YYSTYPE;Si el usuario escribiese esto directamente al principio del fichero de salida o en las declaraciones C (%{ ... %}) y suprimiese la clusula %union del fichero de entrada a YACCOV, el resultado sera exactamente el mismo. YYSTYPE es el nombre del tipo de la pila de yyparse. Si va a contener valores de un solo tipo, no es necesario utilizar la clusula %union. Basta con poner:%{ . . . #define YYSTYPE tipo . . . %}en la seccin de declaraciones, o bien poner la clusula #define directamente al principio del fichero de salida. Si no se define ningn tipo de datos, por defecto el tipo de la pila ser entero. %token -> Esta clusula indica que todos los smbolos que vienen a continuacin de ella (hasta que aparezca una nueva declaracin o %%) son tokens. Los nombres de los tokens pueden ir separados por comas o por blancos. Tambin se puede indicar su tipo poniendo:%token token1 token2 token3 ...siendo tipo uno de los campos definidos en %union (en el ejemplo anterior nombre1, nombre2 o nombre3). Slo se puede indicar un tipo por cada declaracin %token.- 77 -Anlisis sintctico en procesadores de lenguajeYACCOV asigna automticamente un nmero entero a cada token, que ser el que le corresponda segn el cdigo ASCII si es un literal de un solo carcter o cualquier nmero que se le asigne si no lo es. En este caso, si queremos asignarle un nmero concreto, podemos indicarlo en esta declaracin, poniendo detrs del nombre del token el cdigo que queramos que tenga, que no debe coincidir con el de ningn otro. Generalmente es mejor dejar que sea el programa quien elija los cdigos numricos para los tokens, ya que se ocupar de que sean todos distintos y de que no coincidan con los de los caracteres ASCII, liberando de esta carga al programador. %type -> Se utiliza para declarar el tipo de los smbolos no terminales. Su estructura es similar a la de %token con la diferencia de que %type tiene que llevar obligatoriamente un nombre de tipo detrs:%type variable1 variable2 variable3 ...%left, %right, %nonassoc -> Estas clusulas se utilizan para declarar un token y a la vez especificar su precedencia y asociatividad. Su sintaxis es la misma que la de %token. Indican que todos los tokens nombrados a continuacin de ellas son asociativos de izquierda a derecha, de derecha a izquierda o no asociativos respectivamente. Tambin pueden especificar su tipo y su cdigo numrico como ocurra con la clusula %token. La asociatividad de un operador OP determina cmo se asocian los usos repetidos de ste, es decir, dada la expresin X OP Y OP Z, si se debe analizar agrupando primero X con Y o Y con Z. %left indica asociatividad de izquierda a derecha (primero se agrupa X con Y, es decir, se ejecutar (X OP Y) OP Z y %right de derecha a izquierda (primero se agrupa Y con Z, es decir, se ejecutar X OP (Y OP Z)). %nonassoc indica que no hay asociatividad, es decir, X OP Y OP Z se considerar un error de sintaxis. La precedencia de un operador determina cmo se asocia ste con otros operadores. Si en la seccin de declaraciones aparecen varias declaraciones de asociatividad, cada una de ellas tendr una precedencia un nivel superior a la que la precede, es decir, si en el fichero de entrada aparece:%left + - %left * / %right ^la precedencia ms baja la tienen los tokens + y -, la de * y / ser superior a la de los anteriores y la precedencia ms alta de todas ser la de ^. Dentro de una misma declaracin de asociatividad, todos los tokens tienen la misma precedencia. %start -> Esta clusula indica que lo que viene a continuacin de ella es el smbolo inicial de la gramtica. Tiene que ser necesariamente un no terminal, si no lo es se producir un error. Si no aparece esta clusula en el fichero de entrada, se toma como smbolo inicial el no terminal que aparece en la parte izquierda de la primera regla especificada en la descripcin de la gramtica. %expect -> YACCOV, al final de su ejecucin saca un mensaje indicando el nmero de conflictos shift/reduce y reduce/reduce que encontr en la gramtica (si los haba). Si ya sabemos cuntos conflictos shift/reduce tiene la gramtica y queremos evitar que salga el mensaje, basta con poner en la seccin de declaraciones esta clusula seguida del nmero de conflictos de este tipo que esperamos que se produzcan. Si en la gramtica aparece un nmero de conflictos shift/reduce distinto al que indicamos, el mensaje saldr de todas formas. %pure_parser -> Indica que se quiere obtener un analizador reentrante. Normalmente, el analizador producido por YACCOV no lo es, porque utiliza dos variables estticamente localizadas para la comunicacin con yylex, que son yylval e yylloc. Al poner esta clusula en la seccin de declaraciones, se consigue que estas dos variables sean punteros pasados como argumentos a yylex, donde deber aparecer:- 78 -Anlisis sintctico en procesadores de lenguajeyylex (yylval, yylloc) YYSTYPE *yylval; YYLTYPE * yylloc; { ... *yylval = valor; return INT; ... } /* Poner valor en la pila de YACCOV */ /* Devolver el tipo del token. */El resto del fichero de salida no se modifica. %semantic_parser -> Esta clusula hace que se utilice como estructura para el analizador que se va a generar el fichero "SEM.PRS", en lugar de "SIMPLE.PRS". Este fichero no define las mismas macros que "SIMPLE.PRS" por lo que un fichero de entrada que fuera vlido para este ltimo, podra requerir algunos cambios para que pueda llevar como estructura el contenido de "SEM.PRS" Todas estas declaraciones pueden ir separadas por blancos o por ;. Cualquier smbolo que aparezca en una regla gramatical y no haya sido declarado en esta seccin se considera no terminal (excepto los tokens literales de un solo carcter).6.10.2 Descripcin de la gramticaEsta parte del fichero de entrada es la nica que tiene que aparecer necesariamente. Contiene la descripcin de la gramtica, que deber ir expresada de forma que YACCOV pueda entenderla. Los smbolos, tanto terminales como no terminales, se representan solamente con su nombre. Por convenio se escriben en maysculas los tokens y en minsculas los no terminales, para distinguirlos. Los smbolos terminales de un slo carcter (signos de puntuacin, parntesis, etc.) pueden ser representados por ese mismo carcter encerrado entre comillas, por ejemplo, el token * se representar mediante *. Las reglas de produccin sern de la forma:parte_izquierda : parte_derecha ;parte_izquierda es el smbolo no terminal descrito por esa regla y parte_derecha es un conjunto de smbolos terminales y/o no terminales. Por ejemplo:exp : exp + exp ;indica que si en la entrada del analizador aparece una expresin seguida de un signo + y otra expresin, todo esto debe ser agrupado para formar una nueva expresin. Los espacios en blanco (incluyendo tabuladores y marcas de fin de lnea) en las reglas se utilizan slo para separar smbolos. Se pueden aadir tantos como se quiera. El signo : separa las dos partes de la regla y el ; indica el fin de esta. Si existe ms de una regla para describir a un no terminal, se puede utilizar la siguiente notacin:parte_izquierda : componentes de la regla 1 | componentes de la regla 2 | ... ;Aunque vayan expresadas de esta forma, YACCOV internamente las trata como reglas independientes. No es necesario poner una regla en cada lnea, pero normalmente se utiliza esta notacin para hacer la gramtica ms legible. Si en la parte derecha de una regla no hay nada, significa que el no terminal que aparece en su parte izquierda acepta la cadena vaca. Por ejemplo, para definir una secuencia de cero o ms expresiones separadas por comas, se podra escribir:exps /* vaco */ | exps1 ; exps1 : exp | exps1 , exp ; :- 79 -Anlisis sintctico en procesadores de lenguajeCuando la parte derecha de una regla est vaca suele escribirse el comentario /* vaco */ para hacer ms legible la descripcin de la gramtica. Acompaando a las reglas pueden aparecer acciones, que determinan su semntica. Normalmente slo existe una accin para cada regla y va al final de ella, detrs de todos sus componentes y antes del ;. Se pueden poner comentarios en cualquier parte de la decripcin de la gramtica. Para que una gramtica sea correcta hay que tener en cuenta dos cosas: todos los smbolos que aparecen en la parte izquierda de alguna regla tienen que ser no terminales y todos los no terminales que aparecen en la descripcin de la gramtica deben estar en la parte izquierda de al menos una regla de produccin.6.10.3 Cdigo C aadido.Todo lo incluido en esta seccin se copia literalmente al final del fichero de salida de YACCOV. Este es el lugar ms apropiado para poner cualquier cosa que queramos que acompae al analizador y que no tenga que estar delante de la definicin de yylex. Los cdigos de yylex e yyerror suelen estar aqu, aunque tambin pueden ir en ficheros independientes. El fichero de salida contiene muchas variables estticas, macros y funciones cuyos nombres comienzan por yy o YY, por lo que sera recomendable evitar que los nombres de las variables, funciones, etc. que aparezcan en esta seccin empiecen por estas letras. En programas pequeos, suele incluirse todo el cdigo que acompaa a yyparse en esta seccin, pero para proyectos ms complejos es mejor distribuir el texto fuente en varios ficheros para facilitar la localizacin y correccin de los errores. Si esta seccin est vaca, se puede omitir el %% que la separa de las reglas gramaticales.6.11 SemnticaLas reglas de produccin solamente determinan la sintaxis, es decir, la estructura de las sentencias del lenguaje. La semntica viene determinada por los valores semnticos asociados a los tokens y no terminales de la gramtica y por las acciones que aparecen en las reglas.6.11.1 Valores semnticosUna gramtica formal define qu tokens pueden aparecer en cada sitio, por ejemplo, si una regla menciona el token constante_entera, quiere decir que cualquier constante entera es sintcticamente vlida en esa posicin, independientemente de su valor. Pero este valor es muy importante a la hora de ejecutar la entrada una vez que sta ha sido analizada. Por esta razn cada token de la gramtica lleva asociado un valor semntico, que puede ser su valor si representa a un nmero, su nombre si representa a un identificador, etc. Los signos de puntuacin y operadores aritmticos no tienen valor semntico. Los smbolos no terminales pueden llevar tambin un valor semntico asociado. Las reglas gramaticales no utilizan los valores semnticos para nada, stos son utilizados en las acciones que las acompaan. En un programa simple, puede ser suficiente con un solo tipo de datos para los valores semnticos de todos los smbolos de la gramtica. Por defecto se usa el tipo entero para todos ellos. Para especificar cualquier otro tipo se define YYSTYPE en la seccin de declaraciones. Pero en la mayora de los programas se necesitarn diferentes tipos de datos, por ejemplo, una constante numrica puede ser de tipo int o long, mientras que una cadena de caracteres necesita el tipo (char *) y el valor semntico de un identificador podra ser un puntero a una entrada en la tabla de smbolos. Para poder utilizar valores semnticos de varios tipos son necesarias dos cosas: declarar todos los tipos posibles utilizando la clusula %union y elegir uno de esos tipos para cada smbolo que vaya a utilizar valores semnticos, asignndoselos en las declaraciones %token y %type de la forma vista.6.11.2 AccionesPara que sea til, nuestro compilador adems de analizar la entrada, deber producir una salida. Conseguir esto es la principal funcin de las acciones que acompaan a las reglas gramaticales. Las acciones son trozos de programa escritos en C que van asociados a algunas reglas gramaticales. Cada vez que el analizador semntico efecte una reduccin utilizando una de las reglas gramaticales, inmediatamente despus ejecutar la accin correspondiente a esa regla. La mayor parte de las veces, el propsito de una accin es hallar el valor semntico del smbolo que aparece en la parte izquierda de la regla a partir de los valores semnticos de los componentes de su parte derecha. Por ejemplo, la siguiente regla:- 80 -Anlisis sintctico en procesadores de lenguajeexpr :expr + expr{ $$ = $1 + $3; }indica que se deben combinar las dos expresiones que aparecen en la parte derecha separadas por el signo ms, para dar lugar a otra expresin de orden superior. La accin indica que el valor semntico de la nueva expresin debe ser calculado sumando los valores semnticos de las otras dos expresiones. Si la accin no asigna un valor semntico a $$, el valor del smbolo que est en la parte izquierda de la regla ser impredecible y podra ocasionar problemas si se utilizara posteriormente en otras acciones. El cdigo C de una accin puede hacer referencia a los valores semnticos de los componentes de la regla, utilizando la construccin $N (siendo N un nmero entero) para representar el valor del smbolo que aparece en la posicin N de la parte derecha de la regla y $$ para referirse al valor semntico del smbolo de la parte izquierda de la regla. Por ejemplo en:expr1 : expr2 + expr3 { $$ = $1 + $3; }$$ se refiere al valor semntico de expr1, $1 al de expr2 y $3 al de expr3. Estas construcciones sern transformadas en referencias a elementos de un array al pasar al fichero de salida (yyparse ). En $N, N puede ser 0 o negativo, para referenciar smbolos que hayan sido introducidos en la pila del analizador antes que los de la regla que est siendo analizada. No es recomendable hacer esto, a menos que se conozca con certeza el contexto en que es aplicada la regla. Un ejemplo de utilizacin de esta construccin podra ser:expr previa + expr {...} | expr previa - expr {...} ; previa: /* vaco */ { expr_previa = $0; } ; expr1:En este caso, $0 se refiere siempre al valor de la expresin que va antes de previa. Si se ha elegido un solo tipo de datos para los valores semnticos, las construcciones $$ y $N tendrn siempre ese tipo. Pero si se han especificado varios mediante la clusula %union, entonces se debe indicar para cada smbolo que vaya a tener un valor semntico, cul va a ser su tipo. Cada vez que se use $$ o $N, el tipo de la construccin vendr determinado por el del smbolo al que se refiere. Tambin se puede especificar el tipo en las construcc

analisis sintactico ii

Documents