Antes de continuar, se recomienda encarecidamente familiarizarse con los conceptos básicos del análisis de sintaxis, el análisis sintáctico LL(1) y las reglas para calcular los conjuntos Primero y Siguiente de una gramática.
- Introducción al análisis de sintaxis
- ¿Por qué Primero y Seguir?
- FIRST Conjunto en análisis de sintaxis
- SEGUIR establecido en análisis de sintaxis
Suponiendo que el lector esté familiarizado con los conceptos básicos discutidos anteriormente, comencemos a discutir cómo implementar el programa C para calcular el primero y el siguiente de la gramática dada.
Ejemplo :
Input :
E -> TR
R -> +T R| #
T -> F Y
Y -> *F Y | #
F -> (E) | i
Output :
First(E)= { (, i, }
First(R)= { +, #, }
First(T)= { (, i, }
First(Y)= { *, #, }
First(F)= { (, i, }
-----------------------------------------------
Follow(E) = { $, ), }
Follow(R) = { $, ), }
Follow(T) = { +, $, ), }
Follow(Y) = { +, $, ), }
Follow(F) = { *, +, $, ), }
Las funciones seguir y seguir primero están ambas involucradas en el cálculo del Conjunto de Seguimiento de un No-Terminal dado. El conjunto de seguimiento del símbolo de inicio siempre contendrá «$». Ahora, el cálculo de Follow se divide en tres casos amplios:
- Si un No-Terminal en el RHS de cualquier producción es seguido inmediatamente por un Terminal, entonces puede ser incluido inmediatamente en el conjunto Seguir de ese No-Terminal.
- Si un No-Terminal en el RHS de cualquier producción es seguido inmediatamente por un No-Terminal, entonces el Primer Conjunto de ese nuevo No-Terminal se incluye en el siguiente conjunto de nuestro No-Terminal original. En caso de que encuentre un épsilon, es decir, ” # ”, pase al siguiente símbolo en la producción.
Nota: “#” nunca se incluye en el conjunto Seguir de ningún No terminal. - Si se llega al final de una producción mientras se calcula el seguimiento, el conjunto de seguimiento de ese no terminal incluirá el conjunto de seguimiento del no terminal en el LHS de esa producción. Esto se puede implementar fácilmente mediante recursividad.
Suposiciones:
- Epsilon está representado por ‘#’.
- Las producciones son de la forma A=B, donde ‘A’ es un único No-Terminal y ‘B’ puede ser cualquier combinación de Terminales y No-Terminales.
- LHS de la primera regla de producción es el símbolo de inicio.
- La gramática no se deja recursiva.
- Cada producción de un no terminal se ingresa en una línea diferente.
- Solo las letras mayúsculas son no terminales y todo lo demás es una terminal.
- No utilice ‘!’ o ‘$’ ya que están reservados para propósitos especiales.
Explicación: almacene la gramática en una producción
de array de caracteres 2D . La función findfirst es para calcular el primero de cualquier no terminal. Cálculo de las primeras caídas en dos casos amplios:
- Si el primer símbolo en el RHS de la producción es una Terminal, entonces se puede incluir directamente en el primer conjunto.
- Si el primer símbolo en el lado derecho de la producción es un no terminal, vuelva a llamar a la función findfirst en ese no terminal. Manejar estos casos como Recursion es la mejor solución posible. Nuevamente aquí, si el Primero del nuevo No-Terminal contiene un épsilon entonces tenemos que pasar al siguiente símbolo de la producción original que puede ser nuevamente un Terminal o un No-Terminal.
Nota: Para el segundo caso, es muy fácil caer en un BUCLE INFINITO incluso si el código parece perfecto. Por lo tanto, es importante realizar un seguimiento de todas las llamadas a funciones en todo momento y nunca volver a llamar a la misma función.
A continuación se muestra la implementación:
C
// C program to calculate the First and
// Follow sets of a given grammar
#include<stdio.h>
#include<ctype.h>
#include<string.h>
// Functions to calculate Follow
void followfirst(char, int, int);
void follow(char c);
// Function to calculate First
void findfirst(char, int, int);
int count, n = 0;
// Stores the final result
// of the First Sets
char calc_first[10][100];
// Stores the final result
// of the Follow Sets
char calc_follow[10][100];
int m = 0;
// Stores the production rules
char production[10][10];
char f[10], first[10];
int k;
char ck;
int e;
int main(int argc, char **argv)
{
int jm = 0;
int km = 0;
int i, choice;
char c, ch;
count = 8;
// The Input grammar
strcpy(production[0], "E=TR");
strcpy(production[1], "R=+TR");
strcpy(production[2], "R=#");
strcpy(production[3], "T=FY");
strcpy(production[4], "Y=*FY");
strcpy(production[5], "Y=#");
strcpy(production[6], "F=(E)");
strcpy(production[7], "F=i");
int kay;
char done[count];
int ptr = -1;
// Initializing the calc_first array
for(k = 0; k < count; k++) {
for(kay = 0; kay < 100; kay++) {
calc_first[k][kay] = '!';
}
}
int point1 = 0, point2, xxx;
for(k = 0; k < count; k++)
{
c = production[k][0];
point2 = 0;
xxx = 0;
// Checking if First of c has
// already been calculated
for(kay = 0; kay <= ptr; kay++)
if(c == done[kay])
xxx = 1;
if (xxx == 1)
continue;
// Function call
findfirst(c, 0, 0);
ptr += 1;
// Adding c to the calculated list
done[ptr] = c;
printf("\n First(%c) = { ", c);
calc_first[point1][point2++] = c;
// Printing the First Sets of the grammar
for(i = 0 + jm; i < n; i++) {
int lark = 0, chk = 0;
for(lark = 0; lark < point2; lark++) {
if (first[i] == calc_first[point1][lark])
{
chk = 1;
break;
}
}
if(chk == 0)
{
printf("%c, ", first[i]);
calc_first[point1][point2++] = first[i];
}
}
printf("}\n");
jm = n;
point1++;
}
printf("\n");
printf("-----------------------------------------------\n\n");
char donee[count];
ptr = -1;
// Initializing the calc_follow array
for(k = 0; k < count; k++) {
for(kay = 0; kay < 100; kay++) {
calc_follow[k][kay] = '!';
}
}
point1 = 0;
int land = 0;
for(e = 0; e < count; e++)
{
ck = production[e][0];
point2 = 0;
xxx = 0;
// Checking if Follow of ck
// has already been calculated
for(kay = 0; kay <= ptr; kay++)
if(ck == donee[kay])
xxx = 1;
if (xxx == 1)
continue;
land += 1;
// Function call
follow(ck);
ptr += 1;
// Adding ck to the calculated list
donee[ptr] = ck;
printf(" Follow(%c) = { ", ck);
calc_follow[point1][point2++] = ck;
// Printing the Follow Sets of the grammar
for(i = 0 + km; i < m; i++) {
int lark = 0, chk = 0;
for(lark = 0; lark < point2; lark++)
{
if (f[i] == calc_follow[point1][lark])
{
chk = 1;
break;
}
}
if(chk == 0)
{
printf("%c, ", f[i]);
calc_follow[point1][point2++] = f[i];
}
}
printf(" }\n\n");
km = m;
point1++;
}
}
void follow(char c)
{
int i, j;
// Adding "$" to the follow
// set of the start symbol
if(production[0][0] == c) {
f[m++] = '$';
}
for(i = 0; i < 10; i++)
{
for(j = 2;j < 10; j++)
{
if(production[i][j] == c)
{
if(production[i][j+1] != '\0')
{
// Calculate the first of the next
// Non-Terminal in the production
followfirst(production[i][j+1], i, (j+2));
}
if(production[i][j+1]=='\0' && c!=production[i][0])
{
// Calculate the follow of the Non-Terminal
// in the L.H.S. of the production
follow(production[i][0]);
}
}
}
}
}
void findfirst(char c, int q1, int q2)
{
int j;
// The case where we
// encounter a Terminal
if(!(isupper(c))) {
first[n++] = c;
}
for(j = 0; j < count; j++)
{
if(production[j][0] == c)
{
if(production[j][2] == '#')
{
if(production[q1][q2] == '\0')
first[n++] = '#';
else if(production[q1][q2] != '\0'
&& (q1 != 0 || q2 != 0))
{
// Recursion to calculate First of New
// Non-Terminal we encounter after epsilon
findfirst(production[q1][q2], q1, (q2+1));
}
else
first[n++] = '#';
}
else if(!isupper(production[j][2]))
{
first[n++] = production[j][2];
}
else
{
// Recursion to calculate First of
// New Non-Terminal we encounter
// at the beginning
findfirst(production[j][2], j, 3);
}
}
}
}
void followfirst(char c, int c1, int c2)
{
int k;
// The case where we encounter
// a Terminal
if(!(isupper(c)))
f[m++] = c;
else
{
int i = 0, j = 1;
for(i = 0; i < count; i++)
{
if(calc_first[i][0] == c)
break;
}
//Including the First set of the
// Non-Terminal in the Follow of
// the original query
while(calc_first[i][j] != '!')
{
if(calc_first[i][j] != '#')
{
f[m++] = calc_first[i][j];
}
else
{
if(production[c1][c2] == '\0')
{
// Case where we reach the
// end of a production
follow(production[c1][0]);
}
else
{
// Recursion to the next symbol
// in case we encounter a "#"
followfirst(production[c1][c2], c1, c2+1);
}
}
j++;
}
}
}
Producción :
First(E)= { (, i, }
First(R)= { +, #, }
First(T)= { (, i, }
First(Y)= { *, #, }
First(F)= { (, i, }
-----------------------------------------------
Follow(E) = { $, ), }
Follow(R) = { $, ), }
Follow(T) = { +, $, ), }
Follow(Y) = { +, $, ), }
Follow(F) = { *, +, $, ), }
Publicación traducida automáticamente
Artículo escrito por Siddhant-Bajaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA