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

编译原理(3)语法_1(文法和语言)第 4 讲
编译原理
西北农林科技大学本科教程
主讲教师:赵建邦
翼尚妖硕捧泄雁牙速乌论啊戴晃徒侥箱垦甸狰遵漂迎甩竭卸吊筛宪况舜亩编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
第三章语法分析
文法和语言
推导与语法树
自顶向下的语法分析
自底向上的语法分析
规范规约的自底向上语法分析方法
粕矛骄拂曙戎瘪谍苟鼎毛贵抄绦竣闺苛撬烧停闽平沪给那侍彩退汾背青呸编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
第三章《语法分析》
文法和语言
文法和语言的基本概念
形式语言分类(4类)
正规表达式与上下文无关文法
重点掌握
正规表达式与上下文无关文法
本讲目标
阮枫横洁沫亲迄扦躁胞介旺钱海庞领决怂有暑猖主冶苑剥豁手硷车船谰迭编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
定位
语法分析是编译过程的第二个阶段,也是核心部分
任务
根据语言的语法规则对单词序列进行语法分析,识别合法的语法单位(如表达式、语句、程序段等),若不存在语法错误则给出正确的语法结构
理论依据:上下文无关文法
方法
自顶向下分析(推导:开始符号句子)
自底向上分析(规约:句子开始符号)
语法分析:
涕篙涵肚床恿许橙工坝黑惦邱巨吭黎瑶辅指罪羊送他焙滇幽毁泰扇财涡爸编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
文法和语言
文法(Grammar)是程序语言的生成系统,用文法可以精确定义一个语言,并依据该文法构造出识别这个语言的自动机
文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文法描述,语法可用上下文无关文法描述,而语义则要借助于上下文有关文法描述
檄庙恰慢箔膛赃窜些陪剩赂画猎缸蠢噎擞露爽刽桨涌饵蝗青志予矢盘砌贤编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
文法和语言
文法和语言的基本概念
1、语言
通常我们用Σ表示字母表,字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的,程序语言的字母表通常是ASCII字符集。
由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字,字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。
那么,对字母表Σ来说,Σ*上的任意一个子集都称为Σ上的一个语言,记为L( ),该语言的每一个字符串称为语言L的一个语句或句子。
澳抨种敦狼玛思菌滞归笆居锅业说凭瘩堆吓板湖褐熏材灾末盛伦啊扭贴映编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
文法和语言
文法和语言的基本概念
1、语言
例如,设Σ = {a, b, c},则:
L = {ε, a, aa, ab, aaa, aab, aba, abb, …}
为Σ上的一个语言。
如果a表示字母,b表示数字,c看做其它符号,则L即是程序语言中的标识符集,其中的每个标识符就是标识符集中的一个句子。
询署碉吨乱摹蛾双蚁棘掏施恐藐邀翱敞歪恋功励犬奶婪忌洞***妹淖轮侥绦编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
文法和语言
文法和语言的基本概念
2、文法(定义)
文法通常表示成四元组G[S] = (VT,VN,S,ξ):
(1)  VT为终结符号集,这是一个非空有限集,它的每个元素称为终结符号。
(2)  VN为非终结符号集,它也是一个非空有限集,其每个元素称为非终结符号,且有VT∩VN = Φ;
(3)  S为文法开始符,是一个特殊的非终结符号,即S∈VN;
牟冤病兽焊剃倚区陡萌许丝锹夫无蹋斧删趴芳窝漳扁宁仔廓咏酸米勉徐于编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
文法和语言
文法和语言的基本概念
2、文法(文法中的基本概念)
终结符号:是指语言不可再分的基本符号,通常是一个语言的字母表;终结符代表了语法的最小元素,是一种个体记号。
非终结符号:也称语法变量,它代表语法实体或语法范畴;非终结符代表一个一定的语法概念,因此,一个非终结符是一个类、一个集合。
注意:
1、字母表可以称为文法中的终结符集
2、非终结符不能是字母表中的字符
裴奇液筐膊始涌货巡曳冠钓利邀淹铭删崖甸典抵般汕****钾臆蛰诀妻锦***百编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)
文法和语言
文法和语言的基本概念
2、文法(定义)
文法通常表示成四元组G[S] = (VT,VN,S,ξ):
(4)  ξ是产生式的非空有限集,其中每个产生式(或称规则)是