短语、直接短语和句柄课件

1、2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄短语短语 令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 则称 是相对于非终结符A的, 句型的短语。SA*+且 A 短语、直接短语和句柄2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄则称是直接短语。 直接短语直接短语 SA*且 A 令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 短语、直接短语和句柄2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄 注意：短语和直接短语的区别在于第二个条件, 直接短语中的第二个条件表示有文法规则 A ，因此，每个直接短语都是某规则右部。 短语、直接短

2、语和句柄2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄句柄句柄 一个句型的最左直接短语称为该句型的句柄。句柄特征： (1) 它是直接短语，即某规则右部。 (2) 它具有最左性。短语、直接短语和句柄2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄 注意: 短语、直接短语和句柄都是针对某一句型的，都是指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。 短语、直接短语和句柄2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄 例如 设有文法GS=(S,A,B,a,b,P,S) 其中P为： 求句型 baSb的全部短语、直接短语和句柄。 S

3、ABAAa | bBBa | Sb短语、直接短语和句柄2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄对文法，首先建立该句型的推导过程： 最左推导:最右推导:SABAAa | bBBa | SbSAB ASbbBSbbaSbSAB baBbaSbbBB 分析 根据短语定义，可以从句型的推导过程 中找出其全部短语、直接短语和句柄。 句型 baSb短语、直接短语和句柄2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄句型baSb中的子串Sb，是(相对于非终结符B)句型baSb的短语，且为直接短语。 SAB bBBbaBbaSb(2) SbaB*B Sb (1) SS*S baSb +

4、句型本身是(相对于非终结符S)句型baSb的短语。 根据最左推导: S A*+ A 短语、直接短语和句柄2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄句型baSb中的子串a，是(相对于非终结符B)句型baSb的短语，且为直接短语、句柄。 句型baSb中的子串ba，是(相对于非终结符A)句型baSb的短语。 B a(3) SbBSb*根据最右推导:SAB ASb bBSbbaSb(4) SASb*A ba+S A*+ A 短语、直接短语和句柄2.5 2.5 语法树与文法的二义性语法树与文法的二义性 推导和语法树推导和语法树 1. 语法树语法树 对句型的推导过程给出一种图形表示, 这种表

5、示称为语法树，也称推导树。 短语、直接短语和句柄 2.5.1 2.5.1 推导和语法树推导和语法树例如 设有文法GE:构造句型i*i+i的语法树。首先给出句型的推导过程 (最左推导) ：EE+T | ET | TTT*F | T/F | FF(E) | iEE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+i短语、直接短语和句柄2.5.1 2.5.1 推导和语法树推导和语法树根据推导过程构造句型i*i+i的语法树如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+T ii*i+Tii*i+FFi*i+ii短语、直接短语和句柄2.5.1 2.5.1 推导和语法

6、树推导和语法树 由例可知，语法树的构造过程是从文法的开始符号出发，构造一个推导的过程。 因为文法的每一个句型 (句子) 都存在一 个推导，所以文法的每个句型(句子) 都存在一棵对应的语法树。短语、直接短语和句柄EE+T E+F E+i T+i T*F+i T*i+i F*i+i i*i+i2.5.1 2.5.1 推导和语法树推导和语法树 对句型i*i+i，还可给出最右推导： EE+TTT*FFiiFi短语、直接短语和句柄2.5.1 2.5.1 推导和语法树推导和语法树 这也就是说，一棵语法树表示了 一个句型的种种可能的(但未必是所 有的)不同推导过程, 包括最左(最右) 推导。短语、直接短语和

7、句柄3.5.1 3.5.1 推导和语法树推导和语法树 2. 子树语法树的子树是由某一结点连同所有分枝组成的部分。EE+TTT*FFiiFi短语、直接短语和句柄3.5.1 3.5.1 推导和语法树推导和语法树 3. 简单子树 语法树的简单子树是指只有单层分枝的子树。EE+TTT*FFiiFi短语、直接短语和句柄2.5.1 2.5.1 推导和语法树推导和语法树 句型的短语、直接短语和句柄的直观解释是： 短语：子树的末端结点形成的符号串是 相对于子树根的短语。 直接短语：简单子树的末端结点形成的 符号串是相对于简单子树根的直接短语。 句柄：最左简单子树的末端结点形成的 符号串是句柄。短语、直接短语和

