编译原理文法和语言

《编译原理文法和语言》由会员分享，可在线阅读，更多相关《编译原理文法和语言（75页珍藏版）》请在装配图网上搜索。

1、编编 译译 原原 理理3.1 3.1 符号和符号串符号和符号串3.2 3.2 文法和语言的形式定义文法和语言的形式定义3.3 3.3 文法的分类文法的分类3.4 3.4 语法树和二义性语法树和二义性3.5 3.5 有关文法的实用限制有关文法的实用限制第三章第三章 文法和语言文法和语言语言的组成语言的组成语言：语言：句子的集合句子的集合句子：句子：多个单词按一定规则组成多个单词按一定规则组成单词：单词：多个字符按一定规则组成多个字符按一定规则组成程序设计程序设计语言语言编程语言编程语言程序的语句集合程序的语句集合语句：语句：多个单词按语法规则组成多个单词按语法规则组成单词：单词：多个字符按词法规

2、则组成多个字符按词法规则组成l程序设计语言和自然语言的组成结构程序设计语言和自然语言的组成结构l语言定义的方法语言定义的方法u枚举方法枚举方法 一个语言中的句子有限（非形式化描述）一个语言中的句子有限（非形式化描述）u形式化描述方法（文法）形式化描述方法（文法）一组数学符号（形式化描述）一组数学符号（形式化描述）产生语言中全部句子的有限个规则产生语言中全部句子的有限个规则u自动机方法自动机方法识别某字母表上所有符号串是否是该语言句子的一识别某字母表上所有符号串是否是该语言句子的一种装置（算法或过程）种装置（算法或过程）产生的观点产生的观点识别的观点识别的观点3.1 3.1 符号和符号串符号和符

3、号串一、字母表与符号一、字母表与符号1.1.字母表：字母表：元素的非空有限集合元素的非空有限集合 例：例：=aa，b b，cc =begin,end,if,then,elsebegin,end,if,then,else2.2.符号：符号：字母表中的元素字母表中的元素 例：例：a a，b b，c c begin,end,if,then,else begin,end,if,then,else3.1 3.1 符号和符号串符号和符号串字母表辨析：字母表辨析：例：例：1 1=aaaa，bbbb，cccc 2 2=a,a,b,ba,a,b,b 3 3=aa，b b，aa 4 4=解析：解析：1和和2是字是

4、字母表，体现了字母表，体现了字母表的整体性和母表的整体性和可辨认性；可辨认性；3中中有相同的符号；有相同的符号；4也不是字母表，也不是字母表，因为要求字母表因为要求字母表非空。非空。3.1 3.1 符号和符号串符号和符号串一、字母表与符号一、字母表与符号3.3.符号串：符号串：由字母表由字母表 中的符号组成的任何有穷序列中的符号组成的任何有穷序列 例：例：=a,b =a,b ,a,b,aa,ab,aabba ,a,b,aa,ab,aabba都都是是 上的符号串上的符号串 l符号串的长度：符号串的长度：符号串符号串x中符号的数目中符号的数目,|x|=ml空符号串：空符号串：无任何符号的符号串无任

5、何符号的符号串,记为记为,|=0 3.1 3.1 符号和符号串符号和符号串一、字母表与符号一、字母表与符号4.4.符号串的头和尾：符号串的头和尾：对于符号串对于符号串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 3.1 符号和符号串符号和符号串二、字符串和字符串集合的运算二、字符串和字符串集合的运算1.字符串的连接：字符串的连接：设设x

