编译原理算符优先语法分析实验报告.docx

《编译原理算符优先语法分析实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专题4_算符优先语法分析李若森13281132计科1301一、理论传授语法分析的设计方法和实现原理；算符优先文法、最左素短语、算符优先矩阵、优先函数的基本概念；算符优先文法句型最左素短语的确定；算符优先分析算法的实现。二、目标任务实验项目实现算符优先分析算法，完成以下描述算术表达式的算符优先文法的算符优先分析过程。G[E]:E→E+T

2、E-T

3、TT→T*F

4、T/F

5、FF→(E)

6、i设计说明终结符号i为用户定义的简单变量，即标识符的定义。加减乘除即运算符。设计要求(1)构造该算符优先文法的优先关系矩阵或优先函数；(2)输入串应是词法分析的输出二元式

7、序列，即某算术表达式“专题1”的输出结果，输出为输入串是否为该文法定义的算术表达式的判断结果；(3)算符优先分析程序应能发现输入串出错；(4)设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。任务分析重点解决算符优先矩阵的构造和算符优先算法的实现。能力培养深入理解理论对实践的指导作用；基本原理、实现技术和方法的正确运用。一、实现过程OPG优先关系设G是一OG（简单优先）文法，a,b∈Vt，U,V,W∈Vn(1)a=b当且仅当OG有形如U→….ab….或U→….aVb….的规则(2)a

8、+>b….或W=+>Vb…..(3)a>b当且仅当OG有形如U→….Wb….的规则，而且W=+>….a或W=+>….aV若a,b之间至多存在上述三种优先关系之一，OG为OPG（算符优先）文法。FIRSTVT集和LASTVT集a)FIRSTVT集§两条原则1.若有规则U→b…或U→Vb…，则b∈FIRSTVT(U)2.若有规则U→V…且b∈FIRSTVT(V)，则b∈FIRSTVT(U)§过程描述数据结构：STACK栈布尔数组F(U,b)U∈Vn，b∈VtF(U,b)真b∈FIRSTVT(U)假bÏFIRSTVT(U)§算法分析初始：F(U,b)初

9、值(根据原则①)F(U,b)为真的(U,b)对进STACK栈循环：直至STACK空(根据原则②)弹出栈顶元素，记(V,b)对每一个形如U→V…的规则若F(U,b)为假，变为真，进STACK栈若F(U,b)为真，再循环结果：FIRSTVT(U)={b∣F(U,b)=TRUE}FIRSTVT(E)={+,-,*,/,(,i}FIRSTVT(T)={*,/,(,i}FIRSTVT(F)={(,i}表3-1bU+-*/()iETTTTTTTTTTTFTTa)LASTVT集§两条原则①若有规则U→…a或U→…aV，则a∈LASTVT(U)②若有规则U→…V

10、且a∈LASTVT(V)，则a∈LASTVT(U)§过程描述数据结构：STACK栈布尔数组F(U,a)U∈Vn，a∈VtF(U,a)真a∈LASTVT(U)假aÏLASTVT(U)§算法分析初始：F(U,a)初值(根据原则①)F(U,a)为真的(U,a)对进STACK栈循环：直至STACK空(根据原则②)弹出栈顶元素，记(V,a)对每一个形如U→V…的规则若F(U,a)为假，变为真，进STACK栈若F(U,a)为真，再循环结果：LASTVT(U)={a∣F(U,a)=TRUE}LASTVT(E)={+,-,*,/,),i}LASTVT(T)={*

11、,/,),i}LASTVT(F)={),i}表3-2aU+-*/()iETTTTTTTTTTTFTT最左素短语算符优先文法句型的一般形式：#N1a1N2a2……NnanNn+1#ai∈VtNi∈Vn(可有可无)最左素短语的确定：一个OPG句型的最左素短语是满足以下条件的最左子串：Njaj…..NiaiNi+1其中：aj-1ai+1aj-1ai+1所以，构造OPG优先矩阵算法根据构造OPG优先矩阵算法，可得如下优先关系：+FIRSTVT(T)LASTVT(E)+-F

12、IRSTVT(T)LASTVT(E)-*FIRSTVT(F)LASTVT(T)*/FIRSTVT(F)LASTVT(T)/(FIRSTVT(E)LASTVT(E))()#FIRSTVT(E)LASTVT(E)#所以，构造OPG优先矩阵如表3.3所示：表3.3OPG优先矩阵+-*/()i#+-*/()i#acc算法框架主要数据结构pair:用pair来存储单个二元组。该对照表由专题1定义。map:存储离散化后的终结符和非终结符。int[][]:存储算符优先矩阵。0代表空，1代表

13、，2代表，3代表，4代表acc。函数定义init:voidinit();功能：初始化算符优先矩阵，关键字及识别码对照表，离散化终结符传入