Requisito previo: análisis | Conjunto 2 (Analizadores de reducción de desplazamiento o de abajo hacia arriba)
Shift Reduce los intentos del analizador para la construcción del análisis de una manera similar a como se hace en el análisis de abajo hacia arriba, es decir, el árbol de análisis se construye desde las hojas (abajo) hasta la raíz (arriba). Una forma más general del analizador shift-reduce es el analizador LR.
Este analizador requiere algunas estructuras de datos, es decir
- Un búfer de entrada para almacenar la string de entrada.
- Una pila para almacenar y acceder a las reglas de producción.
Operaciones básicas –
- Desplazamiento: implica mover símbolos del búfer de entrada a la pila.
- Reducir: si el identificador aparece en la parte superior de la pila, se realiza su reducción mediante el uso de la regla de producción adecuada, es decir, el lado derecho de una regla de producción se saca de una pila y el lado izquierdo de una regla de producción se coloca en la pila.
- Aceptar: si solo el símbolo de inicio está presente en la pila y el búfer de entrada está vacío, la acción de análisis se llama aceptar. Cuando se obtiene la acción aceptada, significa que se realizó un análisis sintáctico exitoso.
- Error: esta es la situación en la que el analizador no puede realizar la acción de cambio ni reducir la acción y ni siquiera aceptar la acción.
Ejemplo 1 – Considere la gramática
S –> S + S
S –> S * S
S –> id
Realice el análisis Shift Reduce para la string de entrada «id + id + id».
Ejemplo 2: Considere la gramática
E –> 2E2
E –> 3E3
E –> 4
Realice el análisis Shift Reduce para la string de entrada “32423”.
Ejemplo 3 – Considere la gramática
S –> ( L ) | una
L –> L , S | S
Realice el análisis Shift Reduce para la string de entrada “( a, ( a, a ) ) “.
| Pila | Búfer de entrada | Acción de análisis |
|---|---|---|
| ps | ( un , ( un , un ) ) $ | Cambio |
| ps | un , ( un , un ) ) $ | Cambio |
| $( un | , ( un , un ) ) $ | Reducir S → a |
| $( S | , ( un , un ) ) $ | Reducir L → S |
| $( L | , ( un , un ) ) $ | Cambio |
| $( L , | ( un , un ) ) $ | Cambio |
| $( L , ( | a , a ) ) $ | Cambio |
| $( L , ( un | , a ) ) $ | Reducir S → a |
| $( L , ( S | , a ) ) $ | Reducir L → S |
| $( L , ( L | , a ) ) $ | Cambio |
| $( L , ( L , | a ) ) $ | Cambio |
| $( L , ( L , un | ps | Reducir S → a |
| $(L, (L, S) | ps | Reducir L →L, S |
| $( L, ( L | ps | Cambio |
| $(L, (L) | ps | Reducir S → (L) |
| $(L, S | ps | Reducir L → L, S |
| $( L | ps | Cambio |
| $(L) | ps | Reducir S → (L) |
| $S | ps | Aceptar |
A continuación se muestra la implementación-
C++
// Including Libraries
#include <bits/stdc++.h>
using namespace std;
// Global Variables
int z = 0, i = 0, j = 0, c = 0;
// Modify array size to increase
// length of string to be parsed
char a[16], ac[20], stk[15], act[10];
// This Function will check whether
// the stack contain a production rule
// which is to be Reduce.
// Rules can be E->2E2 , E->3E3 , E->4
void check()
{
// Copying string to be printed as action
strcpy(ac,"REDUCE TO E -> ");
// c=length of input string
for(z = 0; z < c; z++)
{
// checking for producing rule E->4
if(stk[z] == '4')
{
printf("%s4", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
//printing action
printf("\n$%s\t%s$\t", stk, a);
}
}
for(z = 0; z < c - 2; z++)
{
// checking for another production
if(stk[z] == '2' && stk[z + 1] == 'E' &&
stk[z + 2] == '2')
{
printf("%s2E2", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
stk[z + 2] = '\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
}
}
for(z = 0; z < c - 2; z++)
{
//checking for E->3E3
if(stk[z] == '3' && stk[z + 1] == 'E' &&
stk[z + 2] == '3')
{
printf("%s3E3", ac);
stk[z]='E';
stk[z + 1]='\0';
stk[z + 1]='\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
}
}
return ; // return to main
}
// Driver Function
int main()
{
printf("GRAMMAR is -\nE->2E2 \nE->3E3 \nE->4\n");
// a is input string
strcpy(a,"32423");
// strlen(a) will return the length of a to c
c=strlen(a);
// "SHIFT" is copied to act to be printed
strcpy(act,"SHIFT");
// This will print Labels (column name)
printf("\nstack \t input \t action");
// This will print the initial
// values of stack and input
printf("\n$\t%s$\t", a);
// This will Run upto length of input string
for(i = 0; j < c; i++, j++)
{
// Printing action
printf("%s", act);
// Pushing into stack
stk[i] = a[j];
stk[i + 1] = '\0';
// Moving the pointer
a[j]=' ';
// Printing action
printf("\n$%s\t%s$\t", stk, a);
// Call check function ..which will
// check the stack whether its contain
// any production or not
check();
}
// Rechecking last time if contain
// any valid production then it will
// replace otherwise invalid
check();
// if top of the stack is E(starting symbol)
// then it will accept the input
if(stk[0] == 'E' && stk[1] == '\0')
printf("Accept\n");
else //else reject
printf("Reject\n");
}
// This code is contributed by Shubhamsingh10
C
//Including Libraries
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//Global Variables
int z = 0, i = 0, j = 0, c = 0;
// Modify array size to increase
// length of string to be parsed
char a[16], ac[20], stk[15], act[10];
// This Function will check whether
// the stack contain a production rule
// which is to be Reduce.
// Rules can be E->2E2 , E->3E3 , E->4
void check()
{
// Copying string to be printed as action
strcpy(ac,"REDUCE TO E -> ");
// c=length of input string
for(z = 0; z < c; z++)
{
//checking for producing rule E->4
if(stk[z] == '4')
{
printf("%s4", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
//printing action
printf("\n$%s\t%s$\t", stk, a);
}
}
for(z = 0; z < c - 2; z++)
{
//checking for another production
if(stk[z] == '2' && stk[z + 1] == 'E' &&
stk[z + 2] == '2')
{
printf("%s2E2", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
stk[z + 2] = '\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
}
}
for(z=0; z<c-2; z++)
{
//checking for E->3E3
if(stk[z] == '3' && stk[z + 1] == 'E' &&
stk[z + 2] == '3')
{
printf("%s3E3", ac);
stk[z]='E';
stk[z + 1]='\0';
stk[z + 1]='\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
}
}
return ; //return to main
}
//Driver Function
int main()
{
printf("GRAMMAR is -\nE->2E2 \nE->3E3 \nE->4\n");
// a is input string
strcpy(a,"32423");
// strlen(a) will return the length of a to c
c=strlen(a);
// "SHIFT" is copied to act to be printed
strcpy(act,"SHIFT");
// This will print Labels (column name)
printf("\nstack \t input \t action");
// This will print the initial
// values of stack and input
printf("\n$\t%s$\t", a);
// This will Run upto length of input string
for(i = 0; j < c; i++, j++)
{
// Printing action
printf("%s", act);
// Pushing into stack
stk[i] = a[j];
stk[i + 1] = '\0';
// Moving the pointer
a[j]=' ';
// Printing action
printf("\n$%s\t%s$\t", stk, a);
// Call check function ..which will
// check the stack whether its contain
// any production or not
check();
}
// Rechecking last time if contain
// any valid production then it will
// replace otherwise invalid
check();
// if top of the stack is E(starting symbol)
// then it will accept the input
if(stk[0] == 'E' && stk[1] == '\0')
printf("Accept\n");
else //else reject
printf("Reject\n");
}
// This code is contributed by Ritesh Aggarwal
Producción –
GRAMMAR is - E->2E2 E->3E3 E->4 stack input action $ 32423$ SHIFT $3 2423$ SHIFT $32 423$ SHIFT $324 23$ REDUCE TO E -> 4 $32E 23$ SHIFT $32E2 3$ REDUCE TO E -> 2E2 $3E 3$ SHIFT $3E3 $ REDUCE TO E -> 3E3 $E $ Accept