编译原理实验报告3-LL(1)文法构造

编译原理上机实验报告小组成员：王金名、周攀、汪国辉、澎湃、王帅、齐娟娟、刘鸳鸳一、实验目的：了解LL（1）文法分析的基本原理；提高上机实践能力；增强团队协作能力。

二、实验内容：通过LL1文法分析表分析任意一个符号串是否为某文法的句子；显示具体分析过程；打开、新建、保存分析表；保存分析结果三、实验原理：1.C#字符串处理及数组处理，这是本实验最强有力的工具；2.LL（1）文法分析的基本原理，详见教材P80 LL（1）分析器的总控算法；3.C#文件操作，C#常用控件使用。

四、实验步骤：1.构造应用程序框架，利用内置分析表实现分析符号串的最基础功能（1）使用Visual Studio 2005 新建C#语言环境的windows应用程序LL1GAnalysis；（2）将窗体的名称改成From_Main，相应的代码名称会随之更改；（3）添加texbox控件ID为textBox_input，添加listView控件，ID为listView_Result；（4）public partial class Form_Main : Form里面编写相应代码：//全局变量const int Max = 100;public string[,] staticmTable ={{"","i","+","*","(",")","#"},{"S","<error>","<error>","<error>","S::=A","S::=A","<error>"},{"A","<error>","<error>","<error>","A::=BA\'","A::=BA\'","<error>"},{"A\'","A\'::=iBA\'","<error>","A\'::=ε","<error>","<error>","A\'::=ε"},{"B","<error>","<error>","<error>","B::=CB\'","B::=CB\'","<error>"},{"B\'","B\'::=ε","B\'::=+CB\'","B\'::=ε","<error>","<error>","B\'::=ε"},{"C","<error>","<error>","<error>","C::=(","C::=)A*","<error>"} };string[] VN = new string[Max]; int VNLength;string[] VT = new string[Max]; int VTLength;//以下是分析过程中要用到的公共函数public void addTolistView_Result(string step, string stack, string input, stringproduction)//分析步骤及结果显示（向listView中添加条目，并保存到string类型变量（analysisResult）作最终保存分析结果时使用{string strResultbuf = "";strResultbuf += step.PadRight(20, ' ');strResultbuf += stack.PadRight(20, ' ');strResultbuf += input.PadRight(20, ' ');strResultbuf += production.PadRight(20, ' ') + "\r\n";analysisResult += strResultbuf;ListViewItem li = new ListViewItem();li.Text = step;ListViewItem.ListViewSubItem ls = new ListViewItem.ListViewSubItem();ls.Text = stack;li.SubItems.Add(ls);ls = new ListViewItem.ListViewSubItem();ls.Text = input;li.SubItems.Add(ls);ls = new ListViewItem.ListViewSubItem();ls.Text = production;li.SubItems.Add(ls);listView_Result.Items.Add(li);}public void GetVN(string[,] table)//从分析表中获取非终结符{int i;for ( i = 1; i < table.GetLength(0);i++ ){VN[i-1] = table[i,0];}VNLength = i;}public void GetVT(string[,] table)//从分析表中获取终结符{int i;for (i = 1; i < table.GetLength(1); i++){VT[i-1] = table[0,i];}VTLength = i;}public int isVT(string str)//判断str是不是VT中的符号{int mark = 0;for (int i = 0; i < VTLength; i++){if (VT[i] == str){mark = 1;}}return mark;}public int isVN(string str)//判断str是不是VN中的符号{int mark = 0;for (int i = 0; i < VNLength; i++){if (VN[i] == str){mark = 1;}}return mark;}public string outStack(string[] Stack, int top)//栈内符号合并输出的时候用 {string str = "";for (int i = 0; i <= top; i++){str += Stack[i];}return str;}public void removeAllItems(ListView list)//清空listview Items{int itemcount = list.Items.Count;for (int i = itemcount; i > 0 ;i-- ){list.Items.RemoveAt(0);}}public string matchInTable(string[,] mt,string stacktop, string nowstr)//查表栈顶与ch 交叉处的标志并返回{int i,j;for (i = 0; i < mt.GetLength(0); i++ ){if (mt[i,0] == stacktop){break;}}for (j = 0; j < mt.GetLength(1);j++ ){if (mt[0,j] == nowstr){break;}}if (i < mt.GetLength(0)&&j<mt.GetLongLength(1)){return mt[i,j];}else{return"error! ";}}//以下是分析过程public void Start_Analysis(string[,] mTable)//开始分析并显示分析过程{tabControl_mTable.SelectTab(tabPage_Show);ShowmTable(mTable);removeAllItems(listView_Result);listView_Result.BeginUpdate();int top = -1; int step = 0;string[] Stack = new string[Max];string str = textBox_input.Text.Trim();//初始化GetVN(mTable); GetVT(mTable);top++; Stack[top] = "#";top++; Stack[top] = VN[0];str += "#";//分析while (true){if (isVT(Stack[top]) == 1)//Stack[top]是终结符，则比较栈顶符与当前符号{if (Stack[top] == str[0].ToString())//匹配当前符号{if (Stack[top] == "#")//ok{step++;addTolistView_Result(step.ToString(), outStack(Stack, top), str, "OK!");step = 0;break;}else//同时退栈{step++;addTolistView_Result(step.ToString(), outStack(Stack, top), str, ""); top--;str = str.Remove(0, 1);}}else//错误{step++;addTolistView_Result(step.ToString(), outStack(Stack, top), str,"Error!");break;}}else if (isVN(Stack[top]) == 1)//Stack[top]是非终结符，则查表{string production = matchInTable(mTable, Stack[top], str[0].ToString());if (production != "<error>"){step++;addTolistView_Result(step.ToString(), outStack(Stack, top), str, production);string probuf = "";if (production[1] == '\''){probuf = production.Remove(0, 5);}else{probuf = production.Remove(0, 4);}char[] chbuf = probuf.ToCharArray();int i = chbuf.Length - 1;string strbuf = "";Stack[top] = null;top--;while (i >= 0){if (chbuf[i] != 'ε'){if (chbuf[i] != '\''){top++;Stack[top] = strbuf.Insert(0, chbuf[i].ToString());strbuf = "";}else if (chbuf[i] == '\''){strbuf += strbuf.Insert(0, chbuf[i].ToString());}}else { break; }i--;}}else//错误production.Length != 0不在分析表中{step++;addTolistView_Result(step.ToString(), outStack(Stack, top), str, "Error!");break;}}else//错误非法字符{step++;addTolistView_Result(step.ToString(), "错误", str, "非法字符:" +str[0].ToString());break;}}//分析结束listView_Result.EndUpdate();}private void button_Start_Click(object sender, EventArgs e)//菜单及按钮开始分析(菜单项及开始按钮公用函数){string[,] mTable;if (radioButton_Staticmt.Checked){mTable = staticmTable;ShowmTable(mTable);Start_Analysis(mTable);}else if (radioButton_Createmt.Checked){if (created == 1){mTable = creamTable;ShowmTable(mTable);Start_Analysis(mTable);}else{MessageBox.Show("你还没有创建分析表，请先创建！", "错误提示",MessageBoxButtons.OK, MessageBoxIcon.Exclamation);}}else if (radioButton_Openmt.Checked){if (opened == 1){mTable = openmTable;ShowmTable(mTable);Start_Analysis(mTable);}else{MessageBox.Show("你还没有打开分析表，请先打开或创建！", "错误提示",MessageBoxButtons.OK, MessageBoxIcon.Exclamation);}}}2.实现显示分析表及新建分析表并利用该表分析句子的功能（1）添加tabControl控件ID为tabControl_mTable建立3个页面tabPage_Show显示当前分析表、tabPage_Edit新建分析表、tabPage_Open打开分析表（2）tabPage_Show中添加listView控件ID为listView_mtableshow用于显示分析表（3）tabPage_Edit中添加两个Button 控件ID分别为button_StartAdd开始添加、button_FilishAdd 完成添加；两个textBox控件ID分别为textBox_VT 、textBox_VN、分别用于获取要添加的终结符及非终结符个数；一个tableLayoutPanel控件ID为tableLayoutPanel_mTable用于根据用户输入的VT及VN的个数建立输入表（4）编辑相应代码：private void button_StartAdd_Click(object sender, EventArgs e)//新建分析表并开始输入{try{int conwidth,conheight,col, row;TextBox txb;tableLayoutPanel_mTable.Controls.Clear();conwidth = 50; conheight = 20;col = Convert.ToInt32(textBox_VT.Text)+1;row = Convert.ToInt32(textBox_VN.Text)+1;tableLayoutPanel_mTable.ColumnCount =col;tableLayoutPanel_mTable.RowCount = row;for (int i = 0; i < col;i++ ){for (int j = 0; j < row;j++ ){if (i == 0&&j==0){Label lb = new Label();lb.Text = "VN\\VT";lb.Width = conwidth;lb.ForeColor = Color.Red;tableLayoutPanel_mTable.Controls.Add(lb,i,j);}else{txb = new TextBox();txb.Width = conwidth;txb.Height = conheight;tableLayoutPanel_mTable.Controls.Add(txb,i,j);}}}}catch{MessageBox.Show("终结符或非终结符格式不对！\n请输入数字！","错误提示",MessageBoxButtons.OK, MessageBoxIcon.Exclamation);}}private void button_FilishAdd_Click(object sender, EventArgs e)//完成添加,更新分析表 {int col = tableLayoutPanel_mTable.ColumnCount;int row = tableLayoutPanel_mTable.RowCount;if (col > 1&&row>1){creamTable = new string[row, col];for (int i = 0; i < row; i++){for (int j = 0; j < row; j++){if (i == 0 && j == 0){creamTable[i, j] = "";}else{creamTable[i, j] =((TextBox)tableLayoutPanel_mTable.GetControlFromPosition(j, i)).Text.Trim();if (creamTable[i,j].Length == 0){creamTable[i, j] = "<error>";}}}}MessageBox.Show("成功更新分析表!");tabControl_mTable.SelectTab(tabPage_Show);radioButton_Createmt.Checked = true;created = 1;ShowmTable(creamTable);}else{MessageBox.Show("请先点击“开始添加”创建表格！","错误提示",MessageBoxButtons.OK, MessageBoxIcon.Exclamation);}}public void ShowmTable(string[,] mTable)//显示分析表{listView_mtableshow.Clear();ColumnHeader colHeader;ListViewItem lvi;ListViewItem.ListViewSubItem lvsi;for (int i = 1; i <= mTable.GetLength(1); i++){colHeader = new ColumnHeader();colHeader.Text = i.ToString();listView_mtableshow.Columns.Add(colHeader);}for (int i = 0; i < mTable.GetLength(0); i++){lvi = new ListViewItem();lvi.Text = mTable[i, 0];for (int j = 1; j < mTable.GetLength(1); j++){lvsi = new ListViewItem.ListViewSubItem();lvsi.Text = mTable[i, j];lvi.SubItems.Add(lvsi);}listView_mtableshow.Items.Add(lvi);}}private void miFileNew_Click(object sender, EventArgs e)//菜单新建分析表{tabControl_mTable.SelectTab(tabPage_Edit);}3.实现打开、保存分析表、保存分析结果的功能（1）添加主菜单menuStrip_Main两个Item：miFile文件、miGraAnylysis语法分析。