6、和和y是两个字符串，则是两个字符串，则xy被称被称 为符号串为符号串x与与y连接。连接。l x=x=xl (xy)z=x(yz)l|xy|=|x|+|y|例：例：x=ST，y=abu，则，则xy=STabu，可看出可看出|x|=2，|y|=3，|xy|=53.1 3.1 符号和符号串符号和符号串2.字符串字符串x的方幂：的方幂：即把即把x重复写重复写n次，记为次，记为z=xn。例：若例：若x=AB 则则:x0=x1=AB x2=ABAB x3=ABABAB xn=xxn-1=xn-1 x (n0)二、字符串和字符串集合的运算二、字符串和字符串集合的运算对于对于m,n0lxmxn=xm+nl(x

7、m)n=xmn3.1 3.1 符号和符号串符号和符号串3.字符串字符串A与与B的乘积：的乘积：设设A和和B为符号串集合，则为符号串集合，则 A与与B的乘积定义为的乘积定义为AB=xy|x A且且y B 例：若集合例：若集合A=ab,cde 集合集合B=0,1 则则 AB=ab0,ab1,cde0,cde1 二、字符串和字符串集合的运算二、字符串和字符串集合的运算3.1 3.1 符号和符号串符号和符号串4.字符串集合的正闭包：字符串集合的正闭包：设设为字母表，为字母表，则则+=12n，n1例：若例：若=0,1 则则+=0,1,00,01,10,11,000,001,二、字符串和字符串集合的运算二

8、、字符串和字符串集合的运算 注：指定字母表注：指定字母表后，可用后，可用n表示表示上所有长度上所有长度为为n的串的集合。的串的集合。3.1 3.1 符号和符号串符号和符号串5.字符串集合的闭包字符串集合的闭包(星闭包星闭包)：设设为字母表，为字母表，则则*=012n,n0l*可表示可表示上所有有穷长的串的集合；上所有有穷长的串的集合；l*=0+l+=*=*l*=+，+=*-例：若例：若=0,1,则则*=,0,1,00,01,10,11,二、字符串和字符串集合的运算二、字符串和字符串集合的运算l 若若A为某语言的基本字符集为某语言的基本字符集 Aa,b,z,0,1,9,+,_/,(,),=lB为

9、单词集为单词集 B=begin,end,if,then,则则B A*。l语言的句子是定义在语言的句子是定义在B上的符号串。上的符号串。l若令若令C为句子集合，则为句子集合，则C B*,程序程序 C 为什么对符号、符号串、符号串集合为什么对符号、符号串、符号串集合以及它们的运算感兴趣？以及它们的运算感兴趣？3.2 3.2 文法和语言的形式定义文法和语言的形式定义一、文法的直观理解一、文法的直观理解1.1.什么是文法什么是文法 文法是对语言结构的定义与描述，即从文法是对语言结构的定义与描述，即从形式上描述和规定语言结构，也称为语法形式上描述和规定语言结构，也称为语法。例：句子：例：句子：“我是大学

10、生我是大学生”。该句子的结构该句子的结构（称为语法结构）是由它的语法决定的（称为语法结构）是由它的语法决定的。如何定义该句子的语法结构呢？如何定义该句子的语法结构呢？语法规则语法规则一、文法的直观理解一、文法的直观理解2.2.语法规则语法规则 通过建立一组规则（产生式），来描述句通过建立一组规则（产生式），来描述句子的语法结构。子的语法结构。规定用规定用“:=:=”表示表示“由由组成组成”或或“定义定义为为”。:=:=:=:=|:=:=你你|我我|他他:=:=王民王民|大学生大学生|工人工人|英语英语:=:=:=:=是是|学习学习:=:=|3.2 3.2 文法和语言的形式定义文法和语言的形式定

11、义一、文法的直观理解一、文法的直观理解3.3.由产生式推导句子由产生式推导句子 推导方法：从一个要识别的符号开始推导，推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。每次仅用一条产生式去进行推导。3.2 3.2 文法和语言的形式定义文法和语言的形式定义 我我 我我 我我是是 我是我是 我是我是大学生大学生:=:=:=:=|:=:=你你|我我|他他:=:=王民王民|大学生大学生|工人工人|英语英语:=:=:=:=是是|学习学习:=:=|推导方法：推导方法：从一个要识别的符号从一个要识别的符号开始推

