ANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEAnlisis Sintctico Descendente con RetrocesoElanlisissintcticodescendente(ASD) intentaencontrarentrelasproduccionesdelagramticaladerivacinporlaizquierdadel smboloinicialparaunacadena de entrada.EjemploAnalizarlacadenadeentrada!cad"dadala gramtica siguienteANALISIS SINTACTICO DESCENDENTE!cad"# se toma la primera produccinANALISIS SINTACTICO DESCENDENTE$!cad"# se toma la segunda produccin.$siguiente %oja del rbol A & cabdANALISIS SINTACTICO DESCENDENTE$!cad" se compara con la siguiente %oja del rboletiquetadacon!b".'omono concuerda# se indica el error ( se vuelve a Aparaversi%a(otraalternativanointentada.ANALISIS SINTACTICO DESCENDENTE$!cad"# se toma la siguiente alternativa quecomienza por a.$siguiente %oja del rbol A# & cadANALISIS SINTACTICO DESCENDENTE!cad"# coincide d con d& anlisis e)itosoANALISIS SINTACTICO DESCENDENTEAnlisisSintcticoDescendentecon PredictivoEl analizador deberealizarla previsin de lareglaaaplicarsloconverelprimer smboloqueproduceparaqueel algoritmo tenga una complejidad lineal.ANALISIS SINTACTICO DESCENDENTEEjemplo . Sentif E)press t%en Sent. Sentwhile E)press do Sent. Sentbegin Sent endE)isteslounaposibilidaddederivacin# seg*n que el primer smbolo que %a(a en la entrada sea un i+# ,%ile o beginANALISIS SINTACTICO DESCENDENTEAnlisis Sintctico Descendente con Predictivo-asgramticasquesonsusceptiblesdeser analizadassintcticamentede+orma descendentemedianteunanlisispredictivo( consultandoun*nicamenteunsmbolode entradapertenecenal grupo --(.).Apartirdegramticas--(.)sepueden construiranalizadoressintcticosdescendentes predictivos (ASD/)# que son ASD sin retroceso.ANALISIS SINTACTICO DESCENDENTEConjuntos de Prediccin Son conjuntos de smbolos terminales 0A(udanapredecirqu1reglasedebeaplicar para el no 2erminal que %a( que derivar.Seconstru(enapartirdelossmbolosdelas partesderec%asdelasproduccionesdela gramtica. El analizador consulta el siguiente smbolo en la entrada.0sipertenecealconjuntodeprediccindeunaregla aplica esa regla# si no da error.ANALISIS SINTACTICO DESCENDENTEEjemplos de Conjuntos de PrediccinSupngaselaentrada!bab)cc"#quese %anledo(alossmbolossubra(ados en !bab)cc"# ( la gramtica es0 A& a 3 c 4 ) ' 4 30 3 & bA0 '& c$56u1produccindebetomarpara seguir el anlisis7ANALISIS SINTACTICO DESCENDENTE-a cadena de derivaciones %a sido0A & 3 & bA & ba3c & babAc$A%ora%a(queseguirdesarrollandola variableAutilizandolosconjuntosde prediccin.$'omolasiguienteletraesuna.).seeligela segunda opcin (A & ) ') ANALISIS SINTACTICO DESCENDENTE-a gramticanocumplelosrequisitospara--(.)porque siapareceuna!a"enlaentrada%a(dos posibles opciones.-uego el anlisis$ no puede ser predictivo (#$ la gramtica no es --(.).ANALISIS SINTACTICO DESCENDENTE$'lculo de los conjuntos de prediccin0'lculo de los primeros0'lculo de los siguientesANALISIS SINTACTICO DESCENDENTEClculo de los Conjuntos de Prediccin-os conjuntos de prediccin se calculan0en+uncindelosprimerossmbolosque puede generar la parte derec%a de la regla# (0cuandolapartederec%apuedegenerar la cadena vaca# en +uncin delos smbolos que puedenapareceracontinuacindela parteizquierdadelareglaenuna+orma sentencial derivable del smbolo inicial. ANALISIS SINTACTICO DESCENDENTE/arapoderde+inirlosconjuntode prediccin es necesario determinar$conjunto de primeros0calcularlosprimerossmbolosquegenera 0una cadena de terminales ( no terminales $conjunto de siguientes0obtenerlossmbolosquepuedenseguira un no terminal en una +orma sentencial.ANALISIS SINTACTICO DESCENDENTE'lculo de los primerosANALISIS SINTACTICO DESCENDENTESea una gramticaDe+.8$Siesuna+ormasentencialcompuesta porunaconcatenacindesmbolos# /9:;()eselconjuntodeterminales(o ramticaANALISIS SINTACTICO DESCENDENTE'lculo de los siguientesANALISIS SINTACTICO DESCENDENTESeaplicaanoterminales(?@)dela gramtica (A)$ Devuelveelconjuntodeterminalesque puedenapareceracontinuacindeAen alguna+ormasentencialderivadadel smbolo inicial ($ Ansmbolo(B)querepresentael+inaldela cadena de entrada.ANALISIS SINTACTICO DESCENDENTEDe+.8Si A esunsmboloinicialnoterminal delagramtica#S:>(A)eselconjuntode terminales((B)quepuedenaparecera continuacindeAenalguna+orma sentencialderivadadel smbolo inicial.De+. +ormalANALISIS SINTACTICO DESCENDENTE9eglasparael'lculodelconjuntodelos siguientesANALISIS SINTACTICO DESCENDENTE'lculodelossiguientesdela gramticaANALISIS SINTACTICO DESCENDENTEGramticaANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTE'lculo de los conjuntos de prediccinANALISIS SINTACTICO DESCENDENTE-a +uncin /9ED$se aplica a producciones dela gramtica (A &= )$devuelveunconjuntodeprediccin quepuedecontenercualesquierade losterminalesdelagramtica(el smbolo B# pero nunca puede contener ramticas --(.)# se debe cumplirANALISIS SINTACTICO DESCENDENTE'aractersticas de la condicin --(.)$-asecuenciadetokensseanalizadeizquierda a derec%a.$Siemprederivaelnoterminalque aparezca ms a la izquierda.$Sloesnecesarioveruntokendela secuenciadeentradaparaaveriguar que regla de produccin seguir.ANALISIS SINTACTICO DESCENDENTEEjemplo de la >ramtica --(.)ANALISIS SINTACTICO DESCENDENTESi se aCade la regla 3 & aANALISIS SINTACTICO DESCENDENTE5'umple esta gramtica la condicin --(.)7ANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTE;odi+icacin de gramticas no --(.)0Eliminacin de la ambigDedad0Eactorizacin por la izquierda0Eliminacindelarecursividadporla izquierdaANALISIS SINTACTICO DESCENDENTE'aractersticas$Algunascaractersticasgarantizanque una gramtica no es --(.)09ecursiva por la izquierda0Smbolos comunes por la izquierda0Ambigua$E)istenm1todosparamodi+icarla( convertirla en una gramtica --(.)ANALISIS SINTACTICO DESCENDENTEEliminacin de la AmbigDedad$;s de un rbol sintctico posible.$@o e)iste una metodologa para eliminarla$SolucinreplantearseeldiseCodelamismaparaencontrarunagramtica no ambiguaequivalente(quegenereelmismo lenguaje)ANALISIS SINTACTICO DESCENDENTEEactorizacin por la :zquierda$Sidosproduccionesalternativasdeun smbolo A empiezan igual# no se sabr por cul de ellas seguir.$Solucinreescribirlasproduccionesde Apararetrasarladecisin%asta%aber visto losu+icientedelaentradacomopara elegir la opcin correcta.ANALISIS SINTACTICO DESCENDENTE9egla general para +actorizar por la izquierda$Encontrarelpre+ijomslargocom*n a dosomsproduccionesdeA#perosiempreaqu1l queseacom*nams producciones$Sie)isteunpre+ijocom*nmscortoen variasproducciones(otro mslargoen un par deellas#%a(queeliminarprimeroelmscorto com*n a las varias ( FG HI tal que 4H4 J 4 F 4).ANALISIS SINTACTICO DESCENDENTESolucin sustituir las produccionesANALISIS SINTACTICO DESCENDENTE$Sea la gramticaSent & i+ Expr t%en Sent else Sent endi+Sent & i+ Expr t%en Sent endi+Sent & otras$Solucin sustituirlo por dos producciones de la +ormaANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEEliminacin recursiva por la izquierda$Anagramticaesrecursivaporla izquierda.ANALISIS SINTACTICO DESCENDENTE9egla para modi+icar una gramtica$9eglaparamodi+icarunagramtica(deje de ser recursiva por la izquierda.ANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEEjemplodeunaconversindeuna gramtica en --(.)ANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEAnalizador sintctico descendente predictivo dirigido por tablaANALISIS SINTACTICO DESCENDENTE$;odelodeunASD/norecursivo dirigido por tabla$;odelodelanalizadorsintctico predictivo$'onstruccindelatablasdeanlisis sintctico$/rocedimientoparaconstruirtablasde anlisis --(.)$;ensajes de error de tipo sintcticoANALISIS SINTACTICO DESCENDENTE'aractersticas$Es otra +orma de construir un ASD/$'onstruccinutilizandounapilade smbolos (terminales ( no terminales)$Alavistadeuntokendepreanlisisse buscar en la tabla de anlisis.$/rimeroconstruirlatabla(despu1s realizar el proceso de anlisis.ANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEE)plicacin del gr+ico$El programa tiene en cuenta A# el smbolo delacimadelapila#(a#elsmboloen curso de la entrada.ANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTE'onstruccindelastablasdeanlisis SintcticoANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTE/rocedimientos para construir tablas de anlisis ANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTEANALISIS SINTACTICO DESCENDENTE