自下而上语法解析.docVIP

自下而上语法分析 对于产生语言来讲，自上而下分析的方法是自然的。对于分析语言来讲，自下而上分析的方法更自然，因为语法分析处理的对象一开始都是终结符组成的输入序列，而不是文法的开始符号。同时，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要强，从而使得LR分析成为最为实用的语法分析方法。 3.5.1 自下而上分析的基本方法 思路：从句子ω开始，从左到右扫描ω，反复用产生式的左部替换产生式的右部、谋求对ω的匹配，最终得到文法的开始符号，或者发现一个错误。 3.5.1.1 规范归约与“剪句柄” 定义3.13设αβδ是文法G的一个句型，若存在S =*αAδ，A =+β，则称β是句型αβδ相对于A的短语，特别的，若有A→β，则称β是句型αβδ相对于产生式A→β的直接短语。一个句型的最左直接短语被称为句柄。 ## ① 直观上，句型是一个完整结构，短语是句型中的某部分。S是一个句型，而不是一个短语。 ② 短语形成的两个要素： 1．从S可以推导出A，即S=*αAδ； 2．从A至少一次推导出β，即A=+β。 特征： ① 短语：以非终结符为根的子树中所有从左到右排列的叶子； ② 直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2）； ③ 句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。 问题：id1+id2是句型id1+id2*id3的一个短语吗？ 答案：不是。因为： ① 没有一个E的子树，它的全部叶子是id1+id2；或者 ② 找不到某个E，使得E=* E*id3，E=+ id1+id2 定义3.14 若α是文法G的句子且满足下述条件，则称序列αn，αn-1，...，α0是α的一个最左归约。 1. αn=α 2. α0=S（S是G 的开始符号） 3. 对任何i(0i=n)，αi-1是从αi把句柄替换为相应产生式左部非终结符得到的。 ## 注意：最左归约的逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约。 需要解决的问题： ① 确定右句型中将要归约的子串（确定句柄）； ② 确定如何选择正确的产生式进行归约。 3.5.1.2 移进-归约分析器工作模式 解决方法：移进-归约分析――用一个栈“记住”将要归约句柄的前缀，句柄未形成前移进，形成后归约。 移进-归约分析器的工作模式：（不同的分析表决定了不同的分析方法） 工作方法：放幻灯，每个幻灯片是一个格局。 格局：（#栈，当前剩余输入#，改变格局的动作） 改变格局的动作： ① 移进（shift）：reduce）：accept）：error）：3.5.2 LR分析 LR分析的特点： ① 采用最一般的无回溯移进-归约方法； ② 可分析的文法是LL文法的真超集； ③ 能够及时发现错误，快到从左到右扫描输入序列的最大可能； ④ 分析表较复杂，难以手工构造。 3.5.2.1 LR分析与LR文法 1 移进-归约分析表 LR分析器的核心是LR分析表和驱动器。 文法：E→E-T | T T→T*F | F F→-F | id id - * # E T F 0 s4 s5 1 2 3 1 s6 acc 2 r2 s7 r2 3 r4 r4 r4 4 r6 r6 r6 5 s4 s5 8 6 s4 s5 9 3 7 s4 s5 10 8 r5 r5 r5 9 r1 s7 r1 10 r3 r3 r3 action goto 动作表（action）与转移表（goto）：两者都是二维数组，且行下标由称之为状态的整型数统一表示。动作表以终结符作为列下标，转移表以非终结符作为列下标。 action根据输入确定改变格局的动作，而goto仅指示非终结符的状态转移。故仅有动作表与输入有关。 2 格局与改变格局的动作 开始格局：（#0，ω#，第一个动作） 结束格局：（#0S，#，接受） 出错格局：（#δ，ω#，报错） 改变格局的四个动作： ① action[s, a]= si：终结符进栈并转向状态i（移进） ② = rj：用第j个产生式的左部替换栈中的句柄（与⑤共同完成归约） ③ = acc：接收 ④ = blank：报错 ⑤ goto[s, A] = s：在s状态下遇到A转移到状态s。 事实