算符优先分析文法
一、写在前面
&&&&& 算符优先分析文法是一种工具，在编译的过程中，隶属于语法分析环节，却又与中间代码的生成息息相关，编译可以分为五个阶段：词法分析、语法分析、语义分析（中间代码的生成）、代码优化、目标代码生成。语法分析是指：在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。也就是说语法分析是检验输入串的语法是否正确，注意这里的语法正确，只是简单地符合自己定义的规范，而不能检测出运行时错误，比如"X/0"，空指针错误，对象未初始化等错误。在这一个实验中，我将通过算符优先分析文法这一个工具，在语法分析的时候，顺便进行语义分析，也就是识别出语法单位，同时简要的将识别出的中间代码进行计算（目标代码的生成+运行），得到相应的结果，来检验自己设计的正确性。可以说题目虽然叫做算符优先分析文法，其实却是一个贯穿了“词法分析+语法分析+语义分析+中间代码优化+目标代码生成+运行”全过程的一个极具概括性的程序。如果能将这个程序得心应手的完成出来，我相信诸位对编译原理的掌握也算是炉火纯青了。时隔将近两年再来整理自己以前写过的实验报告，还是挺有感慨的，对一件东西感兴趣，原来影响还会如此深远，还记得自己当时连续六个小时全神贯注写出的实验报告，现在看看竟然写了五六十页，核心内容也有三四十页，不觉的感慨当年充满热情的时代慢慢的竟走出许久~~二、算符优先分析文法实验
2.1、任务：&& 实验目的：&&&&&&&&&& 1.了解掌握算符优先分析的基本方法、内容；&&&&&&&&&& 2.学会科学思考并解决问题，提高程序设计能力。& 实验内容与要求：& & & & 用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中；若存在错误，提示错误相关信息。&& 文法表示：&&&& S→v=E|E?|clear&&&& E→E+T|E-T|T&&&& T→T*F|T/F|F&&&& F→ (E)|v|c& && 单词种别码设计：&&&&&&& =&& 1&&&&&&& ？& 2&&&&&&& +&& 3&&&&&&& -&&& 4&&&&&&& *&& 5&&&&&&& /&&& 6&&&&&& （& 7&&&&&&& ）& 8&&&&&&& v&&&& 9&&&&&& c&&&& 10&&&&&& clear 11&&&&&& #&&&& 12&&&&&& N&&& 13&& 可归约串语义解释：&&&&&&& 变量归约；常量归约；运算归约；括号归约；&&&&&&& 赋值语句；输出语句;清除语句。&& 演示示例：&&&&&&&& a=5&&&&&&&& b=a+10&&&&&&&& b?&&&&&&&& b+a*a?&&&&&&&& a=a+b &2.2、分析与设计
&&&&& 首先，这是一个很好的题目，从知识的理解、将形式化的东西转化成具体的过程、编程能力、编程技巧、调试改错能力等多个方面考察了我们的学习情况。 算符优先文法是一种自下而上的文法分析方法，这种方法的用处十分广泛，虽然有的文法不能用算符优先分析文法，如类似…PQ…..（P，Q为非终结符）这样形式的产生式，但是对于大部分文法这种分析方法还是十分有用的。&&&& 其次，对于本程序中的文法，实质上是算数表达式的计算。用这种文法就是再好不过了，作为从算符文法抽象出来的算符优先文法当然继承了算符文法的特性。下面就切入正题了，我将详细介绍一下我对于这个文法的思考出发点和分层分析的方法。&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&模块一：构建firstVT()和lastVT()这两个集合&&&&&&& 基于“优先”这两个字，有效的回避了左递归（自上而下文法分析）和二义性的问题。关键是如何体现“优先”这两个字。这就需要firstVT()和lastVT()集合了。firstVT(E)={a|E→a…..|E→Qa….|firstVT(Q)},从这个定义可以看到，firstVT()主要找到是本产生式中的第一个非终结符和若第一个是非终结符则包含该非终结符的firstVT()集，因为firstVT有可能要求Q的firstVT()集，因此有可能要用递归才能求尽所有的firstVT()集。同理，lastVT(E)={a|E→….a|E→…….aQ},可见这两个关系好像反对称的影像。说了这么多，还是没有说到这两个集合要干什么用。让我们想象一个句型…aQ…..&&&&&& 在这个句型中我们知道只有等Q的短语规约为Q了，才有可能将…aQ….再次向上规约，因此a的优先级要小于Q产生式的firstVT(Q)集，因为我们可以断定a必定是比Q中第一个出现的终结符优先级低的，也就是说优先级a&优先级firstVT(Q)，至于第二个，第三个终结符。。。我们不敢判定。于是才要费尽心思地构造firstVT()这样的一个集合。同理，对于lastVT()，让我们想一下这种情况…..Qa…..,对于这个句型我们知道只有当Q的短语归约成了Q，我们才敢将….Qa……向上归约。这样的话就是说Q的产生式中最后出现的一个终结符的优先级必定是比a的优先级高的，也就是优先级lastVT(Q)&优先级a，同样的对于倒数第二个，倒数第三个终结符。。。我们不敢判定。说了这么多我想应该能够理解这两个集合存在的必要性和决定性了。
& 因为是程序，我就说一下程序如何实现这两个集合的求解。&&&& 首先是一些数据结构和意义：& && char FIRSTVT[20][20];&&& 存储firstVT()集，第二维代表第几个产生式，第一维代表集合中的第几个元素&&&& char LASTVT[20][20];& & 存储lastVT()集，第二维代表第几个产生式，第一维代表集合中的第几个元素&&&& char INPUT[20][20];& & 按照一定的形式存储文法中的所有产生式。& 然后是几个函数：&& 1.& void setFIRSTVT(char X,int T)；&&&&&&&& 这个函数的目的是将求出的终结符X，存放到第T条产生式的左部对应的firstVT集合中。&& 2.& void getFIRSTVT(char X,int S)&&&&&&& S标记产生式的位置，X为将要计算的产生式的左部。这个函数就比较复杂了，它将完成求出一个产生式左部的firstVT的终结符的重要任务，可以说是主控程序了。它的算法是逐个遍历产生式，对每个产生式求出该产生式的直接a,并且若有E→Qa…还要递归的求出Q的firstVT()将其并入firstVT(E)的集合中。&& 3.& 同理void setLASTVT(char X,int T)&& 4.& void getLASTVT(char X,int S)和上面类似。&& 5.& void DisplayFirstVT_LasVT()&&&&&&& 这个函数也是主程序开始时要进入的位置。它主要提示用户输入文法（产生式组），然后调用上面的函数计算并显示两种集合。&下面是void getFIRSTVT(char X,int S)的函数。
1 //找出FIRSTVT集元素
2 void getFIRSTVT(char X,int S)
int i,j=<span style="color: #,k;//j当前数组指针
int T=<span style="color: #;//X position
int L=<span style="color: #;//X offspring length
char C[<span style="color: #];
for(i=<span style="color: #;i&<span style="color: #;i++)
<span style="color: #
<span style="color: #
if(INPUT[i][<span style="color: #]==X)//找到将要处理的产生式
<span style="color: #
<span style="color: #
T=i; //标记产生式的位置
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
//按照规则从产生式的右部第一个字符开始处理，直至遇上'/n'
<span style="color: #
//每一次都判断指针j指向的字符若满足p--&w中w的规定则放进C[]
<span style="color: #
//若遇上‘|’或'\n'则求这段右部对应的firstVT()
<span style="color: #
for(i=<span style="color: #;i&<span style="color: #;i++)
<span style="color: #
<span style="color: #
if(INPUT[T][i]=='|'||INPUT[T][i]=='\n')
<span style="color: #
{//刚开始走不到这里
<span style="color: #
L=j;//j指针所指位置为C[]中字符串的长度
<span style="color: #
j=<span style="color: #;//交给L后就清零，以供下一次使用
<span style="color: #
for(k=<span style="color: #;k&L;k++)
<span style="color: #
{//要是数组C[]中的终结符，如小写字母'a'~'z'，加减乘除，乘方，#
<span style="color: #
//则归入fisrstVT集中
<span style="color: #
//若是Aab...则a成为F()一部分，b被忽略,A也不用求first集？？？需要求！！！除非A==X
<span style="color: #
//若是QRa...，则不是算符优先文法，故不可能
<span style="color: #
//若是a...则只是填进a
<span style="color: #
<span style="color: #
if((C[k]&=<span style="color: #&&C[k]&=<span style="color: #2)||C[k]=='+'||C[k]=='*'||C[k]=='-'||C[k]=='/'||C[k]=='!'||C[k]=='('||C[k]==')'||C[k]=='#'||C[k]=='\?'||C[k]=='=')
<span style="color: #
{//只能用一次,因是算符优先文法，故前两个中必会至少存在一个终结符
<span style="color: #
setFIRSTVT(C[k],S);//存入FIRSTVT中，S标记产生式的位置
<span style="color: #
break;//跳出循环保证存入的是最左边的终结符
<span style="color: #
<span style="color: #
<span style="color: #
if(C[<span style="color: #]&=<span style="color: #&&C[<span style="color: #]&=<span style="color: #&&C[<span style="color: #]!=X)
<span style="color: #
{//若C[0]中为A~Z,并且C[0]不是X(否则将无限循环)，则递归的进行填充
<span style="color: #
int flag=<span style="color: #,
<span style="color: #
for(count=<span style="color: #;count&<span style="color: #;count++)
<span style="color: #
<span style="color: #
if(INPUT[count][<span style="color: #]==C[<span style="color: #])//找到将要处理的产生式
<span style="color: #
<span style="color: #
flag=<span style="color: #;//若存在，则填充
<span style="color: #
<span style="color: #
<span style="color: #
if(flag==<span style="color: #)
<span style="color: #
{//递归，所用极妙，画龙点睛
<span style="color: #
getFIRSTVT(C[<span style="color: #],S);//S为子集中的元素填入父集中指明了方向
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
else if(INPUT[T][i]!='|'&&INPUT[T][i]!='\0')//该行没结束，过滤'\0'
<span style="color: #
<span style="color: #
C[j]=INPUT[T][i];//j从0开始
<span style="color: #
j++;//移进
<span style="color: #
<span style="color: #
if(INPUT[T][i]=='\n')
<span style="color: #
{//该行结束
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: # }
& 比如说对于这个文法分析出的集合如下：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 模块二：构建优先符号表&&&& 为了体现“优先”的关系，只是构建出了上面的两种集合是不够的，由上面分析我们知道了这两个集合的用处。说白了就是为了构造出算符优先分析表。因为关系无非四类1.等于，2.大于，3.小于，4没有关系。注意这里的“没有关系”也是一种关系。&&&&&& 而由第一个阶段产生的两个集合就可以找到所有的大于和小于关系，那就只剩下了等于关系，如果等于关系找到了，剩余的没有填写的关系就是没有关系。等于关系是这样的：如果存在这样的句型.....ab....或.......aQb.....则关系(a==b)。这样的结果也是显而易见的，因为a和b注定要共同归约，没有谁先谁后，因此是等于关系。&&&&& 好了现在所有关系都搞请了，就可以建表了。& 还是首先解释一下新定义的一个数据结构:& char PriorityTable[20][20];&&&&& 优先关系表，其中存放着终结符以及终结符对应的关系。& 然后是一些函数：&& 1.int&& IsVT(char ch)& & && 判断ch是否为终结符，若是则返回1，否则返回0&& 2.int&& SearchTbl(char ch)& & & 搜索终结符ch在符号表中的行列数，用来定位将要填写的位置。& 3.int FL_map(char ch)& & & 这个映射既是查找产生式左部的位置，若存在则返回该产生式的条数，即是第几个产生式，失败则返回-1这个出错标记。& 4.void&& &createPriorityTable()& & & 这个是建表的主控程序，用来填写所有关系与表中。遍历所有的产生式，填写所有的关系。这里主要解释一下程序是如何找到横纵坐标并且将关系填写进去的。对于简单的情况只要拿一个终结符来使用SearchTbl(终结符)就可以找到横（纵）坐标了，但是因为对于大小关系我们往往要填的是“终结符&firstVT()”或“lastVT()&终结符”这样的情况，因此势必要从集合中取出终结符，并用该终结符来映射坐标，即是用到了类似这样的转换：& & & & temp_column=FIRSTVT[FL_map(C[2])][count_1];&&& &&& & & tbl_column=SearchTbl(temp_column);//将上述结果再次转换& 或者temp_row=LASTVT[FL_map(C[1])][reg];&&&&&&& tbl_row=SearchTbl(temp_row);//map&& 这样的映射。知道了这些程序不难读懂。&& 5.void DisplayPriorityTable()&&&&& 这个函数就是显示优先关系表的内容的。下面是 void&& &createPriorityTable() 函数的实现过程：
createPriorityTable()
2 {//创建并填写优先级表
//对每个产生式遍历，求出四种关系1.=,2.&,3.&,4.没有关系
char temp[<span style="color: #]={'+','-','*','/','(',')','v','c','=','?','#','\0'};
int j,L,i;
int tbl_row,tbl_//表的元素坐标
char C[<span style="color: #];
for(int r=<span style="color: #;r&<span style="color: #;r++)
PriorityTable[<span style="color: #][r]=temp[r-<span style="color: #];//初始化行头，第0行
PriorityTable[r][<span style="color: #]=temp[r-<span style="color: #];//初始化第0列
//扫描产生式的右部，如果发现终结符且该终结符周围有其他字符
//若该其他字符为终结符，则这两者关系为相等
//若该其他字符为非终结符，则根据非终结符的firstVT,LastVt填表
for(int p=<span style="color: #;p&<span style="color: #;p++)
j=<span style="color: #;
for(i=<span style="color: #;i&<span style="color: #;i++)
{//注意，此处因为时间有限考虑不是很全面，只是对老师给定的文法进行了周密的部署
//在别的文法上可能需要少许加工，不是问题
if(INPUT[p][i]=='|'||INPUT[p][i]=='\n')
{//刚开始走不到这里
L=j;//j指针所指位置为C[]中字符串的长度
j=<span style="color: #;//交给L后就清零，以供下一次使用
if(L&<span style="color: #)//大于一则处理，否则不关心
{ //对于清零指令l自动忽略
if(IsVT(C[<span style="color: #])&&IsVT(C[<span style="color: #])||(L==<span style="color: #)&&IsVT(C[<span style="color: #])&&IsVT(C[<span style="color: #])&&(FL_map(C[<span style="color: #])!=-<span style="color: #))
{//若为终结符因至少有两个,若出现两个终结符则C[0]'=='C[1]||C[2]，注意这是此文法的情况
//则需要填表，查表找到C[0]的行数，C[1],C[2]的列数进行填表
tbl_row=SearchTbl(C[<span style="color: #]);//记录行数
if(IsVT(C[<span style="color: #]))
{//列数，若是终结符 v=
tbl_column=SearchTbl(C[<span style="color: #]);
if(IsVT(C[<span style="color: #])&&(L==<span style="color: #))
{//列数 (E)
tbl_column=SearchTbl(C[<span style="color: #]);
PriorityTable[tbl_row][tbl_column]='=';//填表
if((L==<span style="color: #)&&IsVT(C[<span style="color: #])&&IsVT(C[<span style="color: #])&&(FL_map(C[<span style="color: #])!=-<span style="color: #))
{//v=E,这种情况
int count_1=<span style="color: #;
char temp_
tbl_row=SearchTbl(C[<span style="color: #]);// =&firstVT(E)
while(FIRSTVT[FL_map(C[<span style="color: #])][count_1]!='\0')
{//填写小于关系
temp_column=FIRSTVT[FL_map(C[<span style="color: #])][count_1];//映射，仔细体会
tbl_column=SearchTbl(temp_column);//将上述结果再次转换
PriorityTable[tbl_row][tbl_column]='&';//填写关系
count_1++;//准备填写下一个
count_1=<span style="color: #;//清零
if((L==<span style="color: #)&&IsVT(C[<span style="color: #])&&IsVT(C[<span style="color: #])&&(FL_map(C[<span style="color: #])!=-<span style="color: #))
{//弥补(E)，针对本文法
//首先填写&关系
char temp_row,temp_
int reg=<span style="color: #;
tbl_row=SearchTbl(C[<span style="color: #]);
while(FIRSTVT[FL_map(C[<span style="color: #])][reg]!='\0')
{//填写小于关系 '('&firstVT(E)
temp_column=FIRSTVT[FL_map(C[<span style="color: #])][reg];
tbl_column=SearchTbl(temp_column);//皆是映射
PriorityTable[tbl_row][tbl_column]='&';
reg=<span style="color: #;//清零
tbl_column=SearchTbl(C[<span style="color: #]);
while(LASTVT[FL_map(C[<span style="color: #])][reg]!='\0')
{//填写大于关系 lastVT(E)&')'
temp_row=LASTVT[FL_map(C[<span style="color: #])][reg];
tbl_row=SearchTbl(temp_row);//map
PriorityTable[tbl_row][tbl_column]='&';
reg=<span style="color: #;//reset
else if((FL_map(C[<span style="color: #])!=-<span style="color: #)&&IsVT(C[<span style="color: #]))
{//C[0]肯定为非终结符lastVT(C[0])&C[1]
//填写大于关系
char temp_row,temp_
int count=<span style="color: #;
tbl_column=SearchTbl(C[<span style="color: #]);
while(LASTVT[FL_map(C[<span style="color: #])][count]!='\0')
{//填写大于关系
temp_row=LASTVT[FL_map(C[<span style="color: #])][count];
tbl_row=SearchTbl(temp_row);//同上
PriorityTable[tbl_row][tbl_column]='&';
count=<span style="color: #;
if(L==<span style="color: #)
{//在这种情况下C[2]必为非终结符，求C[2]的firstVT(),填写小于关系
//E+T,E-T,T*F,T/F等情况
tbl_row=SearchTbl(C[<span style="color: #]);
while(FIRSTVT[FL_map(C[<span style="color: #])][count]!='\0')
<span style="color: #0
{//填写小于关系
<span style="color: #1
temp_column=FIRSTVT[FL_map(C[<span style="color: #])][count];
<span style="color: #2
tbl_column=SearchTbl(temp_column);//map
<span style="color: #3
PriorityTable[tbl_row][tbl_column]='&';
<span style="color: #4
<span style="color: #5
<span style="color: #6
count=<span style="color: #;
<span style="color: #7
<span style="color: #8
<span style="color: #9
<span style="color: #0
<span style="color: #1
else if(INPUT[p][i]!='|'&&INPUT[p][i]!='\0')//该行没结束，过滤'\0'
<span style="color: #2
<span style="color: #3
C[j]=INPUT[p][i];//j从0开始
<span style="color: #4
j++;//移进
<span style="color: #5
<span style="color: #6
if(INPUT[p][i]=='\n')
<span style="color: #7
{//该行结束
<span style="color: #8
<span style="color: #9
<span style="color: #0
<span style="color: #1
<span style="color: #2
//补上#的关系
<span style="color: #3
for(int m1=<span style="color: #;m1&<span style="color: #;m1++)
<span style="color: #4
<span style="color: #5
PriorityTable[SearchTbl('#')][m1]='&';//这个容易理解，补行
<span style="color: #6
<span style="color: #7
for(int m2=<span style="color: #;m2&<span style="color: #;m2++)
<span style="color: #8
<span style="color: #9
PriorityTable[m2][SearchTbl('#')]='&';//补列
<span style="color: #0
<span style="color: #1
PriorityTable[SearchTbl('#')][SearchTbl('#')]='=';
<span style="color: #2 }
&比如说对于这个文法分析出来的优先关系表如下：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 模块三：构建词法分析的程序&&&& 做好了上面两步运算已经累得不行了，下面还要继续进行分析，那就是词法分析程序，多亏这个程序在实验一已经完成过，这里就拿出那里的代码进行必要的改进和删除，保留适合本文法要求的部分即可。其实想来无非是用到了识别标识符、识别常数、识别+、-、*、/、？、#、（、）、保留字clear等符号的算法罢了。还是比较好写的。但考虑到后面的运算，也就是最精彩的部分a=3;b=a+3;这样的句子，我们不得不在进行词法分析的时候将这些标识符登记到标识符表中，将句子打碎成二元组存放到符号表中。注意这里的符号表没有什么其他意义，就是存放将句子解释成的有序序列罢了。综上所述，词法分析这一过程就是识别字符串，若正确则填表，若错误，则报错。两个任务：填表、报错。由此也可以看到表格处理和错误处理在整个编译过程中无处不在。这里新增了一些数据结构和全局变量：typedef struct {& char IDentifier[30];//标识符长度& int&//定义标识符代表的数值}IDentifierTtypedef struct {& int&//种别码& int&//数值或者标识符入口指针}SymbolTIDentifierTable& idTbl[30];//定义全局标识符表SymbolTbl symbol[100];//定义符号表，记录输入的程序片段下面是这一模块的具体的函数：1.void InsertID(char name[],int entry,int value)&&& 功能是将标识符的名字和数值插入到以entry为标识符入口地址的标识符表中。2.int& ScanEntry(char name[])&&&& 查找标识符表中是否有空闲位置，若有则返回入口地址，若无则报错。3.void Insert_Into_SymbolTbl(int syn,int value,int &pointer)&&&& 将句子打散成的所有的二元组（名字和数值）插入到以pointer为符号表入口地址的符号表中。4.bool& IsExist(char id[])&&&& 查找表中是否已经存在该标识符5.int& Search_Free_Entity( )&&& 这个函数即是在标识符表中申请一个可用的存储空间，若有则返回入口地址，否则报错，申请失败。6.bool IsLetter(char letter)& && 判断是否为字母7.bool IsDigit(char digit)&&&& 判断是否为数字8.void Scanner(char sentence[],char name[],int &syn,int &scan_point,int &value)& & 扫描子程序，识别正规式。对句子进行扫描，抛出一个个单词。scan_point为扫描的总指针，name和value用来记录返回值；sentence即是要分析的句子；syn为种别码。这个程序是词法分析的核心，在上一实验中已详细介绍过，再次不必赘述。9.bool Check_Is_Right(char sentence[])&&& 检查句子是不是#。。。#的形式，因为程序的需要，输入的句子规定必须是这样的形式。10.void LexicalAnalysisCtl()&&& 词法分析的主控程序，也就是老师上课一再讲的那个主控程序。这个程序控制着Scanner(char sentence[],char name[],int &syn,int &scan_point,int &value)产生不同的正规式，并且负责着登记数据和错误处理。11.void Clear_Symbol_Tbl()&&& 这个函数负责着清除符号表中的句子，以便接下来的句子输入。12.void Clear_IDentifier_Tbl()&&& 这个函数的功能是清楚标识符表的所有内容。一般会在“清除语句”中使用。下面是Scanner的程序：
1 void Scanner(char sentence[],char name[],int &syn,int &scan_point,int &value)
char token[<span style="color: #],
int p_token=<span style="color: #;//token的指针
int digit_value=<span style="color: #;//记录常数的大小
for(int n=<span style="color: #;n&<span style="color: #;n++)
token[n]='\0';//对字符数组清零
<span style="color: #
ch=sentence[scan_point];
//读入一个字符
<span style="color: #
if(ch=='#'&&scan_point==<span style="color: #)
<span style="color: #
{//该字符的种别码已经在主程序中登记了
<span style="color: #
scan_point++;//刚开始的第一个字符一定为‘#’
<span style="color: #
ch=sentence[scan_point];//指针下移，扫描下一字符
<span style="color: #
<span style="color: #
if(IsLetter(ch))
//ch是否为字母
<span style="color: #
<span style="color: #
while(IsLetter(ch)||IsDigit(ch)) //ch是否为字母或数字
<span style="color: #
<span style="color: #
token[p_token++]=
<span style="color: #
scan_point++;
<span style="color: #
ch=sentence[scan_point];
//读入一个字符
<span style="color: #
<span style="color: #
token[p_token]='\0';
<span style="color: #
syn=<span style="color: #;//代表找到了标识符
<span style="color: #
if(strcmp(token,"clear")==<span style="color: #)
<span style="color: #
{//代表找到了保留字“clear”
<span style="color: #
syn=<span style="color: #;
<span style="color: #
<span style="color: #
strcpy(name,token);//带回标识符
<span style="color: #
<span style="color: #
else if(IsDigit(ch))
//ch是否为数字
<span style="color: #
<span style="color: #
digit_value=<span style="color: #;
<span style="color: #
while(IsDigit(ch))
<span style="color: #
{ //此处假设只是整数
<span style="color: #
digit_value=digit_value*<span style="color: #+ch-'<span style="color: #';
<span style="color: #
scan_point++;
<span style="color: #
ch=sentence[scan_point];
//读入一个字符
<span style="color: #
<span style="color: #
value=digit_//带回整数值
<span style="color: #
syn=<span style="color: #;
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
switch(ch)
<span style="color: #
<span style="color: #
case'=':syn=<span style="color: #;
<span style="color: #
case'?':syn=<span style="color: #;
<span style="color: #
case'+':syn=<span style="color: #;
<span style="color: #
case'-':syn=<span style="color: #;
<span style="color: #
case'*':syn=<span style="color: #;
<span style="color: #
case'/':syn=<span style="color: #;
<span style="color: #
case'(':syn=<span style="color: #;
<span style="color: #
case')':syn=<span style="color: #;
<span style="color: #
case'#':syn=<span style="color: #; break;
<span style="color: #
default:printf("输入句子有误！\n");exit(<span style="color: #);break;
<span style="color: #
<span style="color: #
scan_point++;//保持指针始终指向待判断的字符
<span style="color: #
ch=sentence[scan_point];
//读入一个字符
<span style="color: #
<span style="color: # }
&下面是主控程序：
1 void LexicalAnalysisCtl()
2 {//主控程序
char sentence[<span style="color: #0]="\0";
int syn=-<span style="color: #;
char name[<span style="color: #]="";
int scan_point=<span style="color: #;//从开始处扫描
int id_//定义标识符表入口指针
int sym_pointer=<span style="color: #,
<span style="color: #
<span style="color: #
<span style="color: #
printf("请输入句子,以#开始并且以#结束\n");
<span style="color: #
scanf("%s",sentence);
<span style="color: #
}while(!Check_Is_Right(sentence));
<span style="color: #
Insert_Into_SymbolTbl(<span style="color: #,-<span style="color: #,sym_pointer);
<span style="color: #
printf("(%d ,
)\n",<span style="color: #);
<span style="color: #
while(syn!=<span style="color: #)
<span style="color: #
{//直到扫描到第二个‘#’为止
<span style="color: #
Scanner(sentence,name,syn,scan_point,value);
<span style="color: #
switch(syn)
<span style="color: #
{//若是单词
<span style="color: #
case <span style="color: #:printf("(%d , %s)\n",syn,name);
<span style="color: #
//登记到表中
<span style="color: #
if(!IsExist(name))
<span style="color: #
{//不存在则插入
<span style="color: #
//查找可插入位置
<span style="color: #
id_pointer=Search_Free_Entity();
<span style="color: #
InsertID(name,id_pointer,-<span style="color: #);//-1代表还没被赋值
<span style="color: #
<span style="color: #
//搜索该标识符的入口地址放入value中
<span style="color: #
entry=ScanEntry(name);
<span style="color: #
Insert_Into_SymbolTbl(syn,entry,sym_pointer);
<span style="color: #
<span style="color: #
case <span style="color: #://常数
<span style="color: #
Insert_Into_SymbolTbl(syn,value,sym_pointer);
<span style="color: #
printf("(%d
, %d)\n",syn,value);
<span style="color: #
<span style="color: #
default:printf("(%d ,
)\n",syn);
<span style="color: #
Insert_Into_SymbolTbl(syn,-<span style="color: #,sym_pointer);//-1代表该处不需要值
<span style="color: #
<span style="color: #
<span style="color: #
printf("--------------------词法分析正确！！！-------------------------\n");
<span style="color: #
//打印出符号表和标识符表
<span style="color: #
printf("标识符的入口地址
标识符的值(-1代表没被赋值)\n");
<span style="color: #
for(int m1=<span style="color: #;m1&<span style="color: #;m1++)
<span style="color: #
{//标识符表
<span style="color: #
if(!(strcmp(idTbl[m1].IDentifier,"")==<span style="color: #))
<span style="color: #
<span style="color: #
printf("\t%d
%d\n",m1,idTbl[m1].IDentifier,idTbl[m1].value);
<span style="color: #
<span style="color: #
<span style="color: #
printf("符号表的入口地址
具体的值(或标识符入口)\n");
<span style="color: #
for(int m2=<span style="color: #;m2&sym_m2++)
<span style="color: #
<span style="color: #
printf("\t%d
%d\n",m2,symbol[m2].syn ,symbol[m2].value);
<span style="color: #
<span style="color: #
printf("---------------------------------------------------------------\n");
<span style="color: # }
比如说对于#temp=2+(3*(2+4))#这个句子的词法分析结果为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&模块四：核心功能模块------算符优先分析& & & 前面做了那么多铺垫就是为了算符优先分析做准备。到了这一步，真的很不容易，因此我们更要对今天的编译器的处理能力感到惊叹，的确不是一个人可以完成的，就算一个人可以完成那所用的时间也真的不值。但是对于我们来说，学习一些《编译原理》上的一些处理问题的办法和角度，对我们未来的工作和生活绝对是大有裨益的。好了，就说一说这个费了我两天才完成的核心程序吧。&&&& 其实，核心程序并没有那么难以理解！只要我们举几个简单的例子，模拟一下计算机在处理这个句子的过程，便不难写出程序。& && 首先分析我们现在有什么？& && 1.现在的情况是已经分析出了句子的单词，并且变成了单词块，存放在SymbolTbl symbol[100]中，单词的形式是（种别码，常数值）（种别码，标识符入口地址）、（种别码，用-1表示无意义）这是三大类。&&&& 2.并且分析出了标识符存放在了IDentifierTable& idTbl[30]中。标识符的形式是（标识符名字，标识符的值），用-1表示暂未被赋值（这里就凑合一点，时间比较紧，待改进）。& && 3.分析出了算符优先分析的优先关系表存放在char PriorityTable[20][20]中。& && 4.已经编码出了种别码表，放在char SymbolTbl_Define[15]中，这个是老师要求的次序，便于一致。但又需要一次转换，以后再说。& && 好了，我们已经有了这么多数据和方法（函数function），是不是马上就可以进行下去了呢？！还不行，因为我们迫切需要一个后进先出的存储结构来保存我们的数据，来完成我们的移进，归约。那就是——栈。我们需要构造一个这样的栈：它的每个元素的数据结构都是符号表中元素的数据结构，即为（种别码，--），--处即为上面分析的三种情况。栈的能力主要有：
template &typename T&1.T gettop()& 获得栈顶元素2.int getTopPointer()&得到栈顶指针的数值3.T& traverseStack(int pointer)&定义遍历整个栈的能力4. void push(T num)&将元素压栈的能力5.T& pop()&将元素弹出栈的能力6.Stack(){top=-1;}&初始化的能力7.void Clear_Stack()&清空堆栈的能力数据对象：Stack&SymbolTbl&& Reource_S//定义堆栈还有几个分析将使用的函数：char SearchSyn(int syn)根据种别码返回相应字符，因为我们是在对种别码进行大小比较，需要先将该种别码映射成具体的终结符。然后再将该终结符映射成优先关系表中的横纵坐标。int Search_Priority_Setxy(char ch)搜索一个字符在优先符表中的位置，这就是我说的“将该终结符映射成优先关系表中的横纵坐标。”的映射方法。void& Print_Context(int Stack_Top,int Sym_Pointer)打印出当前堆栈和符号表的上下文void& MainProc_Analysis()主分析函数，整个算法的核心。& 好了，有了这些东西，我们的分析总算可以一马平川了。&&& 1.首先将符号表的第一个元素#,对应的（种别码，-1）压栈，即& & && SymbolTbl& temp_& &&&& temp_sym.syn=12;&&&&&& temp_sym.value=-1;//-1代表这个地方不需要&&&& & Reource_Symbol.push(temp_sym);//将#压栈&&& 2.对于堆栈定义两个指针，一个指针pStackTop始终指向栈顶，在栈被修改（push,pop）之后都要修改。另一个堆栈指针是pScanStack，负责对整个堆栈的扫描，不断地查找可归约串的结束位置。 对于符号表，定义Sym_scan_pointer指针，从一开始，对符号表进行扫描。&& 3.因为现在不仅是语法分析，还包含了语义分析，我们要定义好语义子程序，比如说“清除语句”，#clear#，我们遇到这个东西时，就要1.清空符号表和标识符表；2.清除屏幕（我自己理解的，清除应该就是这些吧。。。）& 因此，我们在进行其他分析之前，先把这个清除语句搞定。&&& if(sym_length&=3&&(symbol[1].syn==11))&& {//清除语句，清除屏幕并且清空标号表中的值&&& && Clear_IDentifier_Tbl();&&& && Clear_Symbol_Tbl();&&& && system("cls");&&& &&&& }&& 4.扫除了这些障碍，我们总算可以进行真正的分析了。&& 首先栈扫描指针和栈顶指针同时指向栈顶开始分析：下面进行永真循环：*******************************************************************{查看栈扫描指针pScanStack所指的元素和符号表指针所指元素的关系。4.1若为小于：&& 则将符号表指针所指元素压栈，修改栈的两个指针都指向栈顶。符号表指针下移。4.2若为等于：& 此时要分两种情况：@1.若是栈扫描指针pScanStack所指的元素和符号表指针所指元素都是#，则查看栈中是否只有两个元素且栈顶元素是否为N，若为真，则说明归约成功，输出栈顶的值，然后结束分析。否则，则报错。& @2.若不是上面的情况，则按照小于关系处理。4.3若为大于：& 这个时候，就是激动人心的时候了，因为要进行归约了。& 首先对齐pStackTop，pScanStack这两个指针，虽然这个时候肯定是对齐的（自己想），然后进入小循环 while(Prior_Relation=='&')，小循环的内容是：& &&&&&&&&&&&& ************************************************&&&& 判断现在栈扫描指针所指元素的种别码，该种别码所对应元素即是大于符号表中指针所指的元素。&& 4.3.1若该元素为标识符：语义分析：判断标识符是否已定义；弹出栈顶元素，将N（13，标识符的值）压入栈中，这里取了一次巧，即是让N来承载归约的结果，更加方便。重新修改栈顶指针，栈扫描指针，将栈扫描指针指向从栈顶数第一个终结符的位置，即下移。&&& pScanStack=Reource_Symbol.getTopPointer()-1;重新定位行列指针（列不变），修改关系。&& row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Prior_Relation=PriorityTable[row_prior][column_prior];&&&& 4.3.2若该元素为常量，则分析的过程和标识符极其相似，唯一不同的是，N(13,值）中的‘值’，一个是从标识符表中查到的，另一个是直接就有的。4.3.3若该元素为‘=’，这时根据文法的要求，出现等号就应该满足“v=N”这种情况。首先判断是否满足，若不满足则报错，若满足，则将这三个元素归约为一个元素N（13，旧N.value),并且要反填符号表，将该变量的值赋为旧N.value。这一步语义分析十分重要，直接关系着以后引用这个变量时是否能够找到它的值。&&&&&&&&&&& idTbl[Reource_Symbol.traverseStack(pScanStack-1).value].value=Reource_Symbol.gettop().//此时栈顶必为E&&&&& 然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。&& 4.3.4若该元素为+、-、*、/，则这四个的处理方式一样。首先判断栈顶是否满足N op N,op={+|-|*|/},若满足则归约，否则认为是错误的，进行报错处理。规约之后，同样的将N op N归约为N，并且将& “新N.value=(N1.value op N1.value)”& ------语义分析
&& 然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。&&&& 4.3.5若该元素为‘）’，这个时候栈顶一定为（N），若不是，则句子出错，进行错误处理，又因为’(‘是大于任何终结符的，因此（N）就构成了“鱼眼睛”，“& = &”,所以需要归约将（N）归约为N，做相应的语义分析子程序:&&&&&&& N.value=（N1.value），然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。& 因为’(‘小于任何终结符，因此不会出现在这里。&&&&&&&& 然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。&&&& 4.3.6若该元素为‘？’根据文法，出现这个东西，就是要打印N?中N的值了，因此先查看栈顶是否满足N？若满足，则归约，并作相应的语义动作，打印。&&&&& 然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。&&&&& 满足大于关系的就这些终结符，我已一一分析了它们的语法分析和语义的动作。若该元素不是上面的终结符，则认为句子错误。否则将进行 while(Prior_Relation=='&')，的判断，若满足继续循环，否则，进入永真大循环中。
&&&&&&&&&&&&& *******************************************************************************************************************}//永真循环结尾
上面就是整个算符优先算法的精髓了。比如说对于上文的#temp=2+(3*(2+4))#分析的过程和结果为：
经过这么长时间的分析又浪费了一个晚上的时间，但觉得还是一气呵成，并且又理了一遍思路，还是值得的。& 通过上面的叙述，整个程序的结构呼之欲出：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&五.总控模块&最后的main()函数直接调用各个模块就可以了。代码如下：
char//是否继续的标记
//计算并显示firstVT()和LastVT()
DisplayFirstVT_LasVT();
//创建算符优先关系表
createPriorityTable();
//打印算符优先关系表
DisplayPriorityTable();
//cout&&"请输入语句的个数"&&
while(<span style="color: #)
//首先要清空符号表，这样才能进行下一轮分析
Clear_Symbol_Tbl();
//词法分析，登记符号表
LexicalAnalysisCtl();
//语法语义分析，产生运行结果
MainProc_Analysis();
cout&&"continue? y or n"&&
if(!(ch=='y')&&!(ch=='Y'))
cout&&"the procedure is end"&&
exit(<span style="color: #);
return <span style="color: #;
& 好了，这次的实验分析就到这里了。2.3．程序架构设计& 根据上面的思路，我采用了分文件的形式，这样思路比较清晰，程序比较简洁。下面的四个头文件中分别存放的是四个模块的代码。& #include "firstVT_lastVT.h"//计算firstVT()和LastVT()的程序& #include "GetPriorityTable.h"//创建算符优先关系表的程序& #include "Simple_Lexical_Analysis.h"//词法分析的程序& #include "MainProc_Analysis.h" //主分析程序，用来进行语法和语义分析& 再加上最后的总控程序，整个程序的架构就是这个样子了。2.4．测试&此处使用老师给的范例：演示示例：&&&&&&&& a=5&&&&&&&& b=a+10&&&&&&&& b?&&&&&&&& b+a*a?&&&&&&&& a=a+b
这里试验一下“清除语句”的作用：比若说输入#a=3#:
这里归约的结果为3，即a=3,此时用清除语句，将清屏，并清除标识符表。#clear#
回车之后：
此时输入#b=2#，可以看到表示表中只有b,没有a
则说明a被清除。
2.5、感想&&& 这次的实验花费了我不少时间，但也从中学到了很多，从最初的第一个模块一路走来，也遇到许多挫折，特别是明明逻辑都对却找不到错误的原因的时候，多亏了调试工具。& 编写这个程序一部分来自于学习的课程要求，另一部分也来自于自己对编程的喜爱，或许正是这种感觉一直支持我到现在吧。代码虽然写完了，对于老师给的文法绝对是没问题的，可是毕竟也有它的局限性。即便如此，编译原理的处理问题的思想，思考问题的角度，都让我大受启发。这个程序其实是很全面的，它从词法分析--&语法分析--&语义分析----&问题求解，基本上走完了编译器的大部分生命周期。对于我们理解编译的过程和具体的实现都是很有帮助的。当然，编译原理博大精深，比如说对于数组的处理、中间代码的生成等很多方面，都值得我们认真揣摩。2.6、源代码（所有）
2 模块一：
3 /****************#include"firstVT_lastVT.h"************************/
5 //程序功能大意说明
6 //该子程序主要是求算符优先文法中的firstVT()和lastVT()
7 //因为求firstVT()和lastVT(),可能造成的递归性，我们需要慎重对待。
8 //直至求完所有集合的元素为止
9 //这里要注意递归的运用和FirstVT(),LastVT()的定义
10 //firstVT(E)为a...或Qa....中的终结符a,以及firstVT(Q)中的所有元素。
11 //lastVT(E)为...a或....aQ中的终结符a,以及lastVT(Q)中的所有元素。
13 //引用外部变量
14 extern char FIRSTVT[<span style="color: #][<span style="color: #];
15 extern char LASTVT[<span style="color: #][<span style="color: #];
16 extern char PriorityTable[<span style="color: #][<span style="color: #];
17 extern char INPUT[<span style="color: #][<span style="color: #];
19 //填写firstVT集合
20 void setFIRSTVT(char X,int T)
21 {//X为终结符，T标记产生式id
for(i=<span style="color: #;i&<span style="color: #;i++)
for(j=<span style="color: #;j&<span style="color: #;j++)
{//扫描判断是否加入
if(X==FIRSTVT[i][j])
{//若集合中已出现，则不加
else if(FIRSTVT[i][j]=='\0')
FIRSTVT[i][j]=X;//填入数组最后
43 //找出FIRSTVT集元素
44 void getFIRSTVT(char X,int S)
int i,j=<span style="color: #,k;//j当前数组指针
int T=<span style="color: #;//X position
int L=<span style="color: #;//X offspring length
char C[<span style="color: #];
for(i=<span style="color: #;i&<span style="color: #;i++)
if(INPUT[i][<span style="color: #]==X)//找到将要处理的产生式
T=i; //标记产生式的位置
//按照规则从产生式的右部第一个字符开始处理，直至遇上'/n'
//每一次都判断指针j指向的字符若满足p--&w中w的规定则放进C[]
//若遇上‘|’或'\n'则求这段右部对应的firstVT()
for(i=<span style="color: #;i&<span style="color: #;i++)
if(INPUT[T][i]=='|'||INPUT[T][i]=='\n')
{//刚开始走不到这里
L=j;//j指针所指位置为C[]中字符串的长度
j=<span style="color: #;//交给L后就清零，以供下一次使用
for(k=<span style="color: #;k&L;k++)
{//要是数组C[]中的终结符，如小写字母'a'~'z'，加减乘除，乘方，#
//则归入fisrstVT集中
//若是Aab...则a成为F()一部分，b被忽略,A也不用求first集？？？需要求！！！除非A==X
//若是QRa...，则不是算符优先文法，故不可能
//若是a...则只是填进a
if((C[k]&=<span style="color: #&&C[k]&=<span style="color: #2)||C[k]=='+'||C[k]=='*'||C[k]=='-'||C[k]=='/'||C[k]=='!'||C[k]=='('||C[k]==')'||C[k]=='#'||C[k]=='\?'||C[k]=='=')
{//只能用一次,因是算符优先文法，故前两个中必会至少存在一个终结符
setFIRSTVT(C[k],S);//存入FIRSTVT中，S标记产生式的位置
break;//跳出循环保证存入的是最左边的终结符
if(C[<span style="color: #]&=<span style="color: #&&C[<span style="color: #]&=<span style="color: #&&C[<span style="color: #]!=X)
{//若C[0]中为A~Z,并且C[0]不是X(否则将无限循环)，则递归的进行填充
int flag=<span style="color: #,
for(count=<span style="color: #;count&<span style="color: #;count++)
if(INPUT[count][<span style="color: #]==C[<span style="color: #])//找到将要处理的产生式
flag=<span style="color: #;//若存在，则填充
if(flag==<span style="color: #)
{//递归，所用极妙，画龙点睛
getFIRSTVT(C[<span style="color: #],S);//S为子集中的元素填入父集中指明了方向
else if(INPUT[T][i]!='|'&&INPUT[T][i]!='\0')//该行没结束，过滤'\0'
C[j]=INPUT[T][i];//j从0开始
j++;//移进
if(INPUT[T][i]=='\n')
{//该行结束
109 //存储LASTVT集
110 void setLASTVT(char X,int T)
111 {//X为终结符，T标记产生式id
for(i=<span style="color: #;i&<span style="color: #;i++)
for(j=<span style="color: #;j&<span style="color: #;j++)
if(X==LASTVT[i][j])
{//若集合中已出现，则不加
else if(LASTVT[i][j]=='\0')
LASTVT[i][j]=X;//填入数组最后
134 //找出LASTVT集元素
135 void getLASTVT(char X,int S)
int i,j=<span style="color: #,k;//j当前数组指针
int T=<span style="color: #;//X position
int L=<span style="color: #;//X offspring length
char C[<span style="color: #];
for(i=<span style="color: #;i&<span style="color: #;i++)
if(INPUT[i][<span style="color: #]==X)//找到将要处理的产生式
T=i; //标记产生式的位置
//按照规则从产生式的右部第一个字符开始处理，直至遇上'/n'
//每一次都判断指针j指向的字符若满足p--&w中w的规定则放进C[]
//若遇上‘|’或'\n'则求这段右部对应的LASTVT()
for(i=<span style="color: #;i&<span style="color: #;i++)
if(INPUT[T][i]=='|'||INPUT[T][i]=='\n')
{//刚开始走不到这里
L=j;//j指针所指位置为C[]中字符串的长度
j=<span style="color: #;//交给L后就清零，以供下一次使用
for(k=L-<span style="color: #;k&=<span style="color: #;k--)
{//要是数组C[]中的终结符，如小写字母'a'~'z'，加减乘除，乘方，#
//则归入LASTVT集中
//若是Aab...则a成为F()一部分，b被忽略,A也不用求first集？？？需要求！！！除非A==X
//若是QRa...，则不是算符优先文法，故不可能
//若是a...则只是填进a
if((C[k]&=<span style="color: #&&C[k]&=<span style="color: #2)||C[k]=='+'||C[k]=='*'||C[k]=='-'||C[k]=='/'||C[k]=='!'||C[k]=='('||C[k]==')'||C[k]=='#'||C[k]=='\?'||C[k]=='=')
{//只能用一次
setLASTVT(C[k],S);//存入LASTVT中，S标记产生式的位置
break;//跳出循环保证存入的是最左边的终结符
if(C[L-<span style="color: #]&=<span style="color: #&&C[L-<span style="color: #]&=<span style="color: #&&C[L-<span style="color: #]!=X)
{//若C[0]中为A~Z,并且C[]中没有终结符，则递归的进行填充
int flag=<span style="color: #,
for(count=<span style="color: #;count&<span style="color: #;count++)
if(INPUT[count][<span style="color: #]==C[L-<span style="color: #])//找到将要处理的产生式
flag=<span style="color: #;
if(flag==<span style="color: #)
{//同firstVT()
getLASTVT(C[L-<span style="color: #],S);//S为子集中的元素填入父集中指明了方向
else if(INPUT[T][i]!='|'&&INPUT[T][i]!='\0')//该行没结束，过滤'\0'
C[j]=INPUT[T][i];//j从0开始
j++;//移进
if(INPUT[T][i]=='\n')
{//该行结束
202 void DisplayFirstVT_LasVT()
printf("\t*-------------------------------------------------------*\n");
printf("\t|\t欢迎使用算符优先文法分析器......
printf("\t|\t因时间有限，适用范围可能有限！
printf("\t|\t请输入算符优先文法，按两次回车代表输入完成:
printf("\t|\t版权所有：软件工程2班，朱彦荣，
printf("\t*-------------------------------------------------------*\n");
for(i=<span style="color: #;i&<span style="color: #;i++)
{//获得产生式放入input[][]中
for(j=<span style="color: #;j&<span style="color: #;j++)
scanf("%c",&INPUT[i][j]);
if(INPUT[i][j]=='\n')
break;//每行接收一个产生式
if(INPUT[i][<span style="color: #]=='\n')
break;//遇到又一次回车，结束输入
//保存FIRSTVT集
for(i=<span style="color: #;INPUT[i][<span style="color: #]!='\n';i++)
{//对所有的产生式
getFIRSTVT(INPUT[i][<span style="color: #],i);//第i+1个产生式，求fistvt()，核心算法
printf("FIRSTVT SET:\n");
for(i=<span style="color: #;INPUT[i][<span style="color: #]!='\n';i++)
{//对所有产生式，进行输出fistvt集，最大处理能力20个产生式
printf("FIRSTVT(");
printf("%c",INPUT[i][<span style="color: #]);
printf(")={");
for(j=<span style="color: #;FIRSTVT[i][j]!='\0';j++)
printf("%c",FIRSTVT[i][j]);
if(FIRSTVT[i][j+<span style="color: #]!='\0')
printf(",");//添加逗号
printf("}\n");
printf("\n");
for(i=<span style="color: #;INPUT[i][<span style="color: #]!='\n';i++)
{//对所有的产生式
getLASTVT(INPUT[i][<span style="color: #],i);//第i+1个产生式，求lastvt()，核心算法
for(i=<span style="color: #;INPUT[i][<span style="color: #]!='\n';i++)
printf("LASTVT(");
printf("%c",INPUT[i][<span style="color: #]);
printf(")={");
for(j=<span style="color: #;LASTVT[i][j]!='\0';j++)
{//逐次输出
printf("%c",LASTVT[i][j]);
if(LASTVT[i][j+<span style="color: #]!='\0')
printf(",");
printf("}\n");
printf("\n");
264 /*******************end #include "firstVT_lastVT.h"************************/
266 模块二：
267 /**************#include "GetPriorityTable.h"**********************/
268 //此分程序主要是计算优先关系表
269 //优先分析表是算符优先文法的关键，因此应该慎重对待
270 //如何建表，建什么类型的表，表的使用是不是方便都是我们要考虑的情况
272 extern char FIRSTVT[<span style="color: #][<span style="color: #];
273 extern char LASTVT[<span style="color: #][<span style="color: #];
274 extern char PriorityTable[<span style="color: #][<span style="color: #];
275 extern char INPUT[<span style="color: #][<span style="color: #];
IsVT(char ch)
278 {//判断是否是终结符
if((ch&=<span style="color: #&&ch&=<span style="color: #2)||ch=='+'||ch=='*'||ch=='-'||ch=='/'||ch=='!'||ch=='('||ch==')'||ch=='#'||ch=='\?'||ch=='=')
return <span style="color: #;//为终结符
return <span style="color: #;//不是终结符
SearchTbl(char ch)
287 {//返回符号所在的行列
int index=-<span style="color: #;
//该排列即为优先关系表中元素的排列情况
//行和列的排列相同便于查找和引用
//因此即可以查行又可以查列
char temp[<span style="color: #]={'+','-','*','/','(',')','v','c','=','?','#','\0'};
for(int i=<span style="color: #;i&<span style="color: #;i++)
if(ch==temp[i])
index=i+<span style="color: #;//之所以是i+1，因为该顺序从一开始
return//返回所查找的横(纵)坐标
304 int FL_map(char ch)
305 {//这个映射既是查找产生式左部的位置
switch(ch)
case 'S': return <span style="color: #;break;
case 'E': return <span style="color: #;break;
case 'T': return <span style="color: #;break;
case 'F': return <span style="color: #;break;
default: return -<span style="color: #;break;//查找失败
createPriorityTable()
317 {//创建并填写优先级表
//对每个产生式遍历，求出四种关系1.=,2.&,3.&,4.没有关系
char temp[<span style="color: #]={'+','-','*','/','(',')','v','c','=','?','#','\0'};
int j,L,i;
int tbl_row,tbl_//表的元素坐标
char C[<span style="color: #];
for(int r=<span style="color: #;r&<span style="color: #;r++)
PriorityTable[<span style="color: #][r]=temp[r-<span style="color: #];//初始化行头，第0行
PriorityTable[r][<span style="color: #]=temp[r-<span style="color: #];//初始化第0列
//扫描产生式的右部，如果发现终结符且该终结符周围有其他字符
//若该其他字符为终结符，则这两者关系为相等
//若该其他字符为非终结符，则根据非终结符的firstVT,LastVt填表
for(int p=<span style="color: #;p&<span style="color: #;p++)
j=<span style="color: #;
for(i=<span style="color: #;i&<span style="color: #;i++)
{//注意，此处因为时间有限考虑不是很全面，只是对老师给定的文法进行了周密的部署
//在别的文法上可能需要少许加工，不是问题
if(INPUT[p][i]=='|'||INPUT[p][i]=='\n')
{//刚开始走不到这里
L=j;//j指针所指位置为C[]中字符串的长度
j=<span style="color: #;//交给L后就清零，以供下一次使用
if(L&<span style="color: #)//大于一则处理，否则不关心
{ //对于清零指令l自动忽略
if(IsVT(C[<span style="color: #])&&IsVT(C[<span style="color: #])||(L==<span style="color: #)&&IsVT(C[<span style="color: #])&&IsVT(C[<span style="color: #])&&(FL_map(C[<span style="color: #])!=-<span style="color: #))
{//若为终结符因至少有两个,若出现两个终结符则C[0]'=='C[1]||C[2]，注意这是此文法的情况
//则需要填表，查表找到C[0]的行数，C[1],C[2]的列数进行填表
tbl_row=SearchTbl(C[<span style="color: #]);//记录行数
if(IsVT(C[<span style="color: #]))
{//列数，若是终结符 v=
tbl_column=SearchTbl(C[<span style="color: #]);
if(IsVT(C[<span style="color: #])&&(L==<span style="color: #))
{//列数 (E)
tbl_column=SearchTbl(C[<span style="color: #]);
PriorityTable[tbl_row][tbl_column]='=';//填表
if((L==<span style="color: #)&&IsVT(C[<span style="color: #])&&IsVT(C[<span style="color: #])&&(FL_map(C[<span style="color: #])!=-<span style="color: #))
{//v=E,这种情况
int count_1=<span style="color: #;
char temp_
tbl_row=SearchTbl(C[<span style="color: #]);// =&firstVT(E)
while(FIRSTVT[FL_map(C[<span style="color: #])][count_1]!='\0')
{//填写小于关系
temp_column=FIRSTVT[FL_map(C[<span style="color: #])][count_1];//映射，仔细体会
tbl_column=SearchTbl(temp_column);//将上述结果再次转换
PriorityTable[tbl_row][tbl_column]='&';//填写关系
count_1++;//准备填写下一个
count_1=<span style="color: #;//清零
if((L==<span style="color: #)&&IsVT(C[<span style="color: #])&&IsVT(C[<span style="color: #])&&(FL_map(C[<span style="color: #])!=-<span style="color: #))
{//弥补(E)，针对本文法
//首先填写&关系
char temp_row,temp_
int reg=<span style="color: #;
tbl_row=SearchTbl(C[<span style="color: #]);
while(FIRSTVT[FL_map(C[<span style="color: #])][reg]!='\0')
{//填写小于关系 '('&firstVT(E)
temp_column=FIRSTVT[FL_map(C[<span style="color: #])][reg];
tbl_column=SearchTbl(temp_column);//皆是映射
PriorityTable[tbl_row][tbl_column]='&';
reg=<span style="color: #;//清零
tbl_column=SearchTbl(C[<span style="color: #]);
while(LASTVT[FL_map(C[<span style="color: #])][reg]!='\0')
{//填写大于关系 lastVT(E)&')'
temp_row=LASTVT[FL_map(C[<span style="color: #])][reg];
tbl_row=SearchTbl(temp_row);//map
PriorityTable[tbl_row][tbl_column]='&';
reg=<span style="color: #;//reset
else if((FL_map(C[<span style="color: #])!=-<span style="color: #)&&IsVT(C[<span style="color: #]))
{//C[0]肯定为非终结符lastVT(C[0])&C[1]
//填写大于关系
char temp_row,temp_
int count=<span style="color: #;
tbl_column=SearchTbl(C[<span style="color: #]);
while(LASTVT[FL_map(C[<span style="color: #])][count]!='\0')
{//填写大于关系
temp_row=LASTVT[FL_map(C[<span style="color: #])][count];
tbl_row=SearchTbl(temp_row);//同上
PriorityTable[tbl_row][tbl_column]='&';
count=<span style="color: #;
if(L==<span style="color: #)
{//在这种情况下C[2]必为非终结符，求C[2]的firstVT(),填写小于关系
//E+T,E-T,T*F,T/F等情况
tbl_row=SearchTbl(C[<span style="color: #]);
while(FIRSTVT[FL_map(C[<span style="color: #])][count]!='\0')
{//填写小于关系
temp_column=FIRSTVT[FL_map(C[<span style="color: #])][count];
tbl_column=SearchTbl(temp_column);//map
PriorityTable[tbl_row][tbl_column]='&';
count=<span style="color: #;
else if(INPUT[p][i]!='|'&&INPUT[p][i]!='\0')//该行没结束，过滤'\0'
C[j]=INPUT[p][i];//j从0开始
j++;//移进
if(INPUT[p][i]=='\n')
{//该行结束
//补上#的关系
for(int m1=<span style="color: #;m1&<span style="color: #;m1++)
PriorityTable[SearchTbl('#')][m1]='&';//这个容易理解，补行
for(int m2=<span style="color: #;m2&<span style="color: #;m2++)
PriorityTable[m2][SearchTbl('#')]='&';//补列
PriorityTable[SearchTbl('#')][SearchTbl('#')]='=';
449 void DisplayPriorityTable()
450 {//显示优先关系表查看是否正确
printf("构造的算符优先关系表如下：\n");
for(i=<span style="color: #;i&<span style="color: #;i++)
for(j=<span style="color: #;j&<span style="color: #;j++)
printf("%c ",PriorityTable[i][j]);
printf("\n");
462 /*****************#include "GetPriorityTable.h"*******************/
466 模块三：
468 /***************#include"Simple_Lexical_Analysis.h"*******************/
469 #include "stdlib.h"
470 #include "string.h"
471 #include "math.h"
472 #include "iostream"
473 using namespace
475 typedef struct
char IDentifier[<span style="color: #];//标识符长度
int//定义标识符代表的数值
479 }IDentifierT
481 typedef struct
int//种别码
int//数值或者标识符入口指针
485 }SymbolT
486 extern char FIRSTVT[<span style="color: #][<span style="color: #];
487 extern char LASTVT[<span style="color: #][<span style="color: #];
488 extern char PriorityTable[<span style="color: #][<span style="color: #];
489 extern char INPUT[<span style="color: #][<span style="color: #];
490 extern IDentifierTable
idTbl[<span style="color: #];
491 extern SymbolTbl symbol[<span style="color: #0];//定义符号表
492 /*单词种别码设计：
507 //此处简单起见，就只考虑标识符，运算符，数字
508 //定义一个结构存储（种别码、单词的入口地址）或者（种别码，常数值）或者（种别码）
509 void InsertID(char name[],int entry,int value)
510 {//插入到标识符表中
strcpy(idTbl[entry].IDentifier,name);//插入名字
idTbl[entry].value=//插入数值
ScanEntry(char name[])
516 {//查找符号表中是否有空闲位置
for(int i=<span style="color: #;i&<span style="color: #;i++)
if(strcmp(idTbl[i].IDentifier,name)==<span style="color: #)
return//返回入口地址
return -<span style="color: #;//失败返回失败码
528 void Insert_Into_SymbolTbl(int syn,int value,int &pointer)
529 {//插入到符号表中
symbol[pointer].syn =
symbol[pointer].value =
pointer++;
IsExist(char id[])
536 {//查找表中是否已经存在该标识符
int i=<span style="color: #;
for(i=<span style="color: #;i&<span style="color: #;i++)
if(strcmp(idTbl[i].IDentifier,id)==<span style="color: #)
return true;
return false;
Search_Free_Entity( )
550 {//查找表中是否已经存在该标识符
int i=<span style="color: #;
for(i=<span style="color: #;i&<span style="color: #;i++)
if(strcmp(idTbl[i].IDentifier,"")==<span style="color: #)
return//返回空闲入口
return -<span style="color: #;//查找失败
562 /*********************判断是否为字母********************/
563 bool IsLetter(char letter)
564 {//注意C语言允许下划线也为标识符的一部分可以放在首部或其他地方
if (letter &= 'a'&&letter &= 'z' || letter &= 'A'&&letter &= 'Z' || letter=='_')
return true;
return false;
574 /*********************判断是否为字母********************/
577 /*****************判断是否为数字************************/
578 bool IsDigit(char digit)
if (digit &= '<span style="color: #'&&digit &= '<span style="color: #')
return true;
return false;
589 /*****************判断是否为数字************************/
591 void Scanner(char sentence[],char name[],int &syn,int &scan_point,int &value)
char token[<span style="color: #],
int p_token=<span style="color: #;//token的指针
int digit_value=<span style="color: #;//记录常数的大小
for(int n=<span style="color: #;n&<span style="color: #;n++)
token[n]='\0';//对字符数组清零
ch=sentence[scan_point];
//读入一个字符
if(ch=='#'&&scan_point==<span style="color: #)
{//该字符的种别码已经在主程序中登记了
scan_point++;//刚开始的第一个字符一定为‘#’
ch=sentence[scan_point];//指针下移，扫描下一字符
if(IsLetter(ch))
//ch是否为字母
while(IsLetter(ch)||IsDigit(ch)) //ch是否为字母或数字
token[p_token++]=
scan_point++;
ch=sentence[scan_point];
//读入一个字符
token[p_token]='\0';
syn=<span style="color: #;//代表找到了标识符
if(strcmp(token,"clear")==<span style="color: #)
{//代表找到了保留字“clear”
syn=<span style="color: #;
strcpy(name,token);//带回标识符
else if(IsDigit(ch))
//ch是否为数字
digit_value=<span style="color: #;
while(IsDigit(ch))
{ //此处假设只是整数
digit_value=digit_value*<span style="color: #+ch-'<span style="color: #';
scan_point++;
ch=sentence[scan_point];
//读入一个字符
value=digit_//带回整数值
syn=<span style="color: #;
switch(ch)
case'=':syn=<span style="color: #;
case'?':syn=<span style="color: #;
case'+':syn=<span style="color: #;
case'-':syn=<span style="color: #;
case'*':syn=<span style="color: #;
case'/':syn=<span style="color: #;
case'(':syn=<span style="color: #;
case')':syn=<span style="color: #;
case'#':syn=<span style="color: #; break;
default:printf("输入句子有误！\n");exit(<span style="color: #);break;
scan_point++;//保持指针始终指向待判断的字符
ch=sentence[scan_point];
//读入一个字符
653 bool Check_Is_Right(char sentence[])
654 {//检查句子是不是#。。。#的形式
int len=strlen(sentence)-<span style="color: #;
if(sentence[<span style="color: #]=='#'&&sentence[len]=='#')
{//&&sentence[strlen[sentence]-1]=='#'
return true;
return false;
663 void LexicalAnalysisCtl()
664 {//主控程序
char sentence[<span style="color: #0]="\0";
int syn=-<span style="color: #;
char name[<span style="color: #]="";
int scan_point=<span style="color: #;//从开始处扫描
int id_//定义标识符表入口指针
int sym_pointer=<span style="color: #,
printf("请输入句子,以#开始并且以#结束\n");
scanf("%s",sentence);
}while(!Check_Is_Right(sentence));
Insert_Into_SymbolTbl(<span style="color: #,-<span style="color: #,sym_pointer);
printf("(%d ,
)\n",<span style="color: #);
while(syn!=<span style="color: #)
{//直到扫描到第二个‘#’为止
Scanner(sentence,name,syn,scan_point,value);
switch(syn)
{//若是单词
case <span style="color: #:printf("(%d , %s)\n",syn,name);
//登记到表中
if(!IsExist(name))
{//不存在则插入
//查找可插入位置
id_pointer=Search_Free_Entity();
InsertID(name,id_pointer,-<span style="color: #);//-1代表还没被赋值
//搜索该标识符的入口地址放入value中
entry=ScanEntry(name);
Insert_Into_SymbolTbl(syn,entry,sym_pointer);
case <span style="color: #://常数
Insert_Into_SymbolTbl(syn,value,sym_pointer);
printf("(%d
, %d)\n",syn,value);
default:printf("(%d ,
)\n",syn);
Insert_Into_SymbolTbl(syn,-<span style="color: #,sym_pointer);//-1代表该处不需要值
printf("--------------------词法分析正确！！！-------------------------\n");
//打印出符号表和标识符表
printf("标识符的入口地址
标识符的值(-1代表没被赋值)\n");
for(int m1=<span style="color: #;m1&<span style="color: #;m1++)
{//标识符表
if(!(strcmp(idTbl[m1].IDentifier,"")==<span style="color: #))
printf("\t%d
%d\n",m1,idTbl[m1].IDentifier,idTbl[m1].value);
printf("符号表的入口地址
具体的值(或标识符入口)\n");
for(int m2=<span style="color: #;m2&sym_m2++)
printf("\t%d
%d\n",m2,symbol[m2].syn ,symbol[m2].value);
printf("---------------------------------------------------------------\n");
723 void Clear_Symbol_Tbl()
//将符号表的syn全部设置为0
for(int i=<span style="color: #;i&<span style="color: #0;i++)
symbol[i].syn=<span style="color: #;//代表没定义
symbol[i].value=-<span style="color: #;//指定为-1
734 void Clear_IDentifier_Tbl()
735 {//清空标识符表
for(int i=<span style="color: #;i&<span style="color: #;i++)
strcpy(idTbl[i].IDentifier,"");
idTbl[i].value=-<span style="color: #;
742 /*************#include"Simple_Lexical_Analysis.h"****************/
745 模块四：
747 /***********#include "MainProc_Analysis.h"********************/
749 #include"iostream"
750 using namespace
752 extern char FIRSTVT[<span style="color: #][<span style="color: #];
753 extern char LASTVT[<span style="color: #][<span style="color: #];
754 extern char PriorityTable[<span style="color: #][<span style="color: #];
755 extern char INPUT[<span style="color: #][<span style="color: #];
756 extern IDentifierTable
idTbl[<span style="color: #];//定义全局标识符表
757 extern SymbolTbl symbol[<span style="color: #0];//定义符号表
758 extern char SymbolTbl_Define[<span style="color: #];
760 //创建堆栈，准备对数据进行处理
761 #define MAXSIZE
762 //创建模板栈
763 template &typename T&
764 class Stack{
765 public:
Stack(){top=-<span style="color: #;}//构造函数，进行初始化操作
~Stack(){}//析构函数
bool IsEmpty(){
if(top==-<span style="color: #)
return true;
return false;
}//判断栈是否为空
//返回栈顶元素
T gettop()
return a[top];
//得到栈顶指针的数值
int getTopPointer()
//定义遍历整个栈的能力
traverseStack(int pointer)
//若pointer&0则报错
if(pointer&<span style="color: #)
cout&&"已到栈底，溢出!"&&
exit(<span style="color: #);//退出，分析失败
if(pointer&top)
cout&&"试图访问栈外元素，超界!"&&
exit(<span style="color: #);//退出，分析失败
return a[pointer];//返回元素值
//将元素压栈
void push(T num)
if(top&=MAXSIZE)
//将元素弹出栈
if(top==-<span style="color: #)
cout&&"栈已空，不能再弹"&&
exit(<span style="color: #);
void Clear_Stack()
{//清空堆栈的能力
top=-<span style="color: #;
822 private:
a[MAXSIZE];
826 /*单词种别码设计：
841 //char SymbolTbl_Define[15]={'=','\?','+','-','*','/','(',')','v','c','l','#','N','\0'};
844 /********经过以下连个函数就可以知道种别码对应的字符在符号表中的位置************/
845 char SearchSyn(int syn)
846 {//根据种别码返回相应字符
return SymbolTbl_Define[syn-<span style="color: #];
Prior_Position[<span style="color: #]={'+','-','*','/','(',')','v','c','=','?','#','\0'};
850 int Search_Priority_Setxy(char ch)
851 {//搜索一个字符在优先符表中的位置
for(int i=<span style="color: #;i&<span style="color: #;i++)
if(ch==Prior_Position[i])
return i+<span style="color: #;//返回该位置
return -<span style="color: #;//失败则提示错误
861 /*******************************************************************/
862 Stack&SymbolTbl&
Reource_S//定义堆栈
Print_Context(int Stack_Top,int Sym_Pointer)
864 {//打印出当前堆栈和符号表的上下文
int syn,value,sym_
cout&&"\t当前堆栈情况为"&&
cout&&"\t\t";
for(int i=<span style="color: #;i&=Stack_Ti++)
{//打印出堆栈
syn=Reource_Symbol.traverseStack(i).
value=Reource_Symbol.traverseStack(i).
cout&&"("&&syn&&","&&value&&")
cout&&endl&&"\t当前符号表情况为"&&
cout&&"\t\t";
for(i=<span style="color: #;symbol[i].syn!=<span style="color: #;i++)
877//计算符号表的长度i
sym_length=i+<span style="color: #;//长度，最后一个为#，从1开始数
for(int j=Sym_Pj&sym_j++)
{//打印出堆栈
syn=symbol[j].
value=symbol[j].
cout&&"("&&syn&&","&&value&&")
MainProc_Analysis()
888 {//现在的情况是已经分析出了句子的单词，并且变成了单词块，存放在SymbolTbl symbol[100];中
//并且分析出了标识符存放在了IDentifierTable
idTbl[30];中
//分析出了算符优先分析的优先关系表存放在char PriorityTable[20][20];中
//已经编码出了种别码表，放在char SymbolTbl_Define[15];中
cout&&"下面开始核心算法："&&
int row_prior,column_//行列定位指针
char Prior_R//优先关系
int sym_//符号表长度
int pStackT//栈顶指针
int pScanS//定义扫描堆栈指针
int Statement_count=<span style="color: #;//记录步骤序号
//现在的算法是1.初始化栈，在栈中放入#(12，),然后开始分析
temp_sym.syn=<span style="color: #;
temp_sym.value=-<span style="color: #;//-1代表这个地方不需要
Reource_Symbol.push(temp_sym);//将#压栈
//对symbol中的内容定义指针，并且略过第一个#
int Sym_scan_pointer=<span style="color: #;//从一开始
for(i=<span style="color: #;symbol[i].syn!=<span style="color: #;i++)
911//计算符号表的长度i
sym_length=i+<span style="color: #;//长度，最后一个为#，从1开始数
//判断符号表第一个元素的syn==11?即是否为clear
if(sym_length&=<span style="color: #&&(symbol[<span style="color: #].syn==<span style="color: #))
{//清除语句，清除屏幕并且清空标号表中的值
Clear_IDentifier_Tbl();
Clear_Symbol_Tbl();
Reource_Symbol.Clear_Stack();
system("cls");
//下面比较栈中元素和符号表中元素的大小关系
pStackTop=Reource_Symbol.getTopPointer();
pScanStack=pStackT//扫描指针从栈顶开始
Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
while(<span style="color: #)
row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));//栈扫描指针
column_prior=Search_Priority_Setxy(SearchSyn(symbol[Sym_scan_pointer].syn));//符号表扫描指针
Prior_Relation=PriorityTable[row_prior][column_prior];
if(Prior_Relation=='&'||(Prior_Relation=='='&&(column_prior!=<span style="color: #||row_prior!=<span style="color: #)))
{//要是为小于或等于关系，则进栈
//这里的等于关系可能为(N),v=,这两种关系
Reource_Symbol.push(symbol[Sym_scan_pointer]);//栈顶++
//扫描指针后移，不能回头
Sym_scan_pointer++;
//注意此时还要改变堆栈指针的值，让我调试了好久。。。
pStackTop=Reource_Symbol.getTopPointer();//得到变动后的栈顶指针，始终指向栈顶
pScanStack=pStackT//进行下一次判断，此时扫描指针指向新移进来的元素
cout&&Statement_count++&&".这里是小于、等于关系，压栈！"&&
Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
else if(Prior_Relation=='='&&column_prior==<span style="color: #&&row_prior==<span style="color: #)
{//规约到最后#N,查看栈中是否满足情况
//输出N的数值并结束
if(Reource_Symbol.gettop().syn==<span style="color: #&&(Reource_Symbol.getTopPointer()==<span style="color: #))
{//若满足#N的情况，则归约成功！
cout&&Statement_count++&&"."&&"归约成功!!!"&&
Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
final_value=Reource_Symbol.gettop().
printf("最后的结果为
\n",final_value);
Reource_Symbol.Clear_Stack();
break;//退出大循环,唯一的正确出口
cout&&"句子错误，程序结束!"&&
exit(<span style="color: #);
else if(Prior_Relation=='&')
{//注意下面两句话要放在循环之前!!!
pStackTop=Reource_Symbol.getTopPointer();//得到栈顶指针
pScanStack=pStackT//扫描指针从栈顶开始
while(Prior_Relation=='&')
//若优先关系始终为大于，则堆栈指针前移，不断寻找可归约串
//因为可归约串始终在栈顶的某段区域，那么就要试探着先看一下栈顶元素是不是
//若栈顶元素可归约则直接归约为N(13,),否则查看栈顶方向的两个元素同样道理
//因为文法的产生式右部最多只有三个元素，因此若是到了三个元素还没有搜索到
//可归约串，则视为语法错误，停止分析
//此处构建两个指针，一个既是栈顶指针，另一个为扫描可归约串的指针
//这里不可能出现'（'
//判断栈顶元素是否可归约
judge=Reource_Symbol.traverseStack(pScanStack).//判断该种别码
//若是单个变量或常量则规约为N
//此处还要进行语义分析，对于标识符要查标识符表判断是否存在，若不存在则为错
if(judge==<span style="color: #)
if(idTbl[Reource_Symbol.traverseStack(pScanStack).value].value==-<span style="color: #)
cout&&"此变量可能没被定义，按照-1处理"&&
if(Reource_Symbol.traverseStack(pScanStack).value&<span style="color: #)
{//若该变量的符号表入口地址为负值，则说明查无此元素，则认为语法出错，变量未定义
cout&&"该变量未定义"&&
exit(<span style="color: #);
{//否则将该标识符规约为N
temp_sym.syn=<span style="color: #;
//获得符号表中关于该变量的值
temp_sym.value=idTbl[Reource_Symbol.traverseStack(pScanStack).value].
Reource_Symbol.pop();//先弹出栈顶元素
Reource_Symbol.push(temp_sym);//将N压栈
<span style="color: #00
pStackTop=Reource_Symbol.getTopPointer();//得到变动后的栈顶指针，始终指向栈顶
<span style="color: #01
//扫描指针要前移，因为要分析终结符，而栈顶已变成非终结符
<span style="color: #02
pScanStack=Reource_Symbol.getTopPointer()-<span style="color: #;//进行下一次判断
<span style="color: #03
if(pScanStack&<span style="color: #)
<span style="color: #04
<span style="color: #05
cout&&"句子错误，程序结束!"&&
<span style="color: #06
exit(<span style="color: #);
<span style="color: #07
<span style="color: #08
row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
<span style="color: #09
Prior_Relation=PriorityTable[row_prior][column_prior];//此处列是不会变的，因为大于关系
<span style="color: #10
cout&&Statement_count++&&"."&&"此处将变量规约为N"&&
<span style="color: #11
Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
<span style="color: #12
<span style="color: #13
<span style="color: #14
else if(judge==<span style="color: #)
<span style="color: #15
{//若是常量，则要记住该常量值以便进行规约时赋值
<span style="color: #16
temp_sym.syn=<span style="color: #;
<span style="color: #17
temp_sym.value=Reource_Symbol.traverseStack(pScanStack).
<span style="color: #18
Reource_Symbol.pop();//先弹出栈顶元素
<span style="color: #19
Reource_Symbol.push(temp_sym);//将N压栈
<span style="color: #20
pStackTop=Reource_Symbol.getTopPointer();
<span style="color: #21
pScanStack=Reource_Symbol.getTopPointer()-<span style="color: #;//进行下一次判断
<span style="color: #22
if(pScanStack&<span style="color: #)
<span style="color: #23
<span style="color: #24
cout&&"句子错误，程序结束!"&&
<span style="color: #25
exit(<span style="color: #);
<span style="color: #26
<span style="color: #27
row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
<span style="color: #28
Prior_Relation=PriorityTable[row_prior][column_prior];//同标识符
<span style="color: #29
cout&&Statement_count++&&"."&&"此处将常量规约为N"&&
<span style="color: #30
Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
<span style="color: #31
<span style="color: #32
else if(judge==<span style="color: #)
<span style="color: #33
{//v=E,此时要进行赋值操作，然后规约
<span style="color: #34
if(Reource_Symbol.traverseStack(pScanStack-<span style="color: #).syn==<span style="color: #)//一定为9
<span style="color: #35
{//若前面为标识符则正确，应该为该变量赋值
<span style="color: #36
//语义分析
<span style="color: #37
idTbl[Reource_Symbol.traverseStack(pScanStack-<span style="color: #).value].value=Reource_Symbol.gettop().//此时栈顶必为E
<span style="color: #38
temp_sym.syn=<span style="color: #;
<span style="color: #39
temp_sym.value=Reource_Symbol.gettop(). //N中的值永远为真正的值，而不是地址
<span style="color: #40
//开始归约
<span style="color: #41
Reource_Symbol.pop();
<span style="color: #42
Reource_Symbol.pop();
<span style="color: #43
Reource_Symbol.pop();//弹出三个元素
<span style="color: #44
Reource_Symbol.push(temp_sym);//规约为N
<span style="color: #45
pStackTop=Reource_Symbol.getTopPointer();
<span style="color: #46
pScanStack= Reource_Symbol.getTopPointer()-<span style="color: #;//始终指向规约后的第一个非终结符
<span style="color: #47
if(pScanStack&<span style="color: #)
<span style="color: #48
<span style="color: #49
cout&&"句子错误，程序结束!"&&
<span style="color: #50
exit(<span style="color: #);
<span style="color: #51
<span style="color: #52
row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
<span style="color: #53
Prior_Relation=PriorityTable[row_prior][column_prior];//进行下次判断
<span style="color: #54
cout&&Statement_count++&&"."&&"此处遇到等号要将v=E规约为N,程序面临结束！"&&
<span style="color: #55
Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
<span style="color: #56
<span style="color: #57
<span style="color: #58
<span style="color: #59
cout&&"等号前面应该有变量！"&&
<span style="color: #60
exit(<span style="color: #);
<span style="color: #61
<span style="color: #62
}//end if(judge==1)
<span style="color: #63
if(judge==<span style="color: #)
<span style="color: #64
{//+，此时栈顶应该为N+N的形式
<span style="color: #65
//只需把两个数相加，并且把结果放在N中即可
<span style="color: #66
if(Reource_Symbol.traverseStack(pScanStack-<span style="color: #).syn==<span style="color: #&&Reource_Symbol.traverseStack(pScanStack+<span style="color: #).syn==<span style="color: #)//一定为13
<span style="color: #67
{//若前面为N并且栈顶为N则正确
<span style="color: #68
//语义分析,newtemp()
<span style="color: #69
temp_sym.syn=<span style="color: #;
<span style="color: #70
temp_sym.value=Reource_Symbol.traverseStack(pScanStack-<span style="color: #).value+Reource_Symbol.traverseStack(pScanStack+<span style="color: #). //N中的值永远为真正的值，而不是地址
<span style="color: #71
//开始归约
<span style="color: #72
Reource_Symbol.pop();
<span style