编译原理ll(1)语法识别

LL（1）文法的判别
编译原理实验报告
一、实验名称：LL（1）文法的判别
二、实验目的：
（1）能导出空串的非终结符算法
（2）实现首符集，后跟符集和可选集算法
（3）输出要指出是否为LL（1）文法
三、实验原理：
LL(1)文法使用的是确定的自顶向下的分析技术。

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

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

四、实验思路
1、从键盘读入输入串，并判断正误；
2、若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法；
3、若符合LL（1）文法，由程序自动构造LL（1）分析表；
4、由算法判断输入符号串是否为该文法的句型。

五、实验小结
通过本次实验对LL(1)分析法知识进行了加深和巩固，LL(1)分析法是介于SLR(1)分析法和LR(1)分析法之间的一种语法分析
方法，这种分析法能解决SLR(1)分析法和LR(1)分析法所不能解决的冲突动作，并且其分析表的状态个数与SLR(1)相同。

能够独立完成实验，并且对程序进行修改，能够对发现的问题进行解决。

LL（1）文法的判别
实验要求：
1)能导出空串的非终结符算法
2)实现首符集，后跟符集和可选集算法
3)输出要指出是否为LL（1）文法，此外输出截图里要有“学校，学号，姓名”，不是输出截图的名字，要把这三个作
为输出结果
对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的
产生式A—>α|β满足下列条件：
（1）如果α、β均不能推导出ε，则FIRST(α) ∩FIRST(β) = Φ。

（2）α和β至多有一个能推导出ε。

（3）如果β*═> ε，则FIRST(α) ∩FOLLOW(A) = Φ。

将满足上述条件的文法称为LL(1)文法。

在这个实验中，要求我们判别LL(1)文法，这需要先要搞清楚这个文法的文法规则，并计算出该文法的FIRST、FOLLOW、SELECT集，再进行判别。

我这里使用的是链表来存储这些集合，进而对结果进行处理。

这次试验，是考察我们对于L（1）文法分析表的搭建，考虑之后决定使用链表来进行存储，本次试验难度还是很难的。

程序
另见压缩包
截图。

1、判断各非汇总结符是否可以推出空（1）将各非终结符出示状态置为“未知”（2）按顺序扫描各产生式右部。

分为下面几种情况：a、若遇到符号“ε”，检查左部非终结符状态，若不是“空”，将其置为“空”，继续扫描下一产生式；b、若遇到终结符，检查左部非终结符状态，若为“未知”，将其置为“非空”，继续扫描下一产生式；c、若遇到非终结符，检查该非终结符状态，若为“未知”，则跳过当前产生式，扫描下一产生式；若为“非空”，检查左部非终结符状态，若为“未知”，将其置为“非空”，继续扫描下一产生式；若为“空”，继续扫描本产生式的下一符号；d、若遇到“\0”，检查左部非终结符状态，若不是“空”，将其置为“空”，继续扫描下一产生式；e、若上述a,b,c,d过程引起了非终结符状态的改变，则跳到(2)处继续循环，否则跳出循环，判断结束。

2、求非终结符的first集扫描各产生式的右部，分为下面几种情况：A、若遇到终结符，将该终结符加入左部非终结符的first集，继续扫描下一产生式；B、若遇到符号“ε”，将“ε”加入左部非终结符的first集，继续扫描下一产生式；C、若遇到非终结符，将该非终结符的first集— {ε} 加入左部非终结符的first集，然后检查该非终结符是否可以推出空，若可以为空，则扫描本产生式的下一符号；若不为空，则继续扫描下一产生式；D、若遇到“\0”，将“ε”加入左部非终结符的first集，继续扫描下一产生式；3、求某一非终结符的FOLLOW集（1）在产生式右部找到该非终结符，扫面它后面的符号，分为下面几种情况：A、若是终结符，则将该终结符加入该非终结符的folow集；B、若是非终结符，将该非终结符的first集— {ε} 加入该非终结符的folow集，然后检查该非终结符是否可以推出空，若可以为空，则扫描本产生式的下一符号；若不为空，则继续扫描下一产生式；C、若是“\0”，则将该产生式的左部非终结符的follow集加入它的follow集。

专题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:出错标识符首字符所在位置返回值：是否成功解析。

实验七：LL(1)文法的判断一：要求输入：任意的上下文无关文法。

