《编译原理》课程简介 (29).pdf

编 译 原 理 C O M P I L A T I O N P RIN C IP LE 第五章 语法分析自下而上分析5.1.2 分析树与规范规约5.1.2 分析树与规范规约二、分析树n语法分析过程可用一棵语法分析树表示出来。n自下而上分析过程：边输入单词符号，边归约。即，在自下而上分析的每一步，都可画出一棵子树，随着归约的完成，便最终形成一棵分析树。n如果文法无二义，分析树恰好等同于语法树。n核心问题：识别可归约串bdbaceSABA5.1.2 分析树与规范规约三、规范归约n定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有SA且A 则称是句型相对于非终结符A的短语。*+n特别地，如果有A,则称是句型相对于规则A 的直接短语。n一个句型的最左直接短语称为该句型的句柄。5.1.2 分析树与规范规约E T|E+TT F|T*F F (E)|i和句型i1*i2+i3：E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3n短语：i1，i2，i3，i1*i2，i1*i2+i3n直接短语：i1，i2，i3n句柄：i1考虑文法G(E)例例5.1.2 分析树与规范规约n在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。EFFTTTi1+*EFi3i25.1.2 分析树与规范规约n可用句柄来对句子进行归约句型 归约规则 abbcde (2)A baAbcde aAcde aAcBe S (3)A Ab(4)B d(1)S aAcBe5.1.2 分析树与规范规约n定义：假定是文法G的一个句子，我们称序列n，n-1，0 是的一个规范归约，如果此序列满足：p1、n=p2、0为文法的开始符号，即0=Sp3、对任何i，0 i n，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。5.1.2 分析树与规范规约n把上例倒过来写，则得到：S aAcBe aAcde aAbcde abbcden显然这是一个最右推导。最右推导常被称为规范推导。容易看到，规范归约是关于的一个最右推导 的逆过程。因些，规范归约也称最左归约。n 由规范推导推出的句型称为规范句型。(1)(4)(2)(3)5.1.2 分析树与规范规约bdbaceSABAdbaceSABAdaceSABaceSABS|编译原理谢 谢Thanks