Estudio

RECONOCIMIENTO DESCENDENTE. CONCEPTOS BÁSICOS 7.1 Técnica descendente Comencemos presentando la forma como funciona el reconocimiento descendente. La técnica consiste en procesar la hilera de entrada, símbolo por símbolo, e ir identificando cuál producción fue la que se aplicó para generar ese símbolo. Ilustremos esta técnica con un ejemplo. Consideremos la siguiente gramática 1. 2. 3. 4. 5. 6.      ab b ba c c a

MODULO 7

y esta hilera de entrada: abcacb┤ Nos interesa determinar si dicha hilera pudo haber sido generada por la gramática dada, es decir, si dicha hilera pertenece al lenguaje que genera esa gramática. Para hacer este proceso utilizaremos un autómata de pila, en el cual, la configuración inicial de la pila es ▼. En la figura siguiente presentamos la formacomo va evolucionando la pila de acuerdo al símbolo de entrada que estemos procesando.

x:

▼ a (a)

b ▼ b (b)

a b ▼ c (c)

a b ▼ a (d) Figura 7.1

b ▼ c (e)

b ▼ b (f)

▼ ┤ (g)

Como hemos dicho, la configuración inicial de la pila es ▼, debido a que el símbolo inicial de la gramática es el no terminal . La configuración inicial de la pila siempre será el símbolo de pilavacía con el símbolo inicial de la gramática. Estando la pila en su configuración inicial leemos el primer símbolo de la hilera a reconocer, es decir la a.

Esta situación se presenta en el caso (a) de la figura 7.1. En el tope de la pila está el no terminal y el símbolo de entrada es el terminal a. El razonamiento aquí es: existe alguna producción cuyo símbolo del lado izquierdo sea el noterminal y que pueda generar el terminal a? La respuesta es si: la producción 1. Hemos detectado que el terminal a se obtuvo aplicando la producción 1, por consiguiente, debemos continuar nuestro proceso de reconocimiento con los símbolos del lado derecho de la producción 1. Para lograr esto reemplazamos el símbolo en el tope de la pila (el no terminal ) por el resto del lado derecho de la producción1 en reversa, y leemos el siguiente símbolo. Estamos en el caso (b) de la figura 7.1: en el tope de la pila está el no terminal y el símbolo de entrada es el terminal b. Nuestro razonamiento aquí será el mismo: existe alguna producción cuyo símbolo del lado izquierdo sea el no terminal y que pueda generar el terminal b? La respuesta es nuevamente si: la producción 3. Hemos detectado que elterminal b se obtuvo aplicando la producción 3, por consiguiente, debemos continuar nuestro proceso de reconocimiento con los símbolos del lado derecho de la producción 3. Para lograr esto reemplazamos el símbolo en el tope de la pila (el no terminal ) por el resto del lado derecho de la producción 3 en reversa, y leemos el siguiente símbolo. Estamos en el caso (c) de la figura 7.1: en el tope de lapila está el no terminal y el símbolo de entrada es el terminal c. Nuestro razonamiento aquí es nuevamente el mismo: existe alguna producción cuyo símbolo del lado izquierdo sea el no terminal y que pueda generar el terminal c? La respuesta es nuevamente si: la producción 5. Hemos detectado que el terminal c se obtuvo aplicando la producción 5, por consiguiente, debemos continuar nuestro procesode reconocimiento con los símbolos del lado derecho de la producción 5. Para lograr esto reemplazamos el símbolo en el tope de la pila (el no terminal ) por el resto del lado derecho de la producción 5 en reversa, y leemos el siguiente símbolo. Fijémonos que como el resto del lado derecho de la producción 5 es vacío, es decir, es la secuencia nula, nuestro proceso de reemplazo es equivalente adesapilar el símbolo en el tope de la pila. Quedamos en el caso (d) de la figura 7.1: en el tope de la pila hay un terminal, el terminal a. Cuando en el tope de la pila hay un terminal fue porque llegó como consecuencia de una operación de reemplazo. El símbolo de entrada en ese momento debe ser exactamente ese mismo terminal para confirmar que efectivamente se aplicó esa producción (en nuestro...