资源描述：
《编译原理语法1(文法和语言)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4讲编译原理西北农林科技大学本科教程主讲教师：赵建邦第三章语法分析3.1文法和语言3.2推导与语法树3.3自顶向下的语法分析3.4自底向上的语法分析3.5规范规约的自底向上语法分析方法第三章《语法分析》3.1文法和语言文法和语言的基本概念形式语言分类（4类）正规表达式与上下文无关文法重点掌握文法的表示本讲目标定位语法分析是编译过程的第二个阶段，也是核心部分任务根据语言的语法规则对单词序列进行语法分析，识别合法的语法单位（如表达式、语句、程序段等），若不存在语法错误则给出正确的语法结构（语法树）理论依据：上下文无关文法方法自顶向下分析（推导：开始符号句子）自底向上分析（规约：句子开
2、始符号）语法分析：英语语法结构3.1文法和语言文法(Grammar)是程序语言的生成系统，用文法可以精确定义一个语言，并依据该文法构造出识别这个语言的自动机文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述3.1文法和语言3.1.1文法和语言的基本概念1、语言通常我们用Σ表示字母表，字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的，程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字，字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示
3、。那么，对字母表Σ来说，Σ*上的任意一个子集都称为Σ上的一个语言，记为L()，该语言的每一个字符串称为语言L的一个语句或句子。3.1文法和语言3.1.1文法和语言的基本概念1、语言例如，设Σ = {a,b,c}，则:L = {ε,a,aa,ab,aaa,aab,aba,abb,…}为Σ上的一个语言。如果a表示字母，b表示数字，c看做其它符号，则L即是程序语言中的标识符集，其中的每个标识符就是标识符集中的一个句子。3.1文法和语言3.1.1文法和语言的基本概念2、文法（定义）文法通常表示成四元组G[S] = (VT，VN，S，ξ):(1)VT为终结符号集，这是一个非空有限集，它的每个
4、元素称为终结符号。(2)VN为非终结符号集，它也是一个非空有限集，其每个元素称为非终结符号，且有VT∩VN= Φ；(3)S为文法开始符，是一个特殊的非终结符号，即S∈VN；3.1文法和语言3.1.1文法和语言的基本概念2、文法（定义）文法通常表示成四元组G[S] = (VT，VN，S，ξ):(4)ξ是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(α，β)，通常写作α → β或α ::= β读作“α产生β”、“α是β”或“α定义为β”。在此，α为产生式的左部，而β为产生式的右部，α、β是由终结符和非终结符组成的符号串，α∈(VT∪VN)+且至少有一个非终结符，而β∈(VT∪
5、VN)*。3.1文法和语言3.1.1文法和语言的基本概念2、文法（文法中的基本概念）终结符号：是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。非终结符号：也称语法变量，它代表语法实体或语法范畴；非终结符代表一个特定的语法概念，因此，一个非终结符是一个类、一个集合。注意：1、字母表可以称为文法中的终结符集2、非终结符不能是字母表中的字符3.1文法和语言3.1.1文法和语言的基本概念2、文法（文法中的基本概念）文法开始符号S：是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目
6、标的中间变量产生式：(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。P→α1P→α2……P→αn如果：P → α1
7、α2
8、…
9、αn其中，每个αi(i=1,2,…,n)称为P的一个候选式，直竖“
10、”读为“或”，它与“→”一样是用来描述文法的元语言符号(即不属于Σ的字符)。3.1文法和语言可以写成：例如，定义一个仅包含加和乘运算的表达式的文法G[E]:G[S] = (VT，VN，S，ξ):VT={+*()i}VN={E,T,F}S=Eξ为以下产生式的集合：E→E+T
11、T T→T*F
12、F F→(E)
13、i两种文法都可以识别包含加和乘运算的表达式，它们
14、的区别将在后面的课程中讲解VT={+*()i}VN={E}S=Eξ:E→E+EE→E*EE→(E)E→i3.1文法和语言或者：ξ:E→i
15、E+E
16、E*E
17、(E)3.1.1文法和语言的基本概念关于文法表示的约定：在此后的讨论中，用大写字母A、B、S、E等表示非终结符，用小写字母a、b、i、j等表示终结符，并用希腊字母等表示文法符号串，即α、β、δ、γ等均属于(VT∪VN)*。2.3正规表达式与优先自动机简介例3.1试构造产生标识符的文法。[解答]首先，标识符是以字母开头