8、句柄2.5.1 2.5.1 推导和语法树推导和语法树EE+TTT*FFiiFi短语:ni*i+ini*in第一个in第二个in第三个in三个i都是直接短语n第一个i是句柄注意:i+i不是句型的短语句子 i*i+i短语、直接短语和句柄2.5.1 2.5.1 推导和语法树推导和语法树 前例 对文法GS=(S,A,B,a,b,P,S)其中P为： 可用语法树非常直观地求出句型baSb的全部短语，直接短语和句柄。SABAAa | bBBa | Sb短语、直接短语和句柄2.5.1 2.5.1 推导和语法树推导和语法树 分析 首先根据句型baSb的推导过程画出对 应的语法树如下： Sb 为句型的相对于B的短

9、语、直接短语baSb 为句型的相对于S的短语ba 为句型的相对于A的短语a 句型的相对于B的短语、直接短语和句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbB Sba由语法树可知短语、直接短语和句柄2.5.2 2.5.2 文法的二义性文法的二义性从前面的讨论可以看出，对于文法G中 任一句型的推导序列, 我们总能为它构造 一棵语法树，现在我们提出一个问题： 文法的某个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左(最右)推导呢？ 短语、直接短语和句柄2.5.2 2.5.2 文法的二义性文法的二义性 例如 设有文法GE： 句子 i*i+i 有两个不同的最左推导

10、，对应两棵不同的语法树。E E+E | E*E | (E) | i短语、直接短语和句柄2.5.2 2.5.2 文法的二义性文法的二义性 最左推导1 EE+EE*E+E i*E+Ei*i+E i*i+i 最左推导2 EE*Ei*E i*E+Ei*i+E i*i+i EE*EE+EiiiEE+EE*Eiii短语、直接短语和句柄2.5.2 2.5.2 文法的二义性文法的二义性 如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。 或者说，若一个文法中存在某个句子，它有两个不同的最左 (最右) 推导，则这个文法是二义性的。 E E+E | E*E | (E) | i短语、直接短语和句

11、柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除 1. 不改变文法中原有的语法规则, 仅加进一些非形式的语法规定。 EE+EE*Eiii短语、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除2. 构造一个等价的无二义性文法。即 把排除二义性的规则合并到原有文法中, 改写原有的文法。例如，对于上例文法GE，将运算符的 优先顺序和结合规则：*优先于; 、* 左结合加到原有文法中, 可构造出无二义 性文法如下 ：短语、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除则句子i*i+i只有唯一一棵语法树：EE+T | TTT*F | FF(E) |

