北邮编译原理语法分析.docx

编译原理语法分析班级：学号：姓名：ytinrete程序设计2题目：语法分析程序的设计与实现。实验内容：编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。实验要求：在对输入表达式进行分析的过程中，输出所采用的产生式。方法1：编写递归调用程序实现自顶向下的分析。方法2：编写LL(1)语法分析程序，要求如下。(1) 编程实现算法4.2，为给定文法自动构造预测分析表。(2) 编程实现算法4.1，构造LL(1)预测分析程序。方法3：编写语法分析程序实现自底向上的分析，要求如下。(1) 构造识别所有活前缀的DFA。(2) 构造LR分析表。(3) 编程实现算法4.3，构造LR分析程序。方法4：利用YACC自动生成语法分析程序，调用LEX自动生成的词法分析程序。方法2：编写LL（1）语法分析程序首先对文法进行处理，预存文法的拓广文法，非终结符的FIRST集和FOLLOW集。其次编程实现算法4.2，为给定文法自动构造分析表。最后输入待处理字符串，通过实现的算法4.1，利用分析表分析出字符串，能够接受则返回接受，否则返回错误。源代码：#include #include #include #include #include #include #include using namespace std;string original9= /保存原文法 E-E+T, E-E-T, E-T, T-T*F, T-T/F, T-F,F-i , F-(E), F-n;string G11= /拓广文法 E-TA,A-+TA,A-TA,A-e,T-FB,B-*FB,B-/FB,B-e,F-(E),F-i,F-n; string FIRST5=/first集 E:(in,/ EA:+-e,/ AT:(in,/ TB:*/e,/ BF:(in / F;string FOLLOW5=/follow集 E:)$,/ EA:)$,/ AT:+-)$,/ TB:+-)$,/ BF:+-*/)$,/ F;char VN5=E,A,T,B,F;/存储非终结符char VT9=i,n,+,-,*,/,(,),$;/存储终结符typedef struct Block char vn; /非终结符 char vt; /终结符 string s;/产生式 block;/存储分析预测表每个位置对应的终结符，非终结符，产生式block table45;/ 5*9=45char is_vt(char a)/是否为非终结符，不是返回xfor(int i=0; i5; i+)if(a=VNi)return x;if(isalpha(a)/是字母return i;if(isdigit(a)/是数字return n;for(int i=0+2; i9; i+)if(a=VTi)return a;int find_table(char X, char a)/查找是否存在符合的产生式for(int i=0; i45; i+)if(tablei.vn=X&tablei.vt=is_vt(a)if(0!=tablei.s.size()return i;elsereturn 999;/error项return 999;void LL_one(string temp)stackST;/栈ST.push($);/初始化压入栈ST.push(E);cout栈 输入 输出endl;/23,20,5int i=0, j=1;/temp指针char X;docout99)cout9)cout: ;elsecout: ;/输出stackt_ST;/栈char t_char;int i2=ST.size();for(int i1=0; i1i2; i1+)t_char=ST.top();t_ST.push(t_char);ST.pop();for(int i1=0; i1i2; i1+)t_char=t_ST.top();t_ST.pop();coutt_char;ST.push(t_char);for(int i1=0; i123-i2; i1+)cout ;cout|;for(int i1=0; i120-temp.size()+i; i1+)cout ;for(int i1=i; i1temp.size(); i1+)couttemp.at(i1);cout ;/开始处理X=ST.top();if($=X|x!=is_vt(X)/是终结符或Sif(temp.at(i)=X|(is_vt(temp.at(i)=X)ST.pop();couttemp.at(i)被接收;i+;elsecoutendlendlendlendl无法接受！endl;return;else/是非终结符号int t_table=find_table(X, temp.at(i);if(999!=t_table)ST.pop();/弹出Xint t_i=tablet_table.s.size()-1;coutewhile(tablet_table.s.at(t_i)!=)/压栈ST.push(tablet_table.s.at(t_i);t_i-;elsecoutendlendlendlendl无法接受！endl;return;j+;coutendl;while($!=X);coutendlendl字符串被成功接收！endl;int main()cout1.原文语法为：endl;for(int i=0; i=8; i+)coutoriginaliendl;coutendl2.拓广文法为：endl;for(int i=0; i=8; i+)coutGiendl;coutendl3.FIRST集与FOLLOW集：endl;for(int i=0; i5; i+)coutFIRST(FIRSTi.at(0)=;for(int j=2; jFIRSTi.size(); j+)coutFIRSTi.at(j), ;coutendl;for(int i=0; i5; i+)coutFOLLOW(FOLLOWi.at(0)=;for(int j=2; jFOLLOWi.size(); j+)coutFOLLOWi.at(j), ;coutendl;coutendl算法4.2 预测分析表的构造:endlendl;/初始化int t=0;for(int i=0; i5; i+)for(int j=0; j9; j+)tablet.s.clear();tablet.vn=VNi;tablet.vt=VTj;t+;/将产生式添加string temp;char t_a, t_b;for(int i=0; i11; i+)/11个产生式temp.clear();temp=Gi;/取产生式t_a=temp.at(0);t_b=temp.at(3);if(e=t_b)/follow集int j;for( j=0; j5; j+)/取follow集字符if(t_a=FOLLOWj.at(0)break;string t_follow(FOLLOWj, 2, FOLLOWj.size()-2);for( j=0; j45; j+)/遍历整个表if(tablej.vn=t_a)for(int k=0; kt_follow.size(); k+)if(tablej.vt=t_follow.at(k)tablej.s.clear();tablej.s=temp;else/first集bool isvn=false;for(int k=0; k5; k+)if(t_b=VNk)isvn=true;if(isvn)/取first集int j;for( j=0; j5; j+)/取follow集字符if(t_a=FIRSTj.at(0)break;string t_first(FIRSTj, 2, FIRSTj.size()-2);for(int k=0; k45; k+)if(tablek.vn=t_a)for(int l=0; lt_first.size(); l+)if(tablek.vt=t_first.at(l)tablek.s.clear();tablek.s=temp;elsefor(int k=0; k45; k+)if(tablek.vt=t_b&tablek.vn=t_a)tablek.s.clear();tablek.s=temp;/将预测分析表输出cout ;for(int i=0; i9; i+)cout VTi ;coutendl-endl;t=0;for(int i=0; i5; i+)coutVNi: ;for(int j=0; j9; j+)couttablet.s;for(int k=0; k7-tablet.s.size(); k+)cout ;t+;coute