Contenido - analisis sintactico PDF

Preview

Summary

analisis sintactico...

Description

Análisis ascendencia recursiva Ascendencia recursiva es una de las principales técnicas de análisis que construye el árbol de análisis sintáctico y la parte superior se lee la entrada de izquierda a derecha. Utiliza procedimientos para cada terminal y no terminal entidad. Este análisis técnica recursiva analiza la entrada para realizar un análisis, un árbol que puede requerir o no retroceder. Pero la gramática asociada a ella (si no cuenta) no puede evitar retrocesos. Una forma de análisis recursivo de ascendencia que no requiere ningún rastreo se conoce como análisis predictivo. Este análisis se considera técnica recursiva ya que utiliza libres de contexto gramática que es de naturaleza recursiva.

Rastreo Desde arriba los analizadores inicio desde el nodo raíz (símbolo de inicio) y coincide con la cadena de entrada contra las normas de producción para sustituir (si corresponde). Para entender esto, tomar el siguiente ejemplo de CFG: S → rXd | rZd X → oa | ea Z → ai

Para una cadena de entrada: leer, un analizador de arriba a abajo, se comportará como esta: Se iniciará con la de las normas de producción y coincidirá con su rendimiento en la izquierda de la carta de la entrada, es decir, 'r'. La producción de S (S → rXd) coincide con ella. Por lo tanto, el top-down analizador avanza a la siguiente carta de entrada (es decir 'E' ). El analizador intenta expandir no terminal 'X' y comprueba su producción desde la izquierda (X → oa). Que no se corresponde con el siguiente símbolo de entrada. Por lo tanto, el de arriba a abajo retroceso analizador para obtener la siguiente regla de producción X, (X → ea). Ahora, el analizador de entrada coincide con todas las letras de forma ordenada. La cadena es aceptada.

Analizador Predictivo Analizador sintáctico Predictivo recursivo es un analizador ascendencia, que tiene la capacidad de predecir que la producción se debe usar para sustituir la cadena de entrada. El analizador predictivo no sufren de retroceso. Para cumplir sus cometidos, el analizador predictivo utiliza un puntero hacia delante, que apunta a la siguiente entrada los símbolos. Para que el analizador de libres, el analizador predictivo pone algunas limitaciones a la gramática y acepta sólo una clase de gramática conocida como LL(k) gramática.

Análisis predictivo utiliza una pila y un análisis a fin de analizar el cuadro de entrada y generar un análisis árbol. Tanto la pila y la entrada contiene un símbolo de final $ para indicar que la pila está vacía y la entrada es consumida. El analizador se refiere al análisis tabla para tomar cualquier decisión sobre la entrada de pila y combinaciones de elementos.

Ascendencia recursiva en el análisis, el analizador puede tener más de una producción entre los que elegir para una sola instancia de entrada, mientras que analizador de predicción, cada paso ha de una producción más para elegir. Es

posible que haya casos en que no hay producción de la cadena de entrada, con lo que el procedimiento de análisis.

LL Analizador Acepta un analizador LL LL gramática. LL gramática es un subconjunto libre de contexto gramática pero con algunas limitaciones para obtener la versión simplificada, con el fin de lograr una fácil implementación. LL gramática se puede aplicar a través de ambos algoritmos recursivos, de ascendencia o tabla. LL analizador se denota como LL(k). La primera L en LL(k) es el análisis de la entrada de izquierda a derecha, la segunda L en LL(k) representa más a la izquierda de derivación y k representa el número de lecturas. Por lo general k = 1, de modo que LL(k) también puede ser escrito como LL(1).

Algoritmo LL Análisis Nos puede adherirse a determinista LL(1) para analizador explicación, ya que el tamaño de la tabla crece de forma exponencial con el valor de k. En segundo lugar, si en la gramática no es LL(1), a continuación, por lo general, no es LL(k), para cualquier k. A continuación se muestra un algoritmo para LL(1) El análisis: Input: string ω parsing table M for grammar G Output: If ω is in L(G) then left-most derivation of ω,

