First, a wave of theory (from the Compilation Principles book)

We will construct a Boolean array F[P,a] such that F[P,a] is true if and only if a∈FIRSTVT(P).

To start, assign an initial value to each array element F[P,a] as described above (1). We use a STACK to place all the symbol pairs (P,a) of the array elements F[P,a] whose initial values are true in the STACK.

Then, perform the following operation on the STACK:

If the STACK is not empty, the top item is ejected, called (Q,a). For every P->Q… If F[P.a] is false, change its value to heavy and push (P,a) onto the STACK.

This process must be repeated until the STACK is empty.

Take a look at the pseudo-code implemented using stacks

Finally, code!

``````#include <bits/stdc++.h>
using namespace std;

const int Max = 40;

int num; // Number of grammar rules
char str[Max][Max];// Grammar rules
bool F[Max][Max] = {0};//FIRSTVT Boolean array
bool L[Max][Max] = {0};// Boolean array of LASTVT
char terminal[Max];// Array of terminators
int k = 0;// Record the number of terminators
char notTerminal[Max];// Non-terminal array
typedef struct real_f// The element inside the Boolean array {
/* data */
char NT;    // Corresponding non-terminal
char T;     // Corresponding terminator
}real_f;

stack<real_f *> stack1;/ / stack

// Determine if a character is a terminator
bool isTer(char ch){
for(int i = 0; terminal[i] ! ='\ 0'; i ++){if(terminal[i] == ch){
return true; // Returns true if it is the terminator}}return false;
}

// Computes the position of the terminator in the array to facilitate the stack and subsequent table listing
int findTer(char ch){
for(int i = 0; terminal[i] ! ='\ 0'; i ++){if(terminal[i] == ch){
return i;// Returns the position of the terminator}}return - 1;// Return -1 if not found
}

// Push operation
void inStack(int ntsite,int tsite,char flag){
if(flag == 'f') {if(! F[ntsite][tsite]){ F[ntsite][tsite] =1;/ / 1
real_f *node = (real_f*)malloc(sizeof(real_f));
node->NT = notTerminal[ntsite];
node->T = terminal[tsite];
stack1.push(node);// push into the stack}}else if(flag == 'l') {if(! L[ntsite][tsite]){ L[ntsite][tsite] =1;
real_f *node = (real_f*)malloc(sizeof(real_f));
node->NT = notTerminal[ntsite];
node->T = terminal[tsite];
stack1.push(node); }}}/ / FIRSTVT calculation
void calFITSRVT(a){
// Assign an initial value of 1 to each Boolean array element and stack it according to rule (1)
for(int i = 0; i < num; i ++){for(int j = 0; str[i][j] ! ='\ 0'; j ++){if(j == 2 || str[i][j] == '|') {if(isTer(str[i][j + 1])){ P->a...
inStack(i,findTer(str[i][j + 1]),'f');
}
else if(isTer(str[i][j + 2])){ // P->Qa...
inStack(i,findTer(str[i][j + 2]),'f'); }}}}// Then start working on the stack
while(! stack1.empty())
{
real_f *topnode = stack1.top(a);//cout<<topnode->NT<<" "<<topnode->T<<endl;
stack1.pop(a);for(int i = 0; i < num; i ++){for(int j = 0; str[i][j] ! ='\ 0'; j ++){//cout<<" << STR [I]<
if(j == 2 || str[i][j] == '|') {if(topnode->NT == str[i][j + 1]) {// P->Q...
//cout<<" matching P->Q... << STR [I]<
inStack(i,findTer(topnode->T),'f');
}
}
}
}
}

cout<<"FIRSTVT Boolean array element is :"<<endl;
cout<<"";
for(int i = 0; i < k; i ++){ cout<<""<<terminal[i];
}
cout<<endl;
for(int i = 0; i < num; i ++){ cout<<notTerminal[i]<<"";
for(int j = 0; j < k; j ++){ cout<<F[i][j]<<"";
}
cout<<endl;
}

cout<<"The set of FIRSTVT for each non-terminal is :"<<endl;
int last = k - 1;
for(int i = 0; i < num; i ++){ last = k -1;
cout<<"FIRSTVT("<<str[i][0] < <") = {";
// Find the last corresponding terminator
while (F[i][last] == 0)
{
last --;
}
for(int j = 0; j < k; j ++){if(F[i][j] == 1) {if(j == last){
cout<<terminal[j]<<"}";
break;
}
cout<<terminal[j]<<"、"; } } cout<<endl; }}/ / LASTVT calculation
void calLASTVT(a){
// Assign an initial value of 1 to each Boolean array element and stack it according to rule (1)
for(int i = 0; i < num; i ++){// You need to know the length of the grammar first, and then look for it from the back
int len = strlen(str[i]);
for(intj = len; str[i][j] ! ='>'; j --){if(j == len || str[i][j] == '|') {if(isTer(str[i][j - 1])){// P->... a
inStack(i,findTer(str[i][j - 1]),'l');
}
else if(isTer(str[i][j - 2])){// P->... aQ
inStack(i,findTer(str[i][j - 2]),'l'); }}}}// Then start working on the stack
while(! stack1.empty())
{
real_f *topnode = stack1.top(a);//cout<<topnode->NT<<" "<<topnode->T<<endl;
stack1.pop(a);for(int i = 0; i < num; i ++){int len = strlen(str[i]);
for(intj = len; str[i][j] ! ='>'; j --){if(j == len || str[i][j] == '|') {if(topnode->NT == str[i][j - 1]) {inStack(i,findTer(topnode->T),'l');
}
}
}
}
}

cout<<"The value of the LASTVT Boolean element is :"<<endl;
cout<<"";
for(int i = 0; i < k; i ++){ cout<<""<<terminal[i];
}
cout<<endl;
for(int i = 0; i < num; i ++){ cout<<notTerminal[i]<<"";
for(int j = 0; j < k; j ++){ cout<<L[i][j]<<"";
}
cout<<endl;
}

cout<<"The LASTVT set for each non-terminal is :"<<endl;
int last = k - 1;
for(int i = 0; i < num; i ++){ last = k -1;
cout<<"LASTVT("<<str[i][0] < <") = {";
// Find the last corresponding terminator
while(! L[i][last]) { last --; }for(int j = 0; j < k; j ++){if(L[i][j] == 1) {if(j == last){
cout<<terminal[j]<<"}";
break;
}
cout<<terminal[j]<<"、"; } } cout<<endl; }}int main(a){
cout<<"Please enter the number of grammar rules :";
cin>>num;
cout<<"Please enter grammar rules :"<<endl;
for(int i = 0; i < num; i ++){ cin>>str[i]; notTerminal[i] = str[i][0];// The first symbol must be non-terminal, extract it
}
// Extract the terminator
for(int i = 0; i < num; i ++){for(int j = 0; str[i][j] ! ='\ 0'; j ++){if((str[i][j] < 'A' || str[i][j] > 'Z') && str[i][j] ! =The '-'&& str[i][j] ! ='>'&& str[i][j] ! ='|'){
terminal[k ++] = str[i][j];
}
}
}
cout<<"The terminators in this rule are :";
for(int i = 0; i < k; i ++){ cout<<terminal[i]<<"";
}
cout<<endl;

cout<<"The non-terminal characters in this rule are :";
for(int i = 0; i < num; i ++){ cout<<notTerminal[i]<<"";
}
cout<<endl;

calFITSRVT(a);calLASTVT(a);return 0;
}
Example 1: / * S - > a | ^ | (T) T - > T, S | S example 2: S - > aAcBe a - - > b > Ab | b d * /
Copy the code``````

The result of example 1:

If there is any mistake, please correct it