一個c++撰寫的語法分析器(編譯愿意LL(1)文法)

1 輸入任意文法，改寫文法使其成為LL(1)文法，
1.1 由于老師給的應該是最適合我們聯系的LL（1）文法，所以說我也是用以下文法進行分析，
E→E+T | T
T→T*F | F
F→( E ) | i
注意e在此表示‘’，也就是空，表示沒有任何字符輸入，
1.2 消除左遞回
? E--------?TE’
? E’----------?+TE’|e
? T ------------?FT’
? T’---------------*FT’|e
? F------------------?(E)|i
1.3 消除回溯
1.3.1 FIRST和FALLOW集合

1.3.2 判斷
FIRST(E’)∩FOLLOW(E’)= 空集
FIRST(T’)∩FOLLOW(T’)=空集

所以上述文法式LL(1)文法

2 構造文法的預測分析表；

3 設計堆疊和預測分析表的機內表示
我將會使用MAP作為機內表示的資料結構
? ///E’,T’分別表示為e,t
? //~表示空，也就是 無輸入

map<pair<string,string>,string> forecast;
void fore_init()
{
forecast[pair<string,string>(“E”,“i”)]=“Te”;
forecast[pair<string,string>(“T”,“i”)]=“Ft”;
forecast[pair<string,string>(“F”,“i”)]=“i”;
forecast[pair<string,string>(“e”,"+")]="+Te";
forecast[pair<string,string>(“t”,"+")]="~";
forecast[pair<string,string>(“t”,"*")]="*Ft";
forecast[pair<string,string>(“E”,"(")]=“Te”;
forecast[pair<string,string>(“T”,"(")]=“Ft”;
forecast[pair<string,string>(“F”,"(")]="(E)";
forecast[pair<string,string>(“e”,")")]="~";
forecast[pair<string,string>(“t”,")")]="~";
forecast[pair<string,string>(“e”,"#")]="~";
forecast[pair<string,string>(“t”,"#")]="~";
}

4 設計并書寫語法分析程式；