课程编译原理实验名称实验二 LL(1)分析法实验目的1．掌握LL(1)分析法的基本原理；2．掌握LL(1)分析表的构造方法；3．掌握LL(1)驱动程序的构造方法。

一.实验内容及要求根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。

本次实验的目的主要是加深对预测分析LL（1）分析法的理解。

对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG（2）G->+TG（3）G->ε（4）T->FS（5）S->*FS（6）S->ε（7）F->(E)（8）F->i程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。

输出过程如下：步骤分析栈剩余输入串所用产生式1 E i+i*i# E->TG... ... ... ...二.实验过程及结果代码如下：#include<iostream>#include "edge.h"using namespace std;edge::edge(){cin>>left>>right;rlen=right.length();if(NODE.find(left)>NODE.length())NODE+=left;}string edge::getlf(){return left;}string edge::getrg(){return right;}string edge::getfirst(){return first;}string edge::getfollow(){return follow;}string edge::getselect(){return select;}string edge::getro(){string str;str+=right[0];return str;}int edge::getrlen(){return right.length();}void edge::newfirst(string w){int i;for(i=0;i<w.length();i++)if(first.find(w[i])>first.length())first+=w[i];}void edge::newfollow(string w){int i;for(i=0;i<w.length();i++)if(follow.find(w[i])>follow.length()&&w[i]!='@')follow+=w[i];}void edge::newselect(string w){int i;for(i=0;i<w.length();i++)if(select.find(w[i])>select.length()&&w[i]!='@') select+=w[i];}void edge::delfirst(){int i=first.find('@');first.erase(i,1);}int SUM;string NODE,ENODE;//计算firstvoid first(edge ni,edge *n,int x){int i,j;for(j=0;j<SUM;j++){if(ni.getlf()==n[j].getlf()){if(NODE.find(n[j].getro())<NODE.length()){for(i=0;i<SUM;i++)if(n[i].getlf()==n[j].getro())first(n[i],n,x);}elsen[x].newfirst(n[j].getro());}}}//计算followvoid follow(edge ni,edge *n,int x){int i,j,k,s;string str;for(i=0;i<ni.getrlen();i++){s=NODE.find(ni.getrg()[i]);if(s<NODE.length()&&s>-1) //是非终结符if(i<ni.getrlen()-1) //不在最右for(j=0;j<SUM;j++)if(n[j].getlf().find(ni.getrg()[i])==0){if(NODE.find(ni.getrg()[i+1])<NODE.length()){for(k=0;k<SUM;k++)if(n[k].getlf().find(ni.getrg()[i+1])==0){n[j].newfollow(n[k].getfirst());if(n[k].getfirst().find("@")<n[k].getfirst().length())n[j].newfollow(ni.getfollow());}}else{str.erase();str+=ni.getrg()[i+1];n[j].newfollow(str);}}}}//计算selectvoid select(edge &ni,edge *n){int i,j;if(ENODE.find(ni.getro())<ENODE.length()){ni.newselect(ni.getro());if(ni.getro()=="@")ni.newselect(ni.getfollow());}elsefor(i=0;i<ni.getrlen();i++){for(j=0;j<SUM;j++)if(ni.getrg()[i]==n[j].getlf()[0]){ni.newselect(n[j].getfirst());if(n[j].getfirst().find('@')>n[j].getfirst().length())return;}}}//输出集合void out(string p){int i;if(p.length()==0)return;cout<<"{";for(i=0;i<p.length()-1;i++){cout<<p[i]<<",";}cout<<p[i]<<"}";}//连续输出符号void outfu(int a,string c){int i;for(i=0;i<a;i++)cout<<c;}//输出预测分析表void outgraph(edge *n,string (*yc)[50]){int i,j,k;bool flag;for(i=0;i<ENODE.length();i++){if(ENODE[i]!='@'){outfu(10," ");cout<<ENODE[i];}}outfu(10," ");cout<<"#"<<endl;int x;for(i=0;i<NODE.length();i++){outfu(4," ");cout<<NODE[i];outfu(5," ");for(k=0;k<ENODE.length();k++){flag=1;for(j=0;j<SUM;j++){if(NODE[i]==n[j].getlf()[0]){x=n[j].getselect().find(ENODE[k]);if(x<n[j].getselect().length()&&x>-1){cout<<"->"<<n[j].getrg();yc[i][k]=n[j].getrg();outfu(9-n[j].getrlen()," ");flag=0;}x=n[j].getselect().find('#');if(k==ENODE.length()-1&&x<n[j].getselect().length()&&x>-1){cout<<"->"<<n[j].getrg();yc[i][j]=n[j].getrg();}}}if(flag&&ENODE[k]!='@')outfu(11," ");}cout<<endl;}}//分析符号串int pipei(string &chuan,string &fenxi,string (*yc)[50],int &b) {char ch,a;int x,i,j,k;b++;cout<<endl<<" "<<b;if(b>9)outfu(8," ");elseoutfu(9," ");cout<<fenxi;outfu(26-chuan.length()-fenxi.length()," "); cout<<chuan;outfu(10," ");a=chuan[0];ch=fenxi[fenxi.length()-1];x=ENODE.find(ch);if(x<ENODE.length()&&x>-1){if(ch==a){fenxi.erase(fenxi.length()-1,1);chuan.erase(0,1);cout<<"'"<<a<<"'匹配";if(pipei(chuan,fenxi,yc,b))return 1;elsereturn 0;}elsereturn 0;}else{if(ch=='#'){if(ch==a){cout<<"分析成功"<<endl;return 1;}elsereturn 0;}elseif(ch=='@'){fenxi.erase(fenxi.length()-1,1);if(pipei(chuan,fenxi,yc,b))return 1;elsereturn 0;}else{i=NODE.find(ch);if(a=='#'){x=ENODE.find('@');if(x<ENODE.length()&&x>-1)j=ENODE.length()-1;elsej=ENODE.length();}elsej=ENODE.find(a);if(yc[i][j].length()){cout<<NODE[i]<<"->"<<yc[i][j];fenxi.erase(fenxi.length()-1,1);for(k=yc[i][j].length()-1;k>-1;k--)if(yc[i][j][k]!='@')fenxi+=yc[i][j][k];if(pipei(chuan,fenxi,yc,b))return 1;elsereturn 0;}elsereturn 0;}}}void main(){edge *n;string str,(*yc)[50];int i,j,k;bool flag=0;cout<<"请输入上下文无关文法的总规则数："<<endl;cin>>SUM;cout<<"请输入具体规则（格式：左部右部，@为空）："<<endl;n=new edge[SUM];for(i=0;i<SUM;i++)for(j=0;j<n[i].getrlen();j++){str=n[i].getrg();if(NODE.find(str[j])>NODE.length()&&ENODE.find(str[j])>ENODE.length()) ENODE+=str[j];}//计算first集合for(i=0;i<SUM;i++){first(n[i],n,i);}//outfu(10,"~*~");cout<<endl;for(i=0;i<SUM;i++)if(n[i].getfirst().find("@")<n[i].getfirst().length()){if(NODE.find(n[i].getro())<NODE.length()){for(k=1;k<n[i].getrlen();k++){if(NODE.find(n[i].getrg()[k])<NODE.length()){for(j=0;j<SUM;j++){if(n[i].getrg()[k]==n[j].getlf()[0]){n[i].newfirst(n[j].getfirst());break;}}if(n[j].getfirst().find("@")>n[j].getfirst().length()){n[i].delfirst();break;}}}}}//计算follow集合for(k=0;k<SUM;k++){for(i=0;i<SUM;i++){if(n[i].getlf()==n[0].getlf())n[i].newfollow("#");follow(n[i],n,i);}for(i=0;i<SUM;i++){for(j=0;j<SUM;j++)if(n[j].getrg().find(n[i].getlf())==n[j].getrlen()-1)n[i].newfollow(n[j].getfollow());}}//计算select集合for(i=0;i<SUM;i++){select(n[i],n);}for(i=0;i<NODE.length();i++){str.erase();for(j=0;j<SUM;j++)if(n[j].getlf()[0]==NODE[i]){if(!str.length())str=n[j].getselect();else{for(k=0;k<n[j].getselect().length();k++)if(str.find(n[j].getselect()[k])<str.length()){flag=1;break;}}}}//输出cout<<endl<<"非终结符";outfu(SUM," ");cout<<"First";outfu(SUM," ");cout<<"Follow"<<endl;outfu(5+SUM,"-*-");cout<<endl;for(i=0;i<NODE.length();i++){for(j=0;j<SUM;j++)if(NODE[i]==n[j].getlf()[0]){outfu(3," ");cout<<NODE[i];outfu(SUM+4," ");out(n[j].getfirst());outfu(SUM+4-2*n[j].getfirst().length()," ");out(n[j].getfollow());cout<<endl;break;}}outfu(5+SUM,"-*-");cout<<endl<<"判定结论： ";if(flag){cout<<"该文法不是LL(1)文法!"<<endl;return;}else{cout<<"该文法是LL(1)文法!"<<endl;}//输出预测分析表cout<<endl<<"预测分析表如下："<<endl;yc=new string[NODE.length()][50];outgraph(n,yc);string chuan,fenxi,fchuan;cout<<endl<<"请输入符号串：";cin>>chuan;fchuan=chuan;fenxi="#";fenxi+=NODE[0];i=0;cout<<endl<<"预测分析过程如下："<<endl;cout<<"步骤";outfu(7," ");cout<<"分析栈";outfu(10," ");cout<<"剩余输入串";outfu(8," ");cout<<"推导所用产生式或匹配";if(pipei(chuan,fenxi,yc,i))cout<<endl<<"输入串"<<fchuan<<"是该文法的句子！"<<endl;elsecout<<endl<<"输入串"<<fchuan<<"不是该文法的句子！"<<endl;}截屏如下：三.实验中的问题及心得这次实验让我更加熟悉了LL（1）的工作流程以及LL(1)分析表的构造方法。

