Zzzzzzzzzz

Teoría de Lenguajes de Programación Tipos de análisis sintáctico
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...