next up previous contents
Next: 1.2 Antecedentes Up: 1.1 El análisis incremental Previous: 1.1.1 El análisis incremental

1.1.2 El análisis no determinista

La utilización práctica de técnicas no deterministas en la construcción de compiladores para lenguajes de programación es escasa. Las técnicas clásicas como LL(k) y LR(k) son deterministas. Esto quiere decir que para una entrada dada (un programa) sólo se obtendrá un árbol de análisis sintáctico. Como no todas las gramáticas de contexto libre pueden ser transformadas de modo tal que sean reconocidas por un autómata determinista, estas técnicas no reconocen todas las gramáticas de contexto libre, aunque sí las utilizadas en todos los lenguajes de programación. Algunas herramientas basadas en técnicas determinísticas como YACC permiten que la gramática sea ambigüa, pero a la hora de realizar el análisis, cuando se presentan conflictos siguen normas bien conocidas para resolverlos. Por ejemplo, cuando YACC detecta un conflicto de desplazamiento/reducción, opta siempre por realizar el desplazamiento, lo cual le lleva a comportarse bien ante casos como el del else ambiguo.

En el procesamiento del lenguaje natural el uso del no determinismo es obvio ya que los idiomas como el castellano presentan por su propia naturaleza cierto número de ambigüedades a nivel léxico y sintáctico.

Para que un analizador sintáctico sea capaz de tratar con el no determinismo debe ser capaz de tratar con más de un árbol sintáctico. Para no perder eficiencia se debe de buscar un método que permita compartir la mayor cantidad posible de información, ya que mantener varias representaciones completas del mismo árbol cuando tan sólo se diferencien en una serie de ramas (aquellas que corresponden a los distintos caminos a tomar cuando tenemos una ambigüedad) representaría un consumo de memoria excesivamente alto.

ICE es capaz de generar eficientes analizadores no deterministas incrementales, como se puede observar en las resultados empíricos mostrados en [Vilares 93, Vilares y Dion 94]. ICE permite incorporar la incrementalidad y el no determinismo al proceso del análisis sintáctico sin que ello suponga un coste elevado en cuanto a eficiencia, e incrementa en gran medida la flexibilidad en lo concerniente al diseño de gramáticas.


next up previous contents
Next: 1.2 Antecedentes Up: 1.1 El análisis incremental Previous: 1.1.1 El análisis incremental

Miguel A. Alonso Pardo
Thu Nov 20 16:47:01 CET 1997