Diferencia entre revisiones de «Analizador sintáctico descendente»
| Línea 1: | Línea 1: | ||
{{Definición|Nombre=Analizador sintáctico descendente |imagen= |concepto=Un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada}}<div align="justify"> | {{Definición|Nombre=Analizador sintáctico descendente |imagen= |concepto=Un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada}}<div align="justify"> | ||
| − | '''Analizador sintáctico descendente | + | '''Analizador sintáctico descendente''' '''(Top-Down-Parser)'''. Un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la entrada progresivamente en partes cada vez más pequeñas.<br> |
== Características<br> == | == Características<br> == | ||
| − | El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la | + | El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo inicial para una cadena de entrada. |
| − | == Parte del axioma de la gramática | + | == Parte del axioma de la gramática<br> == |
| − | *Procesa la entrada de izquierda a derecha | + | *Procesa la entrada de izquierda a derecha |
| − | *Escoge reglas gramaticales | + | *Escoge reglas gramaticales |
Para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL1 las cuales son:<br> | Para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL1 las cuales son:<br> | ||
| − | * | + | *Eliminar ambiguedad: Para eliminar la ambigüedad se debe reescribir la gramática. |
| − | * | + | *Eliminar recursividad por la izquierda: Una gramática es recursiva por la izquierda si tiene un nodo Terminal a tal que existe una derivación A->Aα para alguna cadena. Es decir por simple observación podemos identificar. |
Para eliminar la recursividad por la izquierda se utiliza la siguiente formula. | Para eliminar la recursividad por la izquierda se utiliza la siguiente formula. | ||
| Línea 35: | Línea 35: | ||
#Escoger reglas gramaticales. | #Escoger reglas gramaticales. | ||
#Obtener el árbol de análisis sintáctico o error | #Obtener el árbol de análisis sintáctico o error | ||
| − | # | + | #El árbol de derivación se construye: |
*Desde la raíz | *Desde la raíz | ||
| Línea 54: | Línea 54: | ||
*Muy eficiente. | *Muy eficiente. | ||
| − | Ejemplo: [[Image: | + | Ejemplo: [[Image:Análisis sintáctico descendente con retroceso.JPG|center|267x153px]] |
<br> | <br> | ||
| Línea 62: | Línea 62: | ||
El analizador debe realizar la previsión de la regla a aplicar sólo con ver el primer símbolo que produce para que el [[Algoritmo|algoritmo]] tenga una complejidad lineal.<br>Las gramáticas que son susceptibles de ser analizadas sintácticamente de forma descendente mediante un análisis predictivo y consultando un únicamente un símbolo de entrada pertenecen al grupo LL(1).<br>A partir de gramáticas LL(1) se pueden construir analizadores sintácticos descendentes predictivos (ASDP), que son ASD sin retroceso.<br>Ejemplo: | El analizador debe realizar la previsión de la regla a aplicar sólo con ver el primer símbolo que produce para que el [[Algoritmo|algoritmo]] tenga una complejidad lineal.<br>Las gramáticas que son susceptibles de ser analizadas sintácticamente de forma descendente mediante un análisis predictivo y consultando un únicamente un símbolo de entrada pertenecen al grupo LL(1).<br>A partir de gramáticas LL(1) se pueden construir analizadores sintácticos descendentes predictivos (ASDP), que son ASD sin retroceso.<br>Ejemplo: | ||
| − | ==== [[Image: | + | ==== [[Image:ASD sin retroceso.JPG|center|236x68px]]Conjuntos de Predicción<br> ==== |
*Son conjuntos de símbolos terminales | *Son conjuntos de símbolos terminales | ||
| Línea 103: | Línea 103: | ||
*[http://ants.dif.um.es/staff/juanbot/traductores/files/20022003/tema4.pdf Traductores] | *[http://ants.dif.um.es/staff/juanbot/traductores/files/20022003/tema4.pdf Traductores] | ||
*[http://www2.uah.es/jcaceres/uploaded/teoria/LenguajesProgramacion/tema4.pdf Lenguajes de Programación]<br> | *[http://www2.uah.es/jcaceres/uploaded/teoria/LenguajesProgramacion/tema4.pdf Lenguajes de Programación]<br> | ||
| − | |||
| − | |||
| − | |||
| − | |||
[[Category:Lenguajes_de_programación]] [[Category:Programación]] | [[Category:Lenguajes_de_programación]] [[Category:Programación]] | ||
Revisión del 08:47 5 may 2011
| ||||
Analizador sintáctico descendente (Top-Down-Parser). Un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la entrada progresivamente en partes cada vez más pequeñas.
Sumario
Características
El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo inicial para una cadena de entrada.
Parte del axioma de la gramática
- Procesa la entrada de izquierda a derecha
- Escoge reglas gramaticales
Para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL1 las cuales son:
- Eliminar ambiguedad: Para eliminar la ambigüedad se debe reescribir la gramática.
- Eliminar recursividad por la izquierda: Una gramática es recursiva por la izquierda si tiene un nodo Terminal a tal que existe una derivación A->Aα para alguna cadena. Es decir por simple observación podemos identificar.
Para eliminar la recursividad por la izquierda se utiliza la siguiente formula.
Ejemplo:
Funcionamiento
La forma en que funciona un analizador sintáctico descendente es:
- Los terminales se examinan en el orden en que aparecen en la cadena de tokens: t1 t2 t3 t4 t5
- Escoger reglas gramaticales.
- Obtener el árbol de análisis sintáctico o error
- El árbol de derivación se construye:
- Desde la raíz
- De izquierda a derecha
Clasificación
- Analizador sintáctico descendente con retroceso.
- Analizador sintáctico descendente con recursión.
- Analizador sintáctico descendente LL(1)
Análisis sintáctico descendente con retroceso
El método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda.
- Se usa el retroceso para resolver la incertidumbre.
- Sencillo de implementar.
- Muy eficiente.
Análisis sintáctico descendente con predictivo
El analizador debe realizar la previsión de la regla a aplicar sólo con ver el primer símbolo que produce para que el algoritmo tenga una complejidad lineal.
Las gramáticas que son susceptibles de ser analizadas sintácticamente de forma descendente mediante un análisis predictivo y consultando un únicamente un símbolo de entrada pertenecen al grupo LL(1).
A partir de gramáticas LL(1) se pueden construir analizadores sintácticos descendentes predictivos (ASDP), que son ASD sin retroceso.
Ejemplo:
Conjuntos de Predicción
- Son conjuntos de símbolos terminales
- Ayudan a predecir qué regla se debe aplicar para el no terminal que hay que derivar.
- Se construyen a partir de los símbolos de las partes derechas de las producciones de la gramática.
- El analizador consulta el siguiente símbolo en la entrada.
- Si pertenece al conjunto de predicción de una regla aplica esa regla, si no da error.
Analizador sintáctico descendente LL(1)
Características de la condición LL(1)
- La secuencia de tokens se analiza de izquierda a derecha.
- Siempre deriva el no terminal que aparezca más a la izquierda.
- Sólo es necesario ver un token de la secuencia de entrada para averiguar que regla de producción seguir.
Diferencias entre el descendente y el ascendente
- En el análisis sintáctico descendente: se construye el árbol sintáctico de arriba hacia abajo y se utiliza más reglas.
- En el análisis sintáctico ascendente: se construye el árbol sintáctico de abajo hacia arriba, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente.
