编译原理实验报告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。

fflush(stdin);
printf("Please input your chioc : ");
ch = getche();
printf("\n");
if(ch == 'I' || ch == 'i')
{
printf("Input a string end up with \'#\':");
gets(string);
i = strlen(string);
if(string[i-1] != '#')
{
string[i] = '#';
string[i+1] = '\0';
}
AnalysisProcess();
goto re2;
}
else if(ch == 'Q' || ch == 'q')
{
Quit();
return ;
int i;
int j;
count = 0;
ch = fgetc(f);
while(!feof(f))
{
if (ch == '-')
{
if ( (ch2=fgetc(f)) == '>' )
{
count++; //累计产生式的字符数条数
}
else
{
fseek(f,-1L, 1);
}
}//if
else if( ch == '|' )
fclose(f);
}//Input

青岛科技大学LL(1)分析编译原理实验报告学生班级__________________________学生学号__________________________学生姓名________________________________年 ___月 ___日一、实验目的LL(1)分析法的基本思想是：自项向下分析时从左向右扫描输入串，分析过程中将采用最左推导，并且只需向右看一个符号就可决定如何推导。

通过对给定的文法构造预测分析表和实现某个符号串的分析，掌握LL(1)分析法的基本思想和实现过程。

二、实验要求设计一个给定的LL(1)分析表，输入一个句子，能根据LL(1)分析表输出与句子相应的语法数。

能对语法数生成过程进行模拟。

三、实验内容（1）给定表达式文法为：G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i（2）分析的句子为:(i+i)*i四、模块流程五、程序代码#include<iostream>#include<stdio.h>#include <string>#include <stack>using namespace std;char Vt[]={'i','+','*','(',')','#'}; /*终结符*/char Vn[]={'E','e','T','t','F'}; /*非终结符*/ int LENVt=sizeof(Vt);void showstack(stack <char> st) //从栈底开始显示栈中的内容{int i,j;char ch[100];j=st.size();for(i=0;i<j;i++){ch[i]=st.top();st.pop();}for(i=j-1;i>=0;i--){cout<<ch[i];st.push(ch[i]);}}int find(char c,char array[],int n) //查找函数，返回布尔值{int i;int flag=0;for(i=0;i<n;i++){if(c==array[i])flag=1;}return flag;}int location(char c,char array[]) //定位函数,指出字符所在位置，即将字母转换为数组下标值{int i;for(i=0;c!=array[i];i++);return i;}void error(){cout<<" 出错!"<<endl;}void analyse(char Vn[],char Vt[],string M[5][6],string str){int i,j,p,q,h,flag=1;char a,X;stack <char> st; //定义堆栈st.push('#');st.push(Vn[0]); //#与识别符号入栈j=0; //j指向输入串的指针h=1;a=str[j];cout<<"步骤"<<"分析栈"<<"剩余输入串"<<" 所用产生式"<<endl;while(flag==1){cout<<h<<" "; //显示步骤h++;showstack(st); //显示分析栈中内容cout<<" ";for(i=j;i<str.size();i++) cout<<str[i]; //显示剩余字符串X=st.top(); //取栈顶符号放入X if(find(X,Vt,LENVt)==1) //X是终结符if(X==a) //分析栈的栈顶元素和剩余输入串的第一个元素相比较if (X!='#'){cout<<" "<<X<<"匹配"<<endl;st.pop();a=str[++j]; //读入输入串的下一字符}else{ cout<<" "<<"acc!"<<endl<<endl; flag=0;}else{error();break;}else{p=location(X,Vn); //实现下标的转换（非终结符转换为行下标）q=location(a,Vt); //实现下标的转换（终结符转换为列下标）string S1("NULL"),S2("null");if(M[p][q]==S1 || M[p][q]==S2) //查找二维数组中的产生式{error();break;} //对应项为空，则出错else{string str0=M[p][q];cout<<" "<<X<<"-->"<<str0<<endl; //显示对应的产生式st.pop();if(str0!="$") //$代表"空"字符for(i=str0.size()-1;i>=0;i--) st.push(str0[i]);//产生式右端逆序进栈}}}}main(){string M[5][6]={"Te" ,"NULL","NULL","Te", "NULL","NULL","NULL","+Te" ,"NULL","NULL","$", "$","Ft", "NULL","NULL","Ft", "NULL","NULL","NULL","$", "*Ft", "NULL","$", "$","i", "NULL","NULL","(E)", "NULL","NULL"}; //预测分析表j string str;int errflag,i;cout<<"文法：E->E+T|T T->T*F|F F->(E)|i"<<endl;cout<<"请输入分析串（以#结束）："<<endl;do{ errflag=0;cin>>str;for(i=0;i<str.size();i++)if(!find(str[i],Vt,LENVt)){ cout<<"输入串中包含有非终结符"<<str[i]<<"(输入错误)!"<<endl;errflag=1;}} while(errflag==1); //判断输入串的合法性analyse(Vn, Vt, M,str);return 0;}六、实验结果七、实验总结。

河南工业大学实验报告课程编译原理实验名称实验二 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)分析表的构造方法。

