咸防际乾皇院 教 案 伤师房 1978 课程名称：编译原理 系部名称：计算机科学系 教研室： 信管教研室 任课教师：刘小豫 技术职称：讲 师
教 案 课程名称： 编译原理 系部名称： 计算机科学系 教 研 室： 信管教研室 任课教师： 刘 小 豫 技术职称： 讲 师
授课题目 算符优先分析 教学目的 1.使学生了解算符优先文法的定义、算符优先分析法。 2.棠据算符优先分析表的构造方法。 教学重点 算符优先文法、算符优先关系表及其构造 教学难点 优先关系表的构造、算符优先分析法的应用 课时安排 4学时 教学方法 多媒体铺助教学结合实例分析 授课班级 计算机科学系计科082 授课时间 208年月17日星期-)第3-4节 授课地点1号教学棱613教室 教学内容： 5.2算符优先分析 算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归 约串」 将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄。 算符优先分析就是定义算符之间（终结符之间）的某种优先关系，借助于这种优先关系 寻找“可归约串”进行归约。 算符优先分析法特别有利于表达式分析，宜于手工实现。 符优先分析控是目干的贪造程，但算符优先分析法不是一种范自监〈生 左归的 在一个符号串中，任意两个相邻终结符号a和b之间（它们之间可能插有一个非终结符） 的优先关系，可能存在以下三种优先关系： (1)员的价先性低干h 记作a←b (②)a的优先性等于b 记作a二b。 (3)a的价先性高千h 记作a>b。 ,‘=’和)'。例如，a《b并不一定意味着 ·、算法优先文法及优先关系表 1.算符文法 算符：终结符 下君瓷德，星买的低一产生式的右都都不合两个相维（所列的丰终结布甲不含如 如果某算符文法的终结符号集，中任意两个符号之间至多有一种优先关系成立，则称 此算符文法为算符优先文法」 在后面的定义中，a、b代表任意终结符：P、Q、R代表任意非终结符：·…代表由终 结符和非终结符组成的任意序列，包括空字
授课题目 算符优先分析 教学目的 1.使学生了解算符优先文法的定义、算符优先分析法。 2.掌握算符优先分析表的构造方法。 教学重点 算符优先文法、算符优先关系表及其构造 教学难点 优先关系表的构造、算符优先分析法的应用 课时安排 4 学时 教学方法 多媒体辅助教学结合实例分析 授课班级 计算机科学系 计科 0821 授课时间 2008 年 11 月 17 日（星期一）第 3-4 节 授课地点 1 号教学楼 613 教室 教学内容： 5.2 算符优先分析 算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归 约串。 将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄。 算符优先分析就是定义算符之间（终结符之间）的某种优先关系，借助于这种优先关系 寻找“可归约串”进行归约。 算符优先分析法特别有利于表达式分析，宜于手工实现。 算符优先分析算法适用于算符优先文法。 算符优先分析过程是自下而上的归约过程，但算符优先分析法不是一种规范归约（非最 左归约） 。 在一个符号串中，任意两个相邻终结符号 a 和 b 之间（它们之间可能插有一个非终结符） 的优先关系，可能存在以下三种优先关系： (1) a 的优先性低于 b 记作 a b。 (2) a 的优先性等于 b 记作 a b。 (3) a 的优先性高于 b 记作 a b。 注意，这三个关系不同于数学中的‘<’，‘=’和‘>’。例如,a b 并不一定意味着 b a,a b 也不一定意味着 b a。 一、算法优先文法及优先关系表 1．算符文法 算符：终结符 一个文法，如果它的任一产生式的右部都不含两个相继（并列）的非终结符，即不含如 下形式的产生式右部： …QR… 则我们称该文发为算符文法。 2．算符优先文法 如果某算符文法的终结符号集 VT中任意两个符号之间至多有一种优先关系成立，则称 此算符文法为算符优先文法。 在后面的定义中，a、b 代表任意终结符；P、Q、R 代表任意非终结符；‘…’代表由终 结符和非终结符组成的任意序列，包括空字
假定G是一个不含e-产生式的算符文法。对于任何一对终结符a,b,我们说： (1)a工b当且仅当文法G中含有形如P·……或P…0h…的产生式： (2)a《b当且仅当G中含有形如P一…aR…的产生式，而R兰b…或R点Qb…: (3)a》b当且仅当G中含有形如P+…Rb…的产生式，而R兰a或R三…aQ。 如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一： a工b,a∈b,ab 则是三种头袋先法树来说明： a=b a《b a>b b 其中6为e或Q,这 6 b 样h在后 个 柄中，同时归约，所 其中6为e或Q,这样 其中6为e或Q,这样 以优先级相同。 a、b不在同一个句柄 a、b不在同一个句柄 中，b先归约，所以a 中，a先归约，所以a 的优先级低于b。 的优先级高于b。 例：分析文法E一→E+EE*E(E是否是算符优先文法 对+和*来 E一E+E且E÷E*E可有+←* 又可有E一E*E且E李EE可有+>来 由语法树也可看出： E (包)+* (6)+>* 二义性文法的语法树 这样+、◆的优先关系不唯一，所以该表达式文法仅是算符文法， 而不是算符优先文法 注意：两个终结符之间的优先关系是有序的，允许有a>b,b>a同时存在，而不允许有 a>b,aSb,a工b三种情况之两种同时存在。 例5.4考虑下面的文法G (1)E→E+TIT (2)T→T*FIF (5.3) (3)FP4FIP (4)P--(E)li
以上三种关系，可用语法树来说明： (1) (2) (3) 例：分析文法 E→E+E|E*E| (E)|i 是否是算符优先文法。 对+和*来说： E→E+E 且 E E*E 可有 + * 又可有 E→E*E 且 E E*E 可有 + * 由语法树也可看出： (a) + * (b)+ * 二义性文法的语法树 这样+、*的优先关系不唯一，所以该表达式文法仅是算符文法，而不是算符优先文法。 注意：两个终结符之间的优先关系是有序的，允许有 a b,b a 同时存在，而不允许有 a b,a b,a b 三种情况之两种同时存在。 其中δ为ε或 Q，这 样 a、b 在同一个句 柄中，同时归约，所 以优先级相同。 其中δ为ε或 Q，这样 a、b 不在同一个句柄 中，b 先归约，所以 a 的优先级低于 b。 其中δ为ε或 Q，这样 a、b 不在同一个句柄 中，a 先归约，所以 a 的优先级高于 b
根据第(4)条规则，我们有('工)'。从规则E→E+T和T三T*F,我们有+4； 由(2)和(3)可得*4↑。由(1)E→E+T和E兰E+T可得+>+。由(3)F→PF和F 三P个F可得个↑。由(4)P(E)和 E=E+T=T+T=T米F+T台FF+T与P个F*F+Ti↑F*F+T 我们有（≤+、(《，(4个和（≤i。总之，按定义，我们可得文法G终结符对的优先关 系表，该表如表5.1所列。因为，对于G的任何终结对(a,b),至多只有一种关系成立。因 此，G是一个算符优先文法。 表5.1优先表 1 y y 工 表中的空白格表示相应终结符偶没有优先关系。 通过检查G的每个产生式的每个候选式，可找出所有满足a工b的终结符对。为了 找出所有满足关系《和，的终结符对，我们首先需要对G的每个非终结符P构造两个集 合IRSTVT(P)和LASTVT(P): FIRSTVT(P)={alP±a…或P兰Qa…,a∈Vr而Q∈VNd LASTVT(P)={aP兰a或P÷…aQ,a∈VT而Q∈VN} 2)构造集合FIRSTVT(P)的算法 ()若有产生式P-…或P→Q…,则FIRSIVT(P) ()②若EFIRSTVT(Q),且有产生式PQ…,则a∈FIRSTVT(P)。 3列三种优先关系的计算 可以直接查看产生式的右 形面 ..aQb 则有a工b成立 ②关系 求每个非终结符R的FIRSTVT(®)，对形如 对每一个b∈FIRSTVT(R)则有a<b成立 计算每个非终结符R的LASTVT(R),对形如产生式 由 R右3>、成立 构造 (实例法讲述) 表达式文法
注：表中的空白格表示相应终结符偶没有优先关系。 3．算符优先关系表的构造 1）定义集合 FIRSTVT(P)和 LASTVT(P) P∈VN 2)构造集合 FIRSTVT（P）的算法 3)三种优先关系的计算 ① 关系 可以直接查看产生式的右部，对形如 P→…ab… 或 P→…aQb… 则有 a b 成立 ② 关系 求每个非终结符 R 的 FIRSTVT(R) ,对形如 P→…aR…中 对每一个 b∈FIRSTVT(R)则有 a b 成立 ③ 关系 计算每个非终结符 R 的 LASTVT(R)，对形如产生式 P→…Rb…中 对每一个 a∈LASTVT(R)则有 a b 成立 4）算符优先关系表的构造 （实例法讲述） 例：表达式文法 E→E+T
E→T ) 解 计算优先关系为： ①工关系 E'→E#P→(E) 有# (工 为求《 >关系，首先计算每个非终结符号的FIRSTVT集合和LASTVT集合 FIRSTVT(E')=(#) ( FIRSTVT(P)=(Ui=(i LASTVT(E')={#料 i ULASTVTD-) ,} =)}U=0 扫描产生式寻找终结符在前非终结符在后的相邻符号对，及非终结符在前终 结符在后的相邻符号对，即产生式右部有形如 P…aQ 或P…Rb…的产生式，求《 >关系 ②关系，所给文法中产生式右部终结符在前非终结符在后的相邻符号对有 FIRSTVT(E) :年 +←FIRSTVT (T 即： 则有 FIRSTVT(F) 即：*下 ↑，.i} ↑F 则有 ←FIRSTVT(F) 即：1 E 则有（←FIRSTVT(E)即：(<{+，*，1，(i ③>关系，所给文法中产生式右部非终结符在前终结符在后的相邻符号对有 E#则有LASTVT(E)>#即：(+，*，1，).i}># 4 则有LASTVT(E)>+即：{+，来，t,,i>+ T* 则有LASTVT(T)>*即： {*,↑ 则有LASTVT()>1即 0. +,*1,i>》 可 注意：符号对的优先关系是有序的。行在前，列在后。 二、算符优先分析算法 算符优先分析和规范归约的核心均为寻找句柄。规范归约的句柄是“最左直接短语”。算符优 先分析的句柄是“最左素短语
E→T T→T*F T→F F→P↑F F→P P→(E) P→i 解： 计算优先关系为： ① 关系 E’→#E# P→(E) 有 ＃ ＃ ，（ ） 为求 、 关系，首先计算每个非终结符号的 FIRSTVT 集合和 LASTVT 集合 FIRSTVT(E’)={#} FIRSTVT(E)={+}∪FIRSTVT(T)={+} ∪{*,↑,(, i}={+,*,↑,(, i} FIRSTVT(T)= {*}∪FIRSTVT(F)={*} ∪{↑,(, i}={*,↑,(, i} FIRSTVT(F)= {↑}∪FIRSTVT(P)={↑} ∪{(, i}={↑,(, i} FIRSTVT(P)= { ( }∪{i} ={(, i} LASTVT(E’)={#} LASTVT(E)={+} ∪LASTVT(T)= {+} ∪{*,↑,) i}={+,*,↑,) ,i} LASTVT(T)={*} ∪LASTVT(F)= {*} ∪{↑,) i}={*,↑,), i} LASTVT(F)={↑} ∪LASTVT(P)= {↑} ∪{) i}={↑,), i} LASTVT(P)={ ) } ∪{i} ={), i} 然后逐条扫描产生式寻找终结符在前非终结符在后的相邻符号对，及非终结符在前终 结符在后的相邻符号对，即产生式右部有形如 P→…aQ… 或 P→…Rb… 的产生式，求 、 关系。 ② 关系，所给文法中产生式右部终结符在前非终结符在后的相邻符号对有 #E 则有 # FIRSTVT(E) 即：# {+,*,↑,(,i} +T 则有 + FIRSTVT(T) 即：+ {*,↑,(,i} *F 则有 * FIRSTVT(F) 即：* {↑,(,i} ↑F 则有 ↑ FIRSTVT(F) 即：↑ { (,i} (E 则有 ( FIRSTVT(E) 即：( {+,*,↑,(,i} ③ 关系，所给文法中产生式右部非终结符在前终结符在后的相邻符号对有 E# 则有 LASTVT(E) # 即： {+,*,↑,),i} # E+ 则有 LASTVT(E) + 即： {+,*,↑,),i} + T* 则有 LASTVT(T) * 即： {*,↑,),i} * P↑ 则有 LASTVT(P) ↑ 即： {),i} ↑ E) 则有 LASTVT(E) ) 即： {+,*,↑,),i} ) ④从而可以构造优先关系矩阵表如下： 表的行列标题都是终结符号及#，表的元素为行列符号对之间的优先关系。 注意：符号对的优先关系是有序的。行在前，列在后。 关系按行填表， 关系按列填表。 该文法算符优先关系表构造结果如表 5.1。 二、算符优先分析算法 算符优先分析和规范归约的核心均为寻找句柄。规范归约的句柄是“最左直接短语”。算符优 先分析的句柄是“最左素短语