12、导，即用相应产生式的开始推导，即用相应产生式的右部右部来替代产生式的来替代产生式的左部左部，每，每次仅用一条产生式去进行推导。次仅用一条产生式去进行推导。例：例：给定给定一组语法规则，考察一个句子：一组语法规则，考察一个句子：“我是大学生我是大学生”的推导过程。的推导过程。一、文法的直观理解一、文法的直观理解4.4.语法树语法树我我 大学生大学生语法成分（在形式语法成分（在形式语言中又称语言中又称“非终非终结符结符”）单词符号（在形单词符号（在形式语言中又称式语言中又称“终结符号终结符号”)是是 3.2 3.2 文法和语言的形式定义文法和语言的形式定义二、文法的形式定义二、文法的形式定义 定义

13、定义:文法文法GS定义为一个四元组，定义为一个四元组，GS=（VN，VT，P，S）VN：非终结符号集：非终结符号集 VT：终结符号集：终结符号集 P：产生式或规则的集合：产生式或规则的集合 S：开始符号（识别符号）：开始符号（识别符号）,SVN其中其中:非终结符号：非终结符号：出现在出现在产生式的左部或右部产生式的左部或右部,且且能推出符号或符号串，能推出符号或符号串，用来表示语言的语法成用来表示语言的语法成分。分。终结符号：终结符号：不出现在不出现在产生式的左部产生式的左部,且不能推且不能推出符号或符号串，是组出符号或符号串，是组成语言的基本单位。成语言的基本单位。VTVN 是字母表是字母表

14、。产生式：产生式：产生式是一产生式是一个有序对个有序对(,),通常写为通常写为:或或；读作；读作“定义为定义为”。3.2 3.2 文法和语言的形式定义文法和语言的形式定义35页页二、文法的形式定义二、文法的形式定义例例 1 文法文法G=（VN，VT，P，S）VN=S VT=0,1 P=S0S1,S01 S为开始符号为开始符号或写成或写成 文法文法GS:S0S1 S01 给定一个给定一个 文法，实际只需文法，实际只需给出产生式集合，给出产生式集合，并指定识别符号并指定识别符号3.2 3.2 文法和语言的形式定义文法和语言的形式定义P=；00；11；99；S=；例例2 2：无符号整数的文法：无符号

15、整数的文法：G=（VN，VT，P，S）VN,VT =0,1,2,3,9 有些产生式具有有些产生式具有相同的左部，可以合相同的左部，可以合在一起。如在一起。如0|1|2|3|9 也可以写做：也可以写做：G:；0|1|2|90|1|2|9；例例2 2：无符号整数的文法：无符号整数的文法：三、推导和归约三、推导和归约3.2 3.2 文法和语言的形式定义文法和语言的形式定义 如如是文法是文法G的产生式，的产生式，和和V*,若有若有v,w满足：满足：v=,w=,其中其中 则称则称v直接推导直接推导到到w，也称，也称w直接归约直接归约到到v，记作记作 v w 1.1.直接推导直接推导/直接归约直接归约例例

16、1：文法：文法GS:S0S1，S01 若若v=0S1，w=0011,有直接推导有直接推导0S10011 三、推导和归约三、推导和归约3.2 3.2 文法和语言的形式定义文法和语言的形式定义 如如是文法是文法G的产生式，的产生式，和和V*,若有若有v,w满足：满足：v=,w=,其中其中 则称则称v直接推导直接推导到到w，也称，也称w直接归约直接归约到到v，记作记作 v w 1.1.直接推导直接推导/直接归约直接归约例例2：文法：文法GS:S0S1，S01 若若v=S，w=0S1,有直接推导有直接推导S0S1 三、推导和归约三、推导和归约3.2 3.2 文法和语言的形式定义文法和语言的形式定义 如

17、如是文法是文法G的产生式，的产生式，和和V*,若有若有v,w满足：满足：v=,w=,其中其中 则称则称v直接推导直接推导到到w，也称，也称w直接归约直接归约到到v，记作记作 v w 1.1.直接推导直接推导/直接归约直接归约例例3：文法：文法GS:S0S1，S01 若若v=0S1，w=00S11,有直接推导有直接推导0S100S11 三、推导和归约三、推导和归约3.2 3.2 文法和语言的形式定义文法和语言的形式定义 若存在直接推导序列若存在直接推导序列 v w0 w1.wn=w，(n0)+则记为则记为v w，称，称v推导出（产生）推导出（产生）w，或，或w归归 约到约到v。2.2.推导推导/