学号 E 专业计算机科学与技术姓名万学进实验日期2010-5-11教师签字成绩实验报告【实验名称】 LL（1）语法分析【实验目的】通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。

使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练掌握开发应用程序的基本方法。

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

构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。

分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。

【设计思想】（1）定义部分：定义常量、变量、数据结构。

（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。

【实验要求】1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。

2、如果遇到错误的表达式，应输出错误提示信息。

3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）S->TE（2）E->+TE|$（3）T->FM（4）M->*FM|$（5）F->(E)|i#【流程图】【源代码】#include<>#include<>int vnNum,grammarNum,vtNum=6;int order;int count=1;charGrammar[20][10],BlankTerminate[20][2] ;char First[5][4]={'S','(','i','\0','E','+','$','\0','T','(','i','\0','M','*','$','\0','F','(','i','\0'}; charFollow[5][6]={'S',')','#','\0','\0',' \0','E',')','#','\0','\0','\0','T','+',')','#','\0','\0','M','+',')','#','\0','\0','F','*','+',')','#','\0'};char Select[8][4]={'(','i','\0','\0','+','\0','\0','\0',')','#','\0','\0', '(','i','\0','\0','*','\0','\0','\0','+',')','#','\0','(','\0','\0','\0','i','\0','\0','\0'};int IndiBlanket[6][7];char VT[10]={'i','+','*','(',')','#'};typedef struct {char *base;char *top;int stacksize;}AnalStack;AnalStack S;int ScanGrammar(){FILE *fp=fopen("文法.txt","r"); FILE *tp;char singleChar,nextChar;int i=0,j=0;while(!feof(fp)){fscanf(fp,"%c",&singleChar);if(singleChar=='#'){Grammar[i][j]='\0';break;}if(singleChar=='\n'){Grammar[i][j]='\0';i++;j=0;continue;}if(singleChar=='-'){tp=fp;fscanf(tp,"%c",&nextChar);if(nextChar=='>'){fp=tp;continue;}}if(singleChar=='|'){Grammar[i+1][0]=Grammar[i][0];Grammar[i][j]='\0';i++;j=1;continue;}Grammar[i][j]=singleChar;j++;}// printf("输入的文法：\n");for(int k=0;k<=i;k++){j=0;while(Grammar[k][j]!='\0'){if(j==1){// printf("->");}//printf("%c",Grammar[k][j]);j++;}// printf("\n");}// printf("%d\n",i);fclose(fp);return i;}int Fill(char gi,char sij,int grammarOrder){int i,j;for(i=0;i<vnNum;i++){if(First[i][0]==gi)break;}j=0;while(VT[j]!='\0'){if(VT[j]==sij)break;j++;}IndiBlanket[i][j]=grammarOrder;return 0;}int Indicate(){int i,j;for(i=0;i<vnNum;i++){for(j=0;j<vtNum;j++){IndiBlanket[i][j]=-1;}}for(i=0;i<=grammarNum;i++){j=0;while(Select[i][j]!='\0'){Fill(Grammar[i][0],Select[i][j],i );j++;}}printf("预测分析表如下：\n");for(i=0;i<vnNum;i++){for(j=0;j<vtNum;j++){printf("%3d",IndiBlanket[i][j]);}printf("\n");}return 0;}int Terminate_$(int grammarNum){int j=0;int count;for(int i=0;i<=grammarNum;i++){BlankTerminate[i][1]='0';}BlankTerminate[0][0]=Grammar[0][0];if(Grammar[0][1]=='$'){BlankTerminate[0][1]='1';}count=1;for(i=1;i<=grammarNum;i++){for(j=0;j<count;j++){if(Grammar[i][0]==BlankTerminate[ j][0]){if(Grammar[i][1]=='$'){BlankTerminate[j][1]='1';break;}}}if(j==count){BlankTerminate[count][0]=Grammar[i][0 ];if(Grammar[i][1]=='$'){BlankTerminate[count][1]='1';}count++;}}count--;// printf("$的终结符表：\n");/*for(i=0;i<j;i++){printf("%c：%c\n",BlankTerminate[i][0],BlankTerminate[i][1]);}*/return count;}AnalStack InitStack(){=(char *)malloc(100*sizeof(char));if(!exit(1);=;=100;*='#';++;*='S';return S;}int Print(char AnalStr[],int i,int sign){int startpos=i;printf("%d\t",count);count++;char *p=;while(p!=+2){printf("%c",*p);p++;}printf("\t");while(AnalStr[i]!='\0'){printf("%c",AnalStr[i]);i++;}printf("\t\t");if(sign==0){int j=0;while(Grammar[order][j]!='\0'){printf("%c",Grammar[order][j]);if(j==0)printf("->");j++;}printf("\n");}if(sign==1){printf("%c匹配\n",AnalStr[startpos]);}return 0;}int Push(char topChar,char curChar,int sign,int ii,char AnalStr[]){int i,j;for(i=0;i<vnNum;i++){if(First[i][0]==topChar)break;}j=0;while(VT[j]!='\0'){if(VT[j]==curChar)break;j++;}order=IndiBlanket[i][j];Print(AnalStr,ii,sign);j=1;while(Grammar[order][j]!='\0'){j++;}j--;while(j!=0){if(Grammar[order][j]!='$'){++;*=Grammar[order][j];}j--;}return 0;}int Analysis(){int i=0;int sign=0;int count=1;char curChar;InitStack();char AnalStr[10]={'\0'};printf("输入产生式：\n");scanf("%s",&AnalStr);printf("步骤\t分析栈\t剩余输入串\t产生式\n");while(AnalStr[i]!='\0'){sign=0;curChar=AnalStr[i];char *p=;char topChar=*p;;if(topChar<'A'||topChar>'Z'){if(topChar==curChar){sign=1;Print(AnalStr,i,sign);i++;continue;}else{printf("Analysis ERROR!\n");return 0;}}if(topChar=='#'){if(topChar==curChar){Print(AnalStr,i,sign);break;}else{return 0;}}else{Push(topChar,curChar,sign,i,AnalS tr);}}printf("预测分析成功!\n");return 0;}int main(){int i,m;grammarNum=ScanGrammar();vnNum=Terminate_$(grammarNum); // printf("Select集:\n");for(i=0;i<=grammarNum;i++){m=0;while(Select[i][m]!='\0'){// printf("%c",Select[i][m]);m++;}// printf("\n");}Indicate();Analysis();return 0;}【运行结果】。

