咸防际乾皇院 教 案 伤师房 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、成立 构造 (实例法讲述) 表达式文法
注：表中的空白格表示相应终结符偶没有优先关系。 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)即：(关系，所给文法中产生式右部非终结符在前终结符在后的相邻符号对有 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。 二、算符优先分析算法 算符优先分析和规范归约的核心均为寻找句柄。规范归约的句柄是“最左直接短语”。算符优 先分析的句柄是“最左素短语
1.最左素短语定义 (1)素短语：设有算符优先文法G(⑤)，其句型的素短语是一个短语，它至少含有一个终结 符，并且除它自身之外不再含任何更小的素短语。 2)最左素短语：处于句型最左边的那个素短语， 例：文法5. ()向型P却+ (2)句型T 、P、i、P却+i是PP+i的短语 ,T+T+i是T+TF+ 的茶面pP哪、i是P+的表 T*F.i是T+T*F+i的素短语 P(Ei P却是P却+i的最左素短语 T却是T+T*F+i的最左素短语 2.句型的一般形式： #N1a2…Nn,Nn1# (5.4) 即任何两个终结符之间项多只有一个非终结符。这是任何算符文法的句型都具有的形式。 优先文法G的任何句型(54)的最左素短语是满足如下条件的最左子串最左素短 语是满足如下条件的最左子串 Na…Na+1, (Ni-a-NjaNmaN-a-NaNma) 4-144 马工+1，…，-工 a>ai. 即a4-14,x1,…，1x4,>+1 算符优先分析算法根据上述定理构造出来的， 个存放输入串的敷组R,算法大意为： ①将榆人串RR?R依次逐个移人符号栈S中，直至符号栈顶元素S与下 一个待输人的符号Rk有关系S>R为止， ②最左素短语尾符号S已在符号栈S的栈顶，由此往前（左）在栈中找最 左素短语的头符号$，直至找到第一个(S,区Q)为止 已 重复上 ,调用语义子程序对它进行加工 直至j=2且RI 分析算法描述 为止 设单元a中存放当前输入符，S为一个符号栈，则： ()将当前输入符存放到a中，将#入符号栈。 2)将找而第 个终结符b与a比较。如果b二a,而b一#且栈中只剩一个非终结符时 则成功：否则a入栈：如果b中a则a入栈：如果b+a,在栈顶寻找最左素短语，并将最左素 短语归约为一个非终结符：如果文法中找不到相应规则，则出错： (3)重复(2)至成功或失败。 算法中，每次都取终结符号进行比较，当符号栈S的某个符号不是终结符号时，便取 其左邻符号（这时 定是终结符)。算法中的为 工作单元，用于存放待比较的终结符号 说明：k代表符号栈$的使用深度 在算法中，若出现减1后小于等于0时，则输入串有错：符号我S应呈现：# #表示正确，输入串是该文法的句子。 算法中并没有指出应把所找到的最左素短语归约到哪一个非终结符号N” N是产生式的左部符号，此产生式的右部和S0+Sk构成如下 一对应关系
1．最左素短语定义 （1）素短语：设有算符优先文法 G(S),其句型的素短语是一个短语，它至少含有一个终结 符，并且除它自身之外不再含任何更小的素短语。 （2）最左素短语：处于句型最左边的那个素短语。 例：文法 5.3 E→E+T|T (1)句型 P*P+i (2)句型 T+T*F+i T→T*F|F P、P*P、i、P*P＋i 是 P*P＋i 的短语 T,T*F,T+T*F,i,T+T*F+i 是 T+T*F+i 的素短语 F→P↑F|P P*P、i 是 P*P＋i 的素短语 T*F,i 是 T+T*F+i 的素短语 P→(E)|i P*P 是 P*P＋i 的最左素短语 T*F 是 T+T*F+i 的最左素短语 2.句型的一般形式： 即任何两个终结符之间顶多只有一个非终结符。这是任何算符文法的句型都具有的形式。 3．定理 一个算符优先文法 G 的任何句型（5.4）的最左素短语是满足如下条件的最左子串最左素短 语是满足如下条件的最左子串 (Nj-1aj-1NjajNj+1aj+1…Ni-1ai-1NiaiNi+1ai+1) 即 4. 算符优先分析算法(根据上述定理构造出来的) 设一个符号栈 S 和一个存放输入串的数组 R，算法大意为： 重复上述过程，直至 j＝2 且 R[k]=#为止。 分析算法描述 设单元 a 中存放当前输入符，S 为一个符号栈，则： (1) 将当前输入符存放到 a 中，将#入符号栈。 (2) 将栈顶第一个终结符 b 与 a 比较。如果 b≡a ，而 b== #且栈中只剩一个非终结符时， 则成功；否则 a 入栈；如果 b≮a,则 a 入栈；如果 b≯a,在栈顶寻找最左素短语，并将最左素 短语归约为一个非终结符；如果文法中找不到相应规则，则出错； (3) 重复(2) 至成功或失败。 算法中，每次都取终结符号进行比较，当符号栈 S 的某个符号不是终结符号时，便取 其左邻符号（这时一定是终结符）。算法中的 Q 为一工作单元，用于存放待比较的终结符号。 说明：k 代表符号栈 S 的使用深度。 在算法中，若出现 j 减 1 后小于等于 0 时，则输入串有错；符号栈 S 应呈现：＃N ＃表示正确，输入串是该文法的句子。 算法中并没有指出应把所找到的最左素短语归约到哪一个非终结符号‘N’。 N 是产生式的左部符号，此产生式的右部和 S[j＋l]...S[k]构成如下一一对应关系：
自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同，非终结符 可以不同，只是占位而己。由于非终结符对归约没有影响，因此，非终结符根本可以不 进 号找s 单非产生式：右部仅含一个非终符的产生式。如P一Q 1 k:=1; S[k]:=‘#'; 2 REPEAT 3 把下一个输入符号读进a中； 4 IF S[k]EVT THEN j:=k ELSE j:=k-1; WHILE S[j]a DO BEGIN 7 REPEAT Q:=s[j]: IF S[j-1]EVT THEN j:=j-1 ELSE j:=j-2 10 UNTIL S[j]Q: 11 把S[j+1小S[k]归约为某个N: 12 k:=j+1; 13 S[k]:=N 14 END OF WHⅢE: 5 FS[j】&aORS[j]工a THEN 16 BEGIN k:=k+1:S[k]:a END 17 ELSE ERROR/调用出错诊察程序* 18 例： 的句子十i,按算符优先分析法，归约过程为 5两种分析法比较 ①算符优先分析比规范归约要快得多，因为算符优先分析跳过了所有单非产生式所对应的归 约步骤。 ②算符优先分析存在某种危险性，可能导致把本来不成句子的输入串误认为是句子。 ③算符优先分析一般用于分析各类表达式 6问题：“算符优先分析法采用移进一归约技术， 其归约过程是规范的”这句话是否正确？ 付优衫 每步自下而上分析识别和归约的是当前句型的最左素短语：而不 是严 优先文法 利用 多矩阵中只有 先分 析法 用算符时 所以单非产生式对归约没有起作用，因而算符优先 分析不是规范归 例文法GE:E一→#E# +E+TTT一T*FFF一PFPP(Ei,其优先矩阵为：
自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同，非终结符 可以不同，只是占位而已。由于非终结符对归约没有影响，因此，非终结符根本可以不 进符号栈 S。 单非产生式：右部仅含一个非终符的产生式。如 P→Q。 例：文法（5.3）的句子 i＋i，按算符优先分析法，归约过程为： ①把第一个 i 归为 P ②把第二个 i 也归为 P ③把 P＋P 直接归为 E 5.两种分析法比较 ①算符优先分析比规范归约要快得多，因为算符优先分析跳过了所有单非产生式所对应的归 约步骤。 ②算符优先分析存在某种危险性，可能导致把本来不成句子的输入串误认为是句子。 ③算符优先分析一般用于分析各类表达式 6.问题：“算符优先分析法采用移进一归约技术，其归约过程是规范的”这句话是否正确？ 在算符优先分析法中，每步自下而上分析识别和归约的是当前句型的最左素短语；而不 是严格地从左到右归约句柄。 算符优先分析法只对算符优先文法进行，利用的是算符优先关系矩阵。该矩阵中只有终 结符号间的优先关系；在归的过程中，利用算符优先关系矩阵无法找到句型中相应于单非产 生式的句柄。因此，在算符优先分析法中，每次归约时，归约的是当前句型的最左素短语。 所以单非产生式对归约没有起作用，因而算符优先分析不是规范归的。 例文法 G[E']：E'→#E# E→E+T|T T→T*F|F F→P^F|P P→(E)|i，其优先矩阵为：
对句子作规范归约和算符优先分析的语法树比较： i 对串 对串+#算符优先分析的过程如下： 步骤栈关系剩余输入串动作 23436 什拼 入栈 木 入栈 5 #pti 归约 6 #E E+T E今E+T 的 成功 现取i分别为3 则有串3+2 对该串进 代分析标过程如下 234567 算符优先分析方法也可采用优先函数来进行。 三、适用范围 表达式的语法分析。 作业：教材P133 3题
对句子 i+i 作规范归约和算符优先分析的语法树比较： 对串 i+i#规范归约的过程如下： 对串 i+i#算符优先分析的过程如下： 现取 i 分别为 3、2、4，则有串 3+2*4#，对该串进行算符优先分析过程如下： 算符优先分析方法也可采用优先函数来进行。 三、适用范围 表达式的语法分析。 作业：教材 P133 3 题