《编译原理 语法分析(2)》由会员分享，可在线阅读，更多相关《编译原理 语法分析(2)（159页珍藏版）》请在金锄头文库上搜索。
1、4.5 自底向上语法分析,“移进归约”分析方法，shift-reduce 将符号串归约为文法开始符号 算法优先分析法、LR分析法 每个归约步骤 一个特定的子符号串匹配某个产生式的右部 将这个子符号串替换为产生式左部的NT,例4.21,文法 S aABe A Abc | b B d 归约 abbcde aAbcde aAde aABe S 对应最右推导 S aABe aAde aAbcde abbcde,rm,rm,rm,rm,4.5.1 句柄（Handle）,符号串的“句柄” 与某个产生式右部匹配的子串 归约为产生式左部最右推导逆过程 形式化定义：一个最右句型g的句柄 S =Aw = w，中之
2、后即为句柄位置，w只包含终结符 一个句型可有多个不同句柄 非多义性文法的最右句型有唯一句柄,*,rm,rm,例4.22,E E + E E + E * E E + E * id3 E + id2 * id3 id1 + id2 * id3,rm,rm,rm,rm,rm,E E * E E + id3 E + E * id3 E + id2 * id3 id1 + id2 * id3,rm,rm,rm,rm,rm,(1) E E + E (3) E (E) (2) E E * E (4) E id,4.5.2 句柄剪枝(Handle Pruning),子串产生式左部语法树剪枝 不断剪枝最右推导的
3、逆过程归约,S,A,Left part Handle (only terminals here),Viable prefix,例4.23,最右句型 id1 + id2 * id3 E + id2 * id3 E + E * id3 E + E * E E + E E,句柄 id1 id2 id3 E * E E + E,归约产生式 E id E id E id E E * E E E + E,4.5.3 移进归约分析的实现,两个问题 定位句柄 确定用哪个产生式进行归约 一般实现方法栈 将输入符号“移进”栈，直至在栈顶形成一个句柄 将句柄“归约”为相应的非终结符 不断重复，直至栈中只剩开始符号，
4、输入缓冲区为空接受输入串 错误处理,例4.24,基本操作,移进（shift） 下个输入符号移到栈顶 归约（reduce） 句柄的右端恰在栈顶，定位句柄左端 确定选用的产生式，用产生式左部非终结符替换栈中的句柄,基本操作,接受（accept） 宣布分析成功结束 错误（error） 发现语法错误，调用错误恢复函数,句柄必然在栈顶？,移进动作在栈内形成句柄 这显然不可能 若形成($aby, z$)局面时b成为句柄 则形成($ab, yz$)局面时b已可成为句柄 归约动作在栈内形成句柄 ($abgd, y$)归约为($abgB, y$)后形成句柄b，再归约为($aAgB, y$) 则存在对应推导S a
5、AgBy abgBy abgdy 这显然不是一个最右推导，矛盾！,*,*,*,4.5.4 活前缀,Viable Prefix 最右句型的前缀 移进归约分析过程中可出现在栈中 其右端不会在最右句柄的右端之后 总是可能通过向其末端添加若干终结符，形成最右句型,4.5.5 冲突（例4.25）,移进/归约冲突，归约/归约冲突 stmt if expr then stmt | if expr then stmt else stmt | other (any other statement) Stack Input $ if expr then stmt else $ 归约if expr then stm
6、t归约为stmt？或是 移进else，归约if expr then stmt else stmt？ 移进/归约冲突 解决方法强制一种动作,例4.26,(1)stmt id ( parameter-list ) (2) stmt expr := expr (3) parameter-list parameter-list , parameter (4,5) parameter-list parameter | id (6,7) expr id ( expr-list ) | id (8) expr-list expr-list , expr | expr 符号串“A(I, J)”，单词流id(i
7、d, id) Stack Input $ id ( id , id ) $ 归约(5)过程参数？归约(7)数组下标？ 归约/归约冲突 解决：(1) idprocid，区分过程/数组,4.6 算符优先分析方法,operator-precedence parsing 算符文法 无e产生式 产生式右部不含连续NT 例4.27 E EAE | - E | ( E ) | id A - | + | * | / | E E - E | E + E | E * E | EE | E E | - E | ( E ) | id,算符优先分析方法的特点,缺点 多优先级算符-难以处理 文法分析器关系不紧密 仅适用少
8、数文法 优点 简单 适合表达式分析,优先级,不相交的三种优先级关系终结符之间 ab，a的优先级低于b ab，a的优先级等于b ab，a的优先级高于b 不同于算术关系 ab，ab可能同时成立 三种关系可能均不成立 确定优先关系 传统意义运算符的优先级：+*，*+,使用算法计算优先关系,非多义性文法，语法树反映优先关系 不含e产生式文法，对任一对终结符a, b ab，当且仅当Pab或PaQb ab，当且仅当PaR，且Rb或RQb ab，当且仅当PRb，且Ra或RaQ 若算符文法G任何终结符对(a,b)至多只满足 ab，ab，ab 之一，则称之为算符优先文法,+,+,+,+,例,(1) E E +
9、T | T (2) T T * F | F (3) F ( E ) | id 传统意义：+*；+ +；( +,*；) +,* 算法计算 由(3)，()（规则1） EE + T，T T * F，+ *（规则2） EE + T，E E + T，+ +（规则3） F(E)，E E + T， + ),+,+,+,4.6.1 使用算符优先关系,目的：确定最右句型的句柄的边界 开始，内部，结束 产生式右部无连续NT句型同样 0a11a22 ann：i为e或单个非终结符，ai为单个终结符 去掉所有NT，在相邻T之间（包括$）填写算符优先关系,使用算符优先关系（续）,$id+id*id$id+id*id$ $
10、E + E * E$ $ + * $,id + * $, ,id, ,+, ,*, ,$,寻找句柄,由左至右扫描，寻找第一个 向回（左）扫描，略过，直至找到 、之间（不包含）的部分即为句柄 $id+id*id$id+id*id$id $E + E * E$ $ + * $E * E 非终结符占位符 使用栈实现非常容易,算法4.5 算符优先分析算法,输入：一个输入串w和一个优先关系表 输出：如果w符合语法，生成语法树框架（所有内部节点表示为占位符）；否则，输出错误 方法： 设置ip指向w$的第一个符号; repeat forever if (栈顶为$且ip指向$) return; else ,算
11、法4.5（续）,令a为最接近栈顶的终结符，b为ip指向符号 if (ab 或 ab) b压栈; ip前移; else if (ab) repeat 栈中符号弹出 until 栈顶符号刚刚弹出符号 else error(); ,例,id + id * id$ + id * id$ + id * id$ id * id$ * id$ * id$ id$ $ $ $ $,STACK,INPUT,Remark,一系列的弹出操作 利用某个产生式进行归约,$ id id + $ + + id id * + * * id id $ * $ + $ accept,$ $ id $ $ + $ + id $ +
12、 $ + * $ + * id $ + * $ + $,4.6.2 直接构造算符优先关系(表),在理解文法含义情况下直接构造优先关系 若q1优先级高于q2， q1q2，q2q1 若q1优先级等于q2（或相同的算符）， 若左结合，q1q2，q2q1， 若右结合，q1q2，q2q1 q(，(q，)q，q)，()，(，) id的优先级高于任何其他符号 $具有最低的优先级,例4.28,4.6.3 处理一元算符,普通一元算符， 对任何算符q，q 优先级高于q，q；否则，q 既是一元算符，也是二元算符，- 词法分析器返回不同单词 仅向前搜索不够，需记住前面符号,4.6.4 优先级函数,每个终结符对应两个整
13、型函数 f(a) g(b)ab 错误无法表示，不严重归约时仍可捕获 不是所有优先关系（表）都存在优先级函数,例4.29,f g,2 1,+,-,*,/,id,(,),$,2 1,4 3,4 5,4 3,6 5,0 5,6 0,0 0,算法4.6 构造优先级函数,输入：一个算符优先关系矩阵 输出：对应的优先级函数，或返回不存在信息 方法： 对每个非终结符a或$创建符号fa和ga 将创建的符号划分为尽量多的组： 若ab，则fa和gb分在同一组 没有关系，也可能分在一组 如ab，cb，则fa和fc会在一组 若还有cd，fa和gd会在一组，而ad不一定成立,算法4.6 （续）,创建有向图 节点符号分组
14、 对任何a、b ab，gb所在组向fa所在组引一条边 若ab，fa所在组向gb所在组引一条边 fa到gb的边（路径）：f(a)必须大于g(b)，反之亦然。 利用有向图获得优先函数 有向图存在回路优先级函数不存在 否则 f(a) = fa所在组开始的最长路径长度 g(a) = ga所在组开始的最长路径长度,例4.30,id + * $, ,id, ,+, ,*, ,$,f g,4 5,id,2 1,+,4 3,*,0 0,$,4.6.5 算符优先分析的错误处理,两种错误 栈顶和当前输入两个终结符无优先关系 句柄与任何产生式右部都不相同 只有这两个错误 考虑算法4.5，总会找到栈底为$，优先级低于
15、任何终结符 压栈过程中相邻符号必须满足、，因此，算法肯定可以找到句柄，进行归约,处理归约错误,错误诊断信息句柄“像”哪个产生式右部？ 句柄abc 右部aEcE：“非法的b” abEdc：“缺少d” 终结符匹配，非终结符不匹配，句柄中无非终结符，右部aEbc：“缺少E”,难点,有穷或无穷个符号串“可被弹出”？ b1b2bk 有穷，预先计算符号串“最相像”右部 有向图 节点终结符 a到b的边a b 路径“可被弹出”的符号串 开始、结束符号，ab1，bkc 回路无穷多个符号串；否则，有穷,例4.31,E E - E | E + E | E * E | EE | E E | - E | ( E ) | id ()，)外均可作开始符号，(外均可做结束符号 长度为1路径：+, -, *, /, , id，长度为2：( ),