18、归约归约三、推导和归约三、推导和归约3.2 3.2 文法和语言的形式定义文法和语言的形式定义例例：GN：NND|D D0|1|2|3|4|5|6|7|8|9 NNDNDDND9N09D09109 2.2.推导推导/归约归约 若存在直接推导序列若存在直接推导序列 v w0 w1.wn=w，(n0)+则记为则记为v w，称，称v推导出（产生）推导出（产生）w，或，或w归归 约到约到v。说明：当符号串已没有非终结符号时，推导就说明：当符号串已没有非终结符号时，推导就 必须终止。因为终结符不可能出现在产必须终止。因为终结符不可能出现在产 生式左部，所以将在产生式左部出现的生式左部，所以将在产生式左部出

19、现的 符号称为非终结符号。符号称为非终结符号。三、推导和归约三、推导和归约3.2 3.2 文法和语言的形式定义文法和语言的形式定义 若存在直接推导序列若存在直接推导序列 v w0 w1.wn=w，(n0)+则记为则记为v w，称，称v推导出（产生）推导出（产生）w，或，或w归归 约到约到v。2.2.推导推导/归约归约 +*如果如果v w，或，或v w，则记作，则记作v w。三、推导和归约三、推导和归约3.2 3.2 文法和语言的形式定义文法和语言的形式定义例例：S 0S1 00S11 000S111 00001111 +则有则有S 00001111 *S 000011112.2.推导推导/归约

20、归约3.2 3.2 文法和语言的形式定义文法和语言的形式定义例：无符号整数的文法例：无符号整数的文法G:；0|1|2|90|1|2|9；如整数如整数10的推导过程：的推导过程：0 0 10四四、句型、句子和语言、句型、句子和语言3.2 3.2 文法和语言的形式定义文法和语言的形式定义1.1.句型句型 *有文法有文法GS，若，若S x，则称，则称x是文法是文法G的句型。的句型。2.2.句子句子 *对文法对文法GS，若，若S x，且且xVT*，则称，则称x是文是文法法G的句子。的句子。例：例：GS：S0S1，S01 S 0S1 00S11 000S111 00001111 G的句型的句型S,0S1

21、,00S11,000S111,00001111等等 G的句子的句子00001111,01等等四四、句型、句子和语言、句型、句子和语言3.2 3.2 文法和语言的形式定义文法和语言的形式定义3.3.语言语言例：例：GS：S0S1，S01 S 0S1 00S11 0n-1S1n-1 0n1n L(G)=0n1n|n1 文法文法G生成的语言记为生成的语言记为L(G)，它是文法，它是文法G的一切句子的集合的一切句子的集合:L(G)=x|S x，且，且x VT*四四、句型、句子和语言、句型、句子和语言3.2 3.2 文法和语言的形式定义文法和语言的形式定义4.4.等价文法等价文法例：例：GA：A0R，A

22、01，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，构

23、造文法。，构造文法。练练 习习G1S：SaBa，Bb|BbG2S：SaBa，Bb|bB3.3 3.3 文法的分类文法的分类 Chomsky对文法中的规则施加不同限制，对文法中的规则施加不同限制，将文法和语言分为四大类：将文法和语言分为四大类：l0型文法型文法 0型语言或短语结构语言型语言或短语结构语言l1型文法型文法 1型语言或上下文有关语言型语言或上下文有关语言l2型文法型文法 2型语言或上下文无关语言型语言或上下文无关语言l3型文法型文法3型语言或正则（正规）语言型语言或正则（正规）语言3.3 3.3 文法的分类文法的分类 对任一产生式对任一产生式，都有，都有(VNVT)*，且，且至少含有

