《编译原理3语法2推导与语法树.ppt

第 5 讲 西北农林科技大学本科教程 主讲教师：赵建邦 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第三章 语法分析 3.1 文法和语言 3.2 推导与语法树 3.3 自顶向下的语法分析 3.4 自底向上的语法分析 3.5 规范规约的自底向上语法分析方法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第三章《语法分析》 3.2 推导与语法树 推导与短语 语法树与二义性 重点掌握 短语、句柄的概念 二义性的消除 本讲目标 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.2.1 推导与短语 1、规范推导 在3.1.1节中，所给句子i+i*i推导序列中的每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换，这样的推导称为最右推导（规范推导），规范推导的逆过程称为规范规约 如果每一步推导都是对句型中的最左非终结符用相应产生式的右部进行替换，则称为最左推导 3.2 推导与语法树 举例：文法G[E]：E?→?E?+?E | E?*?E | (E) | i (3.1) 句子i+i*i的最左推导和最右推导？ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.2.1 推导与短语 2、短语 设αβδ是文法G[S]的一个句型，如果有： 则称β是句型αβδ关于非终结符A的一个短语，或称β是αβδ的一个短语。特别是有A→β产生式时，β为句型αβδ的一个直接短语或简单短语 短语的两个条件缺一不可。仅有A → β未必意味着β就是句型αβδ的一个短语，还需要有 加以限制；即短语属于句型的组成部分。 3.2 推导与语法树 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.2.1 推导与短语 3、句柄 一个句型的最左直接短语称为该句型的句柄。注意，一个句型的直接短语可能不只一个，但最左直接短语则是惟一的。 3.2 推导与语法树 举例：文法G[E]：S?→?AB A → bB ?B → Sb | a 句型“baSb”的短语和句柄？ [解答]： （1） 句型本身是该句型关于开始符号的短语 最左推导 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.2.1 推导与短语 3.2 推导与语法树 [解答]： （2） 句型baSb的子串Sb,是该句型相对于非终结符B的一个短语，而且是该句型的直接短语 （3） 最右推导 句型baSb的子串a, 是该句型相对于非终结符B的一个短语，而且是该句型的直接短语、句柄 最左推导 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.2.1 推导与短语 3.2 推导与语法树 [解答]： （4） 最右推导 句型baSb的子串ba, 是该句型相对于非终结符A的一个短语 注意：短语、直接短语、句柄都是针对某一句型来说的，都是指句型中的哪些符号串能够构成短语、直接短语、句柄。脱离句型，谈论三者是无意义的。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5