Analizadores

Por lo que respecta al parser se han propuesto varias estrategias, independientes del tipo de gramática que se utilice, aunque los principales analizadores se han diseñado para gramáticas independientes del contexto. Dada una gramática, el parser, de acuerdo con la estrategia que siga, especificará cómo se debe llevar a cabo el análisis sintáctico.
Se empezaron a desarrollar a finales de los 60 con conocimientos procedentes de la IA (p. ej. las redes de transición aumentadas) y de los lenguajes formales, los lenguajes de programación.

Las principales estrategias seguidas por los parsers son:

• Análisis descendente (top-down) vs. ascendente (bottom-up)
• Análisis determinista vs. no determinista
• Análisis secuencial o en profundidad (depth-first) vs. en paralelo (breadth-first)

Analizador descendente

Para producir la representación estructural de una oración, esta estrategia compara las reglas de la gramática con la oración que se le presenta para el análisis empezando por la regla más abstracta, la que contiene el símbolo inicial (gramática), y va descendiendo hasta llegar a los elementos terminales (léxico), es decir, va de la gramática a los datos o, si se prefiere, actúa por objetivos. A partir de la primera palabra de la oración establece una hipótesis sobre una posible estructura (correspondencia entre la parte izquierda de las reglas y las categorías presentes en el input) y se mantiene en ella, a menos que se pruebe que es incorrecta.

Analizador ascendente

Para producir una representación estructural, esta estrategia compara la oración de entrada con las reglas de la gramática empezando por la última regla, la que contiene los elementos terminales (léxico), y va ascendiendo hasta llegar a la regla más abstracta, es decir, va de los datos a la gramática. Para aplicar las reglas busca correspondencias entre las categorías presentes en el input y la parte derecha de las reglas. Fue el primer tipo de analizador utilizado y, para algunos autores, su forma de actuar reflejaría mejor el procesamiento de las oraciones que efectúan las personas, aunque esta es una cuestión no exenta de controversias. También se atribuye mayor eficiencia a este tipo de analizadores, ya que al tener conocimientos previos sobre el input resuelve el análisis en menos pasos.

Analizador determinista

El parser actúa condicionado por los datos, que son los que le llevan a proponer una estructura y no otras. Es lo que sucede en los analizadores ascendentes, que parten de la oración: están obligados a seguir un único camino, el que le marcan los datos.

Analizador no determinista

El parser no está condicionado por los datos, por lo que contempla varias posibilidades antes de optar por la correcta. Es lo que sucede en los analizadores descendentes, que parten de la gramática: contemplan varios caminos alternativos, bien sea de forma simultánea, en paralelo, o de forma secuencial, primero uno y, si este falla, luego otro. Este proceso de vuelta atrás se conoce como retrotrazado o backtracking. Estos analizadores parecen más robustos.

Analizador secuencial

Ante varias alternativas, el analizador opta por una y la sigue hasta agotarla; si ésta falla, volverá atrás (backtracking) y elegirá otra; y así sucesivamente hasta dar con el análisis correcto.

Analizador en paralelo

Ante varias alternativas, el analizador, antes de optar por una, examina a las vez todas las de un nivel, después las del nivel superior, etc. Esta forma de proceder suele consumir bastantes recursos de memoria.

ver el ejemplo en el pagina ...

http://www3.unileon.es/dp/dfh/Milka/LC/Sintaxis.htm