南开大学计算机科学与技术学院课程设计报告（2010 ~2011 学年度第一学期）课程名称编译原理设计题目LL(1)分析姓名学号专业班级地点教师1.需求分析语法分析是编译过程的核心部分。

它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。

语法分析器在编译程序中的地位如图1所示：图1 语法分析器在编译程序中的地位语言的语法结构是用上下文无关文法描述的。

因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。

这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。

对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。

或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。

自顶向下分析法就是语法分析办法中的一类。

顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。

这种方法是带“回溯”的。

自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。

或者说，为输入串寻找一个最左推导。

这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。

实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。

每个这种子程序可作为一个布尔过程。

一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。

对于给定的分析文法对象，构造它的预测分析程序；并任意给一算术表达式进行分析测试，本预测分析程序能够使用分析表和栈联合控制实现LL(1)分析，本文将就编译原理中比较常用的一个表达式文法，通过递归下降语法分析法来编写分析器。

文中将为您提供如何通过FIRST、FOLLOW和SELECT集合来判断LL(1)方法，然后如何用递归下降语法分析法分析LL(1)方法的基本递归流程，以及用C++语言来编程实现分析器。

编译原理实验报告一、实验目的编译原理是计算机科学中的重要学科，它涉及到将高级编程语言转换为计算机能够理解和执行的机器语言。