ll1文法实验报告LL1文法实验报告引言LL1文法是一种重要的上下文无关文法，它在编译原理和自然语言处理等领域有着广泛的应用。

本实验旨在通过对LL1文法的分析和实验，探讨其在语法分析中的作用和应用。

实验目的1. 了解LL1文法的定义和特性；2. 分析LL1文法的构造和推导规则；3. 编写一个简单的LL1文法，并进行语法分析；4. 探讨LL1文法在实际应用中的局限性和改进方法。

实验过程首先，我们对LL1文法进行了深入的了解和学习，明确了其定义和特性。

LL1文法是一种上下文无关文法，具有唯一的左推导和右推导，且能够通过预测分析方法进行语法分析。

其构造和推导规则十分严格，要求每个非终结符的每个产生式的首符集都不能相交，且每个非终结符的产生式必须按照首符集进行分组。

接着，我们编写了一个简单的LL1文法，并进行了语法分析。

通过对文法的构造和推导规则进行分析，我们成功地实现了对输入字符串的语法分析，并得出了正确的语法树。

这表明LL1文法在语法分析中具有较高的准确性和可靠性。

然而，在实际应用中，我们也发现了LL1文法的局限性。

由于其严格的构造和推导规则，很多复杂的语法无法直接用LL1文法表示，需要进行一定的改进和优化。

