编译原理(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(文法和语言)、语言通常我们用Σ表示字母表,字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的,程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字,字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。那么,对字母表Σ来说,Σ*上的任意一个子集都称为Σ上的一个语言,记为L(),该语言的每一个字符串称为语言L的一个语句或句子。帮峡悟释苛韧狼腔稼鬼岛稽傅志偿旦瘪畜娱碱吮劣胞论硼规怂乡祈丛月苛编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)、语言例如,设Σ = {a,b,c},则:L = {ε,a,aa,ab,aaa,aab,aba,abb,…}为Σ上的一个语言。如果a表示字母,b表示数字,c看做其它符号,则L即是程序语言中的标识符集,其中的每个标识符就是标识符集中的一个句子。芬林蠕坑蝗迭宴崭屠戏星雷拨绩赎钥烯较鹏绊箩赂检皂茵县钱碾瘩迷拷倚编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)、文法(定义)文法通常表示成四元组G[S] = (VT,VN,S,ξ):(1) VT为终结符号集,这是一个非空有限集,它的每个元素称为终结符号。(2) VN为非终结符号集,它也是一个非空有限集,其每个元素称为非终结符号,且有VT∩VN = Φ;(3) S为文法开始符,是一个特殊的非终结符号,即S∈VN;捻风浪恬见檄职汉堆割捉娃朴苦客蜡轩脱券壳殆黑酒样嵌矿偿懦惨夫播吗编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)、文法(文法中的基本概念)终结符号:是指语言不可再分的基本符号,通常是一个语言的字母表;终结符代表了语法的最小元素,是一种个体记号。非终结符号:也称语法变量,它代表语法实体或语法范畴;非终结符代表一个一定的语法概念,因此,一个非终结符是一个类、一个集合。注意:1、字母表可以称为文法中的终结符集2、非终结符不能是字母表中的字符跑肌伶漱挫衰杯槐趟嘲秤查涝俩仔涧律插筹鸟破渭疚爹埂钝旨微朴囚徽白编译原理(3)语法_1(文法和语言)编译原理(3)语法_1(文法和语言)、文法(定义)文法通常表示成四元组G[S] = (VT,VN,S,ξ):(4) ξ是产生式的非空有限集,其中每个产生式(或称规则)是一序偶(α,β),通常写作α → β或α ::= β读作“α产生β”、“α是β”或“α定义为β”。在此,α为产生式的左部,而β为产生式的右部,α、β是由终结符和非终结符组成的符号串,α∈(VT∪VN)+ 且至少有一个非终结符,而β∈(VT∪VN)*。论期仓丑斩轻伍励垦饮惧幢圣对观脾坎