12、iEE+TTT*FFiiFi短语、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除 例2 定义某程序语言条件语句的文法G为: 试证明该文法是二义性的并消除之。 分析 该文法的句子 if b if b A else A 对应下面两棵不同的语法树： Sif b S | if b S else S | A (其它语句）短语、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除 所以该文法是二义的。 SifbSbSSifAelseASbSSifAelseAifbSSif b S | if b S else S | A句子 if b if b A else A短语

13、、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除 消除文法的二义性可采用下面两种方法： 1. 不改变已有规则，仅加进一非形式的语法规定：else与前面最接近的不带else的 if 相对。SifbSbSSifAelseA文法G的句子 if b if b A else A只对应唯一的一棵语法树，消除了二义性。短语、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除2. 改写文法G为GS S1 | S2 S1 if b S1 else S1 | A S2 if b S | if b S1 else S2 G:Sif b S | if b S else S

14、| A (其它语句）G:短语、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除 这是因为通过分析，得知引起二义性的原因是: ifelse 语句的 if 后可以是if型，因此改写文法时规定:if else之间只能是ifelse语句或其他语句。短语、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除S S1 | S2 S1 if b S1 else S1 | A S2 if b S | if b S1 else S2 ifbSbifAelseASS2S1S1S1对改写后的文法，句子 if b if b A else A 只对应唯一的一棵语法树。短语、直接短

15、语和句柄通常我们只说文法的二义性, 而不说语言的二义性, 这是因为可能有两个不同的文法G和G ，而且其中一个是二义性的，另一个是无二义性的, 但却有L(G)=L(G), 即这两个文法所产生的语言是相同的。2.5.3 2.5.3 文法二义性的消除文法二义性的消除 应该指出的是文法的二义性和语言的二义性是两个不同的概念。短语、直接短语和句柄2.5.3 2.5.3 文法二义性的消除文法二义性的消除 将一个语言说成是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。 例如 L= ai bj ck | i=j 或 j=k 且 i, j, k1便是这种语言。短语、直接短语和句柄2.6

16、 2.6 文法和语言的分类文法和语言的分类 著名的语言学家乔姆斯基(Chomsky) 将文法和语言分为四大类，即0型、1型、 2型、3型。划分的依据是对文法中的规则施加不同的限制。 短语、直接短语和句柄2.6 2.6 文法和语言的分类文法和语言的分类 0型文法（无限制文法） 若文法G=(VN,VT, P, S)中的每条规则 是这样一种结构： 而且中至少含一个非终结符, 则称G 是0型文法。(VNVT)+ , (VNVT)*0型文法描述的语言是0型语言。0型文法没有加任何限制条件，又称为 无限制性文法，相应的语言称为无限制 性语言。0型语言由图灵机识别。短语、直接短语和句柄短语、直接短语和句柄短

17、语、直接短语和句柄短语、直接短语和句柄2.6 2.6 文法和语言的分类文法和语言的分类 例如，有0型文法G=(VN,VT, P, S) 其中：VN=A,B,S , VT=0,1 其描述的 0 型语言为 L0(GS)= P: S 0AB 1B 0 B SA | 01 A1 SB1 A0 S0B STOP短语、直接短语和句柄2.6 2.6 文法和语言的分类文法和语言的分类 1型文法（上下文有关文法） 1型文法也称为上下文有关文法， 相应 的语言又称为上下文有关语言。 若文法G=(VN,VT, P, S)中的每一条规则的 形式为 A , 其中： , (VNVT)* ,AVN ,则称G是1型文法。1型

18、文法描述的语言是1型语言。1型语言由线性界限自动机识别。 (VNVT)+短语、直接短语和句柄2.6 2.6 文法和语言的分类文法和语言的分类 例如，有1型文法G=(VN,VT, P, S) 其中：VN=S,A,B , VT=a,b,c P: S aSAB | abB BA BA BA AA AA AB bA bb bB bc cB cc其描述的1型语言为L1(GS)=anbncn | n1 短语、直接短语和句柄2.6 2.6 文法和语言的分类文法和语言的分类 2型文法（上下文无关文法） 2型文法又称上下文无关文法，其产生的 语言又称为上下文无关的语言。 若文法G=(VN,VT, P, S)中的

19、每一条规则的 形式为 A , 其中： AVN ,(VNVT)*则称G是2型文法。2型文法描述的语言是2型语言。2型语言由下推自动机识别。短语、直接短语和句柄例如前面描述算术表达式的文法GE:EE+E | E*E | (E) | i2.6 2.6 文法和语言的分类文法和语言的分类 短语、直接短语和句柄 其描述的语言为 L2(GS)=x | x a, b+ 且x中a和b的个数相同 例如，有2型文法G=(VN,VT, P, S) 其中：VN=S, A, B , VT=a, b P= S aB | bA A a | aS | bAA B b | bS | aBB 2.6 2.6 文法和语言的分类文法和

20、语言的分类 短语、直接短语和句柄2.6 2.6 文法和语言的分类文法和语言的分类 3型文法（正规文法） 右线性文法和左线性文法都称为3型文法。 若文法G=(VN,VT, P, S)中的每一条规则的形式 为A aB 或 A a , 其中： A , BVN, a VT*, 则称G是右线性文法。 若文法G=(VN,VT, P, S)中的每一条规则的形式 为A Ba 或 A a , 其中： A , BVN , a VT*, 则称G是左线性文法。3型文法描述的语言是3型语言。3型语言由有穷自动机识别。 3型文法也称正规文法。正规文法产生的语言 称为正规语言。短语、直接短语和句柄 例如，用左线性正规文法和

21、右线性正规文法定义标识符 2.6 2.6 文法和语言的分类文法和语言的分类 用I代表标识符; l代表任意一个字母; d代表任意一个数字; 则定义标识符的文法为：左线性文法: P: I l | Il | Id右线性文法: P: I l | lT Tl | d | lT| dT短语、直接短语和句柄 例如，用左线性正规文法和右线性正规文法定义无符号整数2.6 2.6 文法和语言的分类文法和语言的分类 用N代表无符号整数; d代表任意一个数字；则定义的无符号整数文法为：左线性文法: P: N Nd | d右线性文法: P: N dN | d短语、直接短语和句柄2.6 2.6 文法和语言的分类文法和语言

22、的分类 由上述四类文法的定义可知, 从0型文法到3型文法, 是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法, 而由它们所定义的语言类是依次缩小的，有 L0 L1 L2 L3 。 短语、直接短语和句柄 2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 文法是用来描述程序设计语言的，在 实际应用中需要对文法加一些限制条件。 1. 文法中不能含有形如A A 的规则。这种规则我们称之为有害规则。对文法的实用限制有以下两点： 短语、直接短语和句柄 2.7 2.7 有关文法的实用限

23、制和变换有关文法的实用限制和变换 2. 文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则： (1) 某条规则 A 的左部符号A不在所属文法的任何其他规则右部出现，即在推导文法的所有句子中始终都不可能用到的规则。 (2) 对文法中的某个非终结符A，无法从它推出任何终结符号串来。 短语、直接短语和句柄 2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 例如 设有文法GS: P: S Bd A Ad | dB Cd | AeC Ce D e 删除多余规则后的文法变换为: P: S Bd A Ad | dB Ae短语、直接短语和句柄 2.7 2.7 有关文法的实用限制和变换

24、有关文法的实用限制和变换 若程序设计语言的文法含有多余规则， 其中必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。 短语、直接短语和句柄作业P26 2.1 2.2（2） 2.3 L1，L2 ，L3 2.7 2.8 2.9 2.11 2.12短语、直接短语和句柄 本章重点介绍了语言的语法结构的形式描 述、语法树以及文法的二义性, 主要内容有： 1. 设计一个文法定义一个已知的语言 (1) 文法是一个四元组 G=(VN,VT, P, S)， 文法四大要素中，关键是一组规则, 它定义（或描述）了一个语言的结构。 从文法定义可知, 文法对于程序设计者来 说，文法给出了语言的精确定义

25、和描述。 本章小结本章小结本小结花时45分钟2004/2/28短语、直接短语和句柄 (2) 分析已知语言句子的结构特征, 设计 出相应的一组规则，但不唯一。 (4) 若语言是无穷集合, 设计该语言的文 法一定是递归的。本章小结本章小结(3) 设计的文法必须能定义已知的语言, 不能超出或缩小所定义语言的范围。短语、直接短语和句柄 分析 根据语言句子的结构特征，设计出相 应规则例1. 给出语言 L2=an bm| mn1 的文法P2: SAB L2=ab,abb,abbb, aabb,aabbb,aabbbb, aaabbb, aabbbb，AaAb | ab BbB |本章小结本章小结短语、直接

26、短语和句柄 分析 根据语言句子的结构特征，设计出相 应规则 例2. 给出语言 L1=a2n+1|n0 的文法P1: AaB | aP1：AaAa | a 或或L1=a, aaa, aaaaa, aaaaaaa, aaaaaaaaa，Baa | aBa本章小结本章小结短语、直接短语和句柄本章小结本章小结 分析 根据语言句子的结构特征，设计出相应规则 例3. 给出语言L3=anbmck| n,m,k0的文法P3: AaA | bB | cC |P3: AaA | B或或L3=,a,aa,aaa,b,bb,bbb,c,cc,ccc, , ab,abb, ,bc,bcc，CcC |BbB | cC |

27、 CcC |BbB | C短语、直接短语和句柄本章小结本章小结L4=0 ,2,4,6,8,10,12,14,16,18,20,22,24,26, 例4. 写一个 文法,使其语言是正偶数的集合,每个偶数不以0开头。P4: NE | AE N0 | 2 | 4 | 6 | 8 |BN或或分析 不以0开头的偶数集合中串的结构特征:AD | AD E0 | 2 | 4 | 6 | 8 D1 | 2 | 3 | | 9 D0 | 1 | 2 | 3 | 9 B1 | 2 | 3 | | 9 |B0P4:短语、直接短语和句柄本章小结本章小结A 0A1 | P : S 1S0 | 0A1 | 例5. 给出语

28、言L=1n0m1m0n | n,m0的 文法。分析 根据语言句子的结构特征, 设计 出相应规则 L=,01,0011,10,1100,1010,100110, 110100,11001100短语、直接短语和句柄本章小结本章小结P : S a | 0S0 | 1S1例6. 给出语言L=WaWt | W0|1*,Wt 表示W的逆的文法。分析 根据语言句子的结构特征，设计 出相应规则 L=a, 0a0, 1a1, 01a10, 10a01, 00a00, 11a11, 101a101, 110a011, 100a001, W=,0, 1 ,01, 10, 00, 11, 101, 110, 100,

29、 111, 短语、直接短语和句柄本章小结本章小结2. 已知一个文法，确定该文法所定义的 语言。 (2) 给定一个文法，可根据语言和推导定 义推导出文法的句子，从而确定出该文法 所定义的语言。 (1) 文法所定义的语言 L(GS)=x|S x且xVT*短语、直接短语和句柄本章小结本章小结 自然语言描述。 例如, L=x|xa,b+且x中a,b个数相同式子描述。例如 L=a2nbb | n0。正规式描述。 (3) 语言可用短语、直接短语和句柄本章小结本章小结 例1 文法GA=(A,a,b,AbA | a, A) 所生成的语言是什么？ 分析 AbAbbAbbbAbnAbna L(GA)= bna |

30、 n0 短语、直接短语和句柄本章小结本章小结例2 文法GN为:N ND | DD 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1) GN所生成的语言是什么？ (2) 给出句子0127的最左、最右推导。 短语、直接短语和句柄本章小结本章小结L(GN)= | 0,1,2, 9+= | 为可带前导0的正整数= | 为数字串最左推导:NNDN7ND7N27ND27 N127D1270127最右推导:NNDNDDNDDDDDDD 0DDD01DD012D0127N ND | DD 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9短语、直接短语和句

31、柄本章小结本章小结 例3. 已知文法GS=( A,B,a,b,c,d, P, S ) , 其中 P 为:分析 SABaAbBa2Ab2B an-1Abn-1BanbnBanbncBd anbnc2Bd2 anbncm-1Bdm-1anbncmdm L(GS)=anbncmdm | n ,m1 该文法 所生成的语言是什么？ A aAb | ab B cBd | cd S AB短语、直接短语和句柄本章小结本章小结3. 求句型的短语、直接短语和句柄 (1) 短语、直接短语和句柄是对某句 型而言的。 (2) 短语总是句型的某个子串，它对应 子树未端结点形成的符号串。 (3) 直接短语是某条规则右部，它

32、对应 简单子树未端结点形成的符号串。(4) 最左边的直接短语是句柄。 短语、直接短语和句柄本章小结本章小结例1 已知文法GE： 证明 E+T*F是它的一个句型,指出这个句型的短语直接短语和句柄。 EE+TE+T*F 短语: E+T*F、T*F E+T*F是它的一个句型。画出该句型的语法树:句柄: T*F直接短语: T*FETFT+E*EE+T | E-T | TTT*F | T/F | TT(E) | i2.9相似短语、直接短语和句柄本章小结本章小结 例2 已知文法GS： 试找出符号串(a)和(A(SaA)(b)的短语 直接短语和句柄(如果有的话)。S(AS) | (b)A(SaA) | (a) 符号串(a)不是文法的句型，因此 它没有短语直接