编译原理之LL(1)语法分析实验（附完整C/C++代码与测试）

心中带点小风骚
11 月前
Table of Contents
一、实验内容与要求

先从键盘读入要分析的文法，由程序自动构造FIRST、FOLLOW 集以及SELECT集合，判断是否为LL (1)文法。
分析文法为G[E]：
（0）E→ TE’
（1）E’→ +TE’
（2）E’→ε
（3）T→ FT’
（4）T’→ *FT’
（5）T’→ε
（6）F→ (E)
（7）F→a
若符合LL (1)文法，由程序自动构造LL (1)分析表;
由算法判断给定的输入符号串a*(a+a)是否为该文法的句型。
二、实验代码

#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];      //预测分析表
int num;
int numv;//终结符的数量-1
char j[2];

//读取终结符、非终结符与产生式 
void  read()
{
	char c;
	int i=0;
	int n=0;
	cout<<"******************************LL(1)语法分析****************************"<<endl; 
	cout<<"注意：E'用H代替，T‘用J代替，空串用@代替 "<<endl;
	cout<<"请输入产生式的集合（空用'@'表示）,输入一条产生式后换行，最后以'end'结束:"<<endl;
	string ss;
	string dd;
	int j=0;
	int y=0;
	while(cin>>ss&&ss!="end")
	{		 
		dd.clear();
		dd+=ss[0];
		proce[j]+=dd;
		for(i=3;i<ss.length();i++)
		{	
			if(ss[i]!='|'){
				dd.clear();
				dd+=ss[i];
				proce[j]+=dd;
		    } 
			else{
			dd.clear();
			dd+=ss[0];
			dd+=ss[++i];
			proce[++j]+=dd;
		}	
	}
	j++;
}
getnum['#']=0;//#代表结束标志 
//	getzf[0]='#';没有定义数组大小的时候这样输入是错误的 
getzf.push_back('#');
//终结符压栈 
for(int i=0;i<proce.size();i++)
{
	for(int k=0;k<proce[i].length();k++)
	{
		if(proce[i][k]!='-'&&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()&&k!=2){//这里让k!=2是不让第三位置的>进去 
				 getnum[proce[i][k]]=++n;
				 getzf.push_back(proce[i][k]);
				}
			}
		}	  
	}
}
 getnum['@']=++n;
 numv=n;//终结符的数量等于当前n的值 
 getzf.push_back('@');
 //非终结符压栈 
	for(int i=0;i<proce.size();i++)
	{
		for(int k=0;k<proce[i].length();k++)
		{
			if(proce[i][k]!='-'&&proce[i][k]!='|'&&proce[i][k]!='>')
			{
				if(proce[i][k]>64&&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;//终结符加非终结符的数量等于当前i的值 
					 getzf.push_back(proce[i][k]);
					}
				}
			}	  
		}
	}
}

//给终结符的first数组赋值
void get_firstT()
{
	int i;//不能在下面int 
	//先给终结符的first数组赋值
	for( i=1;i<=numv;i++) 
	{
			itoa(i,j,10);
    		first[i]=j;//之前写的是first[i].push_back(j[0])是错的，字符串数组的输入不需要加下标,且如果是j[0]一个字符不能装到一个字符串当中去 
	}
}

//给非终结符的first数组赋值
string get_firstF(int *a)
{//犯了一个错误，下面的a没有加* 
	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(&getnum[proce[i][1]]);
			}
	} 	
	}
	return first[*a]; 
} 

//求follow集 
void  get_follow(int *a){
//犯了一个错误，以stirng开头但是没有返回值 
	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)//这地方应该是j1我写成了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(&first[getnum[proce[i][j1+1]]][jj])==numv)//等于空时
						follow[*a]+=follow[getnum[proce[i][0]]];
						else
						follow[*a]+=first[getnum[proce[i][j1+1]]][jj];
					}
					flag=1;//标志位，如果已经找到*a后面的非终结符就可以停止了 
			}
		}
		}
		 } 
		 
		 	if(flag==1) break; //停止寻找 
	}
}


