Teora de lenguajes y compiladoresAnlisis Sintctico DescendenteSemana 8Unidad IIAnalizador Sintctico

Objetivo GeneralEl alumno al finalizar el curso podr desarrollar aplicaciones que le permitan determinar si una estructura gramatical corresponde a una sentencia valida en la definicin de un lenguaje en particular, teniendo en cuenta el contexto sintctico y semntico. As mismo estar capacitado para proponer nuevas formas estructurales en la definicin de lenguajes de programacin.

Objetivos EspecficosDisear un analizador sintctico.

Objetivos EspecficosAplicar mtodos de desarrollo descendente para la construccin de analizadores sintcticos

Objetivos InstruccionalesAplicar mtodos par el desarrollo de analizadores sintcticos descendentes.

ANALIZADOR SINTCTICO SentenciasSentenciasSentencia;AsignacinSentenciaAsignacinVariableExpresin:=VariableExpresin:=VariableExpresin+xbVariableExpresin*VariableVariablecdey

Funcin:Comprobar que la secuencia de tokens cumple con las reglas de la gramticaGenerar el rbol sintctico

Ventajas de utilizar gramticas:Las gramticas son especificaciones sintcticas y precisas de lenguajes de programacinA partir de una gramtica se puede generar automticamente un analizadorEl proceso de construccin puede llevar a descubrir ambigedadesUna gramtica imparte estructura a un lenguaje de programacin, siendo mas fcil generar cdigo y detectar erroresEs mas fcil de ampliar/modificar el lenguaje si esta descrito con una gramticaANALISIS SINTACTICO

Descendentes (Top-Down): Parten del axioma y aplican las reglas de la gramtica hasta llegar a secuencia de smbolos terminales (tokens):

Analizadores LL(1)Analizadores recursivos

Ascendentes (Bottom-Up): Parten de las hojas (conjunto de tokens) para llegar a la raz (axioma de la gramtica):

Analizadores de Precedencia de OperadorAnalizadores LR(1)TIPOS DE ANALIZADORES SINTACTICOS

Se basa en gramticas LL, que construyen rboles de anlisis sintctico de arriba (raz) hacia abajo (hojas).

La primera L significa que la entrada ser leda de izquierda a derecha y la segunda L indica derivaciones por la izquierda.ANALISIS SINTCTICO DESCENDENTE

Algoritmo:Poner el axioma como raz del rbol de derivacinHasta que solo haya smbolos terminales, derivar mas a la izquierda

Ejemplo:Entrada: Id * Id + idGramtica: Expresion::= Expresion * Termino | Expresion + Termino | Termino Termino ::= id | NumeroDerivacin: Expresion Expresion + Termino Expresion * Termino + Termino Termino * Termino + Termino Id * Termino + Termino Id * Id + Termino Id * Id + idANALISIS SINTCTICO DESCENDENTE

Mas de una opcin: A ::= a|

RetrocesoAnalizar los siguientes elementos de entrada

Recursividad izquierda

Eliminacin de la recursividad

Ambigedad

Factorizacin por la izquierdaPROBLEMAS DE LOS ANALIZADORES SINTCTICO DESCENDENTE

Para cada produccin de la forma:A 1 | 2 | 3 | | n Siempre debemos ser capaces de elegir la alternativa correcta para la generacin de un rbol de anlisis sintctico.Para cumplir esta regla necesitamos informacin adicional, a saber:El conjunto de todos los smbolos terminales que pueden aparecer al principio de una frase que puede derivarse de una secuencia arbitraria de smbolos (CONJUNTO PRIMERO).El conjunto de todos los smbolos terminales que pueden aparecer despus de uno no terminal (CONJUNTO SIGUIENTE).

Sea G(N,T,P,S) una gramtica y secuencia arbitraria de smbolos, es decir (NUT)*, entonces;

Primero() = { t / t T ^ t a } , donde T = T U { }Para calcular Primero(X) para todos los smbolos gramaticales X, aplquense las reglas siguientes hasta que no se puedan aadir mas terminales o a ningn conjunto Primero.1.Si X es terminal, entonces primero(X) es {X}2.Si X es una produccin, entonces adase a Primero(X)3.a. Si X es no terminal y X Y1 Y2 Yk , es una produccin, entonces pngase a en Primero(X) si para alguna i, a esta en Primero(Yi) y esta en todos los Primero(Y1)Primero(Yi-1) ; es decir Y1..Yi-1 b. Si esta en primero(Yj) para toda i = 1,2,,k, entonces adase a primero(X).Por ejemplo, todo lo que esta en Primero(Y1) sin duda esta en Primero(X). Si Y1 no deriva a , entonces no se aade nada ms a Primero(X). Pero si Y1 , entonces se le aade Primero(Y2), y as sucesivamente.CONJUNTO PRIMERO(1/3)

