Un ejemplo sencillo

Para aclarar en lo posible el funcionamiento de los analizadores sintácticos generados por ICE, usaremos un ejemplo tomado de [Vilares 93].

Se trata de analizar la entrada , según la siguiente gramática en la que es el símbolo inicial, las letras minúsculas son los componentes léxicos y las letras mayúsculas los no terminales:

En la figura A.1 se muestra el autómata LALR(1) reconocedor de la gramática . En [Aho et al. 90] se encuentra una buena descripción de cómo construir reconocedores de este tipo. Como la gramática es ambigua, en el estado 2 se producen 3 conflictos reducción-reducción. Esto se traduce en el ejemplo en tres derivaciones válidas para reconocer la entrada abdc, que son las siguientes:

  
Figure A.1: Autómata LALR(1) reconocedor de la gramática .

Al comenzar, el algoritmo añade automáticamente el item (en Earley sería el item asociado a ]). En la tabla A.1 se muestran los items involucrados en el proceso de análisis de nuestra entrada. En este momento estamos en el estado inicial 0 del autómata LALR(1).

Del item pasamos al item aplicando una operación predictor.

Ya que el punto está justo antes de la a y el siguiente componente léxico de entrada es precisamente a, aplicamos el operador scanner según Earley, con lo que obtenemos , el primer item del itemset correspondiente al componente léxico en la posición 1. Este item en Earley estaría asociado a ; a su vez, la máquina LALR(1) indica una transición al estado 1 con a. Por tanto, el estado actual es el estado 1.

Como el punto está justo antes de b y el siguiente componente léxico en la entrada es b, aplicamos la operación scanner con lo que obtenemos , el primer item del itemset correspondiente al componente léxico en la posición 2. Como el reconocedor LALR(1) indica una transición al estado 2 con b, el estado actual pasa a ser el estado 2.

En este estado se produce un triple conflicto de reducción, ya que se puede reducir indistintamente por las reglas R2, R3 y R4 para reconocer la cadena de entrada. YACC, que implemeta un reconocedor determinista LALR(1), resolvería este conflicto reduciendo por la primera regla e ignorando el resto. Sin embargo ICE, debido a su carácter no determinista, es capaz de tratar con ambigüedades como ésta y crear una estructura que representa los tres posibles árboles de análisis sintáctico con la mayor compartición posible.

  
Table: Desarrollo para la entrada w = abde en la gramática .

En el estado 2, aplicando el operador predictor con la regla R2, obtendríamos , en Earley asociado a ). El segundo y tercer elemento de se deben a que hasta el momento en este estado tan sólo se ha reconocido la entrada hasta b y a que el itemset que contiene el primer componente léxico derivado de b es .

El proceso que se seguiría a partir de aquí en caso elegir las reglas R3 o R4 para aplicar con predictor es análogo al que se va a mostrar a continuación. Es por ello que no se van a explicar esos dos caminos alternativos, ya que se alargaría demasiado el ejemplo y realmente no aportan nada nuevo a la comprensión del proceso.

En la situación actual, aplicamos el operador predictor con la regla R5 para volver a obtener .

Ahora podemos aplicar el operador completer para obtener . Con ello hemos reconocido el no terminal C en el itemset . Como la máquina LALR(1) indica que con C hay una transición al estado 3, éste pasa a ser el estado actual.

Al aplicar el operador predictor obtenemos que estaría asociado en Earley a ; como el punto está justo delante de la d y el siguiente componente léxico en la entrada es precisamente d, aplicamos la operación scanner con lo que obtenemos que es el primer item del itemset . El estado actual pasa a ser el 6 ya que así lo indica una transición el reconocedor LALR.

En el estado 6 aplicamos otra vez scanner para reconocer e y obtener el item asociado según el algoritmo de Earley a ; el autómata LALR, por su parte, indica una transición al estado 13.

Ahora, según el algoritmo de Earley deberíamos realizar una operación completer. Para ello se utiliza el puntero de retroceso . Sin embargo, el significado del puntero de retroceso en ICE es diferente al que tiene en Earley. ICE, a diferencia de Earley, utiliza las transiciones de tipo 4 para regresar al estado donde se aplicó el predictor de F (el estado 3) y genera un item que indica el reconocmiento de F en ese estado con el mismo puntero de retroceso que cuando se hizo el predictor. El item obtenido tiene por tanto la forma . Este item estaría asociado en Earley a , por lo que a su vez ahora se debe relizar la operación completer para reconocer B.

Como el predictor para B se hizo en el estado 2 con puntero de retroceso , el item resultante es que en Earley estaría asociado a con lo cual se debe realizar el completer para reconocer A.

Debido a que la operación predictor para A tuvo lugar en el estado 0 y que el puntero de retroceso utilizado en ella había sido , se obtiene el item que en Earley estaría asociado a con lo que estamos en condiciones de realizar un scanner sobre el delimitador final de la cadena. Por su parte, el reconocedor LALR(1) indica una transición al estado 8.

Al realizar el scanner de obtenemos el item . La regla asociada según Earley sería , que indica el reconocimiento de toda la cadena de entrada. Efectivamente, el autómata indica que con se debe realizar una transición al estado 9, que es un estado de aceptación, con lo cual finaliza el proceso.

La descripción que se ha realizado aquí del ejemplo es diferente a la contenida en [Vilares 93] ya que se ha tratado sobre todo de facilitar la comprensión rehuyendo de los estrictos formalismos de las transiciones en , aunque para conseguirlo se haya tenido que tomar una más que discutible asimilación del comportamiento de ICE al del algoritmo Earley con el añadido de un autómata LALR(1). La descripción completamente formal puede encontrarse en [Vilares 93].