本次实验的目的是通过实际操作和编程实践，深入理解编译原理中的词法分析、语法分析、语义分析以及中间代码生成等关键环节，提高我们对编译过程的认识和编程能力。

二、实验环境本次实验使用的编程语言为C+＋，开发环境为Visual Studio 2019。

此外，还使用了一些相关的编译工具和调试工具，如 GDB 等。

三、实验内容（一）词法分析器的实现词法分析是编译过程的第一步，其任务是将输入的源程序分解为一个个单词符号。

在本次实验中，我们使用有限自动机的理论来设计和实现词法分析器。

首先，定义了各种单词符号的类别，如标识符、关键字、常量、运算符等。

然后，根据这些类别设计了相应的状态转换图，并将其转换为代码实现。

在实现过程中，使用了正则表达式来匹配输入字符串中的单词符号。

对于标识符和常量等需要进一步处理的单词符号，使用了相应的规则进行解析和转换。

（二）语法分析器的实现语法分析是编译过程的核心环节之一，其任务是根据给定的语法规则，分析输入的单词符号序列是否符合语法结构。

在本次实验中，我们使用了递归下降的语法分析方法。

首先，根据实验要求定义了语法规则，并将其转换为相应的递归函数。

在递归函数中，通过对输入单词符号的判断和处理，逐步分析语法结构。

