Analisis_sintactico_descendente

ANALISIS SINTACTICO DESCENDENTE

ANALISIS SINTACTICO DESCENDENTE
Análisis Sintáctico Descendente con Retroceso
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.
Ejemplo:
Analizar la cadena de entrada “cad” dada la
gramática siguiente:

ANALISIS SINTACTICO DESCENDENTE“cad”, se toma la primera producción

ANALISIS SINTACTICO DESCENDENTE
• “cad”, se toma la segunda producción.
• siguiente hoja del árbol A → cabd

ANALISIS SINTACTICO DESCENDENTE
• “cad” se compara con la siguiente hoja del
árbol etiquetada con “b”. Como no
concuerda, se indica el error y se vuelve a
A para ver si hay otra alternativa no
intentada.

ANALISIS SINTACTICO DESCENDENTE
• “cad”, setoma la siguiente alternativa que
comienza por a.
• siguiente hoja del árbol A, → cad

ANALISIS SINTACTICO DESCENDENTE
“cad”, coincide d con d → análisis exitoso

ANALISIS SINTACTICO DESCENDENTE
Análisis Sintáctico
Predictivo

Descendente

con

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 complejidadlineal.

ANALISIS SINTACTICO DESCENDENTE
Ejemplo:
. Sent if Express then Sent
. Sent while Express do Sent
. Sent begin Sent end
Existe sólo una posibilidad de derivación,
según que el primer símbolo que haya en la
entrada sea un if, while o begin

ANALISIS SINTACTICO DESCENDENTE
Análisis Sintáctico Descendente con Predictivo
Las gramáticas que son susceptibles de ser
analizadas
sintácticamente
deforma
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.

ANALISIS SINTACTICO DESCENDENTE
Conjuntos de Predicción
 Son conjuntos de símbolos terminales
– Ayudan a predecir qué regla se debeaplicar
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.

ANALISIS SINTACTICO DESCENDENTE
Ejemplos de Conjuntos de Predicción
Supóngase la entrada “babxcc”, quese
han leído ya los símbolos subrayados
en “babxcc”, y la gramática es:
– A →aBc|xC|B
– B → bA
– C →c

•¿Qué producción
seguir el análisis?

debe

tomar

para

ANALISIS SINTACTICO DESCENDENTE

La cadena de derivaciones ha sido:
– A → B → bA → baBc → babAc

• Ahora hay que seguir desarrollando la
variable
A utilizando los conjuntos de
predicción.
• Como la siguiente letra es una .x. se elige
lasegunda opción (A → x C)

ANALISIS SINTACTICO DESCENDENTE
La gramática
no cumple los requisitos para LL(1) porque
si aparece una “a” en la entrada hay dos
posibles opciones.
Luego el análisis:
• no puede ser predictivo y,
• la gramática no es LL(1).

ANALISIS SINTACTICO DESCENDENTE

• Cálculo de los conjuntos de predicción
– Cálculo de los primeros
– Cálculo de los siguientes

ANALISIS SINTACTICODESCENDENTE
Cálculo de los Conjuntos de Predicción
Los conjuntos de predicción se calculan:
– en función de los primeros símbolos que
puede generar la parte derecha de la regla, y
– cuando la parte derecha puede generar
la cadena vacía, en función de los símbolos
que pueden aparecer a continuación de la
parte izquierda de la regla en una forma
sentencial derivable del símbolo inicial.

ANALISISSINTACTICO DESCENDENTE
Para poder definir los conjunto
predicción es necesario determinar:
•conjunto de primeros

de

– calcular los primeros símbolos que genera
– una cadena de terminales y no terminales

•conjunto de siguientes
– obtener los símbolos que pueden seguir
a un no terminal en una forma sentencial.

ANALISIS SINTACTICO DESCENDENTE

Cálculo de los primeros

ANALISIS SINTACTICO...