24、一个非终结符，至少含有一个非终结符，(VNVT)*一、一、0型文法型文法(短语结构文法短语结构文法)说明：对产生式基本无限制说明：对产生式基本无限制例：文法例：文法G，其中，其中VN=A,B,S VT=0,1 P=S0AB 1B0 BSA|01 A1SB1 A0S0B 3.3 3.3 文法的分类文法的分类 对任一产生式对任一产生式，都有，都有|，仅仅仅仅 S除外除外二、二、1型文法型文法(上下文有关文法上下文有关文法)说明：说明：文法左部符号个数不超过右部符号的个数文法左部符号个数不超过右部符号的个数 1A212，其中，其中1,2,(VNVT)*，A VN3.3 3.3 文法的分类文法的分类

25、对任一产生式对任一产生式，都有，都有|，仅仅仅仅 S除外除外二、二、1型文法型文法(上下文有关文法上下文有关文法)说明：说明：文法左部符号个数不超过右部符号的个数文法左部符号个数不超过右部符号的个数例：文法例：文法GS：SCD AbbA CaCA BaaB CbCB BbbB ADaD BDbD AabD3.3 3.3 文法的分类文法的分类 对任一产生式对任一产生式，都有，都有VN，(VNVT)*三、三、2型文法型文法(上下文无关文法上下文无关文法)说明：说明：程序设计语言的文法是上下文无关的，如程序设计语言的文法是上下文无关的，如 C，Pascal例：文法例：文法GS：SaB|bA Aa|a

26、S|bAA Bb|bS|aBB3.3 3.3 文法的分类文法的分类 任一产生式任一产生式的形式都为的形式都为AaB或或Aa，其中其中AVN，BVN，aVT四、四、3型文法型文法(正规文法正规文法)说明：说明：通常用来描述单词结构，其中包括标识符、通常用来描述单词结构，其中包括标识符、常量、保留字、运算符、界符等。常量、保留字、运算符、界符等。例：文法例：文法GS：S0A|1B|0A0A|1B|0SB1B|1|0此处限定产生式形此处限定产生式形如如AaB或或Aa为为右线性右线性文法；若限文法；若限定为定为ABa或或Aa即为即为左线性文法左线性文法 l|l l|d|l|dd|d+|-|*|/|=|

27、=，|；|(|)|其中其中l表示表示az中的任何一英文字母，中的任何一英文字母，d表示表示09中的中的任一数字。任一数字。例：标识符等单词的定义的规则例：标识符等单词的定义的规则3.3 3.3 文法的分类文法的分类3.3 3.3 文法的分类文法的分类五、四种文法的关系五、四种文法的关系 由于四种文法是按照将产生式做进一步限制而定由于四种文法是按照将产生式做进一步限制而定义的，所以它们之间是义的，所以它们之间是逐级逐级“包含包含”的关系，由四种的关系，由四种文法产生的语言也是文法产生的语言也是逐级逐级“包含包含”的关系。的关系。即：即：3型语言类型语言类 2型语言类型语言类 1型语言类型语言类

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