Ahora se puede calcular el conjunto Primero para cualquier cadena X1X2Xn de la siguiente forma:

adase a Primero(X1X2Xn) todos los smbolos distintos de de Primero(X1). Si esta en Primero(X1), adase tambin los smbolos distintos de de Primero(X2); si esta tanto en Primero(X1) y Primero(X2) adanse tambin los smbolos distintos de de Primero(X3) y as sucesivamente.

Por ultimo adase a Primero (X1X2Xn) si para todo i=1..n, Primero(Xi) contiene al .CONJUNTO PRIMERO(2/3)

Ejemplo:Considrese la gramtica siguiente:E TEE +TE | T F TT *F T | F ( E ) | idEntonces : Primero(E) = { ( , id } Primero(E) = { + , } Primero(T) = { ( , id } Primero(T) = { * , } Primero(F) = { ( , id }CONJUNTO PRIMERO(3/3)

Sea G(N,T,P,S) una gramtica y secuencia arbitraria de smbolos, es decir (NUT)*, entonces; Siguiente(X) = { t / t T ^ S X t } Para calcular Siguiente(A) para todos los no terminales A, aplquense las reglas siguientes hasta que no se pueda aadir nada mas a ningn conjunto siguiente:1. Pngase $ en Siguiente(S) , donde S es el smbolo inicial y $ es el delimitador derecho de la entrada.

2.Si hay una produccin A B , entonces todo lo que este en Primero() excepto se pone en Siguiente(B).

3. Si hay una produccin A B o una produccin A B donde Primero() contenga ( es decir ), entonces todo lo que este en Siguiente(A) se pone en Siguiente(B).CONJUNTO SIGUIENTE(1/2)

Ejemplo:Considerando la gramtica anterior, se determino que: E TE Primero(E) = { ( , id } E +TE | Primero(E) = { + , } T F T Primero(T) = { ( , id } T *F T | Primero(T) = { * , } F ( E ) | id Primero(F) = { ( , id } Entonces: Siguiente(E) = { ) , $ } Regla 1 Regla 2 aplicada a F ( E ) Siguiente(E) = { ) , $ } Regla 3 aplicada a E T E Siguiente(T) = { + , ) , $ } Regla 2 aplicada a E +TE Regla 3 aplicada a E +TE Siguiente(T) = { + , ) , $ } Regla 3 aplicada a T F T Siguiente(F) = { + , * , ) , $ } Regla 2 aplicada a T *FT Regla 3 aplicada a T *FTCONJUNTO SIGUIENTE(2/2)

Una gramtica independiente del contexto G(N,T,P,S) se denomina gramtica LL(1) si tiene las siguientes caractersticas:C1) Para las producciones de la forma:A 1 | 2 | 3 | | n se requiere: Primero(i) Primero(j) = Para todo i jC2) si puede derivarse la cadena vaca () de un smbolo no terminal X, se requiere que: Primero(X) Siguiente(X) = Una gramtica cuya tabla de anlisis sintctico no tiene entradas con definiciones mltiples se define como LL(1).Queda la cuestin de lo que se debe hacer cuando la tabla de anlisis sintctico tiene entradas con mltiples definiciones. Un recurso es transformar la gramtica eliminando la recursin por la izquierda y factorizando por la izquierda siempre que sea posible, con la esperanza de producir una gramtica para la cual la tabla de anlisis sintctico no tenga entradas con mltiples definiciones.GRAMTICAS LL(1)

Ejemplo:GRAMTICAS LL(1)Considerar una gramtica que permita la generacin de frases como: program declaracion; declaracion; begin proposicion; proposicion; proposicion; end.La gramtica G viene dada por: T = { b , d , e , p , s , ; , . } N = { A , X , Y } P = { A pX X d ; X | bsYe Y ; sY | S = {A} Es una gramtica de tipo LL(1)?

p = programad = declaracionb = begins = proposicione = end

Solucin:GRAMTICAS LL(1)Primero(A) = { p } Siguiente(A) = { $ }Primero(X) = { d , b } Siguiente(X) = { $ }Primero(Y) = { , ; } Siguiente(Y) = { e , $ }Luego:Por C1) Primero(d;X) Primero(bsYe) = { d } { b } = Primero() Primero(;sY) = { } { ; } = Por C2) Primero(Y) Siguiente(Y) = { , ; } { } = Entonces a partir de la definicin de LL(1) se concluye que esta gramtica es no ambigua y nunca puede ser recursiva izquierda.Esto es obvio ya que una gramtica G es ambigua si hay una palabra en L(G) que posea 2 derivaciones por la izquierda (a partir del smbolo inicial).EN CONCLUSION:Las gramticas LL(1) se usan preferentemente para el anlisis sintctico descendente.

