编译原理(3)语法 1(文法和语言).ppt

编译原理(3)语法_1(文法和语言)第 4 讲
编译原理
西北农林科技大学本科教程
主讲教师:赵建邦
第三章语法分析
文法和语言
推导与语法树
自顶向下的语法分析
自底向上的语法分析
规范规约的自底向上语法分析方法
第三章《语法分析》
文法和语言
文法和语言的基本概念
形式语言分类(4类)
正规表达式与上下文无关文法
重点掌握
文法的表示
本讲目标
定位
语法分析是编译过程的第二个阶段,也是核心部分
任务
根据语言的语法规则对单词序列进行语法分析,识别合法的语法单位(如表达式、语句、程序段等),若不存在语法错误则给出正确的语法结构
理论依据:上下文无关文法
方法
自顶向下分析(推导:开始符号句子)
自底向上分析(规约:句子开始符号)
语法分析:
文法和语言
文法(Grammar)是程序语言的生成系统,用文法可以精确定义一个语言,并依据该文法构造出识别这个语言的自动机
文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文法描述,语法可用上下文无关文法描述,而语义则要借助于上下文有关文法描述
文法和语言
文法和语言的基本概念
1、语言
通常我们用Σ表示字母表,字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的,程序语言的字母表通常是ASCII字符集。
由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字,字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。
那么,对字母表Σ来说,Σ*上的任意一个子集都称为Σ上的一个语言,记为L( ),该语言的每一个字符串称为语言L的一个语句或句子。
文法和语言
文法和语言的基本概念
1、语言
例如,设Σ = {a, b, c},则:
L = {ε, a, aa, ab, aaa, aab, aba, abb, …}
为Σ上的一个语言。
如果a表示字母,b表示数字,c看做其它符号,则L即是程序语言中的标识符集,其中的每个标识符就是标识符集中的一个句子。
文法和语言
文法和语言的基本概念
2、文法(定义)
文法通常表示成四元组G[S] = (VT,VN,S,ξ):
(1)  VT为终结符号集,这是一个非空有限集,它的每个元素称为终结符号。
(2)  VN为非终结符号集,它也是一个非空有限集,其每个元素称为非终结符号,且有VT∩VN = Φ;
(3)  S为文法开始符,是一个特殊的非终结符号,即S∈VN;
文法和语言
文法和语言的基本概念
2、文法(定义)
文法通常表示成四元组G[S] = (VT,VN,S,ξ):
(4)  ξ是产生式的非空有限集,其中每个产生式(或称规则)是一序偶(α,β),通常写作
α → β或α ::= β
读作“α产生β”、“α是β”或“α定义为β”。在此,α为产生式的左部,而β为产生式的右部,α、β是由终结符和非终结符组成的符号串,α∈(VT∪VN) + 且至少有一个非终结符,而β∈(VT∪VN) *。
文法和语言
文法和语言的基本概念
2、文法(文法中的基本概念)
终结符号:是指语言不可再分的基本符号,通常是一个语言的字母表;终结符代表了语法的最小元素,是一种个体记号。
非终结符号:也称语法变量,它代表语法实体或语法范畴;非终结符代表一个特定的语法概念,因此,一个非终结符是一个类、一个集合。
注意:
1、字母表可以称为文法中的终结符集
2、非终结符不能是字母表中的字符