因此，我们对LL1文法进行了进一步的探讨和改进，提出了一些解决方案和改进方法，以更好地满足实际应用的需求。

结论通过本次实验，我们对LL1文法有了更深入的了解和认识，明确了其在语法分析中的作用和应用。

同时，我们也发现了LL1文法的局限性，并提出了一些改进方法。

我们相信，在今后的研究和实践中，LL1文法将会得到更广泛的应用和发展。

计算机硬件实验室实验报告根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。

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

二、实验要求：对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG（2）G->+TG|—TG（3）G->ε（4）T->FS（5）S->*FS|/FS（6）S->ε（7）F->(E)（8）F->i输出的格式如下：(1)LL（1）分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串(3)输出过程如下：步骤分析栈剩余输入串所用产生式1 E i+i*i# E->TG(4)输入符号串为非法符号串(或者为合法符号串)备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。

(2) 在此位置输入符号串为用户自行输入的符号串。

(3)上述描述的输出过程只是其中一部分的。

注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；三、实验过程：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。

2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。

3.程序编写（1）定义部分：定义常量、变量、数据结构。

（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。

四、实验结果：（1）写出程序流程图（2）给出运行结果示例程序：注意：本示例只要修改分析的句子即可，不要改写文法/*LL(1)分析法源程序，只能在VC++中运行*/#include<stdio.h>#include<stdlib.h>#include<string.h>#include<dos.h>char A[20];/*分析栈*/char B[20];/*剩余串*/char v1[20]={'i','+','-','*','/','(',')','#'};/*终结符*/char v2[20]={'E','G','T','S','F'};/*非终结符*/int j=0,b=0,top=0,l;/*L为输入串长度*/typedef struct type/*产生式类型定义*/{char origin;/*大写字符*/char array[5];/*产生式右边字符*/int length;/*字符个数*/}type;type e,t,g,g1,g2,s,s2,s1,f,f1;/*结构体变量*/type C[10][10];/*预测分析表*/void print()/*输出分析栈*/{int a;/*指针*/for(a=0;a<=top+1;a++)printf("%c",A[a]);printf("\t\t");}/*print*/void print1()/*输出剩余串*/{int j;for(j=0;j<b;j++)/*输出对齐符*/printf(" ");for(j=b;j<=l;j++)printf("%c",B[j]);printf("\t\t\t");}/*print1*/void main(){int m,n,k=0,flag=0,finish=0;char ch,x;type cha;/*用来接受C[m][n]*//*把文法产生式赋值结构体*/e.origin='E';strcpy(e.array,"TG");e.length=2;t.origin='T';strcpy(t.array,"FS");t.length=2;g.origin='G';strcpy(g.array,"+TG");g.length=3;g1.origin='G';strcpy(g1.array,"-TG");g1.length=3;g2.origin='G';g2.array[0]='^';g2.length=1;/////////////////////////////////////////////s.origin='S';strcpy(s.array,"*FS");s.length=3;s1.origin='S';strcpy(s1.array,"/FS");s1.length=3;s2.origin='S';s2.array[0]='^';s2.length=1;////////////////////////////////f.origin='F';strcpy(f.array,"(E)");f.length=3;f1.origin='F';f1.array[0]='i';f1.length=1;for(m=0;m<=4;m++)/*初始化分析表*/for(n=0;n<=5;n++)C[m][n].origin='N';/*全部赋为空*//*填充分析表*///char v1[20]={'i','+','-','*','/','(',')','#'};/*终结符*///char v2[20]={'E','G','T','S','F'};/*非终结符*/C[0][0]=e;C[0][5]=e;C[1][1]=g;C[1][2]=g1;C[1][3]=C[1][4]=C[1][7]=g2;C[2][0]=t;C[2][3]=t;C[2][5]=t;C[3][1]=C[3][2]=s2;C[3][3]=s;C[3][4]=s1;C[3][6]=C[3][7]=s2;C[4][0]=f1; C[4][5]=f;printf("LL(1)分析程序，编制人：武普泉，20号，1020562班\n");printf("输入一以#结束的符号串(包括+ - * / () i #)：");do/*读入分析串*/{scanf("%c",&ch);if ((ch!='i') &&(ch!='+') &&(ch!='-')&&(ch!='*')&&(ch!='/')&&(ch!='(')&&(ch!=')')&&(ch!='#')) {printf("输入串中有非法字符\n");exit(1);}B[j]=ch;j++;}while(ch!='#');l=j;/*分析串长度*/ch=B[0];/*当前分析字符*/A[top]='#'; A[++top]='E';/*'#','E'进栈*/printf("步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n");do{x=A[top--];/*x为当前栈顶字符*/printf("%d",k++);printf("\t\t");for(j=0;j<=7;j++)/*判断是否为终结符*/if(x==v1[j]){flag=1;break;}if(flag==1)/*如果是终结符*/{if(x=='#'){finish=1;/*结束标记*/printf("acc!\n");/*接受*/getchar();getchar();exit(1);}/*if*/if(x==ch){print();print1();printf("%c匹配\n",ch);ch=B[++b];/*下一个输入字符*/flag=0;/*恢复标记*/}/*if*/else/*出错处理*/{print();print1();printf("%c出错\n",ch);/*输出出错终结符*/exit(1);}/*else*/}/*if*/else/*非终结符处理*/{for(j=0;j<=4;j++)if(x==v2[j]){m=j;/*行号*/break;}for(j=0;j<=7;j++)if(ch==v1[j]){n=j;/*列号*/break;}cha=C[m][n];if(cha.origin!='N')/*判断是否为空*/{print();print1();printf("%c->",cha.origin);/*输出产生式*/for(j=0;j<cha.length;j++)printf("%c",cha.array[j]);printf("\n");for(j=(cha.length-1);j>=0;j--)/*产生式逆序入栈*/A[++top]=cha.array[j];if(A[top]=='^')/*为空则不进栈*/top--;}/*if*/else/*出错处理*/{print();print1();printf("%c出错\n",x);/*输出出错非终结符*/exit(1);}/*else*/}/*else*/}while(finish==0);}/*main*。

