This page last changed on Jan 27, 2008 by carlos.gonzalez.

Mangos, Agarraderos, Asideros o Handlers

Informalmente un mango de una cadena es una subcadena que concuerda con el lado derecho de una producción y cuya reducción al no terminal del lado izquierdo de la producción representa un paso a lo largo de la inversa de una derivación por la derecha.

En muchos casos, la subcadena situada más a la izquierda β que concuerda con el lado derecho de alguna producción A -> β no es un mango porque una reducción por la producción A -> β produce una cadena no reducible al símbolo inicial.

Por ejemplo, para la gramática con producciones:

  1. S -> aABe
  2. A -> Abc | b
  3. B -> d

la frase abbcder se puede reducir:
abbcde por el agarradero (A -> b en la posición 2)
aAbcde (A -> Abc en la posición 2)
aAde (B -> d en la posición 3)
aABe (S -> aABe en la posición 1)
S

Analizador por Corrimiento Reducción

Hay dos problemas a resolver en un análisis sintáctico por corrimiento reducción:

  1. Ubicar la subcadena a reducir
  2. Determinar la producción a utilizar, en el caso que haya más de una.

Las estructuras a utilizar son parecidas a la de análisis predictivo no recursivo, se usa una pila para manejar los símbolos gramaticales y un buffer para la cadena de entrada. Al igual que el APNR se coloca un símbolo $ para indicar el fondo de la pila y el fin de la cadena.

Al principio la pila está vacía y la cadena a el buffer.

PILA ENTRADA
$ w$

El analizador sintáctico funciona desplazando cero o más símbolos de la entrada a la pila hasta que un mango β este en la cima. Entonces el analizador reduce β al lado izquierdo de la producción utilizada; el analizador repite el proceso hasta que se detecta un error o la pila contiene el símbolo inicial y la entrada está vacía.

PILA ENTRADA
$S $

Para el ejemplo anterior el resultado será el siguiente:

PILA ENTRADA ACCIÓN
$ abbcde$ desplazar
$a bbcde$ desplazar
$ab bcde$ reducir A -> b
$aA bcde$ desplazar
$aAb cde$ desplazar
$aAbc de$ reducir A -> Abc
$aA de$ desplazar
$aAd e$ reducir B -> d
$aAB e$ desplazar
$aABe $ reducir S -> aABe
$S $ Aceptar

Aunque se habla de corrimiento y reducción, existen 4 operaciones (acciones):

  1. desplazar, se correo un elemento de la entrada al tope de la pila.
  2. reducir, se cambia el mango en el tope de la pila por el no terminal adecuado.
  3. Aceptar, se termina el proceso y se indica el éxito.
  4. Error, se llama a la rutina de recuperación de errores.
Document generated by Confluence on Oct 04, 2010 11:24