编译原理文法和语言.ppt
《编译原理文法和语言.ppt》由会员分享,可在线阅读,更多相关《编译原理文法和语言.ppt(75页珍藏版)》请在三一文库上搜索。
1、编 译 原 理,3.1 符号和符号串 3.2 文法和语言的形式定义 3.3 文法的分类 3.4 语法树和二义性 3.5 有关文法的实用限制,第三章 文法和语言,程序设计语言和自然语言的组成结构,语言定义的方法,枚举方法 一个语言中的句子有限(非形式化描述) 形式化描述方法(文法) 一组数学符号(形式化描述) 产生语言中全部句子的有限个规则 自动机方法 识别某字母表上所有符号串是否是该语言句子的一种装置(算法或过程),产生的观点,识别的观点,3.1 符号和符号串,一、字母表与符号,1.字母表:元素的非空有限集合 例:=a,b,c =begin,end,if,then,else 2.符号:字母表中
2、的元素 例: a,b,c begin,end,if,then,else,3.1 符号和符号串,字母表辨析: 例:1=aa,bb,cc 2=a ,a,b ,b 3=a,b,a 4= ,解析:1和2是字母表,体现了字母表的整体性和可辨认性;3中有相同的符号;4也不是字母表,因为要求字母表非空。,3.1 符号和符号串,一、字母表与符号,3.符号串:由字母表中的符号组成的任何有穷序列 例: =a,b ,a,b,aa,ab,aabba都是上的符号串,符号串的长度:符号串x中符号的数目,|x|=m 空符号串:无任何符号的符号串,记为,|=0,3.1 符号和符号串,一、字母表与符号,4.符号串的头和尾:对于
3、符号串z=xy,x是z的头,y是z的尾。如果x非空,那么y是固有尾;如果y非空,那么x是固有头。,例:设z=abc, z的头是,a,ab,abc, 固有头是,a,ab; z的尾是,c,bc,abc, 固有尾是,c,bc。,3.1 符号和符号串,二、字符串和字符串集合的运算,1. 字符串的连接:设x和y是两个字符串,则xy被称 为符号串x与y连接。 x=x=x (xy)z=x(yz) |xy|=|x|+|y|,例:x=ST,y=abu,则xy=STabu, 可看出|x|=2,|y|=3,|xy|=5,3.1 符号和符号串,2. 字符串x的方幂:即把x重复写n次,记为z=xn。,例:若x=AB 则
4、: x0 = x1 =AB x2 = ABAB x3 = ABABAB xn = xxn-1 = xn-1 x (n0),二、字符串和字符串集合的运算,对于m,n0 xmxn=xm+n (xm)n=xmn,3.1 符号和符号串,3. 字符串A与B的乘积:设A和B为符号串集合,则 A与B的乘积定义为AB =xy|xA且yB,例:若集合A=ab,cde 集合B = 0,1 则 AB =ab0,ab1,cde0,cde1,二、字符串和字符串集合的运算,3.1 符号和符号串,4. 字符串集合的正闭包:设为字母表, 则 += 12n,n1,例:若=0, 1 则 +=0,1,00,01,10,11,000
5、,001,二、字符串和字符串集合的运算,注:指定字母表后,可用n表示上所有长度为n的串的集合。,3.1 符号和符号串,5. 字符串集合的闭包(星闭包):设为字母表, 则 *=012n,n0,*可表示上所有有穷长的串的集合; *=0+ +=*=* *= +, += *-,例:若=0, 1,则*=,0,1,00,01,10,11, ,二、字符串和字符串集合的运算,若A为某语言的基本字符集 Aa,b,z,0,1,9, +,_/, ( , ), = B为单词集 B =begin, end, if, then, , 则B A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合,则C B * , 程
6、序 C,为什么对符号、符号串、符号串集合以及它们的运算感兴趣?,3.2 文法和语言的形式定义,一、文法的直观理解,1.什么是文法 文法是对语言结构的定义与描述,即从形式上描述和规定语言结构,也称为语法 。,例:句子:“我是大学生” 。该句子的结构(称为语法结构)是由它的语法决定的 。 如何定义该句子的语法结构呢? 语法规则,一、文法的直观理解,2.语法规则 通过建立一组规则(产生式),来描述句子的语法结构。 规定用“:=”表示“由组成”或“定义为”。,:= :=| :=你|我|他 := 王民|大学生|工人|英语 := :=是|学习 :=|,3.2 文法和语言的形式定义,一、文法的直观理解,3.
7、由产生式推导句子 推导方法:从一个要识别的符号开始推导,即用相应产生式的右部来替代产生式的左部,每次仅用一条产生式去进行推导。,3.2 文法和语言的形式定义, , ,我,我,我是,我是,我是大学生,:= :=| :=你|我|他 := 王民|大学生|工人|英语 := :=是|学习 :=|,推导方法:从一个要识别的符号 开始推导,即用相应产生式的 右部来替代产生式的左部,每 次仅用一条产生式去进行推导。,例:给定一组语法规则,考察一个句子:“我是大学生”的推导过程。,一、文法的直观理解,4.语法树,我,大学生,语法成分(在形式 语言中又称“非终 结符”),单词符号(在形 式语言中又称 “终结符号”
8、),是,3.2 文法和语言的形式定义,二、文法的形式定义,定义: 文法GS定义为一个四元组, GS=(VN,VT,P,S) VN :非终结符号集 VT :终结符号集 P:产生式或规则的集合 S:开始符号(识别符号) , SVN,其中: 非终结符号:出现在产生式的左部或右部,且能推出符号或符号串,用来表示语言的语法成分。 终结符号:不出现在产生式的左部,且不能推出符号或符号串,是组成语言的基本单位。VTVN 是字母表。 产生式:产生式是一个有序对(, ), 通常写为: : 或;读作“定义为”。,3.2 文法和语言的形式定义,35页,二、文法的形式定义,例 1 文法G=(VN,VT,P,S) VN
9、 = S VT = 0, 1 P= S0S1, S01 S为开始符号,或写成 文法GS: S0S1 S01,给定一个 文法,实际只需给出产生式集合,并指定识别符号,3.2 文法和语言的形式定义,P = ; ; ; 0; 1; 9; S = ;,例2:无符号整数的文法: G=(VN,VT,P,S) VN, VT = 0,1,2,3,9,有些产生式具有相同的左部,可以合在一起。如 0|1|2|3|9,也可以写做: G: ; ; ; 0|1|2|9;,例2:无符号整数的文法:,三、推导和归约,3.2 文法和语言的形式定义,如是文法G的产生式,和V*, 若有v,w满足:v=,w= , 其中 则称v直接
10、推导到w,也称w直接归约到v,记作 v w,1.直接推导/直接归约,例1:文法GS: S0S1, S01 若v=0S1,w=0011, 有直接推导0S10011,三、推导和归约,3.2 文法和语言的形式定义,如是文法G的产生式,和V*, 若有v,w满足:v=,w= , 其中 则称v直接推导到w,也称w直接归约到v,记作 v w,1.直接推导/直接归约,例2:文法GS: S0S1, S01 若v=S,w=0S1, 有直接推导S0S1,三、推导和归约,3.2 文法和语言的形式定义,如是文法G的产生式,和V*, 若有v,w满足:v=,w= , 其中 则称v直接推导到w,也称w直接归约到v,记作 v
11、w,1.直接推导/直接归约,例3:文法GS: S0S1, S01 若v=0S1,w=00S11, 有直接推导0S100S11,三、推导和归约,3.2 文法和语言的形式定义,若存在直接推导序列 v w0 w1 . wn=w,(n0) + 则记为v w,称v推导出(产生)w,或w归 约到v。,2. 推导/归约,三、推导和归约,3.2 文法和语言的形式定义,例: GN: NND|D D0|1|2|3|4|5|6|7|8|9 NNDNDDND9N09D09109,2. 推导/归约,若存在直接推导序列 v w0 w1 . wn=w,(n0) + 则记为v w,称v推导出(产生)w,或w归 约到v。,说明
12、:当符号串已没有非终结符号时,推导就 必须终止。因为终结符不可能出现在产 生式左部,所以将在产生式左部出现的 符号称为非终结符号。,三、推导和归约,3.2 文法和语言的形式定义,若存在直接推导序列 v w0 w1 . wn=w,(n0) + 则记为v w,称v推导出(产生)w,或w归 约到v。,2. 推导/归约,+ * 如果v w,或v w,则记作v w 。,三、推导和归约,3.2 文法和语言的形式定义,例: S 0S1 00S11 000S111 00001111 + 则有S 00001111 * S 00001111,2. 推导/归约,3.2 文法和语言的形式定义,例:无符号整数的文法 G
13、: ; ; ; 0|1|2|9;,如整数10的推导过程: 0 0 10,四 、句型、句子和语言,3.2 文法和语言的形式定义,1. 句型,* 有文法GS,若S x,则称x是文法G的句型。,例:GS: S0S1, S01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111等 G的句子00001111, 01等,四 、句型、句子和语言,3.2 文法和语言的形式定义,3. 语言,例:GS: S0S1, S01 S 0S1 00S11 0n-1S1n-1 0n1n L(G)=0n1n|n1,四 、句型、句子和语言,3.2 文法
14、和语言的形式定义,4. 等价文法,例:GA: A0R, A01,R A1 A 0R 0A1 00R1 00A11 0n1n 故GA和GS所产生的语言是相同的, GA和GS是等价文法。,G和G是两个不同的文法,若 L(G) = L(G) , 则G和G为等价文法。,给定文法GA: AbA|cc,下面的符号串中,为该文法句子的是: cc bcbc bcbcc bccbcc bbbcc,练 习,注意: 已知文法求语言,通过推导; 已知语言构造文法,全凭经验。,已知句子L(G)=abna|n1,构造文法。,练 习,G1S: SaBa, Bb|Bb G2S: SaBa, Bb|bB,3.3 文法的分类,C
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 文法 语言
链接地址:https://www.31doc.com/p-2258591.html