[编译原理.3.语法文法和语言..ppt

第 4 讲 西北农林科技大学本科教程 主讲教师：赵建邦 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.1 文法和语言 文法和语言的基本概念 形式语言分类（4类） 正规表达式与上下文无关文法 重点掌握 文法的表示 本讲目标 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定位 语法分析是编译过程的第二个阶段，也是核心部分 任务 根据语言的语法规则对单词序列进行语法分析，识别合法的语法单位（如表达式、语句、程序段等），若不存在语法错误则给出正确的语法结构（语法树） 理论依据：上下文无关文法 方法 自顶向下分析（推导：开始符号 句子） 自底向上分析（规约：句子 开始符号） 语法分析： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 英语语法结构 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.1 文法和语言 文法(Grammar)是程序语言的生成系统，用文法可以精确定义一个语言，并依据该文法构造出识别这个语言的自动机 文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述 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.1.1 文法和语言的基本概念 1、语言 通常我们用Σ表示字母表，字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的，程序语言的字母表通常是ASCII字符集。 由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字，字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。 那么，对字母表Σ来说，Σ*上的任意一个子集都称为Σ上的一个语言，记为L( )，该语言的每一个字符串称为语言L的一个语句或句子。 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.1.1 文法和语言的基本概念 1、语言 例如，设Σ?=?{a, b, c}，则: L?=?{ε, a, aa, ab, aaa, aab, aba, abb, …} 为Σ上的一个语言。 如果a表示字母，b表示数字，c看做其它符号，则L即是程序语言中的标识符集，其中的每个标识符就是标识符集中的一个句子。 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.1.1 文法和语言的基本概念 2、文法 （定义） 文法通常表示成四元组G[S]?=?(VT，VN，S，ξ): (1) ?VT为终结符号集，这是一个非空有限集，它的每个元素称为终结符号。 (2) ?VN为非终结符号集，它也是一个非空有限集，其每个元素称为非终结符号，且有VT∩VN?=?