Sea G una gramtica ; supngase que A , es una produccin con a en Primero(). Entonces, el analizador sintctico expandir A por cuando el smbolo actual de entrada sea a.Algoritmo: Construccin de una tabla de anlisis sintctico predictivoEntrada: Una gramtica GSalida: La tabla de anlisis sintctico MProcedimiento: Para cada produccin A de la gramtica dense los pasos 2 y 3. Para cada terminal a de primero() , adase A a M[A,a]a. Si esta en Primero(), adase A a M[A,b] para cada terminal b de Siguiente(A).

b. Si esta en Primero() y $ esta en Siguiente(A), adase A a M[A,$]4. Hgase que cada entrada no definida de M sea error.CONSTRUCCIN DE TABLAS LL(1)(1/2)

En la gramtica anterior:

CONSTRUCCIN DE TABLAS LL(1)(2/2)

Algoritmo:Entrada: Una cadena W y una tabla de anlisis sintctico M para la gramtica GSalida: Si W esta en L(G) , una derivacin por la izquierda de W; de lo contrario una indicacin de error.

Al principio, el analizador sintctico esta en una configuracin en la que tiene a $S en la pila S, el smbolo inicial de G en el tope y W$ en el buffer de entrada.

Apuntar ptr al primer smbolo de W$ Repetir Sea X el smbolo de la cima de la pila y a el smbolo apuntado por ptr Si X es un terminal o $ entoncesSi X = a entonces Extraer X de la pila y avanzar ptr Caso contrario Error Caso contrario Si M[X,a] = X Y1Y2Yk entonces Extraer X de la pila Meter Yk,Yk-1,,Y1 en la pila con Y1 en la cima Emitir la produccin X Y1Y2Yk Caso contrario Error Hasta X = $ /* la pila esta vaca */ALGORITMO REGURSIVO GUIADO POR TABLA (1/2)

Ejemplo: Analizar si: id + id * id es valida para la gramtica anteriormente presentada.

ALGORITMO REGURSIVO GUIADO POR TABLA (2/2)

Implantacin:

Se asocia un procedimiento a cada no terminal de la gramtica.

El rbol sintctico esta dado implcitamente por la secuencia de llamadas a procedimientos.

ESTRUCTURA DE UN ANALIZADOR SINTACTICO DESCENDENTE RECURSIVO

Ejemplo:

E ::= T EE ::= + T E | T ::= F TT ::= * F T | F ::= (E) | IdESTRUCTURA DE UN ANALIZADOR SINTACTICO DESCENDENTE RECURSIVOProcedure E T; E; write(E)Procedure E c=GetToken; if c = + then write(+); T; E; else rectract; write(E)Procedure F c=GetToken; case c (: write((); E; c=GetToken(); if c = ) then write()); write(F); else Fail; error; Id: write(Id); write(F); otherwise: Fail; error;

PROGRAM Analizador_sintactico; PROCEDURE Error (); PROCEDURE N0; PROCEDURE N1; PROCEDURE Nm;BEGIN Leer_simbolo; N0;END.ESTRUCTURA DE UN ANALIZADOR SINTACTICO DESCENDENTE RECURSIVO

CORRESPONDENCIA ENTRE GRAFOS SINTACTICOS Y LOS PROGRAMASREGLA 1: Representacin de alternativas.IF ch IN PRIMERO(S1) THEN P(S1) ELSE IF ch IN PRIMERO(S2) THEN P(S2) ELSE IF ch IN PRIMERO(Sm) THEN P(Sm) ELSE Error;

CORRESPONDENCIA ENTRE GRAFOS SINTACTICOS Y LOS PROGRAMASREGLA 2: Secuencia de llamada a procedimientos.BEGIN P(S1); P(S2); .; P(S3) END;

CORRESPONDENCIA ENTRE GRAFOS SINTACTICOS Y LOS PROGRAMASWHILE ch IN PRIMERO(S) DO P(S);SREGLA 3: Proposicin de repeticin.

CORRESPONDENCIA ENTRE GRAFOS SINTACTICOS Y LOS PROGRAMASIF ch IN PRIMERO(S) THEN P(S);REGLA 4: Proposicin condicional.

CORRESPONDENCIA ENTRE GRAFOS SINTACTICOS Y LOS PROGRAMASP(S);REGLA 5: Llamada a procedimientoS

CORRESPONDENCIA ENTRE GRAFOS SINTACTICOS Y LOS PROGRAMASREGLA 6: Lectura condicionalSIF ch = t THEN read(ch) ELSE Error;

Teora de lenguajes y compiladoresAnlisis Sintctico DescendenteSemana 8Unidad IIAnalizador Sintctico

****************************