下载文档原格式
编译原理课程设计 LL(1)文法分析器编译原理课程设计ll(1)文法分析器目录开场白...............................................................1第一章详述.....................................................41.1设计内容....................................................41.2设计建议...................................................4第二章设计的基本原理...........................................42.1预测分析表的形成原理.......................................42.2预测分析程序的分解成.........................................5第三章程序设计.................................................53.1总体方案设计...............................................63.2各模块设计.................................................6第四章程序测试.................................................7第三章程序清单. (8)1课程设计设计题目ll(1)文法分析器学生姓名学号专业班级指导教师2021年12月2合肥工业大学课程设计任务书设计题目ll(1)文法分析器成绩预测分析表中自动构造程序的同时实现设计内容及建议：对于任一输出的一个ll(1)文法，结构其预测分析表中。
建议：首先同时实现子集first(x)结构算法和子集follow(a)结构算法，再同时实现教材主要内容p.79得出的预测分析表中结构算法。
编译原理课程设计报告课题名称：编译原理课程设计C-语言词法与语法分析器的实现C-词法与语法分析器的实现1.课程设计目标（1）题目实用性C-语言拥有一个完整语言的基本属性，通过编写C-语言的词法分析和语法分析，对于理解编译原理的相关理论和知识有很大的作用。
通过编写C-语言词法和语法分析程序，能够对编译原理的相关知识：正则表达式、有限自动机、语法分析等有一个比较清晰的了解和掌握。
（2）C-语言的词法说明①语言的关键字：else if int return void while所有的关键字都是保留字，并且必须是小写。
②专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */③其他标记是ID和NUM，通过下列正则表达式定义：ID = letter letter*NUM = digit digit*letter = a|..|z|A|..|Zdigit = 0|..|9注：ID表示标识符，NUM表示数字，letter表示一个字母，digit表示一个数字。
小写和大写字母是有区别的。
④空格由空白、换行符和制表符组成。
空格通常被忽略。
⑤注释用通常的c语言符号/ * . . . * /围起来。
注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。
注释不能嵌套。
（3）程序设计目标能够对一个程序正确的进行词法及语法分析。
2.分析与设计（1）设计思想a. 词法分析词法分析的实现主要利用有穷自动机理论。
有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。
通过有穷自动机理论能够容易的设计出词法分析器。
b. 语法分析语法分析采用递归下降分析。
递归下降法是语法分析中最易懂的一种方法。
它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。
因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。
编译原理上机实验报告小组成员：王金名、周攀、汪国辉、澎湃、王帅、齐娟娟、刘鸳鸳一、实验目的：了解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语法分析。
《编译原理》综合性实验报告实验学期2016 至2017 学年第 1 学期专业计算机科学与技术班级1403学生姓名黄世增学号1411640305任课教师曦实验成绩《编译原理》课程综合性实验报告开课实验室：C210 2016年12月6日四、实验步骤编写程序时，先定义几个全局变量，key[]事先存放7个关键字，words[]用来存放识别出来的单词二元组，text用来存放从文件读取的容，word用于存放识别出来的单词，length存放字符个数，k存放识别出来的单词个数。
首先，将文本容读取到text中，文本容最后一个字符是空白符，然后调用scan 法，逐个扫描每个字符，如果word的第一个字符是字母，则进行拼字符串，再判断是关键字还是标识符；如果word的第一个字符是数字，则在word清空之前判断是否有识别出非数字字符，若有，则出错，若没有，则识别出来的字符串是常数；若word第一个字符是运算符或界限符，则各自存到words[]中。
最后扫描结束后输出。
五、实验结果及分析六、实验小结和思考通过这次实验，我对词法分析器有了进一步的了解，而且对词法分析和语法分析在实践中的应用有了深入的掌握, 让我对高级语言的学习有了更深的认识，了解得更透彻。
七、源程序清单#include<stdio.h>#include<stdlib.h>#include<string>using namespace std;#define MAX 10000struct WordString{string Word;//单词int category;//类别};char *key[7] = {"int","for", "while", "do", "return", "break", "continue"};//关键字WordString words[MAX]; //创建一个单词符号串string text; //读入的文本存入text中string word; //分割出的单词用word表示int length; //字符个数int k; //总单词个数开课实验室：C210 2016年12月8日六、实验小结和思考本实验加深了我对LL(1)分析法的算法和思想的理解。
集美大学计算机工程学院编译原理课程设计报告选题名称:LL（1）文法分析院（系）:计算机工程学院专业:计算机科学与技术班级:计算1412指导教师:付永刚学年学期:2016 ~ 2017 学年第 2 学期2017 年06 月29 日摘要：选题要求：根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。
本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。
具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。
4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合。
5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。
关键词：语法分析；FIRST集合；FOLLOW集合；分析表一、设计内容及要求(1) 基于PL/0语言，通过编程判断该文法是否为LL(1)文法；(2)计算出文法的First() Follow()(3)构造相应文法的预测分析表(4)对某个输入句子进行语法分析二、实现原理1．LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。
就是要求描述语言的文法是无左递归的和无回溯的。
根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a )∩SELECT(A:=b)=Ø。
（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。
所以采用自顶向下语法分析需要消除文法的左递归性。
文法的左递归是指若文法中对任一非终结符A有推导AÞA…，则称该文法是左递归的。
左递归又可以分为直接左递归和间接左递归。
●直接左递归若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。
编译原理课程设计LR1分析语法分析器实现（C++）输⼊的⽂法（第⼀⾏是终结符）将⽂法保存在txt中，命名为text.txt，与LR1.cpp放在同⼀⽬录中即可运⾏。
text.txtabcdeS->aAdS->bAcS->aecS->bedA->e实现代码：LR1.cpp1 #include<fstream>2 #include<iostream>3 #include<string>4 #include<vector>5 #include <algorithm>6#define MAX_Count 1007 #include <set>8 #include <stack>9 #include <iomanip>10 #include <sstream>11 #include <string>12 #include<cstring>13 #include <map>14using namespace std;151617// 重载⼀下+号运算符18 template <typename CSS_LR1>19 vector<CSS_LR1> &operator +(vector<CSS_LR1> &v1,vector<CSS_LR1> &v2)20 {21 v1.insert(v1.end(),v2.begin(),v2.end());22return v1;23 }242526struct VN_Set{27string VN_name;//⾮终结符28set<string> FIRST; //First集合29set<string> FOLLOW;30 };31struct CSS{32string start;//⾮终结符33 vector<string> next; //First集合34 };35struct CSS_LR1{36string start;//⾮终结符37 vector<string> next; //First集合38int num;39 vector<string> tail;40//41// bool operator==(CSS_LR1& rhs) const {42// return (start == rhs.start &&43// next == rhs.next &&44// num == rhs.num &&45// tail == rhs.tail);46// }47bool operator==(const CSS_LR1& rhs) {48return (start == rhs.start &&49 next == rhs.next &&50 num == rhs.num &&51 tail == rhs.tail);52 }5354 };5556int CSSCount = 0;57 CSS css[MAX_Count];//产⽣式58 VN_Set VN_First[MAX_Count];//⾮终结符集的First集合59set<string> VN;// ⾮终结符集合60set<string> VT;//终结符集合61int I_count = 0;//记录LR1项⽬数62 vector<CSS_LR1> I[MAX_Count]; //项⽬集63 map<string,int> mark_Follow;//⽤于标记Follow 防⽌套娃64 map<string,int> GOTO[MAX_Count];65 map<string,string> ACTION[MAX_Count];666768bool cmp_vector(vector<CSS_LR1>&v1, vector<CSS_LR1>&v2)69 {70if(v1.size()!=v2.size()) return false;71for (int i=0; i<v2.size(); i++)72 {73 CSS_LR1 t;74 t = v2[i];75 vector<CSS_LR1>::iterator result = find(v1.begin( ), v1.end( ),t); //查找376if (result == v1.end( )) //没找到77return false;78 }79return true;80 }8182/*83*实现编译原理语法分析中计算⾮终结符的First集Follow集84*/85set<string> get_FIRST(string a){ //求First集合86set<string> T;87for(int i = 0;i<CSSCount;i++){88if(css[i].start==a){ // a->..89for(int j=0;j<css[i].next.size();j++){90if(VT.find(css[i].next[j])!=VT.end()){ //是终结符开头91 T.insert(css[i].next[j]);92// T.erase("*");93break;94 }95else{96if(css[i].next[j]==css[i].start){102if(j!=css[i].next.size()-1)103 T.erase("$");104 }else{105106break;107 }108 }109110111 }112113 }114 }115116return T;117 }118119set<string> get_FOLLOW(string a){120set<string> T;121//cout<<"现在在求"<<a<<" 的Follow"<<endl;122 mark_Follow[a]++;123if(mark_Follow[a]>=2){124return T;125 }126127set<string> temp;128if(a==css[0].start){129 T.insert("#");130 }131for(int i = 0;i<CSSCount;i++){132for(int j =0;j<css[i].next.size();j++){133if(VT.find(css[i].next[j])==VT.end()&&a==css[i].next[j]){ //是⾮终结符，求FOLLOW集合134if(j==css[i].next.size()-1&&a!=css[i].start){//S->...a135set<string> tt = get_FOLLOW(css[i].start);136 T.insert(tt.begin(),tt.end());137 }138for(int k=j+1;k<css[i].next.size();k++){139if(VT.find(css[i].next[k])!=VT.end()){//后⾯⼀个是终结符 S->..av..140 T.insert(css[i].next[k]);141break;142 }143else{144 temp = get_FIRST(css[i].next[k]);145if(temp.find("$")!=temp.end()){//有$ S->..a B..146 T.insert(temp.begin(),temp.end());147 T.erase("$");148if(k==css[i].next.size()-1){ //S->..a B149set<string> tt = get_FOLLOW(css[i].start);150 T.insert(tt.begin(),tt.end());151break;152 }153 }else{154 T.insert(temp.begin(),temp.end());155break;156 }157 }158 }159160 }161 }162163 }164//cout<<a<<" "<<mark_Follow[a]<<endl;165 mark_Follow[a]=0;166return T;167 }168169170void GetFirst_and_Follow(){171set<string>::iterator it;172int count = 0;173 cout<<"========================================="<<endl;174 cout<<'\t' <<"FIRST集合"<<""<<"FOLLOW集合"<<endl;175for(it=VN.begin ();it!=VN.end ();it++)176 {177178 VN_First[count].VN_name = *it;179 VN_First[count].FIRST = get_FIRST(*it);180181 mark_Follow[*it]=0;182 VN_First[count].FOLLOW = get_FOLLOW(*it);183184//-----------输出FIRST--------------------185186 cout<<VN_First[count].VN_name<<'\t';187set<string>::iterator it;188for(it=VN_First[count].FIRST.begin();it!=VN_First[count].FIRST.end();it++){189 cout<<*it<<"";190 }191 cout<<'\t'<<"";192//----------------------------------------193194195196197//------------输出FOLLOW--------------198set<string>::iterator it1;199for(it1=VN_First[count].FOLLOW.begin();it1!=VN_First[count].FOLLOW.end();it1++){200 cout<<*it1<<"";201 }cout<<endl;202203//----------------------204205 count++;206 }cout<<"=========================================";207 cout<<endl<<endl;208 }209210211212213214void input(){215//创建⼀个⽂件输⼊流对象216 ifstream inFile;217//打开⽂件218 inFile.open("test.txt");223 cout << "file doesn't exist" << endl;224225string temp;226 getline(inFile,temp);227for(int j=0;j<temp.length();j++){228 VT.insert(temp.substr(j,1));229 }230set<string>::iterator p;231 cout<<"终结符号:";232for(p = VT.begin();p!=VT.end();p++){233 cout<<*p<<",";234 }cout<<endl;235236int count = 0;//⽂件⾏数237while(getline(inFile,temp)) //按⾏读取⽂件内容238 {239 css[count].start = temp[0] ;240for(int j=3;j<temp.length();j++){241 css[count].next.push_back(temp.substr(j,1));242 }243 VN.insert(css[count].start);//⾮终结符244245 cout<<css[count].start<<"->";246 vector<string>::iterator it;247for(it=css[count].next.begin();it!=css[count].next.end();it++){248 cout<<*it;249 }250 cout<<endl;251252253 count++;254 }255 CSSCount = count;256257258 }259260bool find_in_vector(vector<CSS_LR1> T,CSS_LR1 p){261 vector<CSS_LR1>::iterator it;262for(it=T.begin();it!=T.end();it++){263if(*it==p){264return true;265 }266 }267return false;268 }269270271 vector<CSS_LR1> CLOSURE(CSS_LR1 I){//求闭包272 vector<CSS_LR1> T;273//T.push_back(I);274if(I.num>=I.next.size()) { //规约项⽬A->α.或者接受项⽬275return T;276 }277else{278string temp = I.next[I.num];279if(VT.find(temp)!=VT.end()){ //点后⾯的是终结符 ,移进项⽬ A→α.aβ280return T;281 }282else{ //待约项⽬283for(int i = 0;i<CSSCount;i++){284if(css[i].start==temp){285 CSS_LR1 p;286 p.start = css[i].start;287 p.num = 0;//点在最前⾯288 p.next = css[i].next;289290set<string> f1;291for(int j = I.num+1;j<I.next.size();j++){292set<string> f2;//⽤于暂存first293294if(VT.find(I.next[j])!=VT.end()){295296 f2.insert(I.next[j]);297 }else{298 f2 = get_FIRST(I.next[j]);299 }300301 f1.insert(f2.begin(),f2.end());302if(f2.find("$")==f2.end()){303304break;305 }306 }307308if(f1.size()==0){309 p.tail=I.tail;310 }311else{312 vector<string> first_tail;313if(f1.find("$")!=f1.end()){314 f1.erase("$");315 copy(f1.begin(),f1.end(), back_inserter(first_tail));316 first_tail.insert(first_tail.end(),I.tail.begin(),I.tail.end()); 317 }else{318 copy(f1.begin(),f1.end(), back_inserter(first_tail));319//cout<<first_tail[0]<<endl;320 }321// vector<string>::iterator l;322// for(l=first_tail.begin();l!=first_tail.end();l++){323// cout<<*l<<" ";324// }cout<<endl;325 p.tail=first_tail;326 }327if(!find_in_vector(T,p)){328329 T.push_back(p);330 vector<CSS_LR1> ol = CLOSURE(p);331 vector<CSS_LR1>::iterator z;332for(z=ol.begin();z!=ol.end();z++){333if(find_in_vector(T,*z)){334 }else{335 T.push_back(*z);336 }337 }338339 }344 }345346return T;347 }348349void showI(vector<CSS_LR1> I){//展⽰项⽬集350 vector<CSS_LR1>::iterator it;351for(it=I.begin();it!=I.end();it++){352 CSS_LR1 p = *it;353 cout<<p.start<<"->";354 vector<string>::iterator s;355for(int j = 0;j<p.next.size();j++){356if(j==p.num) cout<<".";357 cout<<p.next[j];358 }if(p.num==p.next.size())cout<<".";359 cout<<",";360for(int k = 0;k<p.tail.size();k++){361 cout<<p.tail[k];362 }cout<<endl;363 }364 }365366void LR1_Analyse(){367 CSS_LR1 p;368//初始项⽬ S’->.S ,#369 p.start = css[0].start+"^";370 p.num = 0;//点在最前⾯371 p.tail.push_back("#");372 p.next.push_back(css[0].start);373374 I[0] = CLOSURE(p);//求闭包后的I[0]375 I[0].insert(I[0].begin(),p);///////////////求闭包遇到了⼀些问题376 I_count=1;377378//计算项⽬集379for(int i=0;i<I_count;i++){//每个项⽬集项⽬集I(i)380381 cout<<"==================="<<endl;382 cout<<"现在在计算项⽬集I"<<i<<endl;383 showI(I[i]);//展⽰项⽬集384 cout<<"==================="<<endl;385386//---------求ACTION的r部分--------------387 vector<CSS_LR1>::iterator t;388for(t=I[i].begin();t!=I[i].end();t++){389 CSS_LR1 t2 = *t;390if(t2.num==t2.next.size()){391int num =0;392for(int xp=0;xp<CSSCount;xp++){393if(css[xp].start==t2.start&&css[xp].next==t2.next){394 num = xp;395break;396 }397 }398399 std::stringstream ss;400 ss<<num;401string s = ss.str();402for(int q = 0;q<t2.tail.size();q++){403 ACTION[i][t2.tail[q]] = "r"+s;404 }405if(t2.num==1&&t2.next[0]==css[0].start){406 ACTION[i]["#"] = "acc";407 }408 }409 }410//--------------------------------------411412413414set<string>::iterator it;415for(it=VN.begin();it!=VN.end();it++){ //每个⾮终结符416//cout<<"项⽬集I"<<i<<"输⼊"<<*it<<endl;417 vector<CSS_LR1> temp;418//cout<<"项⽬集⼤⼩"<<I[i].size()<<endl;419for(int j = 0;j<I[i].size();j++){420 CSS_LR1 lr = I[i][j];421if(lr.num<lr.next.size()&&lr.next[lr.num]==*it){422//cout<<*it<<endl;423 vector<CSS_LR1> t2;424 lr.num++;425 t2 = CLOSURE(lr);426 t2.push_back(lr);427428 temp=temp+t2;429 }430 }431//cout<<"temp.size"<< temp.size()<<endl;432433if(temp.size()>0){434int k;435for(k=0;k<I_count;k++){//找⼀找项⽬集是否已经存在436if(cmp_vector(I[k],temp)){437break;438 }439 }440if(k==I_count){441//产⽣了新的项⽬集442 I[I_count] = temp;443/*444 cout<<"---------------------"<<endl;445 cout<<"新的项⽬集I"<<I_count<<endl;446 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<I_count<<endl<<endl; 447 showI(I[I_count]);//展⽰项⽬集448 cout<<"---------------------"<<endl;449*/450 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<I_count<<endl<<endl; 451 GOTO[i][*it] = I_count;//更新goto表452 I_count++;453 }else{454//项⽬集已经存在，需要⾃⼰指向⾃⼰455 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<k<<endl<<endl;456 GOTO[i][*it] = k;457458 }459460 }465 vector<CSS_LR1> temp;466467for(int j = 0;j<I[i].size();j++){468 CSS_LR1 lr = I[i][j];469470if(lr.num<lr.next.size()&&lr.next[lr.num]==*it){471 vector<CSS_LR1> t2;472 lr.num++;473 t2 = CLOSURE(lr);//闭包求出的结果不包含本⾝474 t2.insert(t2.begin(),lr);/////////求闭包遇到了⼀些问题475//showI(t2);476 temp=temp+t2;477 }478 }479//cout<<"temp.size"<< temp.size()<<endl;480if(temp.size()>0){481int k;482for(k=0;k<I_count;k++){//找⼀找项⽬集是否已经存在483if(cmp_vector(I[k],temp)){484break;485 }486 }487if(k==I_count){488//产⽣了新的项⽬集489 I[I_count] = temp;490/*491 cout<<"---------------------"<<endl;492 cout<<"新的项⽬集I"<<I_count<<endl;493 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<I_count<<endl<<endl;494 showI(I[I_count]);//展⽰项⽬集495 cout<<"---------------------"<<endl;496*/497 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<I_count<<endl<<endl;498 std::stringstream ss;499 ss<<I_count;500string s = ss.str();501 ACTION[i][*it] = "S"+s;//更新AVTION表502 I_count++;503 }else{504//项⽬集已经存在，需要⾃⼰指向⾃⼰505 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<k<<endl<<endl;506 std::stringstream ss;507 ss<<k;508string s = ss.str();509 ACTION[i][*it] = "S"+s;510511 }512513 }514 }515516517 }518519520 }521522void print_line(){523 cout<<"-----------------------------------------------------------------------------"<<endl;524 }525526527528void print_ACTION_GOTO(){529set<string>::iterator it;530 print_line();531 cout<<setw(27) << setiosflags(ios::right) <<"ACTION";532 cout<<setw(20) << setiosflags(ios::left)<<" GOTO"<<endl;533 print_line();534 cout<<setw(8)<<"项⽬集"<<"|";535536for(it=VT.begin();it!=VT.end();it++){537 cout<<setw(8)<<*it<<"|";538 }539 cout<<setw(8)<<"#"<<"|";540for(it=VN.begin();it!=VN.end();it++){541 cout<<setw(8)<<*it<<"|";542 }543 cout<<endl;544for(int j =0;j<I_count;j++){545 cout<<setw(6)<<"I"<<setw(2)<<j<<"|";546for(it=VT.begin();it!=VT.end();it++){547 cout<<setw(8)<<ACTION[j][*it]<<"|";548 }549 cout<<setw(8)<<ACTION[j]["#"]<<"|";550for(it=VN.begin();it!=VN.end();it++){551552if(GOTO[j][*it])//GOTO表为0553 cout<<setw(8)<<GOTO[j][*it]<<"|";554else{555 cout<<setw(8)<<""<<"|";556 }557 }558 cout<<endl;559 }560 print_line();561562 }563564565566//对栈容器进⾏输出,i=0,返回status中的字符串,i=1,返回sign中的字符串，i=2返回inputStr中的字符串567string vectTrancStr(int i,vector<int> status,vector<string> sign){568string buf;569int count = 0;570//输出状态栈571if(i == 0){572 vector<int>::iterator it =status.begin();573//将数字转化为字符串574string str,tempStr;575for(it;it!= status.end();it++){576 stringstream ss;577 ss << *it;578 ss >> tempStr;579 str+=tempStr;580 }581return str;586for(it ; it != sign.end() ;it++){587 buf += *it;588 count++;589 }590 }591592593string str(buf);594return str;595 }596597598599void Input_Analyse(){//输⼊句⼦，开始分析600601 vector<int> status;//定义状态栈602 vector<string> sign;//定义符号栈603604int step = 1; //步骤605string input;606 cout<<"请输⼊分析的字符串(请以#结尾)：";607 cin>>input;//输⼊待分析的句⼦608 input = input+"#";609610 status.push_back(0);//把状态0⼊栈611//把#加⼊符号栈612 sign.push_back("#");613//输出初始栈状态614 cout<<setw(10)<<"步骤"<<setw(10)<<"状态栈"<<setw(10)<<"符号栈"<<setw(10)<<"输⼊串"<<setw(25)<<"动作说明"<<endl;615616int s =0;//初始状态617618int oldStatus;//保存之前的状态619620621string input_s; //获取初始符号622 input_s = input.substr(0,1);623624while(ACTION[s][input_s] != "acc"){//如果action[s][input_s] =="acc" ，则分析成功625//获取字符串626string str = ACTION[s][input_s];627//如果str为空，报错并返回628if(str.size() == 0){629 cout<<"出错";630return ;631 }632//获取S或r后⾯的数字633 stringstream ss;634 ss << str.substr(1);635 ss >> s;//新的状态号636//如果是移进637if(str.substr(0,1) == "S"){638 cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0,status,sign)<<setw(10)<<vectTrancStr(1,status,sign)<<setw(10)<<input<<setw(10)<<"A"<<"CTION["<<status.back()<<","<<input_s<<"]=S"<<s<<","<<"状态"<<s<< 639 sign.push_back(input_s); //输⼊符号⼊栈640 input.erase(0,1);641 status.push_back(s);//将状态数字⼊栈642 }643//如果是规约644else if(str.substr(0,1) == "r"){645string kaitou;//产⽣式的头部646 kaitou = css[s].start;647int pop_num = css[s].next.size();//获取符号栈的出栈次数648649string r;650 stringstream ss;651 ss << s;652 ss >> r;653int oldStatus;//保存之前的状态654int status_size = status.size();655 oldStatus = status[status_size-1-pop_num];656 s=GOTO[oldStatus][kaitou];657 cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0,status,sign)<<setw(10)<<vectTrancStr(1,status,sign)<<setw(10)<<input<<setw(10)<<(string)":产⽣式"+r+(string)"归约,GOTO("<<oldStatus<<","<<kaitou<<")="<<s<< 658//对符号栈进⾏出栈和状态栈进⾏出栈659while(pop_num--){660 sign.pop_back();661 status.pop_back();662 }663664 sign.push_back(kaitou);//再对产⽣式的开始符号⼊栈665 status.push_back(s);//再把新的状态⼊栈666 }667else{668//nothing669 }670671 step++; //步骤数加1672673 s = status.back();//获取栈顶状态674675 input_s = input.substr(0,1);//获取输⼊的字符676 }677 cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0,status,sign)<<setw(10)<<vectTrancStr(1,status,sign)<<setw(10)<<input<<setw(10)<<"A"<<"cc:分析成功"<<endl;678679680 }681int main(){682 input();//输⼊⼆型⽂法683 GetFirst_and_Follow();//求First和Follow集合684 LR1_Analyse();685 print_ACTION_GOTO();//打印ACTION GOTO表686 Input_Analyse();//输⼊句⼦，开始分析687 }LR1.cpp代码的输⼊写的⽐较草率，可以⾃⾏修改⼀下，只要保存到相应的数据结构中，就不影响后⾯的LR1分析。
#include <string.h>#include <stdio.h>#include <stdlib.h>#define MAXPROD 10 //产生式候选数目typedef struct production{char LeftCode; //产生式左部char rightCodes[5]; //产生式右部char allCodes[10]; //产生式}production;char stack[200]; //堆栈体char inputstr[100]; //输入串production prods[MAXPROD]; //产生式集void init (){prods[0].LeftCode = 'E'; strcpy(prods[0].rightCodes,"TX\0"); strcpy(prods[0].allCodes,"E ->TX\0");prods[1].LeftCode = 'X'; strcpy(prods[1].rightCodes,"+TX\0"); strcpy(prods[1].allCodes,"X ->+TX\0");prods[2].LeftCode = 'X'; strcpy(prods[2].rightCodes,"-TX\0"); strcpy(prods[2].allCodes,"X ->-TX\0");prods[3].LeftCode = 'X'; strcpy(prods[3].rightCodes,"ε\0"); strcpy(prods[3].allCodes,"X ->ε");prods[4].LeftCode = 'T'; strcpy(prods[4].rightCodes,"FY\0"); strcpy(prods[4].allCodes,"T ->FY\0");prods[5].LeftCode = 'Y'; strcpy(prods[5].rightCodes,"*FY\0"); strcpy(prods[5].allCodes,"Y ->*FY\0");prods[6].LeftCode = 'Y'; strcpy(prods[6].rightCodes,"/FY\0"); strcpy(prods[6].allCodes,"Y ->/FY\0");prods[7].LeftCode = 'Y'; strcpy(prods[7].rightCodes,"ε\0"); strcpy(prods[7].allCodes,"Y ->ε\0");prods[8].LeftCode = 'F'; strcpy(prods[8].rightCodes,"(E)\0"); strcpy(prods[8].allCodes,"F ->(E)\0");prods[9].LeftCode = 'F'; strcpy(prods[9].rightCodes,"i\0"); strcpy(prods[9].allCodes,"F ->i\0");}//堆栈操作-->产生式倒着存入进栈int StackPush (int *top, production prod){int len, i;if ((*top) < 0){printf("\n\n\t\t\t不知道的错误！\n\n");exit(0);}len = strlen(prod.rightCodes);//判断产生式右边是否为空if (!strcmp(prod.rightCodes, "ε\0")){stack[*top] = '\0';(*top)--;return 0;}for (i = len-1; i >= 0; i--){stack[(*top)++] = prod.rightCodes[i];}stack[*top] = '\0';(*top)--;return 0;}//bool isDigit (char code){if ((code >= '0' && code <= '9') || code == '.') return true;elsereturn false;}//把式子转化为i+i*i的分析式int DigitToStr (char *input){char list[100];int i = 0, flag = 1, n = 0;while (input[i] != '\0'){if (!((input[i] >= '0' && input[i] <= '9') || input[i] == '+' || input[i] == '-' ||input[i] == '*' || input[i] == '/' || input[i] == '(' || input[i] == ')')) {//输入的字符不是0~9+-*/()而是别的字母的话就报错printf ("\n\n\t\t\t输入有误:\n\n\n");exit (0);}if (i==0){if ((input[0] < '0' || input[0] > '9') && (input[0] != '(' && input[0] != '-')){//处理输入的第一个字符是负号的情况printf ("\n\n\t\t\t输入有误:\n\n");exit (0);}if (input[0] == '-'){//处理第一个字符是负号的情况list[n++] = 'i';i++;flag = 0;continue;}}if (!isDigit(input[i])){list[n++] = input[i];if ((input[i+1] == '+' || input[i+1] == '-' || input[i+1] == '*' || input[i+1] == '/') && input[i] != ')'){//排除连续输入两个运算符的情况printf ("\n\n\t\t\t输入有误:\n\n");exit (0);}flag = 1;}if (flag && input[i+1] != '\0' && input[i+1] != '(' && list[n-1] != ')') {list[n++] = 'i';flag = 0;}i++;}list[n] = '\0';strcpy (input, list);return n;}//选择产生式int SelectProd(int top, int flag){if (top == 0) return 10; //分析栈到底了if (inputstr[flag] == '#') //余留串分析完毕{if (stack[top] == 'E') return 0;if (stack[top] == 'X') return 3;if (stack[top] == 'T') return 4;if (stack[top] == 'F') return 10;if (stack[top] == 'Y') return 7;//以上都不是的话，就分析失败return 10;}if (inputstr[flag] == 'i'){if (stack[top] == 'E') return 0;if (stack[top] == 'X') return 3;if (stack[top] == 'T') return 4;if (stack[top] == 'F') return 9;if (stack[top] == 'Y') return 7;//以上都不是的话，就分析失败return 11;}if (inputstr[flag] == '('){if (stack[top] == 'E') return 0;if (stack[top] == 'X') return 3;if (stack[top] == 'T') return 4;if (stack[top] == 'F') return 8;if (stack[top] == 'Y') return 7;//以上都不是的话，就分析失败return 11;}if (inputstr[flag] == ')'){if (stack[top] == 'E') return 0;if (stack[top] == 'X') return 3;if (stack[top] == 'T') return 4;if (stack[top] == 'F') return 11;if (stack[top] == 'Y') return 7;return 11;}if (inputstr[flag] == '+'){if (stack[top] == 'E') return 0;if (stack[top] == 'X') return 1;if (stack[top] == 'T') return 4;if (stack[top] == 'F') return 11;//以上都不是的话，就分析失败return 11;}if (inputstr[flag] == '-'){if (stack[top] == 'E') return 0;if (stack[top] == 'X') return 2;if (stack[top] == 'T') return 4;if (stack[top] == 'F') return 11;if (stack[top] == 'Y') return 7;//以上都不是的话，就分析失败return 11;}if (inputstr[flag] == '*'){if (stack[top] == 'E') return 0;if (stack[top] == 'X') return 3;if (stack[top] == 'T') return 4;if (stack[top] == 'F') return 11;if (stack[top] == 'Y') return 5;//以上都不是的话，就分析失败return 11;}if (inputstr[flag] == '/'){if (stack[top] == 'E') return 0;if (stack[top] == 'X') return 3;if (stack[top] == 'F') return 11;if (stack[top] == 'Y') return 6;//以上都不是的话，就分析失败return 11;}return 12;}int IsOver(int top, int flag, int *n){if (stack[top] == inputstr[flag])printf ("%d\t%s\t\t%s\t\t\t%s\n\n\n", (*n)++, stack, &inputstr[flag], "分析成功");elseprintf ("%d\t%s\t\t%s\t\t\t%s\n\n\n", (*n)++, stack, &inputstr[flag], "分析失败");exit (0);return 0;}//输入、堆栈操作、输出。
LL(1)文法分析及程序设计1.设计目的通过设计、编制、调试LL(1)语法分析程序，加深对LL(1) 语法分析原理的理解。
2.设计要求（1）写出符合LL(1)分析方法要求的文法，给出分析的算法思想、步骤、程序结构以及最终完成语法分析程序设计。
（2）编制完成分析程序后，选取几个例子，上机测试并通过所设计的分析程序。
3.设计方案用LL(1)分析法判别给定文法是否为LL(1)文法，提供其分析过程与结果，最终根据结果设计算法分析程序，对输入的符号串进行分析。
4.设计内容4.1 设计基本思想设计一个LL(1)文法分析器，构造出预测分析表，通过预测分析表，判别用户输入的字符串是否符合LL(1)文法。
并给出分析过程与结果。
4.2 LL(1)文法的基本原理与算法一个上下无关的文法是LL(1)文法的充要条件时，对每个非终结符A的两个不同产生式，A->α,A->β满足SELECT（A->α）∩SELECT（A->β）=φ，其中α和β不同时推出ξ。
如果某个文法满足上述条件，称该文法为LL(1)文法。
LL(1)分析法是一种采用确定的自顶向下的语法分析技术，其含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可以决定如何推导，即便选择哪个产生式规则进行推导。
4.3 LL(1)判别分析步骤(1)将数组X[]中对应的每一个非终结符的标记为“未定”。
(2)扫描文法中的产生式。
1.删除所有右部含有终结符的产生式。
若使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应的非终结符的标记值改为“否”，说明该终结符不能推出ξ。
2.若某一非终结符的某一个产生式右部为ξ，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。
（3）扫描产生式右部的每一个符号。
1.若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若使得产生式右部为空，则对产生式右部的非终结符在数组中对应的标志改为“是”，并删除该非终结符为左部的所有的产生式。
集美大学计算机工程学院编译原理课程设计报告选题名称: LL（1）文法分析院（系）:计算机工程学院专业:计算机科学与技术班级:计算1412 指导教师:付永刚学年学期:2016 ~ 2017 学年第 2 学期2017年06月29日摘要：选题要求：根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。
本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。
具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。
4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合。
5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。
关键词：语法分析；FIRST集合；FOLLOW集合；分析表一、设计内容及要求(1) 基于PL/0语言，通过编程判断该文法是否为LL(1)文法；(2)计算出文法的First() Follow()(3)构造相应文法的预测分析表(4)对某个输入句子进行语法分析二、实现原理1．LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。
就是要求描述语言的文法是无左递归的和无回溯的。
根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a )∩SELECT(A:=b)=Ø。
（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。
所以采用自顶向下语法分析需要消除文法的左递归性。
文法的左递归是指若文法中对任一非终结符A有推导A⇒A…，则称该文法是左递归的。
左递归又可以分为直接左递归和间接左递归。
●直接左递归若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。
消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：A→Aα|β（α,β∈V*，且β不以A开头）对A引入一个新的非终结符A′，把上式改写为：A →βA′A′→αA′|ε●间接左递归若文法中存在某一非终结符A，使得A⇒A…至少需要两步推导，则称该文法是间接左递归的。
消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。
【方法二】直接改写文法：设有文法G10[S]：S→Aα|β⑴A→Sγ⑵因为S⇒Aα⇒Sγα，所以S是一个间接递归的非终结符。
为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）：S→Sγα|β⑶⑶式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：S→βS′S′→γαS′|ε2. 计算First集(1) 若X∈V T ，则First(X)={X}(2) 若X∈V N ，且有产生式X→a…, a∈V T则First(X)={X}(3) 若X∈V N ，且有产生式X→ε,则First(X)={X}(4) 若X，Y1 ，Y2 ，…，Y n 都∈V N，而由产生式X→Y1 Y2 …Y n 。
当Y1 ，Y2 ，…，Y i-1都能推导出ε时，（其中1≤i≤n），则First(Y1)-{ε}, First(Y2)-{ε},…, First(Y i)都包含在First(X)中(5)当(4)中所有Y i都能推导出ε，（i=1，2，…，n），则First(X)=First(Y1)∪First(Y2)∪…First(Y n)∪{ε}反复使用上述步骤直到每个符合的First集合不再增大为止。
3. 计算Follow集对文法中的每个A∈V N，计算Follw(A)：(1) 设S为文法的开始符合，把{#}加入Follow(S)中；(2) 若A→αBβ是一个产生式，则把First(β)的非空元素加入Follow(B)中，如果β能推导出ε，则把Follow(A)也加入(B)中；(3) 反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。
4. 预测分析方法预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程序；先进后出栈；预测分析表。
预测分析程序的框图如下：目录1系统分析 (1)1.1选题要求 (1)1.2预期目标 (1)2.程序流程图 (1)2.1总流程图 (1)2.2F IRST集和F OLLOW集 (2)2.3预测分析表流程 (3)3.代码编写 (3)3.1检查左递归 (3)3.2FIRST集合 (5)3.3FOLLOW集合 (6)3.4分析表输出 (8)4.程序调试 (10)5.总结 (11)6.指导教师评语 (12)7.源码 (13)正文：1.系统分析1.1选题要求根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。
本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。
1.2预期目标构造LL(1)文法语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。
程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。
2.程序流程图2．1.总流程图2.2.First集和Follow集的流程图2.3.预测分析表流程：3.代码编写3.1检查左递归：3.2 first集合3.3 follow集合3.4 分析表输出4. 程序调试导入正确的文法：符合文法的串不符合文法的串导入有左递归的文法：串分析：总结指导教师评语源码：LL1.h#include <iostream>#include <cstring>#include <cstdlib>#include <fstream>using namespace std;class Parser{public:Parser();Parser(const Parser&);friend ostream& operator<<(ostream& output,const Parser& rs);friend istream& operator>>(istream& input,Parser& rs);int Findid(char);int Check();string Checkstr(string&);string Delchar(char,string);int Findchar(char,string);int StrNum(const string&);char RandChar();string GetSub(int,const string&,char);Parser& DelLeft(int);string First(char);string First(const string&);string Follow(char);Parser& FirstAndFollow();Parser& CreateTable();~Parser();char Pop();int Mate(char,char);char Top();char Ip();Parser& Push(const string&);int Analysis();private:int num;string ter,non,end,stack,instack;string *content;string *first;string *follow;string **table;};LL1.cpp#include "LL1.h"Parser::Parser(){content=new string[255];first=new string[255];follow=new string[255];table=new string *[255];}Parser::Parser(const Parser& rs){ter=rs.ter;non=rs.non;end=rs.end;num=rs.num;content=new string[255];first=new string[255];follow=new string[255];table=new string *[255];for(int i=0;i<=num;i++)content[i]=rs.content[i];FirstAndFollow();CreateTable();}ostream& operator<<(ostream& output,const Parser& rs){output<<"文法内容(共"<<rs.num<<"条):"<<endl;int i=0;while(i<rs.num){output<<rs.content[i++]<<endl;}output<<"结终符:"<<rs.ter<<endl;output<<"非结终符:"<<rs.non<<endl;cout<<"非终结符的FIRST集合"<<endl;for(unsigned int j=0;j<rs.non.size();j++)cout<<"FIRST("<<rs.non[j]<<") = {"<<rs.first[j]<<"}\t"<<endl;cout<<"非终结符的FOLLOW集合"<<endl;for(unsigned int j=0;j<rs.non.size();j++)cout<<"FOLLOW("<<rs.non[j]<<") = {"<<rs.follow[j]<<"}\t"<<endl;output<<"预测分析表:"<<endl<<"\t";for(unsigned int j=0;j<rs.ter.size();j++)output<<rs.ter[j]<<"\t";output<<"$"<<endl;for(unsigned int j=0;j<rs.non.size();j++){output<<rs.non[j]<<"\t";for(unsigned int k=0;k<=rs.ter.size();k++)cout<<rs.table[j][k]<<"\t";output<<endl;}return output;}istream& operator>>(istream& input,Parser& rs){unsigned int j=0;char filename[255];cout<<"请输入文件名:";input>>filename;ifstream infile(filename,ios::in);if(!infile){cout<<"无法打开文件！"<<endl;exit(0);}while(1){unsigned int i=0;infile>>rs.end;rs.content[j++]=rs.end;if(infile.eof()) break;while(i<rs.end.size()){if(rs.end[i]=='|'||rs.end[i]=='^');else if(i==1||i==2) i++;else if(rs.end[i]>='A'&&rs.end[i]<='Z'){if(std::string::npos==rs.non.find(rs.end[i])) rs.non.append(1,rs.end[i]);}else if(std::string::npos==rs.ter.find(rs.end[i])) rs.ter.append(1,rs.end[i]);i++;}}rs.num=j-1;if(rs.Check()==0){exit(0);}rs.FirstAndFollow();rs.CreateTable();return input;}int Parser::Findid(char a){int i=0;while(i<num){if(content[i][0]==a) return i;i++;}return -1;}char Parser::RandChar(){switch(rand()%3){case 0:return 'A';case 1:return 'B';case 2:return 'C';case 3:return 'D';}return 'D';}int Parser::Check(){unsigned int j=0;int i=0;while(i<num){if(content[i].size()<=3){cout<<"文法句"<<content[i]<<"长度不对!"<<endl;return 0;}if(content[i][1]!='-'||content[i][2]!='>'){cout<<"文法句"<<content[i]<<"未来使用推导符\"->\"!"<<endl;return 0;}int n=StrNum(content[i]);int s=0;char z=content[i][0];int m=0;for(int k=1;k<=n;k++){string tmp=GetSub(k,content[i],'|');if(z==tmp[0]){s=1;m++;}}if(m==n){cout<<"文法句"<<content[i]<<"将形成无穷推导！"<<endl;return 0;}if(s==1)DelLeft(i);i++;}return 1;}Parser& Parser::DelLeft(int i){int n=StrNum(content[i]);char c=RandChar();char z=content[i][0];int s=0;for(int k=1;k<=n;k++){string tmp=GetSub(k,content[i],'|');if(z==tmp[0]) s=1;}if(s==0) return *this;cout<<"文法句"<<content[i]<<"含有直接左递归,";while(1){if(Findchar(c,non)==-1) break;else c=RandChar();}cout<<"随机产生非终结符为:"<<c<<endl;non.append(1,c);string temp;temp+=z;temp+="->";string next;next+=c;next+="->";for(int k=1;k<=n;k++){string t=GetSub(k,content[i],'|');if(z==t[0]){t.erase(0,1);t+=c;next+=t;next+='|';}else{if(t=="^") t.clear();t+=c;temp+=t;temp+='|';}}next+='^';temp.erase(temp.size()-1,1);content[i]=temp;num=num+1;content[num]=end;for(int j=num-1;j>i;j--)content[j]=content[j-1];content[i+1]=next;return *this;}string Parser::Checkstr(string & a){unsigned int i=0,j=0;for(;i<a.size();i++){for(j=i+1;j<a.size();j++){if(a[i]==a[j]){a.erase(j,1);}}}return a;}string Parser::Delchar(char x,string a) {int j,i=int(a.size());for(j=0;j<i;j++)if(a[j]==x)a.erase(j,1);return a;}int Parser::Findchar(char x,string a){unsigned int i=0;while(i<a.size()){if(a[i]==x) return i;i++;}return -1;}string Parser::GetSub(int i,const string& a,char c='|'){string ch;int j[255];int n=1;j[0]=2;if(i>=int(a.size())) return ch;for(unsigned int k=3;k<a.size();k++)if(a[k]==c) j[n++]=k;for(unsigned int k=j[i-1]+1;k<a.size();k++){if(a[k]==c) break;else if(std::string::npos==ch.find(a[k])) ch.append(1,a[k]);}return ch;}int Parser::StrNum(const string& a){int n=0;for(unsigned int i=3;i<a.size();i++)if(a[i]=='|') n++;return n+1;}string Parser::First(char x){string ch="";if(Findchar(x,ter)!=-1){ ch.append(1,x);ch.append(1,' ');}else if(Findchar(x,non)!=-1){int i=Findid(x);if(i!=-1){string q=content[i];unsigned int k=3;while(k<q.size()){if(q[k-1]=='|'||k==3){if(Findchar(q[k],ter)!=-1||q[k]=='^'){ch.append(1,q[k]);ch.append(1,' ');}else{if(k==3||q[k+1]=='|'||k==q.size()-1) ch+=First(q[k]);else{string temp=First(q[k-1]);if(Findchar('^',temp)!=-1) ch+=First(q[k]);}}k++;}else k++;}}}return ch;}string Parser::First(const string& a){return First(a[0]);}string Parser::Follow(char x){string ch;if(Findchar(x,non)!=-1){if(!Findid(x)){ch+="$";ch+=' ';}int i=0;while(i<num){string q=content[i];unsigned int k=3;char c=content[i][0];while(k<q.size()){while(q[k]==x){if(k<q.size()-1&&q[k+1]!='|'){string temp=Delchar('^',First(q[k+1]));if(ch.find(temp)==string::npos) ch+=temp;if(Findchar('^',First(q[k+1]))!=-1){string follow_c = Follow(c);if(ch!=follow_c&&ch.find(follow_c)==std::string::npos)ch+=follow_c;}}else if(k==q.size()-1){string follow_c = Follow(c);if(ch.find(follow_c)==std::string::npos) ch+=follow_c;}k++;}k++;}i++;}}return ch;}Parser& Parser::FirstAndFollow(){unsigned int i=0;while(i<non.size()){first[i]=First(non[i]);follow[i]=Follow(non[i]);i++;}return *this;}Parser& Parser::CreateTable(){for(unsigned int i=0;i<=non.size();i++)table[i]=new string[255];for(unsigned int i=0;i<non.size();i++){string temp=content[i];int w=Findchar(temp[0],this->non);int n=StrNum(temp);for(int k=1;k<=n;k++){string tmp=GetSub(k,temp);string fir=First(tmp);for(unsigned int j=0;j<fir.size();j++){int idz=Findchar(fir[j],ter);if(idz!=-1)table[w][idz]=tmp;}if(Findchar('^',fir)!=-1||tmp[0]=='^'){string fol=Follow(temp[0]);for(unsigned int j=0;j<fol.size();j++){int z=Findchar(fol[j],ter);if(z==-1) z=int(ter.size());table[w][z]=tmp;}}}}return *this;}Parser::~Parser(){delete[] content;delete[] first;delete[] follow;delete[] table;}char Parser::Pop(){char x=stack[stack.size()-1];stack.erase(stack.size()-1,1);return x;}int Parser::Mate(char x,char ip){if(Findchar(x,ter)!=-1){if(x==ip){Pop();instack.erase(0,1);return 1;}else return 0;}return 0;}char Parser::Top(){return stack[stack.size()-1];}char Parser::Ip(){return instack[0];}Parser& Parser::Push(const string& rs){if(rs.empty()) return *this;string temp=rs;temp.replace(temp.begin(),temp.end(),temp.rbegin(),temp.rend());stack.append(temp);return *this;}int Parser::Analysis(){stack.append("$");char chose;cout<<"是否输入分析串(y or n):";cin>>chose;while(chose=='y'){stack+=non[0];cout<<"请输入分析串<退出(q)>：";cin>>instack;if (instack=="q") exit(0);if(instack[instack.size()-1]!='$') instack+="$";int k=1,flag=0;char x=Top();char c=Ip();cout<<"分析栈\t当前输入\t动作"<<endl;while(x!='$'){x=Top();c=Ip();cout<<stack<<"\t"<<instack<<"\t\t";if(Findchar(x,ter)!=-1){if(Mate(x,c)){k++;cout<<"匹配"<<c<<endl;}else{cout<<"["<<k<<"]出错(终结符不匹配)！"<<endl;flag=1;if(x==')') Pop();else instack.erase(0,1);k++;}}else if(Findchar(x,non)!=-1){int idf=Findchar(x,non);int idz=Findchar(c,ter);if(idz==-1) idz=int(ter.size());string temp=table[idf][idz];if(temp.empty()){cout<<"["<<k<<"]出错（"<<c<<"不属于FIRST("<<x<<")）！"<<endl;flag=1;instack.erase(0,1);k++;}else{Pop();if(temp!="^"){Push(temp);cout<<x<<"->"<<temp<<endl;}else cout<<x<<"->"<<temp<<endl;}}else if(x=='$'&&c=='$'){if(flag==0) cout<<"正确"<<endl;else cout<<"错误"<<endl;}else{cout<<"["<<k<<"]出错(未能识别的字符)！"<<endl;flag=1;instack.erase(0,1);k++;}}}}int main(){Parser LL1;cin>>LL1;cout<<LL1;LL1.Analysis();return 0;}参考来自/code/snippet_54698_3835。
