编译原理语法1(文法和语言).ppt
《编译原理语法1(文法和语言).ppt》由会员分享,可在线阅读,更多相关《编译原理语法1(文法和语言).ppt(37页珍藏版)》请在三一文库上搜索。
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、文法 (定义) 文法通常表示成四元组GS = (VT,
4、VN,S,): (1) VT为终结符号集,这是一个非空有限集,它的每个元素称为终结符号。 (2) VN为非终结符号集,它也是一个非空有限集,其每个元素称为非终结符号,且有VTVN = ; (3) S为文法开始符,是一个特殊的非终结符号,即SVN;,3.1 文法和语言,3.1.1 文法和语言的基本概念 2、文法(文法中的基本概念) 终结符号:是指语言不可再分的基本符号,通常是一个语言的字母表;终结符代表了语法的最小元素,是一种个体记号。 非终结符号:也称语法变量,它代表语法实体或语法范畴;非终结符代表一个一定的语法概念,因此,一个非终结符是一个类、一个集合。,注意: 1、字母表可以称为文法中的终
5、结符集 2、非终结符不能是字母表中的字符,3.1 文法和语言,3.1.1 文法和语言的基本概念 2、文法 (定义) 文法通常表示成四元组GS = (VT,VN,S,): (4) 是产生式的非空有限集,其中每个产生式(或称规则)是一序偶(,),通常写作 或 := 读作“产生”、 “是”或“定义为”。在此,为产生式的左部,而为产生式的右部,、是由终结符和非终结符组成的符号串,(VTVN) + 且至少有一个非终结符,而(VTVN) *。,3.1 文法和语言,3.1.1 文法和语言的基本概念 2、文法(文法中的基本概念) 文法开始符号S:是一个特殊的非终结符,它代表文法所定义的语言中我们最终感兴趣的语
6、法实体,即语言的目标,而其它语法实体只是构造语言目标的中间变量 产生式: (也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。,P1 P2 Pn,如果:,P 1 | 2 | | n,其中,每个i(i=1, 2, , n)称为P的一个候选式,直竖“ | ”读为“或”,它与“”一样是用来描述文法的元语言符号(即不属于的字符)。,3.1 文法和语言,例如,定义一个仅包含加和乘运算的表达式的文法GE: GS = (VT,VN,S,): VT =+ * ( ) i VN = E, T, F S = E 为以下产生式的集合: EE + T | T TT * F | F
7、F (E)|i 两种文法都可以识别包含加和乘运算的表达式,它们的区别将在后面的课程中讲解,VT =+ * ( ) i VN = E S = E : Ei| E+E| E*E |(E),3.1 文法和语言,3.1.1 文法和语言的基本概念 关于文法表示的约定: 在此后的讨论中,用大写字母A、B、S、E等表示非终结符,用小写字母a、b、i、j等表示终结符,并用希腊字母等表示文法符号串,即、等均属于(VTVN)*。,2.3 正规表达式与优先自动机简介,例3.1 试构造产生标识符的文法。 解答 首先,标识符是以字母开头的字母数字串, 用L表示“字母”类非终结符, 用D表示“数字”类非终结符,,T L
8、| D (单个的字母或数字字符),S T | ST (字母或数字串),其次,如果用S表示“字母数字串”类,则T是一字母或数字,ST也是字母数字串,即有,L a | b | | z D 0 | 1 | | 9,而用T表示“字母或数字”类非终结符,则有:,其中,产生式ST | ST是一种左递归形式,由它可以产生一串T,课本例题,最后,作为“标识符”的非终结符I,它或者是一单个字母,或者为一字母后跟字母数字串,即 I L | LS,因此,产生标识符的文法GI为: GI = ( VT, VN, I,): = (a, b, , z, 0, , 9, I, S, T, L, D, I, ) : I L |
9、 LS S T | ST T L | D L a | b | | z D 0 | 1 | | 9,课本例题,解答 根据题意,我们可以将奇数划分为如图3-1所示的三个部分,即最高位允许出现19,用非终结符B表示;中间部分可以出现任意多位数字09,每一位用非终结符D表示;最低位只允许出现1、3、5、7、9等奇数,用A表示。,例3.2 写一文法,使其语言是奇数集合,但不允许出现以0打头的奇数。,课本例题,图3-1 奇数划分示意,课本例题,GN = (0, 1, , 9, N, A, M, B, D, N, ) : NA | MA /*一位数字 | 多位数字*/ MB | MD /*仅两位数字(无中间
10、位) | 多于两位数字*/ A1 | 3 | 5 | 7 | 9 B1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 D0 | B,由于中间部分可出现任意位,所以另引入了一个非终结符M,它包括最高位和中间位部分。假定开始符为N,则可得到文法GN为,课本例题,3.1 文法和语言,3.1.1 文法和语言的基本概念 3、文法产生的语言 设文法GS = (VT, VN, S, ),且、(VTVN)*,如果存在产生式A (VTVN)*),则称A可直接推出,即 其中 “=”表示直接推导,是应用产生规则进行推导的记号,这里仅使用一次规则 注意“=”与“”不同,“”是产生式中的定义记号。直接
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 语法 文法 语言
链接地址:https://www.31doc.com/p-2258611.html