编译原理文法和语言.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

15、homsky对文法中的规则施加不同限制，将文法和语言分为四大类： 0型文法 0型语言或短语结构语言 1型文法 1型语言或上下文有关语言 2型文法 2型语言或上下文无关语言 3型文法3型语言或正则（正规）语言,3.3 文法的分类,对任一产生式，都有(VNVT)*，且至少含有一个非终结符， (VNVT)*,一、0型文法(短语结构文法),说明：对产生式基本无限制,例：文法G，其中VN=A,B,S VT=0,1 P= S0AB 1B0 BSA|01 A1SB1 A0S0B ,3.3 文法的分类,对任一产生式，都有|， 仅仅 S除外,二、1型文法(上下文有关文法),说明：文法左部符号个数不超过右部符号的

16、个数,1A212，其中1,2, ( VNVT )*，A VN,3.3 文法的分类,对任一产生式，都有|， 仅仅 S除外,二、1型文法(上下文有关文法),说明：文法左部符号个数不超过右部符号的个数,例：文法GS： SCD AbbA CaCA BaaB CbCB BbbB ADaD BDbD AabD,3.3 文法的分类,对任一产生式，都有VN ， (VNVT)*,三、2型文法(上下文无关文法),说明：程序设计语言的文法是上下文无关的，如 C，Pascal,例：文法GS： SaB|bA Aa|aS|bAA Bb|bS|aBB,3.3 文法的分类,任一产生式的形式都为AaB或Aa，其中AVN ，BV

17、N ，aVT,四、3型文法(正规文法),说明： 通常用来描述单词结构，其中包括标识符、常量、保留字、运算符、界符等。,例：文法GS： S0A|1B|0 A0A|1B|0S B1B|1|0,此处限定产生式形如AaB或Aa为右线性文法；若限定为ABa或Aa即为左线性文法,l|l l|d|l|dd|d+|-|*|/|=|=，|；|(|)|其中l表示az中的任何一英文字母，d表示09中的任一数字。,例：标识符等单词的定义的规则,3.3 文法的分类,3.3 文法的分类,五、四种文法的关系,由于四种文法是按照将产生式做进一步限制而定义的，所以它们之间是逐级“包含”的关系，由四种文法产生的语言也是逐级“包含

18、”的关系。 即： 3型语言类 2型语言类 1型语言类 0型语言类,1：已知文法GP： PaPQR|abR RQQR bQbb bRbc cRcc 它是Chomsky哪一型文法？,答：由于G的每一个产生式都满足| ， 故该文法是1型文法。,练 习,2：已知文法GZ： ZU0|V1 UZ1|1 VZ0|0 它是Chomsky哪一型文法？并写出全部由此文法描述的只含有四个符号的句子。,答：该文法是3型文法。由此文法描述的只含有四 个符号的句子是：1010，0110，1001，0101。,练 习,ZU0|V1 UZ1|1 VZ0|0,Z,U,0,Z,1,Z,Z,V,1,Z,V,1,Z,0,Z,U,0,

