En este apéndice se realiza una descripción general del generador de analizadores
sintácticos no deterministas e incrementales que se utiliza en
esta tesina: ICE
.
ICE, desarrollado por Vilares como parte de su tesis doctoral [Vilares 92], toma como entrada una clase general de gramáticas de contexto libre. La forma en que se describe dicha gramática es idéntica a la que se utiliza con YACC, lo que permite que cualquier gramática previamente escrita para YACC se pueda utilizar también con ICE sin necesidad de realizar cambios.
Para asegurar la eficiencia computacional, ICE hace uso del concepto de traductor a pila no determinista como modelo operacional para simular todas las posibles computaciones, con una complejidad cúbica tanto espacial como temporal en el peor caso, aunque es lineal para una clase amplia de gramáticas. Otra característica fundamental es que no interpreta directamente las gramáticas, sino que primero las compila. El problema de la compartición óptima de computaciones lo resuelve empleando técnicas de programación dinámica.
ICE representa el análisis por medio de la secuencia de reglas que se deben usar para realizar una reducción de izquierda a derecha de la sentencia de entrada hasta alcanzar el símbolo inicial. Esta representación le permite resolver el problema de la compartición óptima de la estructra sintáctica de salida. Además, debido a su carácter incremental, al modificar una parte de la cadena de entrada tan sólo se eliminan las partes del análisis que habían sido generadas por los elementos de la cadena que han cambiado. La parte del análisis que permanece es la que se corresponde con la parte de la entrada que permanece invariable.
Desde un punto de vista empírico, ICE se muestra superior a otros analizadores de contexto libre y comparable a los analizadores sintácticos deterministas estándar cuando la cadena de entrada no es ambigua.