```cpp
#include<iostream>
#include<map>
#include<stack> 
#include<cstring>
using namespace std;
///E',T'分別表示為e,t 
//~表示空，也就是 無輸入 ，
//這里是forecast集 
map<pair<string,string>,string> forecast;
void fore_init()
{
	forecast[pair<string,string>("E","i")]="Te";
	forecast[pair<string,string>("T","i")]="Ft";
	forecast[pair<string,string>("F","i")]="i";
	forecast[pair<string,string>("e","+")]="+Te";
	forecast[pair<string,string>("t","+")]="~";
	forecast[pair<string,string>("t","*")]="*Ft";
	forecast[pair<string,string>("E","(")]="Te";
	forecast[pair<string,string>("T","(")]="Ft";
	forecast[pair<string,string>("F","(")]="(E)";
	forecast[pair<string,string>("e",")")]="~";
	forecast[pair<string,string>("t",")")]="~";
	forecast[pair<string,string>("e","#")]="~";
	forecast[pair<string,string>("t","#")]="~";
}
void fore_insert(pair<string,string> a,string b)
{
	forecast[a]=b;
}
 ///接下來構建分析堆疊
stack<char> analysis;
void analysis_init()
{
	analysis.push('#');
	analysis.push('E');
}
///接下來構建展示函式
void show(int step,stack<char> analyse,char remaining[],string Production) 
{
	stack<char> reanalyse;
	cout<<step<<"\t\t";
	while(!analyse.empty())
	{		
	reanalyse.push(analyse.top());
	analyse.pop();
	}
	while(!reanalyse.empty())
	{		
	cout<<reanalyse.top();
	reanalyse.pop();
	}
	
	cout<<"\t\t\t"<<remaining<<"\t\t\t"<<Production<<endl;
}
這里是逆序入堆疊函式 
void reprod(string production)
{
	int i=production.length();
	for(--i;i>=0;--i)
	{
		analysis.push(production[i]);
	}
}
///接下來構建判斷函式
//輸入陣列
char in[1000];
void judge()
{
	cin>>in;
	cout<<"\n序號\t\t"<<"堆疊內字符\t\t"<<"余留字符\t\t"<<"所用產生式"<<endl; 
	int i;///這個是in的坐標，用于逐個檢驗字符 
	int j;//這個是產生時的坐標，用來逆序讀入站
	string prod;//這個用來接收產生式 
	pair<string,string> k;//這個是預測分析表的坐標
	string term,nonterm;///終結符，非終結符 
	int step;//用來記錄步驟 
	step=0;
	i=0;
	while(!analysis.empty()) 
	{
		term=analysis.top();
		nonterm=in[i];
		k.first=term;
		k.second=nonterm;
	
		if(forecast.find(k)!=forecast.end())
		{
		prod=forecast[k];///找到產生式 
		show(step,analysis,in+i,term+"->"+prod);///展示現在站內狀況
		analysis.pop();///z頂部元素出戰 
		reprod(prod);//其他元素入站 
		if(analysis.top()==in[i])//如果堆疊頂元素和正在檢驗的字符一致 
		{
				show(step,analysis,in+i,"匹配成功，出堆疊");///展示現在站內狀況	
				i++;//坐標后移 
				analysis.pop();///z頂部元素出戰	
					
		}
		else if(analysis.top()=='~')
		{
			analysis.pop();
			show(step,analysis,in+i,"空字符產生式匹配成功，出堆疊");///展示現在站內狀況
		 } 
		 else
		 {
		 	//什么都不做 
		 }
		}
		else
		{
			if(analysis.top()==in[i])//如果堆疊頂元素和正在檢驗的字符一致 
			{
				show(step,analysis,in+i,"匹配成功，出堆疊");///展示現在站內狀況
				i++;//坐標后移 
				analysis.pop();///z頂部元素出戰	
				continue;			
			}
			else if(analysis.top()=='~')//貌似沒什么用，保險一點加上了 
		    { 
			analysis.pop();
			show(step,analysis,in+i,"空字符產生式匹配成功，出堆疊");///展示現在站內狀況
		    }   
			//show(step,analysis,in+i,term+"->"+prod);///展示現在站內狀況
			cout<<"error"<<endl;
			return; 
		}
		step++; 
	}
	cout<<"acc"<<endl;
	
 } 
int main()
{
	fore_init(); //預測分析表初始化 
	analysis_init();//分析堆疊初始化 
	memset(in,0,1000);
	cout<<"E',T'分別表示為e,t,~表示空，也就是 無輸入"<<endl; 
	judge();
}

5 除錯并運行語法分析程式
5.1 測驗資料：
5.1.1 正確資料i+i*i#

5.1.2 正確資料i*i+i#

5.1.3 正確資料 無限個i+ 最后添加一個i#

5.1.4 錯誤資料iiiiii

5.1.5 非法資料i+i8i

5.2 實驗結果分析
? 分析程式中文法存盤所采用的資料結構
? pair和map資料結構
采用的資料結構是三維坐標，map<pair<string,string>,string> forecast;通過前兩個string來唯一確定出第三個tring，也就是產生式的值，
將產生時存盤到map里
forecast[pair<string,string>(“E”,“i”)]=“Te”;
forecast[pair<string,string>(“T”,“i”)]=“Ft”;
forecast[pair<string,string>(“F”,“i”)]=“i”;
forecast[pair<string,string>(“e”,"+")]="+Te";
forecast[pair<string,string>(“t”,"+")]="~";
forecast[pair<string,string>(“t”,"*")]="*Ft";
forecast[pair<string,string>(“E”,"(")]=“Te”;
forecast[pair<string,string>(“T”,"(")]=“Ft”;
forecast[pair<string,string>(“F”,"(")]="(E)";
forecast[pair<string,string>(“e”,")")]="~";
forecast[pair<string,string>(“t”,")")]="~";
forecast[pair<string,string>(“e”,"#")]="~";
forecast[pair<string,string>(“t”,"#")]="~";
接下來通過
pair<string,string> k;//這個是預測分析表的坐標
string term,nonterm;///終結符，非終結符
string prod;//這個用來接收產生式

term=analysis.top();
nonterm=in[i];
k.first=term;
k.second=nonterm;
prod=forecast[k];///找到產生式
到最后一步位置，便可以唯一確定一個字串
? Stack資料結構
堆疊主要用來當做分析堆疊
stack analysis;
void analysis_init()
{
analysis.push(’#’);
analysis.push(‘E’);
}
初始狀態兩個字符，按照ll1（1），文法進行操作，堆疊空表示接受字串