输出：判断是否为LL（1）文法二：实验目的1．掌握LL(1)的判断，掌握求first和follow集合的算法2．熟悉运用C/C++语言对求first和follow集合进行实现三：实验原理设α＝x1x2…xn，FIRST（α）可按下列方法求得：令FIRST（α）＝Φ，i＝1；（1）若xi∈VT，则xi∈FIRST（α）；（2）若xi∈VN；①若εFIRST（xi），则FIRST（xi）∈FIRST（α）；②若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；（3）i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或i>n为止。

当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。

这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。

下面我们给出文法的FOLLOW集的定义。

设文法G[S]＝（VN，VT，P，S），则FOLLOW（A）＝{a | S …Aa …，a∈VT}。

若S …A，#∈FOLLOW（A）。

由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。

FOLLOW集可按下列方法求得：（1）对于文法G[S]的开始符号S，有#∈FOLLOW（S）；（2）若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则FIRST（y）－{ε}∈FOLLOW（A）；（3）若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST （y），其中x，y∈V *，则FOLLOW（B）∈FOLLOW（A）；四：数据结构与算法typedef struct Chomsky //定义一个产生式结构体{string left; //定义产生式的左部string right; //定义产生式的右部}Chomsky;void apart(Chomsky *p,int i) //分开产生式左右部，i代表产生式的编号string is_empty(Chomsky *p)//判断某非终结符能否直接推出空，空用#代替string isempty(Chomsky *p)//可以间接推出空的非终结符void search(Chomsky *p,int n)//提取产生式中的非终结符void First(Chomsky *p,int n,char m,int mm)//求文法中非终结符的First 集void Follow(Chomsky *p,int n,int m)//求文法的follow集string erase(string s)//去First集及follow集中的重复字符void select(string s1,string s2)//求产生式的select集,s1是产生式左部，s2是产生式右部五：出错分析1:select集计算不出，关键在于能产生空的非终结符没有求出来2:单个符号的first集与一串符号的first集区别3:实验最后没能输出select集，没能判断出来是否是LL(1)文法六：实验结果与分析七：源代码#include<iostream>#include<string>using namespace std;#define max 100typedef struct Chomsky //定义一个产生式结构体{string left; //定义产生式的左部string right; //定义产生式的右部}Chomsky;int n;//产生式总数string strings;//存储产生式string noend;//存放文法中的非终结符string empty;//存放可以推出空的非终结符string first[max];//存放非终结符的first集string follow[max];//存放非终结符的follow集string select[max];//存放产生式的select集void apart(Chomsky *p,int i) //分开产生式左右部，i代表产生式的编号{int j;for(j=0;j<strings.length();j++)if(strings[j]=='-'){p[i].left=strings.substr(0,j);//从0开始的j长度的子串，即0~j-1p[i].right=strings.substr(j+1,strings.length()-j);//从j+1开始的后面子串}}/*string is_empty(Chomsky *p)//判断某非终结符能否直接推出空，空用#代替{//如果可以，返回1//不可以，返回0int i;string s;for(i=0;i<n;i++){if (p[i].right[0]="#"&&p[i].right.length()==1)//直接推出空的{empty=empty+p[i].left;}}s=empty;return s;//s存放能直接推出空的非终结符}string isempty(Chomsky *p)//可以间接推出空的非终结符{int i,j;string s1;for(i=0;i<n;i++){if(is_empty(p).find(p[i].left)>=0)//若此非终结符已经存在直接推出空那里，在此无需重复计算{}else{for(j=0;j<(int)p[i].right.length();j++){if(is_empty(p).find(p[i].right.[j])<0){}}if(j==(int)p[i].right.length())//如果右部所有符号都在直接推出空那里，则此左部也可以推出空{s1=s1+p[i].left[0];}}}}*/void search(Chomsky *p,int n)//提取产生式中的非终结符{int i,j;for(i=0;i<n;i++){if(!(noend.find(p[i].left[0])>=0&&noend.find(p[i].left[0])<noend.length()))noend=noend+p[i].left;for(j=0;j<p[i].right.length();j++){if('A'<=p[i].right[j]&&p[i].right[j]<='Z'){if(noend.find(p[i].right[j])>=0&&noend.find(p[i].right[j])<noend.length()) break;elsenoend=noend+p[i].right.substr(j,1);}}}}void First(Chomsky *p,int n,char m,int mm)//求文法中非终结符的First集{int length=noend.length();string f;int i,j,x,y;int flag=0;for(i=0;i<n;i++){if(m==p[i].left[0]){if('a'<=p[i].right[0]&&'z'>=p[i].right[0])first[mm]=first[mm]+p[i].right.substr(0,1);if(p[i].right[0]=='#')first[mm]=first[mm]+p[i].right.substr(0,1);if('A'<=p[i].right[0]&&'Z'>=p[i].right[0]){for(j=0;j<p[i].right.length();j++){if('A'<=p[i].right[j]&&p[i].right[j]<='Z')flag++;}if(flag==j)//产生式的右部均为非终结符{flag=0;for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++)if(p[i].right[j]==p[x].left[0]&&p[x].right[0]=='#'){flag++;break;}}if(flag==j)//产生式右部的全部非终结符均能推出空{for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++){if(p[i].right[j]==noend[x])break;}y=x;if(first[y]=="")First(p,n,p[i].right[j],x);f=first[y];for(x=0;x<f.length();x++){if(f[x]=='#'){if(x==f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1);}}first[mm]=first[mm]+f;}first[mm]=first[mm]+"#";}else{for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++){if(p[i].right[j]==noend[x])break;}y=x;if(first[y]=="")First(p,n,p[i].right[j],x);f=first[y];for(x=0;x<f.length();x++){if(f[x]=='#'){if(x==f.length()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1);}}first[mm]=first[mm]+f;}}}}}}}void Follow(Chomsky *p,int n,int m)//求文法的follow集{int i,j,x,y,k;string fo;for(i=0;i<n;i++){for(j=0;j<p[i].right.length();j++){if(noend[m]==p[i].right[j]){if(j<p[i].right.length()-1&&'a'<=p[i].right[j+1]&&p[i].right[j+1]<='z') follow[m]=follow[m]+p[i].right.substr(j+1,1);if(j<p[i].right.length()-1&&'A'<=p[i].right[j+1]&&p[i].right[j+1]<='Z') {for(y=0;y<noend.length();y++){if(noend[y]==p[i].right[j+1])break;}fo=first[y];for(x=0;x<first[y].length();x++){if(0<=first[y].find('#')&&first[y].find('#')<first[y].length())fo=first[y].substr(0,first[m].find('#'))+first[y].substr(first[y].find('#')+1);}follow[m]=follow[m]+fo;for(x=0;x<n;x++){if(p[i].right[j+1]==p[x].left[0]&&p[x].right[0]=='#')break;}if(x!=n)//非终结符后面的部分可以推出空{for(y=0;y<n;y++){if(p[i].left[0]==noend[y])break;}k=y;if(follow[k]=="")Follow(p,n,y);follow[m]=follow[m]+follow[k];}}if(j==p[i].right.length()-1){for(y=0;y<n;y++){if(p[i].left[0]==noend[y])break;}k=y;if(follow[k]=="")Follow(p,n,y);follow[m]=follow[m]+follow[k];}}}}}string erase(string s)//去First集及follow集中的重复字符{int i,j;for(i=0;i<s.length();i++){for(j=0;j<s.length();j++){if(i!=j&&s[i]==s[j])s=s.substr(0,j)+s.substr(j+1);}}return s;}/*void select(string s1,string s2)//求产生式的select集,s1是产生式左部，s2是产生式右部{if()//即s2可以推出空#{cout<<s1<<"->"<<s2<<"="<<first(s2)<<endl;}else//即s2不可以推出空#{cout<<s1<<"->"<<s2<<"="<<first(s2)-"#"+<<follow(s1)<<endl;}}*/void main(){cout<<"....................编译原理实验七：LL(1)文法的判断...................."<<endl;int i,j,m;char f;//存放文法开始符号cout<<"请输入文法产生式个数N以及各产生式（空用#代替，左右部的为-）："<<endl; cin>>n;Chomsky *p=new Chomsky[n]; // 初始化产生式数组for(i=0;i<n;i++){strings.erase();//清除cin>>strings;apart(p,i);}cout<<"请输入该文法的开始符号："<<endl;cin>>f;search(p,n);//提取产生式中的非终结符//empty=is_empty(p)+isempty(p);//可以推出空的所有非终结符for(m=0;m<noend.length();m++){if(first[m]=="")First(p,n,noend[m],m);}cout<<"该文法非终结符的first集："<<endl;for(i=0;i<noend.length();i++){first[i]=erase(first[i]);cout<<noend[i]<<":"<<first[i]<<endl;}for(m=0;m<noend.length();m++){if(noend[m]==f)follow[m]=follow[m]+"#";if(follow[m]=="")Follow(p,n,m);}cout<<"该文法非终结符的follow集："<<endl;for(i=0;i<noend.length();i++){follow[i]=erase(follow[i]);cout<<noend[i]<<":"<<follow[i]<<endl;}cout<<"该文法的各产生式的select集："<<endl;for(i=0;i<n;i++){select[i]=erase(select[i]);cout<<p[i].left<<"->"<<p[i].right<<":"<<select[i]<<endl; }system("pause");}11 / 11。

