[第四章第1节语法分析.ppt

I will greet this lecture with love in my heart. 主讲人：韩士元 Email: shiyuanhan@126.com Tel: +86 I will greet this lecture with love in my heart. 第四章 语法分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 源程序 目标程序 词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成 表格管理 错误检测 第四章 语法分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 第四章 语法分析 语法分析的任务: 分析一个文法的句子结构 语法分析器的功能： 按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 源程序 单词符号 取下一单词 ... 语法分 析树 词法分 析器 语法分 析器 符号表 编译程序 后续部分 第四章 语法分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 语法分析的分类 自上而下分析：从文法的开始符号开始，向下推导，推出句子。 自下而上分析：从句子开始，向上归约，归约到文法的开始符号。 第四章 语法分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 自上而下分析 第四章 语法分析 递归下降分析法： 对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 基本思想： 它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。 自上而下分析的主旨： 对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 当某个非终结符有多个产生式候选时，可能带来如下问题: 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。 2. 文法左递归问题。一个文法是含有左递归的，如果存在非终结符P,使自上而下的分析陷入无限循环。 4.1.1 自上而下分析存在的问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 4.1 自上而下分析 文法G=({S,A}, {x, y, z, *}, {S?xAy|z, A?**|*}, S) x * y S x A y * * y * 回溯 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 例4.1 文法G1=({P, U}, {a}, {P?aU, U?P|ε}, P), L(G1)=a+ 例4.2 文法G2=({P}, {a}, {P?Pa|a}, P), L(G2)=a+ 例4.3 文法G3=({P}, {a}, {P?aP|a}, P), L(G3)=a+ 4.1.1 自上而下分析存在的问题 Evaluation only. Created with Aspos