error otherwise. Initial State : $S on stack (with S being start symbol) ω$ in the input buffer SET ip to point the first symbol of ω$. repeat let X be the top stack symbol and a the symbol pointed by ip. if X∈ Vt or $ if X = a POP X and advance ip. else error() endif else /* X is non-terminal */ if M[X,a] = X → Y1, Y2,... Yk POP X PUSH Yk, Yk-1,... Y1 /* Y1 on top */ Output the production X → Y1, Y2,... Yk else error() endif endif until X = $ /* empty stack */

Una gramática G es LL(1) si A → α | β se distinguen dos producciones de G:  Para terminal, α y β derivar cadenas comienzan con un.  En la mayoría de α y β pueden derivar cadena vacía.  Si β → t, a continuación, α no se deriva ninguna cadena que empieza con un terminal en SIGA(A).

Anal i z adorsi nt áct i codescendent e.( TopDownPar s er ) :unanal i z adorpuede empez arc onels í mbol oi ni c i alei nt ent art r ans f or mar l oenl aent r ada,i nt ui t i v ament e es t os er í ai rdi vi di endol aent r adapr ogr es i v ament eenpar t esc adav ezmáspequeñas .

Características El anál i s i ss i nt ác t i c odes c endent e( ASD)i nt ent aenc ont r arent r el aspr oduc ci onesde l agr amát i c al ader i v ac i ónporl ai zqui er dadels í mbol oi ni c i alpar aunac adenade ent r ada.

Parte del axioma de la gramática 

Pr oc es al aent r adadei z qui er daader ec ha.



Es c oger egl asgr amat i c al es .

Par at r abaj arel anál i s i ss i nt ác t i c odes c endent es edeber eal i z arpr i mer ament eal gunas oper ac i onespar aquel agr amát i c as eaLL1l asc ual ess on: 

ELI MI NARAMBI GUEDAD:Par ael i mi narl aambi güedads edeber ees c r i bi rl a gr amát i c a.



ELI MI NARRECURSI VI DADPORLAI ZQUI ERDA:Unagr amát i c aesr ec ur s i v a porl ai z qui er das i t i eneunnodoTer mi nalat al queex i st eunader i v ac i ónA>Aα par aal gunacadena.Esdec i rpors i mpl eobs er v ac i ónpodemosi dent i fi c ar .

Par ael i mi narl ar ecur s i v i dadporl ai z qui er das eut i l i z al as i gui ent ef or mul a.

Fact or i z ar :Set r at ader es c r i bi rl aspr oduc ci onesdel agr amát i c aconi gual comi enz o par ar et r as arl adeci s i ónhas t ahaberv i s t ol os ufi c i ent edel aent r adac omopar ael egi r l aopc i ónc or r ec t a. Ej empl o:

Funcionamiento Laf or maenquef unc i onaunanal i z adors i nt ác t i codesc endent ees :

  

Lost er mi nal ess eex ami nanenelor denenqueapar ec enenl acadena ok ens :t 1t 2t 3t 4t 5 det Es c ogerr egl asgr amat i c al es . Obt enerel ár boldeanál i s i ss i nt áct i c ooer r or

El ár bol deder i v ac i óns ec ons t r uy e:  

Desdel ar aí z Dei zqui er daader ec ha

Clasificación   

Anal i z adors i nt ác t i c odes c endent ec onr et r oc es o. Anal i z adors i nt ác t i c odes c endent ec onr ec ur s i ón. Anal i z adors i nt ác t i c odes c endent eLL( 1)

Análisis sintáctico descendente con retroceso El mét odopar t edelax i omai ni ci alyapl i c at odasl aspos i bl esr egl asalnot er mi nalmás al ai z qui er da.   

Seus ael r et r oc es opar ar es ol v erl ai nc er t i dumbr e. Senc i l l odei mpl ement ar . Muyefi c i ent e.

Ej empl o:

Análisis sintáctico descendente con predictivo El anal i z adordeber eal i z arl apr ev i s i óndel ar egl aaapl i c ars ól oconv erel pr i mer gor i t mot engaunac ompl ej i dadl i neal . s í mbol oquepr oduc epar aqueelal Lasgr amát i casques ons us c ept i bl esdes eranal i z adass i nt áct i c ament edef or ma des c endent emedi ant eunanál i s i spr edi ct i v oyc ons ul t andounúni c ament eunsí mbol o deent r adaper t enecenal gr upoLL( 1) .

Apar t i rdegr amát i casLL( 1)s epuedenc ons t r ui ranal i z ador ess i nt áct i c os des c endent espr edi ct i v os( ASDP) ,ques onASDs i nr et r oc es o. Ej empl o:

Conjuntos de Predicción 

Sonc onj unt osdesí mbol ost er mi nal es



Ayudanapr edec i rquér egl as edebeapl i carpar ael not er mi nalquehayque der i v ar .



Sec ons t r uy enapar t i rdel oss í mbol osdel aspar t esder ec hasdel as pr oduc ci onesdel agr amát i c a.

 

El anal i z adorc ons ul t ael s i gui ent es í mbol oenl aent r ada. Siper t enec eal conj unt odepr edi c ci óndeunar egl aapl i caes ar egl a,s i noda er r or .

Analizador sintáctico descendente LL(1) Car act er í st i casdel acondi ci ónLL( 1)   

Las ec uenc i adet ok enss eanal i z adei z qui er daader ec ha. Si empr eder i v ael not er mi nalqueapar ezc amásal ai zqui er da. Sól oesnec es ar i ov erunt ok endel as ec uenc i adeent r adapar aav er i guarque r egl adepr oduc c i óns egui r .

Diferencias entre el descendente y el ascendente  

Enel anál i s i ss i nt áct i c odes cendent e:s ec onst r uy eel ár bol si nt ác t i codear r i ba hac i aabaj oys eut i l i z amásr egl as . Enel anál i s i ss i nt áct i c oas cendent e:s econs t r uy eel ár bols i nt ác t i codeabaj o hac i aar r i ba,l ocualdi s mi nuy eel númer oder egl asmal apl i c adasconr es pec t oal c as odes c endent e.

Anal i z adorsi nt áct i coascendent e.( Bot t omUpPar ser ) .Unanal i z adorpuede empez arc onl aent r adaei nt ent arl l egarhas t aels í mbol oi ni ci al ,i nt ui t i v ament eel anal i z adori nt ent aenc ont r arl oss í mbol osmáspequeñosypr ogr es i v ament ec onst r ui r l aj er ar quí ades í mbol oshas t aeli ni c i al .

Objetivo de un análisis ascendente El obj et i v odeunanál i s i sas c endent ec ons i s t eencons t r ui rel ár bols i nt ác t i c odes de abaj ohac i aar r i ba,es t oes ,des del ost ok enshaci aelax i omai ni c i al ,l oc ual di s mi nuy e el númer oder egl asmal apl i c adasconr es pec t oal cas odes c endent e( s ihabl amosdel c as oc onr et r oc es o)oampl í ael númer odegr amát i cass us c ept i bl esdeseranal i z adas ( s ihabl amosdel cas oLL( 1) ) .

