编译原理实验3（基于算符优先文法分析的语法分析器 ）_实验三:算符优先分析法判别文法是否为og文法。

• 实验目的

1. 加深对语法分析器工作过程的理解；
2. 加强对算符优先分析实现语法分析程序的掌握；
3. 能够产用一种编程语言实现简单的语法分析程序；
4. 能够使用自己编写的分析程序对简单的程序段进行语法分析。

• 实验要求

1. 根据简单表达式文法构造算符优先分析表
2. 根据构造出来的算符优先分析表进行表达式的分析

• 实验内容

1. 在之前实验的基础上，用算符优先分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。
2. 分析对象（算数表达式）的BNF定义如下：

<表达式> ::= [+|-]<项>{<加法运算符> <项>}

<项> ::= <因子>{<乘法运算符> <因子>}

<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’

<加法运算符> ::= +|-

<乘法运算符> ::= *|/

<关系运算符> ::= =|#|<=|>|>=

<标识符> ::= <字母>{<字母>|<数字>}

<无符号整数> ::= <数字>{<数字>}

<字母> ::= a|b|...|X|Y|Z

<数字> ::= 0|1|...|8|9

1. 改为一般的文法形式，即普通的巴克斯范式

为表示方便：

　　表达式E、项X、因子Y、标识符b，无符号整数z，加法运算符A，乘法运算符C，关系运算符G，

E->AX|X|EAX

X->Y|XCY

Y->b|z|(E)

A->+|-

C->*|/

• 实验步骤

1. 本程序中的文法，实质上为算数表达式的计算；
2. 构建First VT（）和Last VT（）
3. 构建优先符号表
4. 构建词法分析的程序，实验一的内容
5. 编写main()函数，用户输入文法对语句利用算符优先文法进行判别。

• 实验算法及流程图

1. 算法思想

      用栈存储已经看到的输入符号，用优先关系指导移动规约语法分析器的动作，如果栈顶的终结符和下一个输入符之间的优先关系时<或者=，则语法分析器移动,表示还没有发现句柄的右端，如果时>关系，就调用归约。

模块一：解析产生式

1. 功能：把产生式：S->aB解析成VN:S、B，VT：a
2. 输入约定：这实际上是词法分析的范畴，这里为了简便，先用默认产生式是比较简单而且按照规范来写，大写字母代表VN，小写字母代表VT，并且是单个字符。
3. 实现思路：

把产生式以->推导符号为边界分为左右两部分，左边一定是VN，右边大写字母是VN，小写字母是VT，为了避免重复记录，可以用一个map来记录是否出现过，map里key是VN或VT，值是它们在数组里的下标。既能起到记录的作用，又能便于之后使用时快速查找。

模块二：构建FIRSTVT（）和LASTVT（）

1. 功能：根据FIRST()和LASTVT（）定义，通过深度优先搜索来遍历这两个集合。
2. 构造思想：

FIRSTVT（）定义：

简单地说，FIRST集是推导出第一个VT，它是找推出的第一个VT或者第一个VN或者接着VN后的VT。

LASTVT（）定义：

简单地说，找最后一个VT或者最后一个VN和倒数第二个VT。

1. 函数说明

模块三：构建算术优先符号表

1. 功能：根据求出的FIRSTVT()和LASTVT()集构建算术优先符号表。
2. 构造思想：

考虑下面的四种情况：

1. A->...ab...,则a==b
2. A->...aB...，则a<FIRSTVT（B）
3. A->...Ba...,则a>FIRSTVT(B)
4. A->...aBb,则a==b（最后三个）

对于每条产生式判断这四种情况即可构造算术优先符号表。

1. 流程图

模块四：表达式语法分析

1. 功能：

根据求出的算符优先分析表进行语法分析

1. 输入约定:

只含+ - * / ( )这五种运算符，若是其他则会报错。

1. 函数接口

1. 流程图

1. 实现方法:

遍历表达式

考虑下面五种情况：

1. 当前字符是数字，则直到当前字符不是数字时才退出，并压入数据栈
2. 当前字符是VT且符号栈空，压入符号栈
3. 当前字符是VT且符号栈非空，通过算符优先分析表判断当前字符和符号栈顶元素的优先级，若是当前优先级大则压入栈，若相等则弹出栈顶，若小于则用当前栈顶符号来计算，小于完后要continue，其他情况都是++i。
4. 表达式遍历完且符号栈非空，依次弹出栈顶符号来计算。
5. 表达式遍历完且符号栈空，数据栈栈顶元素是表达式计算结果值。

模块五：运算符识别计算

（1）功能

根据符号栈和数据栈来计算表达式的值

（2）构造思路：

数据栈：

如果表达式合法，每次运算数据栈都能弹出两个数字，并在符号栈空计算完时，数据栈存在一个数字，即表达式的结果。因此每次运算弹出两个数字，并把结果压入栈里。

符号栈：

考虑两种情况：