LL(1)语法分析器的构造摘要语法分析的主要任务是接收词法分析程序识别出来的单词符由某种号串，判断它们是否语言的文法产生，即判断被识别的符号串是否为某语法部分。

一般语法分析常用自顶向下方法中的LL分析法，采用种方法时，语法分程序将按自左向右的顺序扫描输入的的符号串，并在此过程中产生一个句子的最左推导，即LL是指自左向右扫描，自左向右分析和匹配输入串。

经过分析，我们使用VC++作为前端开发工具，在分析语法成分时比较方便直观，更便于操作。

运行程序的同时不断修正改进程序，直至的到最优源程序。

关键字语法分析文法自顶向下分析 LL(1)分析最左推导AbstractGrammatical analysis of the main tasks was to receive lexical analysis procedure to identify the words from a website, string, and judge whether they have a grammar of the language, that is, judging by the series of symbols to identify whether a grammar part. General syntax analysis commonly used top-down methods of LL analysis, using methods, Grammar hours will be from the procedures of the order left-to-right scanning input string of symbols, and in the process produced one of the most left the sentence is derived, LL is scanned from left to right, From left to right analysis and matching input strings. After analysis, we use VC + + as a front-end development tool for the analysis of syntax ingredients more convenient visual, more easy to operate. Operational procedures at the same time constantly improving procedures, until the source of optimal .Key WordsGrammatical analysis grammar Top-down analysis LL (1) AnalysisMost left Derivation目录摘要 (1)引言 (3)第一章设计目的 (4)第二章设计的内容和要求 (5)2.1 设计内容 (5)2.2 设计要求 (5)2.3 设计实现的功能 (5)第三章设计任务的组织和分工 (6)3.1 小组的任务分工 (6)3.2 本人主要工作 (6)第四章系统设计 (9)4.1 总体设计 (9)4.2 详细设计 (9)第五章运行与测试结果 (22)5.1 一组测试数据 (22)5.2 界面实现情况 (23)第六章结论 (27)课程设计心得 (28)参考文献 (29)致谢 (30)附录（核心代码清单） (31)引言编译器的构造工具是根据用户输入的语言的文法，编译器的构造工具可以生成程序来处理以用户输入的文法书写的文本。