为了处理语法错误，在分析过程中添加了错误检测和处理机制。

当遇到不符合语法规则的输入时，能够输出相应的错误信息，并尝试进行恢复。

（三）语义分析及中间代码生成语义分析的目的是对语法分析得到的语法树进行语义检查和语义处理，生成中间代码。

在本次实验中，我们使用了三地址码作为中间代码的表示形式。

在语义分析过程中，对变量的定义和使用、表达式的计算、控制流语句等进行了语义检查和处理。

对于符合语义规则的语法结构，生成相应的三地址码指令。

四、实验步骤（一）词法分析器的实现步骤1、定义单词符号的类别和对应的正则表达式。

集美大学计算机工程学院实验报告课程名称：编译原理指导教师：付永钢实验成绩：实验编号：实验三实验名称：LL(1)语法分析器的构造班级：计算14姓名：学号上机实践日期：2017.6上机实践时间：6学时一、实验目的1、掌握LL(1)分析法的基本原理；2、掌握LL(1)分析表的构造方法；3、掌握LL(1)驱动程序的构造方法。

二、实验环境Ubuntu三、实验原理1、对文法要求LL(1)分析法属于自顶向下分析方法，因此需要预测匹配的产生式。

即在LL(1)分析法中，每当在符号栈的栈顶出现非终结符时，要预测用哪个产生式的右部去替换该非终结符。

LL(1)分析方法要求文法满足如下条件：对于任一非终结符A，其任意两个产生式A→α,A→β，都要满足下面条件：First(A→α)∩First(A→β)=∅2、分析表构造LL(1)分析表的作用是对当前非终结符和输入符号确定应该选择用哪个产生式进行推导。

它的行对应文法的非终结符，列对应终结符，表中的值有两种：一是产生式的编号，一是错误编号。

若用T表示LL(1)分析表，则T可表示如下：T: V N×V T→P∪{Error}T(A, t) = A→α，当t∈First(A→α)T(A, t) = Error，否则其中P表示所有产生式的集合。

显然，一个文法G是LL(1)文法，当且仅当T的元素包含唯一的一个产生式或Error。

3、驱动程序构造LL(1)分析主要包括以下四个动作，其中X为符号栈栈顶元素，a为输入流当前字符。

●替换：当X∈V N时选相应产生式的右部β去替换X。

●匹配：当X∈V T时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。

●成功：当格局为（空，空）时报告分析成功。

●报错：出错后，停止分析。

四、实验内容已知文法G[E]:E→E+T|TT→T*F|FF→(E)|i说明：终结符号i为用户定义的简单变量, 即标识符的定义。

《LL（1）分析器的构造》实验报告一、实验名称LL(1)分析器的构造二、实验目的设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。

三、实验内容和要求设计并实现一个LL(1)语法分析器，实现对算术文法:G[E]:E->E+T|TT->T*F|FF->(E)|i所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。

实验要求:1、检测左递归，如果有则进行消除；2、求解FIRST集和FOLLOW集；3、构建LL(1)分析表；4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。

四、主要仪器设备硬件：微型计算机。

软件： Code blocks（也可以是其它集成开发环境）。

