编译原理课件chap05(陈火旺)

《编译原理课件chap05(陈火旺)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章语法分析——自下而上分析所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根结。5.1自下而上分析基本问题我们先讨论自下而上分析的一些基本思想和基本概念：自底向上分析方法，也称移进-归约分析法实现思想（是推导的逆过程）：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的可归约串时，就用该产生式的左部非终结符代替相应右部的文法符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功。第五章语法分析

2、--自下而上分析移进—规约分析（Shift-reduceparsing)22#S.R.P#符号栈输入串要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约。第五章语法分析--自下而上分析33分析过程：把输入符号串从左向右一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的可归约串时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的可归约串，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈

3、中仅含有左界符号和识别符号，则表示分析成功，否则失败。#S.R.P#符号栈输入串第五章语法分析--自下而上分析例1：文法SaAcBeAbAAbBd输入串abbcde#分析第五章语法分析--自下而上分析归约分析过程（移进归约）：步骤符号栈输入符号串动作1#abbcde#移进2#abbcde#移进3#abbcde#归约（A→b4#aAbcde#移进5#aAbcde#归约（A→Ab)?6#aAcde#移进7#aAcde#移进8#aAcde#归约（B→b）9#aAcBe#移进10#aAcBe#规约S→aAcBe11#S#接受SaAcBeAbAAbBd

4、第五章语法分析--自下而上分析上述的每一步规约可以构造一颗语法树：AbBdAAbbSAbbaceBdA问题的提出：①在构造语法树的过程中，何时规约？当可归约串出现在栈顶符号串中就可以规约。②如何知道在栈顶符号串中已经形成可归约串？需要精确定义可规约串这个直观概念。这是自下而上分析的关键。第五章语法分析--自下而上分析自下而上分析的关键问题：如何确定可归约串？通过自底向上分析算法中的优先关系来计算简单优先分析法（规范规约）：寻找句柄算符优先分析法：寻找最左素短语第五章语法分析--自下而上分析一、自底向上优先分析法概述优先分析法又可分简单优先分析法和算符优先分

5、析法。①简单优先分析法：按一定原则求出文法中所有符号（终结符和非终结符）的优先关系，按这种关系求出句柄。（规范归约——从左向右的规约）；②算符优先分析法：只考虑算符（终结符）之间的优先关系，不考虑非终结符之间的优先关系。按这种关系求出最左素短语。（不规范归约）简单优先分析法：准确规范，但分析效率低，实际使用价值不大；算符优先分析法：不规范，但分析速度快，适于实际使用。第五章语法分析--自下而上分析句柄的定义：令G是一文法，S是文法的开始符号，δ是文法G的一个句型。（为δ确定可归约串）如果有SA且A，则称是句型δ相对于非终结符A的短语。

6、若有A，则称是句型δ相对A的直接短语。一个句型的最左直接短语称为该句型的句柄。句柄是自底向上句法分析中当前时刻需要规约的符号串。如果能够自动计算出当前的句柄，则可执行自动句法分析。*+第五章语法分析--自下而上分析注意：短语的两个条件是：S*A且A+[例5.1]考虑文法：ET

7、E+TTF

8、T*FFi

9、(E)（5.2）对于句型i*i+i推导解：E→E+T→T+T→T*F+T→F*F+T→i*F+T→i*i+F→i*i+i第五章语法分析--自下而上分析尽管有E+i+i但是,i+i并不是该句型的一个短语，因为不存在从E(文法开始符）

10、到i*E的推导。但是，i,i*i,和i*i+i自身都是句型i*i+i的短语。而且为直接短语。[例5。2]上题文法（5。2）的另一个句型E+T*F+i的短语有E+T*F+i,E+T*F,T*F,和i.其中T*F和i为直接短语，T*F为句柄。解：E→E+T→E+T+T→E+T*F+T→E+T*F+F→E+T*F+I?T*F+i是否是句柄第五章语法分析--自下而上分析EET+TFT×FFi3i2i1从语法树中可以看出，所以树叶的组合就是其相对应的父亲的短语。第五章语法分析--自下而上分析关于规范归约精确的说，假定是文法G的一个句子，我们称序列nn-1n-2

11、,。。。,0是的一个规范规约，如果此序列满足：（