实验三语法分析---LL（1）分析器目录一. 实验的目的与思路 (2)（1）目的 (2)（2）思路 (2)二. 基本的功能 (3)三．总体设计 (4)四．详细设计 (5)五.源程序清单 (6)六.源代码 (6)....................................................................................................................................................一. 实验的目的与思路（1）目的1. 用程序的方法实现语法分析的LL（1）方法。

（2）思路本程序是采用的LL（1）方法进行的语法分析，而LL（1）的分析方法是属于自上而下的方法。

自上而下分析的基本思想是：对任意输入串，试图用一切可能的方法，从文法开始符号（根结点）出发，自上而下为输入串建立一棵语法树。

从推导的角度看，它是从文法的开始符号出发，反复使用各种产生式，寻找与输入串匹配的推导。

在输入之前必须要进行该文法是不是LL（1）文法的判断，然后再构造相应的LL（1）分析表来用预测分析方法进行语法分析，依据下面的文法及分析表来设计程序实现预测分析的分析过程。

1.文法G[E]：E --> E+T|TT --> T*F|FF --> (E) | i2.通过观察可知道该文法是一个左递归文法，要进行语法分析就必须消除左递归才能继续判断它是不是LL（1）文法，然后才能用预测分析方法进行语法分析。

3.消除左递归：E -->TMM --> +TM|uT --> FQQ --> *FQ|uF --> (E) | i4.在进行LL（1）文法的判断：（1.）各非终结符的FIRST集如下：FIRST（E）= FIRST（TM）= {（，i }FIRST（M）= { + }FIRST（T）= {（，i }FIRST（Q）= { * }FIRST（F）= { （，i }（2.）各非终结符的FOLLOW集如下：FOLLOW（E）= { ），# }FOLLOW（M）= { ），# }FOLLOW（T）= { + ，），# }FOLLOW（Q）= { + ，），# }FOLLOW（F）= { * ，+ ，），# }（3.）各产生式的SELECT集如下：SELECT（E→TM）={ ( ,i }SELECT（M→+TM）={+}SELECT（M→u）={ }, #}SELECT（T→FQ）={ ( ,i }SELECT（Q→*FQ）={ *}SELECT（Q→u）={ +，), # }SELECT（F→(E)）={ ( )SELECT（F→i）={ i }因为：SELECT（M→+TM）∩SELECT（M→u）=ФSELECT（Q→*FQ）∩SELECT（Q→u）=ФSELECT（F→(E)）∩SELECT（F→i）=Ф因此可以判断该文法是一个LL（1）文法可以构造预测分析表。