语法分析LL(1)设计报告——LCC1 问题描述设计一个由正规文法生成First集和Follow集并能输出测试字符串的预测分析过程。

(算法参见教材)【基本要求】模拟算法的基本功能是：（1）输入一个文法G；（2）消除左循环；（3）输出FIRST集；（4）输出FOLLOW集；（5）输出SELECT集合；（6）输出预测分析表；（7）输出预测分析过程。

2 详细设计2.1 数据结构2.1.1 终结符号： vector<CString>2.1.2 非终结符号： vector<CString>2.1.3 文法： vector<CString> 每条文法定义为一个CString2.1.4 First集合： vector<LEFT_GATHER> LEFT_GATHER{（非终结符），（vector）}2.1.5 Follow集合： vector<LEFT_GATHER> LEFT_GATHER{（非终结符），（vector）}2.1.6 Select集合： vector<LEFT_GATHER> LEFT_GATHER{（文法），（vector）}2.1.7 LEFT_GATHERtypedef struct LEFT_GATHER{CString start;vector<CString> end_gather;}LEFT_GATHER;2.2 算法思想2.2.1 判断文法合法性：满足条件：（1）左部以非终结符开始，并且只有一个（2）右部必须有非终结符，并且只能用零个或多个终结符和非终结符组成不合法情况（1）形如A->A（2）形如A->（已包括）2.2.2 消除左递归：1、消除直接左递归原文法: E --> E a1 | E a2 | ... | E an | b1 | b2 | ... | bn消除后: E --> b1 E' | b2 E' | ... | bn E'E'--> a1 E' | a2 E' | ... | an E' | epsilon2、消除间接左递归a) 把所有非终结符号按一定序列排序为E1, E2, ... En；b) for i=1 to n do /*依次处理每个非终结符号*/for j=1 to i-1 do /*处理第1个到i-1个*/若Ei --> Ej r则改为Ei --> S1 r | S2 r | ... | Sk r其中Ej --> S1 | S2 | ... | Skc) 对Ei消除直接左递归。