29、10，1001，0101。练练 习习 ZU0|V1 UZ1|1 VZ0|0ZU 0Z1ZZU 0ZV 1ZV 1Z0ZU 0Z1U 01ZU 0Z1V 10ZV 1Z0U 01ZV 1Z0V 103.4 3.4 语法树和二义性语法树和二义性一、语法树的定义一、语法树的定义 设文法设文法G=(VN,VT,P,S)，若一棵树满足下列，若一棵树满足下列4个条个条件，则此树称作件，则此树称作G的语法树的语法树(推导树或分析树）：推导树或分析树）：l 每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号的一个符号l 根的标记是根的标记是Sl 如果结点如果结点n有标记有标记A,其直接子

30、孙结点从左到右的次其直接子孙结点从左到右的次序是序是n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak一定是一定是P中的一个产生中的一个产生式式l 树的叶结点符号从左至右恰好构成句型树的叶结点符号从左至右恰好构成句型3.4 3.4 语法树和二义性语法树和二义性一、语法树的定义一、语法树的定义 假设表达式文法：假设表达式文法：Eid|(E)|E*E|E+E 则句型则句型id的语法树的语法树句型句型(id)的语法树的语法树句型句型E*E+E的语法树的语法树EidEidE()*EEE+EE3.4 3.4 语法树和二义性语法树和二义性l语法树的画法语法树的画法 方

31、法方法：把开始符：把开始符号做为根结点，号做为根结点，对每一个直接推对每一个直接推导画一个分支，导画一个分支，分支的名字是直分支的名字是直接推导中被替换接推导中被替换的非终结符号，的非终结符号，直到再无分支可直到再无分支可画结束。画结束。例如：推导例如：推导S AB AcBd Accdd abccddSBBdbaAcdc3.4 3.4 语法树和二义性语法树和二义性l语法树的用途语法树的用途 用于描述句型和句子的语法结构。句型的用于描述句型和句子的语法结构。句型的推导过程对应于语法树的构造过程。推导过程对应于语法树的构造过程。例例:GS:SaAS|a ASbA|SS|ba构造句型构造句型aabb

32、aa的的语法树语法树 从左到右从左到右读出语法树的读出语法树的叶子标记叶子标记连接成的连接成的文文法符号串法符号串，为，为GS的的句型句型。SSaAASbaaba3.4 3.4 语法树和二义性语法树和二义性l语法树的用途语法树的用途问题：看不出推导过程中产生式被施用的顺序问题：看不出推导过程中产生式被施用的顺序例例:GS:SaAS|a ASbA|SS|ba构造句型构造句型aabbaa的的语法树语法树SSaAASbaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa3.4 3.4 语法树和二

33、义性语法树和二义性二、短语与句柄二、短语与句柄l对文法对文法GS，是文法的一个句型。如是文法的一个句型。如 果有果有SA且且A，则称，则称是句型是句型 相对于非终结符相对于非终结符A的的短语短语。l如有如有A，则称，则称是句型是句型相对于非相对于非 终结符终结符A 的的直接短语直接短语，也称，也称简单短语简单短语。l一个句型的最左直接短语称为该句型的一个句型的最左直接短语称为该句型的句句 柄柄。*P443.4 3.4 语法树和二义性语法树和二义性二、短语与句柄二、短语与句柄 子树的末端结点子树的末端结点从左到右排列形成的从左到右排列形成的符号串是相对于子树符号串是相对于子树根的短语。根的短语。

34、对文法对文法GS，是是文法的一个句型。如果文法的一个句型。如果有有SA且且A，则称，则称是句型是句型相对于非终相对于非终结符结符A的的短语短语。SSABbabSB例：对于文法例：对于文法GS：S AB A Aa|bB B a|Sb 求句型求句型baSb的全部短语、的全部短语、直接短语和句柄？直接短语和句柄？句型句型baSb的短语：的短语：a,ba,Sb,baSb*3.4 3.4 语法树和二义性语法树和二义性二、短语与句柄二、短语与句柄如有如有A，则称，则称是句是句型型相对于非终结符相对于非终结符A 的的直接短语直接短语，也称，也称简单简单短语短语。SSABbabSB例：对于文法例：对于文法GS

35、：S AB A Aa|bB B a|Sb 求句型求句型baSb的全部短语、的全部短语、直接短语和句柄？直接短语和句柄？句型句型baSb的直接短语：的直接短语：a,Sb 简单子树简单子树(只有只有父子两代父子两代)的末端结的末端结点形成的符号串是相点形成的符号串是相对于简单子树根的直对于简单子树根的直接短语。接短语。3.4 3.4 语法树和二义性语法树和二义性二、短语与句柄二、短语与句柄 一个句型的最左一个句型的最左直接短语称为该句型直接短语称为该句型的的句柄句柄。SSABbabSB例：对于文法例：对于文法GS：S AB A Aa|bB B a|Sb 求句型求句型baSb的全部短语、的全部短语、

36、直接短语和句柄？直接短语和句柄？句型句型baSb的句柄：的句柄：a 最左简单子树的最左简单子树的末端结点形成的符号末端结点形成的符号串是句柄。串是句柄。ETTGE：EE+T|T TT*F|F F(E)|i句型：句型：i*i+i短语：短语：直接短语：直接短语：句柄：句柄：TFFiii*+EF练练 习习i1i2i33.4 3.4 语法树和二义性语法树和二义性三、最左推导和最右推导三、最左推导和最右推导l 如果在推导的任何一步如果在推导的任何一步，其中，其中 、是句型，都是对是句型，都是对中的最左中的最左 （右）非终结符进行替换，则称为（右）非终结符进行替换，则称为最左最左 （右）推导（右）推导。l

37、在形式语言中，最右推导常被称作在形式语言中，最右推导常被称作规范规范 推导推导。由规范推导所得的句型称为。由规范推导所得的句型称为规范规范 句型句型。例：例：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 3.4 语法树和二义性语法树和二义性三、最左推导和最右推导三、最左推导和最右推导答：最右推导：答：最右推导：S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(

38、a,a)(S,(a,a)(a,(a,a)例：例：GS：Sa|(T)TT,S|S给出句子给出句子(a,(a,a)的最左、最右推导。的最左、最右推导。3.4 3.4 语法树和二义性语法树和二义性三、最左推导和最右推导三、最左推导和最右推导3.4 3.4 语法树和二义性语法树和二义性三、最左推导和最右推导三、最左推导和最右推导每一个句型是否都对应唯一的最左每一个句型是否都对应唯一的最左(最右最右)推推导导?例：例：GE:E i|E+E|E*E|(E)，写出句型，写出句型 i*i+i的最左推导。的最左推导。例：例：GE:E i|E+E|E*E|(E)，写出句型，写出句型 i*i+i的最左推导。的最左推

39、导。E E E+E E+E E E*E i E i i i i i E E E E*E E i E+E i E+E i 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 3.4 语法树和二义性语法树和二义性四、文法的二义性四、文法的二义性 若一个文法存在某个句子对应两棵不同若一个文法存在某个句子对应两棵不同的语法树，则称该句子是二义性的，如果一的语法树，则称该句子是二义性的，如果一个文法含有二义性的句子，则称这

40、个文法是个文法含有二义性的句子，则称这个文法是二义的。二义的。或者，若一个文法存在某个句子有两个或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二不同的最左（右）推导，则称这个文法是二义的。义的。3.4 3.4 语法树和二义性语法树和二义性四、文法的二义性四、文法的二义性 以上是以上是自顶向下自顶向下来看文法的二义性，我们还可以来看文法的二义性，我们还可以自底向上自底向上来看文法的二义性。语法的二义性意味着句来看文法的二义性。语法的二义性意味着句型的句柄不唯一。如句型型的句柄不唯一。如句型E+E*i。EEE+EE*iEEE*EE+i3.4 3.4 语法树和二义性语法树和二

41、义性四、文法的二义性四、文法的二义性例：例：条件语句的语法定义条件语句的语法定义 Sif E then S else S Sif E then S 考察句型考察句型if E1 then if E2 then S1 else S2Sif E1 then S else S2if E2 then S1Sif E1 then Sif E2 then S1 else S23.4 3.4 语法树和二义性语法树和二义性四、文法的二义性四、文法的二义性 若文法是二义性的，则在编译时就会产生不确定若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：性，遗憾的是在理论上已经证明：文法的二义性是

42、不文法的二义性是不可判定的可判定的，即不可能构造出一个算法，通过有限步骤，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。来判定任一文法是否有二义性。现在的解决办法是：提出一些现在的解决办法是：提出一些限制条件限制条件，称为无，称为无二义性的充分条件，当文法满足这些条件时，就可以二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。判定文法是无二义性的。E E E E*E E i E+E i E+E i i i i3.4 3.4 语法树和二义性语法树和二义性四、文法的二义性四、文法的二义性Sif E1 then Sif E2 then S1 else S2Sif

43、E1 then S else S2if E2 then S1 E E E+E E+E E E*E i E i i i i i文法文法GP：PPaP|PbP|cP|Pe|f证明文法证明文法G是二义性文法。是二义性文法。练练 习习句型句型fbfbfbPbPPbPPfffPbPPfbPPff3.5 3.5 有关文法的实用限制有关文法的实用限制l有害规则有害规则：形如：形如UU的产生式。会的产生式。会引起引起文文法的二义性，若有，则删去。法的二义性，若有，则删去。例如存在例如存在U:=U，U:=a|b,则有两棵语法树：则有两棵语法树：UaUUa3.5 3.5 有关文法的实用限制有关文法的实用限制l多余

44、规则多余规则：指文法中任何句子的推导都不会：指文法中任何句子的推导都不会用到的规则，若有，则删去。用到的规则，若有，则删去。u文法中某些文法中某些非终结符不在任何规则的右非终结符不在任何规则的右部出现部出现，该非终结符称为，该非终结符称为不可到达不可到达。u文法中某些文法中某些非终结符非终结符，由它，由它不能推出终不能推出终结符号串结符号串，该非终结符称，该非终结符称为为不可终止不可终止。3.5 3.5 有关文法的实用限制有关文法的实用限制 例例GS：1)SBe 2)BCe 3)BAf 4)AAe 5)Ae 6)CCf 7)Df推不出终结符号串，为多余规则推不出终结符号串，为多余规则推不出终结