五、实验过程描述1、程序主要框架程序中编写了以下函数，各个函数实现的作用如下：void input_grammer(string *G);//输入文法Gvoid preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k);//将文法G预处理得到产生式集合P，非终结符、终结符集合U、u，int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GGint* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST集string FIRST(string U,string u,string* first,string s)；//求符号串s=X1X2...Xn的FIRST集string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表void analyse(string **table,string U,string u,int t,string s)；//分析符号串s2、编写的源程序#include<cstdio>#include<cstring>#include<iostream>using namespace std;void input_grammer(string *G)//输入文法G,n个非终结符{int i=0;//计数char ch='y';while(ch=='y'){cin>>G[i++];cout<<"继续输入?(y/n)\n";cin>>ch;}}void preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k)//将文法G预处理产生式集合P，非终结符、终结符集合U、u，{int i,j,r,temp;//计数char C;//记录规则中（）后的符号int flag;//检测到（）n=t=k=0;for( i=0;i<50;i++) P[i]=" ";//字符串如果不初始化，在使用P[i][j]=a时将不能改变，可以用P[i].append(1,a)U=u=" ";//字符串如果不初始化，无法使用U[i]=a赋值，可以用U.append(1,a) for(n=0;!G[n].empty();n++){ U[n]=G[n][0];}//非终结符集合，n为非终结符个数for(i=0;i<n;i++){for(j=4;j<G[i].length();j++){if(U.find(G[i][j])==string::npos&&u.find(G[i][j])==string::npos)if(G[i][j]!='|'&&G[i][j]!='^')//if(G[i][j]!='('&&G[i][j]!=')'&&G[i][j]!='|'&&G[i][j]!='^')u[t++]=G[i][j];}}//终结符集合，t为终结符个数for(i=0;i<n;i++){flag=0;r=4;for(j=4;j<G[i].length();j++){P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';/* if(G[i][j]=='('){ j++;flag=1;for(temp=j;G[i][temp]!=')';temp++);C=G[i][temp+1];//C记录（）后跟的字符，将C添加到（）中所有字符串后面}if(G[i][j]==')') {j++;flag=0;}*/if(G[i][j]=='|'){//if(flag==1) P[k][r++]=C;k++;j++;P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';r=4;P[k][r++]=G[i][j];}else{P[k][r++]=G[i][j];}}k++;}//获得产生式集合P，k为产生式个数}int eliminate_1(string *G,string *P,string U,string *GG)//消除文法G1中所有直接左递归得到文法G2，要能够消除含有多个左递归的情况）{string arfa,beta;//所有形如A::=Aα|β中的α、β连接起来形成的字符串arfa、betaint i,j,temp,m=0;//计数int flag=0;//flag=1表示文法有左递归int flagg=0;//flagg=1表示某条规则有左递归char C='A';//由于消除左递归新增的非终结符，从A开始增加，只要不在原来问法的非终结符中即可加入for(i=0;i<20&&U[i]!=' ';i++){ flagg=0;arfa=beta="";for(j=0;j<100&&P[j][0]!=' ';j++){if(P[j][0]==U[i]){if(P[j][4]==U[i])//产生式j有左递归{flagg=1;for(temp=5;P[j][temp]!=' ';temp++) arfa.append(1,P[j][temp]);if(P[j+1][4]==U[i]) arfa.append("|");//不止一个产生式含有左递归}else{for(temp=4;P[j][temp]!=' ';temp++) beta.append(1,P[j][temp]);if(P[j+1][0]==U[i]&&P[j+1][4]!=U[i]) beta.append("|");}}}if(flagg==0)//对于不含左递归的文法规则不重写{GG[m]=G[i]; m++;}else{flag=1;//文法存在左递归GG[m].append(1,U[i]);GG[m].append("::=");if(beta.find('|')!=string::npos) GG[m].append("("+beta+")");else GG[m].append(beta);while(U.find(C)!=string::npos){C++;}GG[m].append(1,C);m++;GG[m].append(1,C);GG[m].append("::=");if(arfa.find('|')!=string::npos) GG[m].append("("+arfa+")");else GG[m].append(arfa);GG[m].append(1,C);GG[m].append("|^");m++;C++;}//A::=Aα|β改写成A::=βA‘，A’=αA'|β，}return flag;}int* ifempty(string* P,string U,int k,int n){int* empty=new int [n];//指示非终结符能否推导到空串int i,j,r;for(r=0;r<n;r++) empty[r]=0;//默认所有非终结符都不能推导到空int flag=1;//1表示empty数组有修改int step=100;//假设一条规则最大推导步数为100步while(step--){for(i=0;i<k;i++){r=U.find(P[i][0]);if(P[i][4]=='^') empty[r]=1;//直接推导到空else{for(j=4;P[i][j]!=' ';j++){if(U.find(P[i][j])!=string::npos){if(empty[U.find(P[i][j])]==0) break;}else break;}if(P[i][j]==' ') empty[r]=1;//多步推导到空else flag=0;}}}return empty;}string* FIRST_X(string* P,string U,string u,int* empty,int k,int n){int i,j,r,s,tmp;string* first=new string[n];char a;int step=100;//最大推导步数while(step--){// cout<<"step"<<100-step<<endl;for(i=0;i<k;i++){//cout<<P[i]<<endl;r=U.find(P[i][0]);if(P[i][4]=='^'&&first[r].find('^')==string::npos) first[r].append(1,'^');//规则右部首符号为空else{for(j=4;P[i][j]!=' ';j++){a=P[i][j];if(u.find(a)!=string::npos&&first[r].find(a)==string::npos)//规则右部首符号是终结符{first[r].append(1,a);break;//添加并结束}if(U.find(P[i][j])!=string::npos)//规则右部首符号是非终结符,形如X：：=Y1Y2...Yk{s=U.find(P[i][j]);//cout<<P[i][j]<<":\n";for(tmp=0;first[s][tmp]!='\0';tmp++){a=first[s][tmp];if(a!='^'&&first[r].find(a)==string::npos)//将FIRST[Y1]中的非空符加入first[r].append(1,a);}}if(!empty[s]) break;//若Y1不能推导到空，结束}if(P[i][j]==' ')if(first[r].find('^')==string::npos)first[r].append(1,'^');//若Y1、Y2...Yk都能推导到空，则加入空符号}}}return first;}string FIRST(string U,string u,string* first,string s)//求符号串s=X1X2...Xn的FIRST集{int i,j,r;char a;string fir;for(i=0;i<s.length();i++){if(s[i]=='^') fir.append(1,'^');if(u.find(s[i])!=string::npos&&fir.find(s[i])==string::npos){ fir.append(1,s[i]);break;}//X1是终结符，添加并结束循环if(U.find(s[i])!=string::npos)//X1是非终结符{r=U.find(s[i]);for(j=0;first[r][j]!='\0';j++){a=first[r][j];if(a!='^'&&fir.find(a)==string::npos)//将FIRST(X1)中的非空符号加入fir.append(1,a);}if(first[r].find('^')==string::npos) break;//若X1不可推导到空，循环停止}if(i==s.length())//若X1-Xk都可推导到空if(fir.find(s[i])==string::npos) //fir中还未加入空符号fir.append(1,'^');}return fir;}string** create_table(string *P,string U,string u,int n,int t,int k,string* first)//构造分析表，P为文法G的产生式构成的集合{int i,j,p,q;string arfa;//记录规则右部string fir,follow;string FOLLOW[5]={")#",")#","+)#","+)#","+*)#"};string **table=new string*[n];for(i=0;i<n;i++) table[i]=new string[t+1];for(i=0;i<n;i++)for(j=0;j<t+1;j++)table[i][j]=" ";//table存储分析表的元素，“ ”表示error for(i=0;i<k;i++){arfa=P[i];arfa.erase(0,4);//删除前4个字符，如：E::=E+T,则arfa="E+T"fir=FIRST(U,u,first,arfa);for(j=0;j<t;j++){p=U.find(P[i][0]);if(fir.find(u[j])!=string::npos){q=j;table[p][q]=P[i];}//对first（）中的每一终结符置相应的规则}if(fir.find('^')!=string::npos){follow=FOLLOW[p];//对规则左部求follow()for(j=0;j<t;j++){if((q=follow.find(u[j]))!=string::npos){q=j;table[p][q]=P[i];}//对follow（）中的每一终结符置相应的规则}table[p][t]=P[i];//对#所在元素置相应规则}}return table;}void analyse(string **table,string U,string u,int t,string s)//分析符号串s{string stack;//分析栈string ss=s;//记录原符号串char x;//栈顶符号char a;//下一个要输入的字符int flag=0;//匹配成功标志int i=0,j=0,step=1;//符号栈计数、输入串计数、步骤数int p,q,r;string temp;for(i=0;!s[i];i++){if(u.find(s[i])==string::npos)//出现非法的符号cout<<s<<"不是该文法的句子\n";return;}s.append(1,'#');stack.append(1,'#');//’#’进入分析栈stack.append(1,U[0]);i++;//文法开始符进入分析栈a=s[0];//cout<<stack<<endl;cout<<"步骤分析栈余留输入串所用产生式\n";while(!flag){// cout<<"步骤分析栈余留输入串所用产生式\n"cout<<step<<" "<<stack<<" "<<s<<" ";x=stack[i];stack.erase(i,1);i--;//取栈顶符号x,并从栈顶退出//cout<<x<<endl;if(u.find(x)!=string::npos)//x是终结符的情况{if(x==a){s.erase(0,1);a=s[0];//栈顶符号与当前输入符号匹配，则输入下一个符号cout<<" \n";//未使用产生式，输出空}else{cout<<"error\n";cout<<ss<<"不是该文法的句子\n";break;}}if(x=='#'){if(a=='#') {flag=1;cout<<"成功\n";}//栈顶和余留输入串都为#，匹配成功else{cout<<"error\n";cout<<ss<<"不是该文法的句子\n";break;}}if(U.find(x)!=string::npos)//x是非终结符的情况{p=U.find(x);q=u.find(a);if(a=='#') q=t;temp=table[p][q];cout<<temp<<endl;//输出使用的产生式if(temp[0]!=' ')//分析表中对应项不为error{r=9;while(temp[r]==' ') r--;while(r>3){if(temp[r]!='^'){stack.append(1,temp[r]);//将X::=x1x2...的规则右部各符号压栈i++;}r--;}}else{cout<<"error\n";cout<<ss<<"不是该文法的句子\n";break;}}step++;}if(flag) cout<<endl<<ss<<"是该文法的句子\n";}int main(){int i,j;string *G=new string[50];//文法Gstring *P=new string[50];//产生式集合Pstring U,u;//文法G非终结符集合U，终结符集合uint n,t,k;//非终结符、终结符个数,产生式数string *GG=new string[50];//消除左递归后的文法GGstring *PP=new string[50];//文法GG的产生式集合PPstring UU,uu;//文法GG非终结符集合U，终结符集合uint nn,tt,kk;//消除左递归后的非终结符、终结符个数,产生式数string** table;//分析表cout<<" 欢迎使用LL(1)语法分析器!\n\n\n";cout<<"请输入文法（同一左部的规则在同一行输入，例如：E::=E+T|T；用^表示空串）\n";input_grammer(G);preprocess(G,P,U,u,n,t,k);cout<<"\n该文法有"<<n<<"个非终结符：\n";for(i=0;i<n;i++) cout<<U[i];cout<<endl;cout<<"该文法有"<<t<<"个终结符：\n";for(i=0;i<t;i++) cout<<u[i];cout<<"\n\n 左递归检测与消除\n\n";if(eliminate_1(G,P,U,GG)){preprocess(GG,PP,UU,uu,nn,tt,kk);cout<<"该文法存在左递归！\n\n消除左递归后的文法:\n\n"; for(i=0;i<nn;i++) cout<<GG[i]<<endl;cout<<endl;cout<<"新文法有"<<nn<<"个非终结符：\n";for(i=0;i<nn;i++) cout<<UU[i];cout<<endl;cout<<"新文法有"<<tt<<"个终结符：\n";for(i=0;i<tt;i++) cout<<uu[i];cout<<endl;//cout<<"新文法有"<<kk<<"个产生式：\n";//for(i=0;i<kk;i++) cout<<PP[i]<<endl;}else{cout<<"该文法不存在左递归\n";GG=G;PP=P;UU=U;uu=u;nn=n;tt=t;kk=k;}cout<<" 求解FIRST集\n\n";int *empty=ifempty(PP,UU,kk,nn);string* first=FIRST_X(PP,UU,uu,empty,kk,nn);for(i=0;i<nn;i++)cout<<"FIRST("<<UU[i]<<"): "<<first[i]<<endl;cout<<" 求解FOLLOW集\n\n";for(i=0;i<nn;i++)cout<<"FOLLOW("<<UU[i]<<"): "<<FOLLOW[i]<<endl; cout<<"\n\n 构造文法分析表\n\n"; table=create_table(PP,UU,uu,nn,tt,kk,first);cout<<" ";for(i=0;i<tt;i++) cout<<" "<<uu[i]<<" ";cout<<"# "<<endl;for( i=0;i<nn;i++){cout<<UU[i]<<" ";for(j=0;j<t+1;j++)cout<<table[i][j];cout<<endl;}cout<<"\n\n 分析符号串\n\n";cout<<"请输入要分析的符号串\n";cin>>s;analyse(table,UU,uu,tt,s);return 0;}3、程序演示结果（1）输入文法（2）消除左递归（3）求解FIRST和FOLLOW集（4）构造分析表（5）分析符号串匹配成功的情况：匹配失败的情况五、思考和体会1、编写的LL(1)语法分析器应该具有智能性，可以由用户输入任意文法，不需要指定终结符个数和非终结符个数。