19、Z,1,U,0,1,Z,U,0,Z,1,V,1,0,Z,V,1,Z,0,U,0,1,Z,V,1,Z,0,V,1,0,3.4 语法树和二义性,一、语法树的定义,设文法G=( VN,VT,P,S) ，若一棵树满足下列4个条件，则此树称作G的语法树(推导树或分析树）： 每个结点都有一个标记，此标记是V的一个符号 根的标记是S 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式 树的叶结点符号从左至右恰好构成句型,3.4 语法树和二义性,一、语法树的定义,假设表达式文法：Eid|(E)|E*E|E+E 则句型id

20、的语法树 句型(id)的语法树 句型E*E+E的语法树,3.4 语法树和二义性,语法树的画法,方法：把开始符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。,例如：推导 S AB AcBd Accdd abccdd,3.4 语法树和二义性,语法树的用途,用于描述句型和句子的语法结构。句型的推导过程对应于语法树的构造过程。,例: GS:SaAS|a ASbA|SS|ba 构造句型aabbaa的语法树,从左到右读出语法树的叶子标记连接成的文法符号串，为GS的句型。,3.4 语法树和二义性,语法树的用途,问题：看不出推导过程中产生式被施用的顺

21、序,例: GS:SaAS|a ASbA|SS|ba 构造句型aabbaa的语法树,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,3.4 语法树和二义性,二、短语与句柄,对文法GS，是文法的一个句型。如 果有SA且A，则称是句型 相对于非终结符A的短语。 如有A，则称是句型相对于非 终结符A 的直接短语，也称简单短语。 一个句型的最左直接短语称为该句型的句 柄。,*,*,P44,3.4 语法树和二义性,二、短语与句柄,子树的末端结点从左到右排列形成的符号串是相对于子树根的短语。,对文法G

22、S，是文法的一个句型。如果有SA且A，则称是句型相对于非终结符A的短语。,例：对于文法GS：S AB A Aa|bB B a|Sb 求句型baSb的全部短语、 直接短语和句柄？,句型baSb的短语：a,ba,Sb,baSb,*,*,3.4 语法树和二义性,二、短语与句柄,如有A，则称是句型相对于非终结符A 的直接短语，也称简单短语。,例：对于文法GS：S AB A Aa|bB B a|Sb 求句型baSb的全部短语、 直接短语和句柄？,句型baSb的直接短语：a, Sb,简单子树(只有父子两代)的末端结点形成的符号串是相对于简单子树根的直接短语。,3.4 语法树和二义性,二、短语与句柄,一个句

23、型的最左直接短语称为该句型的句柄。,例：对于文法GS：S AB A Aa|bB B a|Sb 求句型baSb的全部短语、 直接短语和句柄？,句型baSb的句柄：a,最左简单子树的末端结点形成的符号串是句柄。,E,T,T,GE：EE+T|T TT*F|F F(E)|i 句型：i*i+i 短语： 直接短语： 句柄：,T,F,F,i,i,i,*,+,E,F,练 习,i1,i2,i3,3.4 语法树和二义性,三、最左推导和最右推导,如果在推导的任何一步，其中 、是句型，都是对中的最左 （右）非终结符进行替换，则称为最左 （右）推导。 在形式语言中，最右推导常被称作规范 推导。由规范推导所得的句型称为规

24、范 句型。,例：GS：Sa|(T) TT,S|S 给出句子(a,(a,a)的最左、最右推导。,答：最左推导： S(T)(T,S)(S,S)(a,S)(a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a),3.4 语法树和二义性,三、最左推导和最右推导,答：最右推导： S(T) (T,S) (T,(T) (T,(T,S) (T,(T,a) (T,(S,a) (T,(a,a) (S,(a,a) (a,(a,a),例：GS：Sa|(T) TT,S|S 给出句子(a,(a,a)的最左、最右推导。,3.4 语法树和二义性,三、最左推导和最右推导,3.4 语法树和二义性,三、

25、最左推导和最右推导,每一个句型是否都对应唯一的最左(最右)推导?,例：GE: E i|E+E|E*E|(E)，写出句型 i*i+i的最左推导。,例：GE: E i|E+E|E*E|(E)，写出句型 i*i+i的最左推导。,推导1：E E+E E*E+E i*E+E i*i+E i*i+i 推导2：E E*E i*E i*E+E i*i+E i*i+i,每一个句型是否都对应唯一的最左(最右)推导?,3.4 语法树和二义性,四、文法的二义性,若一个文法存在某个句子对应两棵不同的语法树，则称该句子是二义性的，如果一个文法含有二义性的句子，则称这个文法是二义的。 或者，若一个文法存在某个句子有两个不同

26、的最左（右）推导，则称这个文法是二义的。,3.4 语法树和二义性,四、文法的二义性,以上是自顶向下来看文法的二义性，我们还可以自底向上来看文法的二义性。语法的二义性意味着句型的句柄不唯一。如句型E+E*i。,3.4 语法树和二义性,四、文法的二义性,例：条件语句的语法定义 Sif E then S else S Sif E then S 考察句型if E1 then if E2 then S1 else S2,3.4 语法树和二义性,四、文法的二义性,若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一

27、文法是否有二义性。 现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。,3.4 语法树和二义性,四、文法的二义性,文法GP： PPaP|PbP|cP|Pe|f 证明文法G是二义性文法。,练 习,句型fbfbfb,3.5 有关文法的实用限制,有害规则：形如UU的产生式。会引起文法的二义性，若有，则删去。,3.5 有关文法的实用限制,多余规则：指文法中任何句子的推导都不会用到的规则，若有，则删去。,文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。 文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。,3.

28、5 有关文法的实用限制,例GS ： 1) SBe 2) BCe 3) BAf 4) AAe 5) Ae 6) CCf 7) Df,3.5 有关文法的实用限制,3.5 有关文法的实用限制,文法中不含有空规则U ：因为有的分 析方法（算符优先分析法）中要求没有空 规则，规则会使得有关文法的一些讨论 和证明变得复杂。后面将详细介绍。,例：对以下文法G1S，构造一个与之等价的文法G2S，使G2S中的每一个非终结符均能导出一个终结符号串。 G1S：SBab|cC Bb|bS CDa DCb|CDa,练 习,解：因为从C、D均推导不出终结符号串，所以这两条为多余规则，将其删去，所有含C、D的规则的右部也均应删去。,G2S：SBab Bb|bS,小 结, 本章出现的概念较多,应重点理解文法,推导,句型，句子及语言的定义等概念. 文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的 形式的含义-只涉及语言的语法不涉及语言的语义. 本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,