Implantación de un analizador
por desplazamiento-reducción
Una forma
de implantar un analizador por desplazamiento-reducción es
mediante una pila y un buffer para la cadena de entrada.
El
análisis sintáctico consiste en leer los componentes
léxicos (o tóquenes) de la entrada e ir desplazándolos
a la pila (prefijos viables) de forma que se puedan explorar los n
componentes léxicos superiores que contiene y ver si se
corresponden con la parte derecha de las producciones (pivote).
Si es así,
se realiza una reducción, que consiste en sacar de la pila
estos n
componentes léxicos y en su lugar meter el símbolo
de la parte izquierda de esa producción.
Estos
pasos se repiten hasta conseguir reducir la cadena de entrada por el
símbolo inicial, es decir, tener en la cima de la pila al
símbolo inicial y el buffer de entrada vacío.
En la
siguiente tabla puede verse el análisis sintáctico
realizado de esta manera, para la siguiente gramática y de la
cadena a b b c d e
S→aABe
A→Abc|b
B→d
|
Pila
|
Entrada
|
Acción
|
|
$
|
a
b b c d e $
|
Desplazar
|
|
$a
|
b
b c d e $
|
Desplazar
|
|
$a
b
|
b
c d e $
|
Reducir
A→b
|
|
$a
A
|
b
c d e $
|
Desplazar
|
|
$a
A b
|
c
d e $
|
Desplazar
|
|
$a
A b c
|
d
e $
|
Reducir
A→Abc
|
|
$a
A
|
d
e $
|
Desplazar
|
|
$a
A d
|
e
$
|
Reducir
B→d
|
|
$a
A B
|
e
$
|
Desplazar
|
|
$a
A B e
|
$
|
Reducir
S→aABe
|
|
$S
|
$
|
Aceptar
|
Tabla
3: Traza
desplazamiento/reducción.
Como puede
verse en la tabla, cuando se hace un desplazamiento se pasa el
símbolo que hay en la entrada a la cima de la pila. Y en las
reducciones se sustituye una secuencia de símbolos (terminales
y no terminales) por un símbolo no terminal.
|
