A.1.1 El núcleo de ICE

Dada una gramática de contexto libre , mediante el uso de técnicas estándar se puede producir un reconocedor LALR(1), posiblemente no determinista, del lenguaje .

Dada una cadena de entrada de longitud n, ICE asocia a cada componente léxico , donde i representa su posición en dicha cadena, un conjunto de items llamado itemset.

Se generan nuevos itemsets mediante la aplicación de transiciones sobre los existentes, hasta que no es posible aplicar más transiciones. Un item representa la configuración de la pila en un momento dado: [], donde p es el estado en que se encuentra el autómata LALR(1) en dicho momento, X es el último símbolo gramatical reconocido en el estado p, es el puntero de retroceso e indica el itemset que contiene el primer componente léxico derivado del símbolo X y es el itemset que se está utilizando en ese momento.

Una transición en , se traduce en de la siguiente forma:

1. 
2. 
3. 
4. 

si y sólo si:

1. Y = X
2. Y = a
3. 
4. 

donde:

y:

donde It el el conjunto de los items involucrados en el proceso de análisis y es el conjunto de transiciones dinámicas. Los casos precedentes se corresponden con:

1. Una acción ir_a del estado p al estado q bajo una transición X en el autómata LALR(1).
2. Meter en la pila el terminal a en el estado p. El nuevo item generado pertenecerá al siguiente itemset .
3. Meter en la pila el no terminal Y en el estado p.
4. Sacar el tope de la pila en el estado p, donde q es un ancestro del estado p bajo la transición X en el autómata LALR(1). En este caso no se genera un nuevo item, sino una transicion dinámica con el fin de tratar la ausencia de información sobre el contenido del resto de la pila. Esta transición se puede aplicar no sólo a la configuración resultante de la primera, sino también sobre aquellas que sean generadas y que compartan la misma estructura sintáctica.

Ciertamente, la definición de las transiciones puede parecer confusa en un primer momento. Su significado adquiere una mayor claridad si se conoce el algoritmo de Earley de análisis sintáctico no determinista [Earley 70, Vilares 92], el cual, a partir de un itemset inicial, va aplicando a los items de cada itemset tres operaciones (scanner, completer y predictor) con las que se generan nuevos items y nuevos itemsets. El proceso finaliza cuando ya no se puede aplicar ninguna operación sobre ningún item. En Earley cada item tiene asociado una producción, un punto en esa producción que indica qué símbolos de la parte derecha han sido reconocidos hasta el momento y un puntero de retroceso al itemset de la posición en la entrada en la que se comenzó a buscar por la instancia de la producción asociada al item. La operación scanner consiste básicamente en leer el siguiente componente léxico de entrada y construir el correspondiente itemset. La operación predictor va aplicando las distintas reglas cuyo lado izquierdo es X cuando en un item el siguiente símbolo a reconocer es X. Completer es la operación que se aplica a un item cuando el punto está al final de la parte derecha de la producción y consiste en copiar del itemset indicado por el puntero de retroceso todos los items que tengan inmediatamente a la derecha del punto el no terminal de la parte izquierda de la producción, corriendo el punto una posición a la derecha, con lo que se indica que hay por lo menos un camino válido para reconocer ese símbolo para la parte de la entrada que se ha analizado.

ICE se diferencia de Earley en que tiene detrás un autómata, lo que le confiere una mayor eficiencia. Es también por ello que los items de ICE incluyen el estado del reconocedor LALR(1).

Lo que hace ICE es usar el autómata LALR(1) como base para las transiciones entre items. Básicamente, consiste en utilizar el autómata como una guía de modo que no se pierda tiempo realizando transiciones entre items que no estén el camino que lleve a alguna de las soluciones.