Zzzzzzzzzz
Según
la
aproximación
que
se
tome
para
construir
el
árbol
sintáctico
se
desprenden
dos
tipos
o
clases
de
analizadores:
• Descendentes:
parten
del
axioma
inicial,
y
van
efectuando
derivaciones
a izquierda
hasta
obtener
la
secuencia
de
derivaciones
que
reconoce
a
la
sentencia.
Pueden
ser:
o Con
retroceso.
o Con
funciones
recursivas.
o De
gramáticas
LL(1).
• Ascendentes:
Parten
de
la
sentencia
de
entrada,
y
van
aplicando
derivaciones
inversas (desde
el
consecuente
hasta
el
antecedente),
hasta
llegar
al
axioma
inicial.
Pueden
ser:
o Con
retroceso.
o De
gramáticas
LR(1).
Análisis descendente con retroceso
Se
parte
del
axioma
inicial
y
se
aplican
en
secuencia
todas
las
posibles
reglas
al
no
terminal
más
a
la
izquierda
de
la
forma
secuencial.
Todas
las
sentencias
de
un
lenguaje
se
encuentran
como
nodos
de
un
árbol
que
representa
todas
las
derivaciones
posibles
a
partir
de
cualquier
forma
sentencial,
y
que
tiene como
raíz
al
axioma
inicial.
El
método
de
análisis
descendente
con
retroceso
pretende
buscar
en
el
árbol
de
la
gramática
la
sentencia
a
reconocer;
cuando
lo
encuentre,
el
camino
que
lo
separa
de
la
raíz
presenta
el
árbol sintáctico.
Puede
ser
que
la
sentencia
sea
errónea
y
que
no
se
encuentre
como
hoja
del
árbol
a
lo
que
es
muy
probable
que
el
árbol
sea
infinito,
por
lo
tanto,
hay
una
necesidad
de
proponer
un
enunciado
que
nos
indique cuándo
se
debe
cancelar
la
búsqueda
porque
se
da
por
fallida.
Figura
1:
Gramática
no
recursiva
a
la
izquierda
Dada
la
gramática
de
la
figura
1,
gramática
no
ambigua
ni
recursiva
por
la
izquierda,
que
reconoce
expresiones
aritméticas,
suponga
que
se
desea
reconocer
la
secuencia:
(
id
+
num
)
*
id
+
num.
El
análisis
descendente
con
retroceso
consiste
en
hacer
una
búsqueda
en
este
árbol
de
la
rama
que
culmine
en
la
sentencia
a reconocer
mediante
un
recorrido
primero
en
profundidad.
Para
desechar
una
rama
del
árbol,
se
pueden
establecer
ciertos
criterios:
cuando
la
secuencia
de
tokens
a
la
izquierda
del
primer
no
terminal
A
no
coincide
con
el
inicio
de
secuencia
a
reconocer.
Se
pueden
establecer
otros
criterios
de
poda
(eliminación
de
ramas),
sin
embargo
este
es
el
que
manejaremos
en
lo
consiguiente.
M.C. Luis R. Basto Díaz
- 1 de 13 -
Teoría de Lenguajes de Programación
En
resumen,
se
recorre
el
árbol...
Regístrate para leer el documento completo.