内容发布更新时间 : 2024/6/18 21:28:07星期一 下面是文章的全部内容请认真阅读。

编译原理实验报告

实验二：语法分析

学 号： 201616408 姓 名： 朱元旭 班 级： 2016164 专 业： 计算机科学与技术 指导教师： 张帆

实验二 语法分析

算符优先分析程序

1. 实验要求

⑴ 选择最有代表性的语法分析方法算符优先法；

⑵ 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。

⑶ 实习时间为4学时。

2. 实验内容及要求

（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表 输出到显示器或者输出到文件）；

（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）

（3）给定表达式文法为： G(E’): E’→#E#

E→E+T | T T→T*F |F F→(E)|i

(4)分析的句子为: (i+i)*i和i+i)*i

3. 算法设计思路

实验的算法实际上课本上已经给出了。但是课本上的算法有一个很不好实现的地方——构造bool型的数组F[P，a]。关键这个是个伪代码，数组中肯定是用不了F[P，A]的。于是，我使用了实验一的词法分析程序，并对其进行了修改，让其生成两张表——终结符表和非终结符表，通过固定终结符以及非终结符在表中的位置，来确定F[P，A]的指向。比如说，在非终结符表中，VN[4]=A，也就是说，A的位置被固定在了4；终结符表中，VT[2]=a，a被固定在了位置2.然后我们就可以根据 伪代码F[P，A] 来设定数组。比如说，伪代码的F[A，a]对应的就是数组中的F[4,2]。完成了布尔数组的构件之后，就可以进行代码的实现了。

a) FIRSTVT集的建立：

程序开始时，先建立布尔数组F[M,N]（M,N是在进行词法分析的时候计算出来的），然后对其进行初始化，令其都为FALSE。进行循环，扫描文法，找到形如P->a…,P->Qa…的产生式，然后调用INSERT函数，将P，a传过去。然后，对栈进行扫描，如果栈不为空的

话，将栈顶几位（Q，a）然后进行出栈。对于形如P->Q…的产生式，进行调用INSERT函数，将P，a传过去，直到栈为空。

b) LASTVT集的建立：

程序开始时，先建立布尔数组F[M,N]，然后对其进行初始化，令其都为FALSE。进行循环，扫描文法，找到形如P->……a,P->……Qa的产生式，然后调用INSERT函数，将P，a传过去。然后，对栈进行扫描，如果栈不为空的话，将栈顶几位（Q，a）然后进行出栈。对于形如P->……Q的产生式，进行调用INSERT函数，将P，a传过去，直到栈为空。

c) Insert函数：

如果F[P,a]为假的话，置其为真，并把二维数组VNT[P,a]入栈 最后，任意非终结符P的FIRSTVT集就是F[P，A]为真的式子 d) 构造优先关系表

遍历文法产生式，对于产生式每个产生式，从左至右进行扫描，如果xi,xi+1或者xi,xi+2xi为终结符，xi+1为非终结符，那么令xiFIRSTVT(xi+1), 如果xi为非终结符，xi+1为终结符，那么令xiFIRSTVT(xi+1) e) 算符优先分析算法

其实，这个到挺好做的，主要是要找出最左素短语。拿栈顶的字符与当前的单词进行比较，如果站内的优先级高于栈外，那么就尽心归约；如果栈内的优先级低于栈外，那么就把单词移入栈内。

4. 程序流程图

词法分析流程图

开始使用词法分析程序，对语法进行分析遇到的符号为终结符？N遇到的符号为非终结符YY是否在终结符表中？是否在非终结符表中？NNm++N++构建维度为M,N的二维数组，用来存放信息结束