下载文档原格式
实验5 语法分析程序的设计（2）一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。
二、实验内容设计一个文法的算法优先分析程序，判断特定表达式的正确性。
三、实验要求1、给出文法如下：G[E]E->T|E+T;T->F|T*F;F->i|(E);2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式；1、给出算符优先分析算法如下：k:=1; S[k]:=‘#’;REPEAT把下一个输入符号读进a中；IF S[k]∈V T THEN j:=k ELSE j:=k-1;WHILE S[j] a DOBEGINREPEATQ:=S[j];IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2UNTIL S[j] Q把S[j+1]…S[k]归约为某个N；k:=j+1;S[k]:=N;END OF WHILE;IF S[j] a OR S[j] a THENBEGINk:=k+1;S[k]:=aENDELSE ERRORUNTIL a=‘#’1、根据给出算法，利用适当的数据结构实现算符优先分析程序；2、利用算符优先分析程序完成下列功能：1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束；2）读入文本文件中的表达式；3）调用实验2中的词法分析程序搜索单词；4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。
四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C++ 程序集成环境五、实验步骤1、分析文法中终结符号的优先关系；2、存放优先关系或构造优先函数；3、利用算符优先分析的算法编写分析程序；4、写测试程序，包括表达式的读入和结果的输出；5、程序运行效果，测试数据可以参考下列给出的数据。
编译原理上机实验报告小组成员：王金名、周攀、汪国辉、澎湃、王帅、齐娟娟、刘鸳鸳一、实验目的：了解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语法分析。
实验5LL语法分析程序的设计与实现引言：LL语法分析器是一种自顶向下的语法分析方法，它从语法开始符号开始，通过向前看的一个或者多个输入符号预测产生式的选择，并且通过栈来保存未处理的非终结符。
本实验将设计并实现一个LL语法分析器，包括设计程序的数据结构，算法以及实现细节，并进行相应的测试。
设计概述：1. 实验环境：本实验采用Java编程语言进行实现。
2.数据结构：本实验的数据结构包括文法集合、FIRST集合和FOLLOW 集合、预测分析表等。
3.算法：a)根据给定的文法，构建文法集合和FIRST集合和FOLLOW集合。
b)根据构建的文法集合、FIRST集合和FOLLOW集合，构建预测分析表。
c)根据预测分析表，进行语法分析，实现LL语法分析器。
4.实现细节：本实验实现的LL语法分析器具备错误恢复和语法错误报告的功能。
具体设计与实现：1.构建文法集合：读取给定的文法文件，将每条文法规则分解成产生式的推导式，构建文法集合。
2.构建FIRST集合和FOLLOW集合：遍历文法集合，根据FIRST集合和FOLLOW集合的定义，递归计算每个非终结符的FIRST集合和FOLLOW集合。
3.构建预测分析表：根据构建的文法集合、FIRST集合和FOLLOW集合，生成预测分析表。
4.语法分析过程：根据预测分析表，进行语法分析。
具体过程如下：a)初始化分析栈和输入串，将开始符号和输入串的结束符号入栈；b)重复以下步骤：i)如果栈顶元素是终结符且与输入符号相同，则将栈顶元素出栈，输入串指针前移；ii) 如果栈顶元素是非终结符，则根据预测分析表，选择产生式进行推导，并将该产生式右侧的符号逆序入栈；iii) 如果栈顶元素是结束符号且输入指针也指向结束符号，分析成功；iv) 如果输入指针指向错误的终结符，进行错误恢复处理；v)如果预测分析表中没有对应的产生式，进行错误恢复处理。
5.错误恢复：错误恢复是语法分析器中一个重要的功能，它通过跳过错误符号，继续进行下一步分析来恢复错误。
专题3_LL(1)语法分析设计原理与实现李若森 13281132 计科1301一、理论传授语法分析的设计方法和实现原理；LL(1) 分析表的构造；LL(1)分析过程；LL(1)分析器的构造。
二、目标任务实验项目实现LL(1)分析中控制程序（表驱动程序）；完成以下描述算术表达式的 LL(1)文法的LL(1)分析程序。
G[E]:E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→(E)|iA→+|-M→*|/设计说明终结符号i为用户定义的简单变量，即标识符的定义。
加减乘除即运算符。
设计要求(1)输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的输出结果，输出为输入串是否为该文法定义的算术表达式的判断结果；(2)LL(1)分析程序应能发现输入串出错；(3)设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。
任务分析重点解决LL(1)表的构造和LL(1)分析器的实现。
三、实现过程实现LL(1)分析器a)将#号放在输入串S的尾部b)S中字符顺序入栈c)反复执行c)，任何时候按栈顶Xm和输入ai依据分析表，执行下述三个动作之一。
构造LL(1)分析表构造LL(1)分析表需要得到文法G[E]的FIRST集和FOLLOW集。
构造FIRST(α)构造FOLLOW(A)构造LL(1)分析表算法根据上述算法可得G[E]的LL(1)分析表，如表3-1所示：表3-1 LL(1)分析表主要数据结构pair<int, string>:用pair<int, string>来存储单个二元组。
该对照表由专题1定义。
map<string, int>:存储离散化后的终结符和非终结符。
vector<string>[][]:存储LL(1)分析表函数定义init:void init();功能：初始化LL(1)分析表，关键字及识别码对照表，离散化（非）终结符传入参数：（无）传出参数：（无）返回值：（无）Parse:bool Parse( const vector<PIS> &vec, int &ncol )；功能：进行该行的语法分析传入参数：vec:该行二元式序列传出参数：emsg:出错信息epos:出错标识符首字符所在位置返回值：是否成功解析。
LL1语法分析程序实验报告实验目的：通过编写LL(1)语法分析程序，加深对语法分析原理的理解，掌握语法分析方法的实现过程，并验证所编写的程序的正确性。
实验准备：1.了解LL(1)语法分析的原理和步骤；2.根据语法规则，构建一个简单的文法；3.准备一组测试用例，包括符合语法规则的输入和不符合语法规则的输入。
实验步骤：1.根据文法规则，构建预测分析表；2.实现LL(1)语法分析程序；3.编写测试用例进行测试；4.分析测试结果。
实验结果：我根据上述步骤，编写了一个LL(1)语法分析程序，并进行了测试。
以下是我的测试结果：测试用例1:输入：9+7*(8-5)分析结果：成功测试用例2:输入：3+*5分析结果：失败测试用例3:输入：(3+5)*分析结果：失败测试用例4:输入：(3+5)*2+4分析结果：成功分析结果符合预期，说明我编写的LL(1)语法分析程序是正确的。
在测试用例1和测试用例4中，分析结果是成功的，而在测试用例2和测试用例3中，分析结果是失败的，这是因为输入不符合文法规则。
实验总结：通过本次实验，我进一步理解了LL(1)语法分析的原理和步骤。
编写LL(1)语法分析程序不仅要根据文法规则构建预测分析表，还要将预测分析表与输入串进行比对，根据匹配规则进行预测分析，最终得到分析结果。
在实验过程中，我发现在构建预测分析表和编写LL(1)语法分析程序时需要仔细思考和调试才能保证正确性。
通过本次实验，我对语法分析方法的实现过程有了更深入的认识，对于将来在编译原理方面的学习和工作有了更好的准备。
LL(1)语法分析设计原理与实现技术实验计科100X班 10284XXX程序设计功能实现LL(1)分析中控制程序（表驱动程序）；完成以下描述算术表达式的LL(1)文法的LL(1)分析程序。
G[E]: E→TE′E′→ATE′|εT→FT′T′→MFT′|εF→(E)|iA→+|-M→*|/说明：终结符号i 为用户定义的简单变量,即标识符的定义。
主要数据结构描述由文法可得：对于E：FIRST( E )= {(, i }对于E’: FIRST( E’ ) ={+，−，ε}对于T: FIRST( T )= ={(, i }对于T’: FIRST( T’)= ={*，∕，ε}对于F: FIRST( F )= ={(, i }对于A: FIRST( A )= ={+, - }对于M: FIRST(M)= ={*, / }由此我们容易得出各非终结符的FOLLOW集合如下：FOLLOW( E )= { )，#}FOLLOW(E’) ={ )，#}FOLLOW( T ) ={+，−，)，#}FOLLOW( T’ ) = FOLLOW( T ) ={+，−，)，#}FOLLOW( F )=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，−，)，#}FOLLOW( A )= { (, i }FOLLOW( M )= { (, i}文法LL(1)的预测分析表(表1)：表1. LL(1)预测分析表注：为编程方便，在程序中，将E’、T’改为G、S程序结构描述1.设计方法:程序通过从文本文档读入数据，将所读数据以空格、回车或者退格为标示符，分为字符串，对字符串进行词法分析，最后将所有字符串按序输出到结果文档中，并在结果文档中标明每个字符串的类别序号。
2、程序中主要函数定义和调用关系如下：函数：void print()作用：输出分析栈void print1();作用：输出剩余串int main();作用：主要逻辑功能程序执行图如下：实验结果测试用例1：i+i*i#测试用例2：i-i++#实验总结相对于递归下降分析法，LL(1)分析法更为有效．采用此种方法的分析器由一张预测分析表（LL(1)分析表）、一个控制程序（表驱动程序）和一个分析栈组成，预测分析表中个元素的含义是：或者指出当前推到所应使用过的产生式，或者指出输入符号串中存在语法错误．LL(1)分析法的局限在于：只能分析LL(1)文法或者某些非LL(1)文法，但需先将其改造成LL(1)文法。
语法分析器设计实验报告一、引言语法分析器是编译器中的重要组成部分，其主要功能是根据给定的文法规则，对输入的程序代码进行语法分析，判断其是否符合语法规范。
本实验旨在设计一个简单的语法分析器，通过实际实现一个基于LL(1)文法的语法分析器，深入了解语法分析的原理和实现方法。
二、实验目标本实验的目标是设计一个能够接受一个输入的程序代码并进行语法分析的程序。
具体而言，需要实现以下功能：1. 构建一个文法规则集合，用于描述程序代码的语法规范；2. 设计并实现一个LL(1)分析表，用于存储语法分析所需的预测分析表；3. 实现语法分析器，能够根据输入的程序代码，逐步地进行语法分析，并输出相应的结果。
三、实验环境本实验使用的是Java语言进行实现，操作系统环境为Windows 10。
使用的集成开发环境为Eclipse。
四、实验步骤1. 设计文法规则集合在语法分析器设计中，首先需要设计一个文法规则集合，用于描述需要分析的程序代码的语法规范。
文法规则集合的设计要符合LL(1)文法的要求，即每个非终结符的产生式至多有一个与输入符号串首符号相关的产生式。
2. 构建LL(1)分析表根据文法规则集合，构建一个LL(1)分析表，用于存储语法分析所需的预测分析表。
LL(1)分析表是一个二维表，其中行表示非终结符，列表示终结符。
表中的每个元素表示相应的产生式编号，用于指示语法分析器在分析过程中应该使用哪个产生式。
构建LL(1)分析表的方法包括：- 遍历文法规则集合，计算每个非终结符的FIRST集合和FOLLOW集合；- 根据计算得到的FIRST集合和FOLLOW集合，填充LL(1)分析表。
3. 实现语法分析器根据LL(1)分析表，实现一个语法分析器。
语法分析器的输入是一个程序代码，输出是语法分析器的分析结果。
实现语法分析器的主要过程包括：- 初始化分析栈，将文法规则的开始符号入栈；- 从输入的程序代码中读取下一个终结符；- 如果分析栈的栈顶是非终结符，根据LL(1)分析表中对应的产生式编号，将产生式右部的符号依次入栈；- 如果分析栈的栈顶是终结符，并且与输入的终结符相同，则将该终结符出栈，并继续读取下一个终结符；- 重复上述过程，直到分析栈为空或者无法继续推导。
语法分析实验报告一: 实验内容:编写语法分析程序, 实现对算术表达式的语法分析, 要求所分析的算术表达式由如下的文法产生。
E->E+T|E-T|TT->T*F|T/F|FF->id|(E)|num二: 实验要求:在对表达式进行分析的同时, 输出所采用的产生式。
1.编写LL(1)语法分析程序, 要求:编程实现算法4.2, 为给定的文法自动构造预测分析表编程实现算法4.1, 构造LL(1)预测分析程序,2.编写语法分析程序, 实现自底向上的分析, 要求：构造识别所有活前缀的DFA构造LR分析表编程实现算法4.3, 构造LR分析程序1.三: 实验分析:2.方法二（编写LL(1)语法分析程序）1.步骤:（1）根据题目所给出的文法构造相应的无左递归文法, 并求出该文法各非终结符的FIRST、FOLLOW集合；（2）构造文法的LL(1)分析表；（3）由此构造LL分析程序。
2.实现方法:1.输入缓冲区为一个字符型数组, 读入输入的算术表达式并保存在此, 以’$’结束；2.为构造文法的LL(1)分析表, 构建一个相对应的字符串数组；3.在实际程序中P代表E', Q代表T', e代表ε,i代表id, n代表num;4.处理输入表达式中代表id和num的子串, 分别将它们转化为'i'和'n'进行分析;5.LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。
对于任何（X，a），总控程序每次都执行下述三种可能的动作之一:(1)若X = a =‘$’, 则宣布分析成功, 停止分析过程。
(2)若X = a!=‘$’, 则把X从STACK栈顶弹出, 让a指向下一个输入符号。
①如果是终结符合, 则栈不加入新符号②如果是非终结符合, 则把表达式右边入栈(3)若M[A, a]中存放着“出错标志”, 则调用出错诊断程序ERROR。
实验五LL（1)文法识别程序设计一、实验目的通过LL（1）文法识别程序的设计理解自顶向下的语法分析思想。
二、实验重难点FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。
三、实验内容与要求实验内容：1．阅读并理解实验案例中LL(1)文法判别的程序实现；2．参考实验案例，完成简单的LL（1)文法判别程序设计。
四、实验学时4课时五、实验设备与环境C语言编译环境六、实验案例1．实验要求参考教材93页预测分析方法，94页图5。
11 预测分析程序框图,编写表达式文法的识别程序。
要求对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子,并能给出分析过程。
表达式文法为：E→E+T｜TT→T*F|FF→i|(E）2．参考代码为了更好的理解代码，建议将图5。
11做如下标注:/* 程序名称：LL（1)语法分析程序＊//* E—>E+T|T *//* T—〉T＊F｜F *//＊F—〉(E）｜i *//＊目的：对输入LL(1）文法字符串,本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。
/*＊**＊＊*＊*＊*＊*＊＊*＊*＊＊**＊＊＊＊***＊＊＊＊＊****＊*＊＊＊＊//＊程序相关说明*//＊A=E’ B=T' ＊//* 预测分析表中列号、行号＊//＊0=E 1=E' 2=T 3=T' 4=F *//＊0=i 1=+ 2=＊3=（4=) 5=# ＊//＊＊**＊＊*＊***＊****＊＊*＊＊＊＊＊＊*＊＊*＊*＊＊**＊/#include”iostream”#include ”stdio。
h”＃include "malloc。
h"＃include ”conio。
h”/*定义链表这种数据类型参见:http：//wenku。
baidu。
com/link?url=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKlNvkCk0qWqvFFxj gO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS#＃#＊/struct Lchar{char char_ch；struct Lchar ＊next；｝Lchar,＊p，＊h，*temp,*top，*base;/＊p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/char curchar；//存放当前待比较的字符：终结符char curtocmp；//存放当前栈顶的字符:非终结符int right；int table［5]［6］={{1，0，0，1，0,0},｛0,1,0，0，1,1｝,{1,0，0,1，0，0｝,{0，1,1,0,1,1}，{1，0,0，1,0，0｝}；/＊存放预测分析表，1表示有产生式，0表示无产生式。
*/ int i,j;void push(char pchar）/＊入栈函数＊/｛temp=(struct Lchar＊)malloc(sizeof（Lchar））；temp—〉char_ch=pchar;temp->next=top;top=temp；｝void pop（void）/＊出栈函数＊/{curtocmp=top—〉char_ch;if（top—〉char_ch!=’#’）top=top—>next；}void doforpush（int t) /*根据数组下标计算的值找对应的产生式，并入栈*/{switch(t）{case 0：push('A');push（'T'）;break；case 3：push（'A'）;push（'T');break;case 11：push（’A')；push（'T’);push（'+');break；case 20:push（'B’)；push（’F'）;break；case 23:push（'B');push（’F'）；break;case 32:push('B')；push(’F’）；push（'＊'）;break;case 40:push('i’）；break;case 43：push(')’)；push('E’)；push(’('）；}}/*根据curchar和curtocmp转为数字以判断是否有产生式*/void changchartoint(）{switch（curtocmp）/*非终结符：栈顶＊/｛cas e ’E’：i=0;break;case ’A’:i=1;break；case 'T’:i=2；break;case 'B':i=3;break；case 'F':i=4；｝switch(curchar）/＊终结符:待识别的表达式中＊/｛case ’i’：j=0；break;case '+’：j=1；break；case ’*’：j=2；break;case '('：j=3；break;case ’）':j=4;break；case ’#’：j=5;｝｝/＊识别算法*/void dosome（void)｛int t；for（;；)｛pop();/＊读取栈顶的字符存curtocmp中*/curchar=h-〉char_ch；/＊读取输入字符链表h中一个字符存入curchar＊/printf(”\n%c\t%c”,curchar,curtocmp)；if(curtocmp==’#' ＆＆curchar==’＃’) /＊如果都是终结符P94 图5。
11圈1、圈5、圈7*/break；if（curtocmp=='A’||curtocmp=='B’｜｜curtocmp==’E’||curtocmp=='T'|｜curtocmp=='F') /＊如果curtocmp不是终结符P94 图5。
11圈1*/{if（curtocmp！='＃') /＊如果curtocmp不是终结符，也不是结束符，则根据预测分析表找到产生式并入栈P94 图5。
11圈1＊/{changchartoint(）；if（table［i][j］）/＊[1。
1]有产生式P94 图5。
11圈2＊/{t=10＊i+j; /＊计算产生式在数组中的位置＊/doforpush(t); /＊找对应t的产生式并入栈P94 图5.11圈3＊/continue;｝else/*［1。
2]没有产生式P94 图5。
11圈4＊/｛right=0；/＊出错＊/break；｝}else if（curtocmp!=curchar) /*如果curtocmp不是终结符，并且是结束符，判断终结符链表字符是否也为终结符P94 图5。
11圈1、1、5、6＊/{right=0; /*出错＊/break;}elsebreak；/*正确P94 图5。
11圈1、1、5、7*/｝else if（curtocmp！=curchar）/＊如果curtocmp是终结符,并且不等于当前终结符链表中的终结符，则出错。
P94 图5。
11圈1、8、9*/{right=0; /*出错＊/break；｝else /＊如果curtocmp是终结符，并且等于当前终结符链表中的终结符,则匹配成功，可以读取下一个链表头的终结符P94 图5.11圈10＊/{h=h->next; /*读取下一字符*/continue；｝}｝int main（void）｛char ch；right=1；base=（struct Lchar＊）malloc(sizeof（Lchar）); /＊初始化非终结符堆栈，栈底为＃,栈顶为文法开始符号*/base-〉next=NULL；base—>char_ch=’#’;temp=（struct Lchar*)malloc（sizeof(Lchar））;temp-〉next=base；temp—〉char_ch='E'；top=temp；/＊初始化非终结符堆栈,栈底为#，栈顶为文法开始符号E＊//＊初始化存放待识别的表达式（终结符）的线性链表头＊/h=（struct Lchar*)malloc（sizeof（Lchar))；h->next=NULL;p=h; /＊开辟了一个空的链表空间,p和h同时指向该空间,该空间将作为终结符链表的头部.＊/printf（”请输入要分析的字符串（＃号结束）\n”)；do{ /＊输入待识别的表达式＊/ch=getch(）；putch(ch)；//在屏幕上输出一个字符if（ch==’i’|｜ch==’+’||ch=='*’|｜ch==’（’｜｜ch==')’｜|ch==’＃’)｛/*将输入的ch存入链表＊/temp=(struct Lchar＊）malloc（sizeof（Lchar））;temp-〉next=NULL;temp->char_ch=ch;h—〉next=temp；h=h-〉next;/＊如果输入正确，h不断的指向新输入的字符，而p始终指向输入终结符字符串的头位置,即前面开辟的空的链表空间.＊/｝else｛temp=p—〉next；/*如果输入错误,提示输入有错，请重新输入，让temp指向输入字符串的头部，并将前面正确输出的字符串再次输出＊/printf(”\nInput a wrong char！Input again：\n”）;for(；;){if (temp！=NULL)printf（”%c”,temp—〉char_ch）；elsebreak；temp=temp—〉next；}｝｝while（ch!='＃’);p=p—>next; /＊消去第一个空头节点，并使头结点指向非空线性链表表头＊//*如果输入正确，h不断的指向新输入的字符,而输入字符串的头位置被记录在p里面.＊/h=p；/＊h重新指向头结点，以便后面识别操作*/dosome(）;/＊开始识别＊/if(right）printf（”\n成功! 输入的表达式可以被该文法识别！\n")；elseprintf("\n错误！表示输入的表达式不可以被该文法识别！\n”）；getch();return 0；3．测试数据及运行结果七、简单LL（1）文法判别程序设计1、判断以下文法是不是LL(1）文法，写出详细的判断过程：E→E+T|E—T|TT→T＊F｜T/F｜FF→i|(E）（1）消除左递归,文法变为：E→TE'E'→+TE’ | —TE’ | εT→FT’T’→＊FT' ｜/FT’ |εF→i ｜（E)（2）可推出的非终结符表为:E E' T T’ F否是否是否（3）各非终结符的FIRST集合为：FIRST(E） = {(,i｝FIRST(E’) ={+,—，ε｝FIRST（T)={(,i｝FIRST(T’) ={*,/，ε｝FIRST(F) =｛（，i}（4）各非终结符的FOLLOW集合为：FOLLOW（E） = ｛）,#}FOLLOW(E’)= {)，#}FOLLOW(T） = ｛）,#,+，-}FOLLOW(T’）= {),#,+,-｝FOLLOW（F） = {*,/，+，-，），＃｝（5）各产生式的SELECT集合为：SELECT(E→TE’)=｛（,i｝SELECT（E’→+TE'）={+｝SELECT(E’→-TE')=｛—}SELECT(E’→ε)={ )，#}SELECT（T→FT’）=｛(，i}SELECT（T’→*FT’)={*}SELECT（T’→/FT'）=｛/}SELECT（T’→ε）={ +，—,）,＃｝SELECT（F→(E）)=｛（}SELECT（F→i）=｛i}（6）有相同左部产生式的SELECT集合的交集是否为空？该文法是否为LL（1)文法？（7）该文法的预测分析表为：2、设计LL（1）文法判别程序设计，源代码如下：/* 程序名称： LL（1）语法分析程序 *//* E—〉E+T|E—T/T *//＊ T->T*F｜T/F/F *//＊ F—>(E)|i ＊//*目的：对输入LL(1）文法字符串,本程序能自动判断所给字符串是否为所给文法的句子,并能给出分析过程。