实验3 ＬL(1）文法构造一、实验目的熟悉ＬL（１）文法的分析条件,了解LL(1)文法的构造方法。

二、实验内容1、编制一个能够将一个非LＬ(1)文法转换为ＬL（1）文法；２、消除左递归;3、消除回溯。

三、实验要求1、将一个可转换非ＬL(1）文法转换为LＬ（1）文法,要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。

2、提取文法左因子算法:１）对文法G的所有非终结符进行排序２)按上述顺序对每一个非终结符Pi依次执行:foｒ( j=1; j＜ i-１；j++）将Pj代入Pi的产生式(若可代入的话）;消除关于Pi的直接左递归:Pi －＞ Pｉα|β ,其中β不以Ｐi开头,则修改产生式为：Pi —> βPi′Pｉ′—＞αPi′｜ε3)化简上述所得文法。

3、提取左因子的算法:Ａ—＞δβ1｜δβ2|…|δβn|γ１｜γ2|…|γｍ(其中,每个γ不以δ开头) 那么,可以把这些产生式改写成A —＞δA′｜γ1| γ２…|γｍA′—>β１|β2|…|βn4、利用上述算法,实现构造一个LL（1）文法:1）从文本文件ｇ．ｔｘｔ中读入文法,利用实验1的结果，存入实验１设计的数据结构；2）设计函数remove_left_ｒeｃｕrｓioｎ(）和remoｖｅ_left＿gｅne()实现消除左递归和提取左因子算法，分别对文法进行操作,消除文法中的左递归和提出左因子；3）整理得到的新文法;4）在一个新的文本文件neｗg．txt输出文法，文法输出按照一个非终结符号一行,开始符号引出的产生式写在第一行,同一个非终结符号的候选式用“｜”分隔的方式输出。

四、实验环境ＰC微机DOS操作系统或Wiｎdoｗｓ操作系统Turbo Ｃ程序集成环境或ViｓuａｌC＋+ 程序集成环境五、实验步骤１、学习LＬ（1）文法的分析条件;２、学习构造LL(1）文法的算法;3、结合实验１给出的数据结构，编程实现构造ＬＬ（1）文法的算法;4、结合实验1编程和调试实现对一个具体文法运用上述算法,构造它的LＬ（１）文法形式;5、把实验结果写入一个新建立的文本文件。

一、实验目的及要求1．掌握LL(1)分析法的基本原理；2．掌握LL(1)分析表的构造方法；3．用LL（1）分析法分析高级语言表达式。

4、了解LL（1）分析器的工作过程。

文法：无二义性的算术表达式的文法（1）把词法分析作为语法分析的子程序实现（5分）（2）独立的语法分析程序（4分）（3）对表达式文法消除左递归、构造LL（1）分析表（4）LL（1）分析表可以直接输入（4分），也可以用程序实现（5分）（5）给一个表达式，给出分析过程（分析栈、输入串、所用规则）（4分）（6）生成一个棵语法树（5分）用二叉树的形式表示出来二、实验内容及原理1、实验原理（1）、LL（1）文法的定义LL(1)分析法属于确定的自顶向下分析方法。

LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。

需要预测分析器对所给句型进行识别。

即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。

LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式A→α,A→β，都要满足下面条件：SELECT(A→α)∩SELECT(A→β)=∅（2）、预测分析表构造LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。

它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。

若用M表示LL(1)分析表，则M可表示如下：M: VN×VT→P∪{Error}M(A, t) = A→α，当t∈select(A→α) ，否则M(A, t) = Error其中P表示所有产生式的集合。

LL（1）⽂法分析表的构造和分析过程⽰例在考完编译原理之后才弄懂，悲哀啊。

不过懂了就好，知识吗，不能局限于考试。

⽂法：E→TE'E'→+TE'|εT→FT 'T'→*FT'|εF→id| (E)⼀、⾸先判断是不是 LL(1)⽂法--------------------------------------------------------------------------------------------------------⽂法G的任意两个具有相同左部的产⽣式 A --> α|β满⾜下列条件：1、如果α和β不能同时推导出ε，则 FIRST（α）∩FIRST(β) = 空2、α和β⾄多有⼀个能推导出ε3、如果β --*--> ε ,则 FIRST（α)∩ FOLLOW（A）＝空--------------------------------------------------------------------------------------------------------对于 E'→+TE'|ε，显然ε --> ε， First(+TE') = {+} ，Follow(E') = {{),#} 显然⼆者交集为空满⾜。

对于 F→id|(E) ，First(id) = {id} First((E)) = {(} 显然⼆者交集为空满⾜。

所以该⽂法是LL(1)⽂法。

⼆、计算出First集和Follow集参考：三、构建LL(1)分析表输⼊：⽂法G输出：分析表M步骤：1、对G中任意⼀个产⽣式 A --> α执⾏第2步和第3步2、for 任意a ∈ First(α)，将 A --> α填⼊M[A,a]3、if ε∈ First(α) then 任意a ∈ Follow(A)，将 A --> α填⼊M[A,a]if ε∈ First(α) & # ∈Follow(A)， then 将 A --> α填⼊M[A,#] （觉得这步没⽤）4、将所有没有定义的M[A,b] 标上出错标志（留空也可以）--------------------------------------------------------------------------------------------------------过程就不赘述了，结果：四、分析过程步骤：1、如果 X = a = # 则分析成功并停机2、如果 X = a != # 则弹出栈顶符号X, 并将输⼊指针移到下⼀个符号上3、如果 X != a，查询分析表M[X,a] , 如果 M[X,a] = {X --> UVW}，则⽤UVW (U在栈顶) 替换栈顶符号 X。