45、符号串，为多余规则。推不出终结符号串，为多余规则。C为不可终止的非终结符。为不可终止的非终结符。非终结符号非终结符号D不在任何规则右部出现，为多不在任何规则右部出现，为多余规则。余规则。D为不可到达的非终结符。为不可到达的非终结符。3.5 3.5 有关文法的实用限制有关文法的实用限制l有关文法左递归的限制有关文法左递归的限制：即要求文法不：即要求文法不 含有含有UU或或UU的产生式。若有，的产生式。若有，则删去，因为含有左递归，则则删去，因为含有左递归，则不能用自不能用自 顶向下的方法来进行语法分析，会造成死顶向下的方法来进行语法分析，会造成死 循环。后面将详细介绍。循环。后面将详细介绍。+3

46、.5 3.5 有关文法的实用限制有关文法的实用限制l文法中不含有空规则文法中不含有空规则U：因为有的分因为有的分 析方法（算符优先分析法）中要求没有空析方法（算符优先分析法）中要求没有空 规则，规则，规则会使得有关文法的一些讨论规则会使得有关文法的一些讨论 和证明变得复杂。后面将详细介绍。和证明变得复杂。后面将详细介绍。例：对以下文法例：对以下文法G1S，构造一个与之等价的文，构造一个与之等价的文法法G2S，使，使G2S中的每一个非终结符均能导中的每一个非终结符均能导出一个终结符号串。出一个终结符号串。G1S：SBab|cC Bb|bS CDa DCb|CDa练练 习习解：因为从解：因为从C、

47、D均推导不出终结符号串，所以这两均推导不出终结符号串，所以这两条为多余规则，将其删去，所有含条为多余规则，将其删去，所有含C、D的规则的右的规则的右部也均应删去。部也均应删去。G2S：SBab Bb|bS小小 结结 本章出现的概念较多本章出现的概念较多,应重点理解文法应重点理解文法,推导推导,句句型，句子及语言的定义等概念型，句子及语言的定义等概念.文法作为程序语言的语法的描述工具文法作为程序语言的语法的描述工具,它用规则它用规则只能陈述的是只能陈述的是:语言的所有句子以什麽样的符号串能出语言的所有句子以什麽样的符号串能出现现.请记住文法和语言的形式定义中的请记住文法和语言的形式定义中的 形式形式 的含义的含义-只涉及语言的语法不涉及语言的语义只涉及语言的语法不涉及语言的语义.本章内容是形式语言理论的一部分本章内容是形式语言理论的一部分.形式语言理形式语言理论是对符号串集合的表示法、结构及其特性的研究。论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。是程序设计语言语法分析研究的基础。