2016.11.30LL(1)文法的判断及转换目录一、实验名称 (2)二、实验目的 (2)三、实验原理 (2)1、First集定义 (2)2、Follow集定义 (2)3、Select集定义 (3)4、含左递归文法 (3)四、实验思路 (3)1、求非终结符是否能导出空 (3)2、求First集算法 (3)3、求Follow集算法 (3)4、求Select集算法 (4)五、实验小结 (4)六、附件 (4)1、源代码 (4)2、运行结果截图 (10)一、实验名称LL(1)文法的判断及转换二、实验目的输入：任意一个文法输出：(1)是否为LL(1)文法(2)若是，给出每条产生式的select集(3)若不是，看看是否含有左公共因子或者含有左递归，并用相应的方法将非LL(1)文法变成LL(1)文法，并输出新文法中每条产生式的select集。

三、实验原理1、First集定义令X为一个文法符号（终止符或非终止符）或ε，则集合First（X）有终止符组成，此外可能还有ε，它的定义如下：1.若X是终止符或ε，则First（X）={X}。

2.若X是非终结符，则对于每个产生式X—>X1X2…Xn，First（X）包含了First （X1）-{ε}。

若对于某个i<n，所有的集合First（X1），...，First（Xi）都包含了ε，则First（X）也包括了First（Xi+1）- {ε}。

若所有集合First（X1），...，First （Xn）都包括了ε，则First（X）也包括了ε。

2、Follow集定义给出一个非终结符A，那么集合Follow（A）则是由终结符组成，此外可能还含有#（#是题目约定的字符串结束符）。

集合Follow（A）的定义如下：1. 若A是开始符号，则#在Follow（A）中。

2. 若存在产生式B—>αAγ，则First（γ）- {ε}在Follow（A）中。

3. 若存在产生式B—>αAγ，且ε在First（γ）中，则Follow（A）包括Follow （B）。

《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";string s;cout<<"请输入要分析的符号串\n";cin>>s;analyse(table,UU,uu,tt,s);return 0;}3、程序演示结果（1）输入文法（2）消除左递归（3）求解FIRST和FOLLOW集（4）构造分析表（5）分析符号串匹配成功的情况：匹配失败的情况五、思考和体会1、编写的LL(1)语法分析器应该具有智能性，可以由用户输入任意文法，不需要指定终结符个数和非终结符个数。