自下而上语法分析

《自下而上语法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、自下而上语法分析对于产生语言来讲，自上而下分析的方法是自然的。对于分析语言来讲，自下而上分析的方法更自然，因为语法分析处理的对象一开始都是终结符组成的输入序列，而不是文法的开始符号。同时，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要强，从而使得LR分析成为最为实用的语法分析方法。3.5.1自下而上分析的基本方法思路：从句子ω开始，从左到右扫描ω，反复用产生式的左部替换产生式的右部、谋求对ω的匹配，最终得到文法的开始符号，或者发现一个错误。3.5.1.1规范归约与“剪句柄”定义3.13设α

2、βδ是文法G的一个句型，若存在S=*>αAδ，A=+>β，则称β是句型αβδ相对于A的短语，特别的，若有A→β，则称β是句型αβδ相对于产生式A→β的直接短语。一个句型的最左直接短语被称为句柄。##①直观上，句型是一个完整结构，短语是句型中的某部分。S是一个句型，而不是一个短语。②短语形成的两个要素：1．从S可以推导出A，即S=*>αAδ；2．从A至少一次推导出β，即A=+>β。特征：①短语：以非终结符为根的子树中所有从左到右排列的叶子；②直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2）；③句柄：

3、最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。问题：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(0

4、逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约。需要解决的问题：①确定右句型中将要归约的子串（确定句柄）；②确定如何选择正确的产生式进行归约。3.5.1.2移进-归约分析器工作模式解决方法：移进-归约分析――用一个栈“记住”将要归约句柄的前缀，句柄未形成前移进，形成后归约。移进-归约分析器的工作模式：（不同的分析表决定了不同的分析方法）工作方法：放幻灯，每个幻灯片是一个格局。格局：（#栈，当前剩余输入#，改变格局的动作）改变格局的动作：①移进（shift）：输入序列中的终结符进栈。（匹配终结

5、符）②归约（reduce）：将栈顶句柄替换为对应的非终结符。（归约产生式）③接受（accept）：宣告分析成功。④报错（error）：发现语法错误，调用错误恢复例程。从移进-归约分析过程中可以看出：①句柄总是在栈顶形成。这是因为在分析的过程中一旦形成某产生式的右部就立即进行归约，而从左到右扫描输入，最早形成的自然是最左的直接短语；②栈中保留的总是一个右句型的前缀（加上若干终结符形成句型），称为活前缀；－13－③如果将每次归约逻辑上认为是构造对应产生式的树，则分析的全过程逻辑上就是从下到上构造一棵分析树；反之，如

6、果将每次归约逻辑上认为是剪去假想分析树上对应产生式的孩子，则分析的全过程逻辑上就是从下到上为分析树剪句柄。需要解决的问题：（由分析表确定）①如何保证栈中总是活前缀(正确移进)；②如何确定栈顶已经形成句柄并选择正确的产生式进行归约(正确归约)。3.5.2LR分析LR分析的特点：①采用最一般的无回溯移进-归约方法；②可分析的文法是LL文法的真超集；③能够及时发现错误，快到从左到右扫描输入序列的最大可能；④分析表较复杂，难以手工构造。3.5.2.1LR分析与LR文法<1>移进-归约分析表LR分析器的核心是LR分析表和

7、驱动器。文法：E→E-T

8、TT→T*F

9、FF→-F

10、idid-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r110r3r3r3actiongoto动作表（action）与转移表（goto）：两者都是二维数组，且行下标由称之为状态的整型数统一表示。动作表以终结符作为列下标，转移表以非终结符作为列下标。action根据输入确定改变格局的动作，而goto仅指示非终结符的状态转移。故仅有动作表与输入有关。<2>格局与改变

11、格局的动作－13－开始格局：（#0，ω#，第一个动作）结束格局：（#0S，#，接受）出错格局：（#δ，ω'#，报错）改变格局的四个动作：①action[s,a]=si：终结符进栈并转向状态i（移进）②=rj：用第j个产生式的左部替换栈中的句柄（与⑤共同完成归约）③=acc：接收④=blank：报错⑤goto[s,A]=s'：在s状态下遇到A转移到状态s'。事实上，②和⑤共同完成归约。算