1. Experiment content and requirements
- First read the grammar to be analyzed from the keyboard, and the program automatically constructs the FIRST, FOLLOW set and SELECT set to judge whether it is LL (1) grammar.
The parsed grammar is G[E]:
(0)E→TE’
(1) E’ → +TE’
(2) E’→ε
(3) T → FT’
(4) T’→ *FT’
(5) T’→ε
(6) F → (E)
(7) F→a
- If it conforms to the LL (1) grammar, the program automatically constructs the LL (1) analysis table;
- The algorithm judges whether the given input symbol string a*(a + a) is a sentence pattern of the grammar.
2. Experiment code
#include<iostream>
#include <stdio.h>
#include <vector>
#include<string>
#include <stack>
#include <map>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <bits/ios_base.h>
using namespace std;
map<char,int>getnum;
vector<char>getzf;
vector<string>proce(10);
vector<string>first(20);
vector<string>follow(20);
int table[100][100]; //Forecast analysis table
int num;
int numv;//number of terminators -1
char j[2];
//Read terminals, non-terminals and productions
void read()
{
char c;
int i=0;
int n=0;
cout<<"******************************LL(1) syntax analysis******** *******************"<<endl;
cout<<"Note: E' is replaced by H, T' is replaced by J, and the empty string is replaced by @"<<endl;
cout<<"Please enter a set of productions (empty is represented by '@'), enter a new line after a production, and finally end with 'end':"<<endl;
string ss;
string dd;
int j=0;
int y=0;
while(cin>>ss & &ss!="end")
{
dd. clear();
dd + =ss[0];
process[j] + =dd;
for(i=3;i<ss. length();i ++ )
{
if(ss[i]!='|'){
dd. clear();
dd + =ss[i];
process[j] + =dd;
}
else {
dd. clear();
dd + =ss[0];
dd + =ss[ + + i];
proce[ + + j] + =dd;
}
}
j + + ;
}
getnum['#']=0;//# represents the end sign
// getzf[0]='#'; It is wrong to input like this when the size of the array is not defined
getzf.push_back('#');
// terminator push
for(int i=0;i<proce. size();i ++ )
{
for(int k=0;k<proce[i].length();k ++ )
{
if(proce[i][k]!='-' & amp; & amp;proce[i][k]!='|')
{
if(proce[i][k]<64||proce[i][k]>90)
{
for( y=0;y<getzf. size();y++ ){
if(proce[i][k]==getzf[y])
break;
}
if(y==getzf.size() & amp; & amp;k!=2){//Let k!=2 here is not to let the third position> enter
getnum[proce[i][k]] = + + n;
getzf.push_back(proce[i][k]);
}
}
}
}
}
getnum['@'] = + + n;
numv=n;//The number of terminators is equal to the current value of n
getzf.push_back('@');
// non-terminal push stack
for(int i=0;i<proce. size();i ++ )
{
for(int k=0;k<proce[i].length();k ++ )
{
if(proce[i][k]!='-' & amp; & amp;proce[i][k]!='|' & amp; & amp;proce[i][k]! ='>')
{
if(proce[i][k]>64 & amp; & amp;proce[i][k]<91)
{
for( y=0;y<getzf. size();y++ ){
if(proce[i][k]==getzf[y])
break;
}
if(y==getzf. size()){
getnum[proce[i][k]] = + + n;
num=n;//The number of terminals plus non-terminals is equal to the current value of i
getzf.push_back(proce[i][k]);
}
}
}
}
}
}
//Assign a value to the first array of the terminal
void get_firstT()
{
int i;//cannot be int below
//First assign a value to the first array of the terminal
for( i=1;i<=numv;i ++ )
{
itoa(i,j,10);
first[i]=j;//It is wrong to write first[i].push_back(j[0]) before, the input of the string array does not need to be subscripted, and if it is j[0], a character cannot into a string
}
}
//Assign a value to the first array of non-terminals
string get_firstF(int *a)
{//I made a mistake, the following a is not added*
for(int i=0;i<proce. size();i ++ )
{
if(getnum[proce[i][0]]==*a)
{
if(getnum[proce[i][1]]<=numv)
{
itoa(getnum[proce[i][1]],j,10);
first[*a] + =j;
}
else
{
//first[getnum[proce[i][0]]].clear();
first[getnum[proce[i][0]]]=get_firstF( & amp;getnum[proce[i][1]]);
}
}
}
return first[*a];
}
//seek follow set
void get_follow(int *a){
// made a mistake, started with stirng but did not return a value
int i,j1;
int flag=0;
for(i=0;i<proce. size();i ++ )
{
for(j1=1;j1<proce[i].length();j1++)
{
if(getnum[proce[i][j1]]==*a)//This place should be j1, I wrote k
{
if(j1==proce[i].length()-1)
{
if(getnum[proce[i][j1]]!=getnum[proce[i][0]])
follow[*a] + =follow[getnum[proce[i][0]]];
}
else
{
if(getnum[proce[i][j1 + 1]]<=numv)
{
itoa(getnum[proce[i][j1+1]],j,10);
follow[*a] + =j;
}
else
{
for(int jj=0;jj<first[getnum[proce[i][j1 + 1]]].size();jj++ )
{
if(atoi( & amp;first[getnum[proce[i][j1 + 1]]][jj])==numv)//equal to empty
follow[*a] + =follow[getnum[proce[i][0]]];
else
follow[*a] + =first[getnum[proce[i][j1 + 1]]][jj];
}
flag=1;//flag bit, if you have found the non-terminal after *a, you can stop
}
}
}
}
\t\t
if(flag==1) break; //stop searching
}
}
//Seek forecast analysis table
void get_table()
{
memset(table,-1,sizeof(table));//tableM was not initialized at the beginning, resulting in E->TA where it should be a space
for(int i=0;i<proce.size();i + + ) //sweep all productions
{
if(proce[i][1]=='@') //If you directly launch an empty word, you will be judged (follow set = fill in the elements in vn on the left side of the production)
{
string flw=follow[getnum[proce[i][0]]];
for(int k=0;k<flw. size();k++)
{
table[getnum[proce[i][0]]][flw[k]-'0']=i;
}
}
string temps=first[getnum[proce[i][1]]];
for(int j=0;j<temps.size();j ++ ) //examine the first set
{
if(atoi( &temps[j])!=numv)
{
// table[getnum[proce[i][0]]][atoi( & amp;temps[j])]=i;//atoi cannot be used in this way, it means from the current position to the last position
table[getnum[proce[i][0]]][temps[j]-'0']=i;
}
else //If there are empty words, check the follw set
{
string flw=follow[getnum[proce[i][1]]];
for(int k=0;k<flw. size();k++)
{
table[getnum[proce[i][0]]][flw[k]-'0']=i;
}
}
}
}
}
// Obtain the corresponding production from the corresponding subscript
string get_proce(int i)
{
if(i<0)return " "; //no such production
string ss;
ss + =proce[i][0];
ss + ="->"; // put -> to add
for(int j=1;j<proce[i].size();j++)
ss + =proce[i][j];
return ss;
}
//Output forecast analysis table
void print_table()
{
cout<<"The predictive analysis table corresponding to this grammar is as follows:"<<endl;
cout<<"________________________________________________________"<<endl;
for(int i=0;i<numv;i++)
cout<<'\t'<<getzf[i];
cout<<endl;
for(int i=numv + 1;i<=num;i + + )
{
cout<<endl<<"________________________________________________________"<<endl;
cout<<getzf[i];
for(int j=0;j<numv;j++)
{
cout<<'\t'<<get_proce(table[i][j])<<"";
}
}
cout<<endl<<"________________________________________________________"<<endl;
cout<<endl;
}
// print the elements in the stack
void print_stack(stack<char>sta){
int length=sta.size();//Number of elements in the stack
vector<char>temp;
for(int i=0;i<length;i + + ){
//cout<<sta.top();
temp.push_back(sta.top());
sta. pop();
}
for(int j=length-1;j>=0;j--){
cout<<temp[j];
\t\t
}
cout<<"\t\t";
}
//Print the current element of the judgment string
void print_string(string str, int index){
int length = str. size();
for(int i=index;i<length;i++){
cout<<str[i];
}
cout<<'#';
cout<<"\t\t";
}
//Analyze the legitimacy of the word symbol string (key)
string word;
bool analyze()
{
stack<char>sta;//Analysis stack
sta.push('#'); //#Most advanced stack
sta.push(proce[0][0]);//Press the start symbol into the analysis stack for initialization
int i=0;
int count=1;//step count
printf("step\t\tanalysis stack\t\tjudgment string\t\tuse rules\\
");//header
while(!sta. empty())
{
cout<<count<<"\t\t";
print_stack(sta);//print the current analysis stack
print_string(word,i);//print the current judgment string
int cur=sta.top();//Take out the top element of the analysis stack
sta. pop();
if(cur==word[i]) //If the top element of the analysis stack is the same as the first element of the judgment string (that is, if it is a terminal symbol), the match is successful, and the analysis stack pops the top element
{
i + + ;
printf("Match out of the stack\\
");
}
else if(cur=='#') //If the top element of the analysis stack is #, the surface analysis ends
{
return 1;
}
else if(table[getnum[cur]][getnum[word[i]]]!=-1) //Find the corresponding predictive analysis table
{
int k=table[getnum[cur]][getnum[word[i]]];
cout<<proce[k][0]<<"->";
for(int j=1;j<proce[k].size();j++)
cout<<proce[k][j];
cout<<endl;
//Add the used production to the analysis stack in reverse order to replace the last popped element
for(int j=proce[k].size()-1;j>0;j--)
{ if(proce[k][j]!='@')
sta.push(proce[k][j]);
}
}
else
{
return 0;
}
count + + ;
}
return 1;
}
//Enter the symbol string to be judged
void scanf()
{
cout<<"Please enter the symbol string to be judged:";
cin>>word;
cout<<"The judgment analysis table is as follows:"<<endl;
if(analyze())
cout<<endl<<"To sum up: the symbol string is valid, it is the sentence pattern of the grammar!"<<endl;
else
cout<<endl<<"Error, the symbol string is not a sentence pattern of the grammar!"<<endl;
}
int main()
{
int k;
int j;
read();
// first set of terminal symbols
get_firstT();
// first set of non-terminals
for(k=numv + 1;k<=num;k + + ) // made a mistake, the position of numv is written as 7
{
get_firstF( &k);
}
follow[numv + 1] + ='0'; //This place adds 0 instead of #
for(k=numv + 1;k<=num;k + + ) // made a mistake, the position of numv is written as 7
{
get_follow( &k);
}
cout<<endl;
get_table();
print_table();
scanf();
return 0;
}
/*Test Data:
Note: E' is replaced by H, T' is replaced by J, and the empty string is replaced by @
E->TH
H->+TH
H->@
T->FJ
J->*FJ
J->@
F->(E)
F->a
end
*/
3. Experimental results
END.< /em>