[编译原理.3.语法3.自顶向下语法分析递归下降..pptVIP

第 6 讲 西北农林科技大学本科教程 主讲教师：赵建邦 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.3 自顶向下的语法分析 递归下降分析法 LL(1)分析法（下一讲内容） 重点掌握 消除左递归 消除回溯 构建递归下降子程序 本讲目标 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.3 自顶向下的语法分析 算法思想： 从文法的开始符号出发，向下推导，如果推导出的句子恰好为输入符号串，则输入符号串为符合该文法的句子； 或者：开始符号作为根节点，向下生长出一棵语法树，其叶子节点组成的句子恰好为输入符号串。这里的每一步“生长”对应一次直接推导。 自顶向下分析方法: 1、不确定的自顶向下分析 2、确定的自顶向下分析 递归下降分析法 LL(1)分析法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1、不确定的自顶向下分析方法 假定文法G[S]为 　　 S?→?xAy　　?? A?→?ab | a 若输入串为xay，则其分析过程如下： (1)建立根节点S； (2)关于S的产生式只有一个，则生长语法树, 匹配语法树的第一个终结符x； (3) A?→?ab | a 有两个候选式，选择第一个, 并且匹配语法树的第二个叶子节点a； (4)输入串xay期待匹配y,而语法树中的b与之匹配失败； S A y a b x 3.3 自顶向下的语法分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1、不确定的自顶向下分析方法 假定文法G[S]为 　　 S?→?xAy　　?? A?→?ab | a 若输入串为xay，则其分析过程如下： (5)撤销匹配a， 注销A所生成的子树，回溯； (6)选择产生式A?→?a，重新匹配a； (7) 匹配输入串的字符y；而语法树的最后 一个叶子节点也是y,因此语法树和输入串xay匹配成功。 S A y a b x a 3.3 自顶向下的语法分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 小结：关于不确定的自顶向下分析方法 这种自顶向下的分析是一个不断试探的过程；即，在分析过程中，如果出现多个产生式(即候选式)可供选择，则逐一试探每一候选式进行匹配，每当一次试探失败，就选取下一候选式再进行试探； 此时，必须回溯到这一次试探的初始现场，包括注销已生长的子树及将匹配指针调回到失败前的状态。 这种带回溯的自顶向下分析方法实际上是一种穷举的试探方法，其分析效率极低，在实用的编译程序中很少使用。 3.3 自顶向下的语法分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2、确定的自顶向下分析方法 确定的自顶向下分析要求文法满足两个条件： (1) 文法不含左递归：即不存在这样的非终结符号A：有A→A…存在或者有 ； 原因：左递归的文法使自顶向下分析工作陷