1. + - * /四则运算，数据栈弹出两个数字，计算完结果压入即可
2. 其他则报错

1. 关键函数

1. int main()函数

功能：创输入样例，计算VN、VT集合，调用GetFirstvt() 、GetLastvt() 、GetPriorityTabel() 、Analyze()

1. void GetFirstvt（）函数

功能：计算并打印FIRSTVT集，调用SearchFirstvt()

1. void SearchFirstvt(int x)

功能：搜索指定VN的FIRSTVT集

1. void GetLastvt()

功能：计算并打印LASTVT集，调用SearchLastvt（）

1. void SearchLastvt(int x)

功能：搜索指定VN的LASTVT集

1. void GetPriorityTabel()

功能：计算并打印算术优先符号表

1. void Analyze()

功能：分析表达式，调用Calculate（）计算

1. voiod Calculate(char t1,char t2)

功能：计算表达式值，调用GetName（）得到结果

1. int GetNum(int d1,int d2,char op)

功能：四则运算

1. void PrintLine(string t=”_____”)

功能：打印一行一行来分割

1. 算法流程

在Itc的程序中，文法是给定的，不用自行输入文法。只需要输入表达式，对表达式进行分析（表达式在实验一中已经进行过词法分析，以词法分析的结果作为输入。）

程序整体执行

函数之间的调用关系

• 实验结果与分析

1. 生成项目

2. 首先先对给出的文法求FirstVT、LASTVT集合

在程序中写了打印出来的函数，看结果是否正确

3.再求算符优先关系表

4.修改原来的代码，再到itc 进行验证

案例1

案例2

根据程序运行得到的结果可以看出：编写的代码正确。

• 实验体会

1.实验总结

本次实验通过对文法进行处理，获取FIRSTVT()集合、LASTVT（）集合和算符优先关系表，从而进一步对语句进行分析判断。通过本次实验我对语义分析有了更进一步的理解。

实验过程中遇到的问题有：

1. FIRSTVT（）和LASTVT()者两个集合的构建。

解决方法：对书本中的原理进一步学习，写出伪代码，进一步进行功能的编写。

1.  如何利用FIRSTVT()和LASTVT() 集合构建算符优先关系表。

解决方式：多次尝试如下的伪代码，从而实现该关系表的代码化。

FOR 每个产生式 P->X1 X2 ……Xn   

DO  FOR  i:=1  TO   n-1    DO      

      IF  X[i]和X[i+1]均为终结符

        THEN   置 X[i]=X[i+1]        

      IF  X[i]和X[i+2]均为终结符,X[i+1]为非终结符,i≤n-2,       

        THEN   置 X[i]=X[i+2]                

      IF  X[i]为终结符, 但X[i+1]为非终结符                                    

      THEN  FOR  FIRSTVT(X[i+1])中的每个a                                    

          DO  置 X[i]<a                

      IF  Xi为非终结符, 但X i+1 为终结符                                  

          THEN  FOR  LASTVT(X i )中的每个a

              DO   置 a>X[i+1]      

1. 实验中的输入输出格式可以进一步调整优化，不过对于ITC的验证已经满足了。代码的注释有待增加，代码可读性也有进一步提升的空间。还有实验中开始的代码是输入文法，对文法求FIRSTVT集 和LASTVT集，再构造算符优先关系表，最后输入表达式，对表达式进行分析。但是itc的验证是以已经给定了文法，然后以实验一的词法分析结果作为输入，所以这里在代码实现上还存在一些问题，需要改进。

2.实验反思

这次的实验花费了我不少时间，但也从中学到了很多，从最初的第一个模块一路走来，也遇到许多挫折，特别是明明逻辑都对却找不到错误的原因的时候，多亏了调试工具。  编写这个程序一部分来自于学习的课程要求，另一部分也来自于对编程的喜爱，或许正是这种感觉一直支持我到现在吧。代码虽然写完了，对于老师给的文法绝对是没问题的，可毕竟也有它的局限性。即便如此，编译原理的处理问题的思想，思考问题的角度，都让我大受启发。这个程序其实是很全面的，它从词法分析-->语法分析-->语义分析---->问题求解，基本上走完了编译器的大部分生命周期。对于我们理解编译的过程和具体的实现都是很有帮助的。

当然，编译原理博大精深，比如说对于数组的处理、中间代码的生成、数据结构的相关知识等很多方面，都值得我们认真揣摩。这次实验难度其实还是可以的，理解和掌握算符优先文法来分析，以及对栈，Table结构体的理解对编写代码尤为重要。

这一次编译原理实验课，总结前几次次实验课的经验与教训：理解好项目给出的数据结构，以及演示模式程序执行的步骤和输出结果，熟练掌握数据结构的相关知识是完成代码的关键。

总的来说，通过这次实验课，既加深了我对编译原理课程重点内容的理解，又复习了数据结构的相关知识，提高了编写代码的能力，收获良多。

最后，特别感谢刘老师一直以来的耐心指导和同学的热心帮助。

代码