Operaciones en un analizador ascendente Amedi daqueunanal i z adors i nt áct i cov ac ons t r uy endoel ár bol ,s eenf r ent aauna c onfi gur ac i óndi s t i nt a( s edenomi naconfigur ac i ónal paráâ)ydebet omaruna dec i s i óns obr eel si gui ent epas ouoper ac i ónar eal i z ar .Bás i cament esedi s ponede c uat r ooper ac i onesdi f er ent es ,ycadat i podeanal i z adorasc endent esedi s t i nguede l osdemásenbas eal ai nt el i genc i asobr ec uándoapl i c arcadaunadedi c has oper ac i ones . Cual qui ermec ani s modeanál i si sas cendent econs i s t eenpar t i rdeunac onfi gur ac i ón i ni ci al ei rapl i c andooper ac i ones ,c adaunadel asc ual esper mi t epas ardeuna c onfi gur ac i ónor i genaot r odes t i no.El pr oc es ofinal i z ar ác uandol ac onfi gur ac i ón des t i nol l egueas ert alqueαr epr es ent ealár bol s i nt ác t i c ocompl et oyenβs ehay an c ons umi dot odosl ost ok ens .Lasoper ac i onesdi s poni bl ess onl ass i gui ent es : 1.ACEPTAR:s eac ept al acadena:β≡EOFyα≡S( ax i omai ni c i al ) . 2.RECHAZAR:l ac adenadeent r adanoesv al i da. 3.REDUCI R:c ons i s t eenapl i c arunar egl adepr oduc c i onhac i aat r asaal gunos el ement oss i t uadosenel ext r emoder ec hodeα. 4.DESPLAZAR:cons i s t euni c ament eenqui t arelt er mi nalmasal ai z qui er dadeβy poner l oal ader ec hadeα.

Clasificación  

Anal i z adors i nt áct i coas c endent econr et r oc es o. Anal i z adors i nt áct i coas c endent eLR( 1)

Análisis ascendente con retroceso Ali gual queoc ur r í ac onelc as odes c endent e,es t et i podeanál i si si nt ent apr obart odas l aspos i bl esoper ac i ones( r educ c i onesydes pl az ami ent os )medi ant eunmét odode f uer z abr ut a,has t al l egaral ár bols i nt áct i c o,obi enagot art odasl asopc i ones ,enc uy o c as ol ac adenas er ec haz a. Enel anál i s i sc onr et r oces onoseper mi t enl asr egl asԑ,pues t oquees t ass epodr án apl i c ardef or mai ndefi ni da.

Análisis ascendente sin retroceso El anál i s i sas c endent es i nr et r oc es obus c aunader i v ac i ónder ec hadel acadenade ent r adadef or madet er mi ni s t a. Es t es esus t ent aens uapl i c ac i ónal asgr amát i c asLR( K) . LaLv i enedel al ec t ur adel ac adenadeent r adadei z qui er daader ec ha. LaRdepr oduc i runár boldeder i v ac i ónder ec ho. Laki ndi c ael númer odes í mbol osqueesnec es ar i ol eeral aent r adapar at omarl a dec i s i óndequépr oduc c i ónempl ear . Unpar s erdel t i pos hi f t r educepuedev er sec omounaut ómat adepi l adet er mi ni s t a ex t endi doquer eal i z ael anál i s i sdeabaj ohac i aar r i ba. Dadaunac adenadeent r adaw,s i mul aunader i v ac i ónmásal ader ec ha.

Análisis ascendente de gramáticas LR(1) Enes t apar t esei nt r oduc i r áunat écni caefi c i ent edeanál i s i ss i nt áct i c oas cendent e ques epuedeut i l i z arpar apr oc es arunaampl i ac l as edegr amát i c asdecont ex t ol i br e. Lat écni c as edenomi naanál i s i ss i nt áct i c oLR( k ) .Laabr ev i at ur aLRobedec eaquel a c adenadeent r adaesex ami nadadei zqui er daader ec ha( eni ngl es ,Lef t t or i ght ) , mi ent r asquel a“ R”i ndi c aqueelpr oc es opr opor c i onael ár bol s i nt ác t i comedi ant el a s ec uenc i adeder i v ac i onesader ec ha( eni ngl es ,Ri ght mos tder i v at i on)enor den i nv er so. ok ensdepr ebús quedaut i l i z adospar a Porul t i mo,l a“ k ”hac er ef er enci aalnumer odet t omarl asdec i s i oness obr es ir educ i rodes pl az ar .Cuandos eomi t e,s eas umequek , es1.

Característic as no deseables para el análisis lineal

Análisis sintáctico descendente ◮

Recursividad por la izquierda ◮

Factores comunes por la izquierda ◮

Ambigüedad

Análisis sintáctico ascendente ◮

Ambigüedad...