第五章语法分析自下而上分析.pptVIP

第五章 语法分析—自下而上分析 内容 自下而上分析基本问题 算符优先分析 语法分析器的自动产生工具YACC 5.1 自下而上分析基本问题 自下而上分析： 从输入开始，逐步进行“归约”，直至归约到文法的开始符号。 5.1.1 归约 自下而上分析法是一种“移进-归约”法。 基本思想： 用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。 5.1.1 归约 例：设文法G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 试对abbcde进行“移进-归约”分析。 5.1.1 归约 例：设文法G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 试对abbcde进行“移进-归约”分析。 5.1.1 归约 分析树和语法树不一定一致。 自下而上分析过程：边输入单词符号，边归约。 核心问题：识别可归约串 5.1.2 规范归约简述 5.1.2 规范归约简述 例：文法G[E]： E→E+T|T T→T*F|F F→(E)|–F|id 考虑文法G[E]上的句子id1+id2*id3。其最右推导和分析树如图5.1(a)、(b)所示。 分析树中的叶子与短语、直接短语和句柄有下述关系。 ①短语：以非终结符为根的子树中所有从左到右排列的叶子； ②直接短语：只有父子关系的树中所有从左到右排列的叶子(树高为2)； ③句柄：最左边父子关系树中所有从左到右排列的叶子(句柄是唯一的)。 根据定义，从文法开始符号经过0步推导得到E1，从E1经过若干步推导得到id1+id2*id3，所以id1+id2*id3是句型id1+id2*id3相对于E1的短语(其中α和δ均为ε，β是句子的全体)。 考虑推导E1 = E2+id2*id3 = T2+id2*id3 = F1+id2*id3 = id1+id2*id3，id1是相对于非终结符E2、T2和F1的短语(其中α为ε，δ为+id2*id3)，特别是相对于F1的直接短语，也是句柄。 id1+id2不是句型id1+id2*id3中相对于任何非终结符的短语，因为找不到任何一个非终结符，它的子树中的所有叶子构成id1+id2。 5.1.2 规范归约简述 例：考虑文法G[E]：E?T|E+T T?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+i3 短语： i1，i2，i3， i1*i2， i1*i2+i3 直接短语： i1，i2，i3 句柄： i1 5.1.2 规范归约简述 可用句柄来对句子进行归约 例：设文法G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 句型 归约规则 abbcde (2) A ? b aAbcde (3) A ? Ab aAcde (4) B ? d aAcBe (1) S ? aAcBe S 5.1.2 规范归约简述 定义：假定?是文法G的一个句子，我们称序列 ?n， ?n-1，? ，?0 是的一个规范归约，如果此序列满足： 1 ?n= ? 2 ?0为文法的开始符号，即?0=S 3 对任何i，0 ? i ? n， ?i-1是从?i经把句柄替换成为相应产生式左部符号而得到的。 5.1.2 规范归约简述 把上例倒过来写，则得到： S ? aAcBe? aAcde ? aAbcde ? abbcde 显然这是一个最右推导。 规范归约是关于是一个最右推导的逆过程 最左归约 规范推导 由规范推导推出的句型称为规范句型。 规范归约的中心问题：确定句型的句柄。 5.1.2 规范归约简述 最右推导，推导的每一步结果都是一个右句型。该推导即分析树 “剪句柄”的全过程。 5.1.3 符号栈的使用与语法树的表示 从分析树上直观地看，“剪句柄”的方法十分简单。但是若在语法分析器中实现剪句柄，则有两个问题必须解决： ① 确定右句型中将要归约的子串(确定句柄)； ② 确定如何选择正确的产生式进行归约。 具体实现采用