//求预测分析表
void get_table()          
{
	memset(table,-1,sizeof(table));//刚开始tableM没有初始化，导致本该是空格的地方出现E->TA 
   for(int i=0;i<proce.size();i++)   //扫所有产生式
   {
       if(proce[i][1]=='@')     //直接推出空字的，特判下（follow集=产生式左边的vn中元素填）
          {
             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++)               //考察first集
       {
       	if(atoi(&temps[j])!=numv) 
       	{
               // table[getnum[proce[i][0]]][atoi(&temps[j])]=i;//atoi不能这么用，他表示的是从当前位一直到末位 
              table[getnum[proce[i][0]]][temps[j]-'0']=i;
           }
           else                                     //有空字的，考察follw集
           {
               string flw=follow[getnum[proce[i][1]]];
              for(int k=0;k<flw.size();k++)
             {
                 table[getnum[proce[i][0]]][flw[k]-'0']=i;
             }
           }
       }
   }
}

//由对应下标获得对应产生式
string get_proce(int i) 
{
    if(i<0)return " ";    //无该产生式
    string ss;
    ss+=proce[i][0];
    ss+="->";		//把->要加上 
    for(int j=1;j<proce[i].size();j++)
       ss+=proce[i][j];
   return ss;
}

//输出预测分析表 
void print_table()
{
    cout<<"该文法对应的预测分析表如下："<<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;
}

//打印栈中元素
void print_stack(stack<char>sta){
	int length=sta.size();//栈中元素数目
	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];
		
	}
	cout<<"\t\t";
} 

//打印判定串的当前元素
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";
}


//分析word符号串的合法性(关键)
string word;
bool analyze()       
{
    stack<char>sta;//分析栈 
    sta.push('#');  //#最先进栈 
	sta.push(proce[0][0]);//将开始符压入分析栈中进行初始化 
    int i=0;
	int count=1;//步骤计数  
    printf("步骤\t\t分析栈\t\t判定串\t\t使用规则\n");//表头 
    while(!sta.empty())
    {
       cout<<count<<"\t\t";
       print_stack(sta);//打印当前分析栈 
       print_string(word,i);//打印当前判定串 
       int cur=sta.top();//取出分析栈的栈顶元素 
       sta.pop();
       if(cur==word[i])       //如果分析栈的栈顶元素与判定串的第一个元素相同（即是终结符的话），则匹配成功，分析栈弹出栈顶元素 
       {
           i++;
           printf("匹配出栈\n");
       }
       else  if(cur=='#')   //如果分析栈的栈顶元素为#则表面分析结束
       {
           return 1;
       }
       else  if(table[getnum[cur]][getnum[word[i]]]!=-1) //查找对应的预测分析表 
       {
 
           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;
           //将使用的产生式逆序加入分析栈中，以取代上一个出栈的元素 
           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;
}


//输入待判断的符号串 
void scanf()  
{
	cout<<"请输入待判定的符号串：";
    cin>>word;
    cout<<"判断分析表如下："<<endl; 
    if(analyze())
        cout<<endl<<"综上：该符号串有效，是该文法的句型！"<<endl;
    else   
		cout<<endl<<"出错，该符号串不是该文法的句型！"<<endl;
}


int main()
{
	int k;
	int j;
	read();
	//终结符的first集 
	get_firstT();
	//非终结符的first集 
	for(k=numv+1;k<=num;k++) //犯了一个错误，numv的位置写成7 
	{
		get_firstF(&k);
	}

		follow[numv+1]+='0'; //这地方加的是0而不是# 
		for(k=numv+1;k<=num;k++) //犯了一个错误，numv的位置写成7 
	{
		 get_follow(&k);
	}
     cout<<endl;  
     get_table();
     print_table();
     scanf();	
     return 0;
}
/*测试数据： 
注意：E'用H代替，T‘用J代替，空串用@代替 
E->TH
H->+TH
H->@
T->FJ
J->*FJ
J->@
F->(E)
F->a
end
*/
三、实验结果

END.
文章出处登录后可见！
已经登录？立即刷新
一、实验内容与要求

二、实验代码

三、实验结果

<img src="https://aitechtogether.com/wp-content/uploads_new/2023/12/b3022632-69a1-44c2-b409-2bd141176706.webp" alt="87d6fee48cbc499c8891fd72cefb43c5.png" height="605" width="818">
