编译原理-第五章习题答案.ppt

* 例P95 优先关系表对应P90表5.1 + * ↑ （ ） f 4 6 6 2 9 g 3 5 8 8 2 * 2.4 算符优先分析中的出错处理(自学) 若在栈顶终结符与下一输入符号之间不存在任何优先关系 若找到某一最左素短语，但不存在任一产生式可用来归约 * 本章教学线索 1 自下而上分析基本问题 2 算符优先分析 3 LR分析法 3.1 LR分析器的逻辑结构及工作过程 3.2 LR（0）项目集规范族和LR（0）分析表的构造 3.3 SLR分析表的构造 3.4 规范LR分析表的构造 3.5 LALR分析表的构造 3.6 LR分析的出错处理 4 语法分析器的自动产生工具YACC * 3 LR分析法 LR(k)分析技术。这里的“L”是指从左至右扫描输入符号串，“R”是指构造一个最右推导的逆过程，“k”是指为了作出分析决定而向前看的输入符号的个数。LR分析方法是当前最广义的无回溯的“移进- 归约”方法。根据栈中的符号串和从左向右顺序查看输入串的k（k≥0）个符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。LR（k）分析技术是knuth于1965年首先提出来的。 优点：适用范围广；分析速度快；报错准确。 构造分析器的工作量很大，不大可能手工构造；用软件工具YACC（Yet Another Compiler Compiler，Bell，1974。）来构造。 * 3.1 LR分析器的逻辑结构及工作过程 a1a2…………..ai……………an# LR分析程序 输出 sm Xm s1 X0 s0 # action goto 分析表 栈 输入串 LR分析器的逻辑模型 栈：栈的每一项内容包括状态s和文法符号X两部分，（s0，＃）为分析开始前预先放置的初态和句子结束符。 LR分析器的核心部分就是一张分析表，它包括“动作”和“状态转换”两部分，都是用二维数组来表示。ACTION[s，a]规定了当前状态s面临输入a应该采取的动作，GOTO[s，X]规定了状态s面对文法符号X（终结符或非终结符）时下一状态是什么。GOTO[s，X]定义了一个以文法符号为字母表的DFA。 * ACTION[s，a]所规定的动作有以下四种可能： 移进 把（s，a）的下一状态s′= GOTO[s，a]和输入符号a推进栈，下一输入符号变成现行输入符号； 归约 指用某一产生式A→β进行归约。假设β的长度为r，归约的动作是A，去除栈顶的r个项，使状态sm-r变成栈顶状态，然后把（sm-r，A）的下一状态s′＝GOTO[sm-r，A]和文法符号A进栈。归约动作不改变现行输入符号。执行归约动作意味着β（＝Xm-r+1…Xm）已呈现于栈顶而且是一个相对于A的句柄。 接受 宣布分析成功，停止分析器的工作。 报错 发现源程序含有错误，调用出错处理程序。 * LR分析器的工作过程 格局：（栈中符号序列，已归约串和剩余输入符号串） 开始：（s0，＃，a1 a2 ……an＃) 中间：（s0s1s2…sm，＃X1X2…Xm，aiai+1…an＃) 分析器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定的，执行ACTION[s，ai]所规定的动作。 1）若ACTION [sm，ai]为“移进”，且s＝GOTO[sm，ai]，则三元式变为（s0s1…sms，＃X1X2…Xmai，ai+1…an＃） 2）若ACTION [sm，ai]＝{A→β}，则按产生式A→β进行“归约”，则三元式变为（s0s1…sm－rs，＃X1X2…Xm－rA，aiai+1…an＃） 此处：s＝GOTO[sm－r，A]，r为β的长度，β＝Xm-r+1…Xm。 3）若ACTION [sm，ai]为“接受”，则三元式不再变化，分析成功； 4）若ACTION [sm，ai]为“报错”，则三元式变化过程终止，报告错误。 * 例：5.7 P102 分析表 为P101图5.5 文法： （1）E→E+T （2）E→T （3）T→T*F （4）T→F （5）F→（E） （6）F→i 状态 ACTION（动作） GOTO（转换） i + * ( ) # E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 * 分析过程中三元式的工作过程 状态 符号 输入串 备注 （1） 0