第2章(2) 短语、直接短语和句柄

《第2章(2) 短语、直接短语和句柄》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、bBBa

4、Sb2.4短语、直接短语和句柄对文法，首先建立该句型的推导过程：最左推导:最右推导:SABAAa

5、bBBa

6、SbSA

7、BASbbBSbbaSbSABbaBbaSbbBB分析根据短语定义，可以从句型的推导过程中找出其全部短语、直接短语和句柄。句型baSb2.4短语、直接短语和句柄句型baSb中的子串Sb，是(相对于非终结符B)句型baSb的短语，且为直接短语。SABbBBbaBbaSb(2)SbaB*BSb(1)SS*SbaSb+句型本身是(相对于非终结符S)句型baSb的短语。根据最左推导:SαAδ*+Aβ2.4短语、直接短语和句柄句型baSb中的子串a，是(相对于非终结符B)句型baSb的短语，

8、且为直接短语、句柄。句型baSb中的子串ba，是(相对于非终结符A)句型baSb的短语。Ba(3)SbBSb*根据最右推导:SABASbbBSbbaSb(4)SASb*Aba+SαAδ*+Aβ2.5语法树与文法的二义性推导和语法树1.语法树对句型的推导过程给出一种图形表示,这种表示称为语法树，也称推导树。2.5.1推导和语法树例如设有文法G[E]:构造句型i*i+i的语法树。首先给出句型的推导过程(最左推导)：EE+T

9、E–T

10、TTT*F

11、T/F

12、FF(E)

13、iEE+TT+TT*F+T

14、F*F+Ti*F+Ti*i+Ti*i+Fi*i+i2.5.1推导和语法树根据推导过程构造句型i*i+i的语法树如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+Tii*i+Tii*i+FFi*i+ii2.5.1推导和语法树由例可知，语法树的构造过程是从文法的开始符号出发，构造一个推导的过程。因为文法的每一个句型(句子)都存在一个推导，所以文法的每个句型(句子)都存在一棵对应的语法树。EE+TE+FE+iT+iT*F+iT*i+iF*i+ii*i+i2.5.1推导和语法

15、树对句型i*i+i，还可给出最右推导：EE+TTT*FFiiFi2.5.1推导和语法树这也就是说，一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程,包括最左(最右)推导。2.5.1推导和语法树2.子树语法树的子树是由某一结点连同所有分枝组成的部分。EE+TTT*FFiiFi2.5.1推导和语法树3.简单子树语法树的简单子树是指只有单层分枝的子树。EE+TTT*FFiiFi2.5.1推导和语法树句型的短语、直接短语和句柄的直观解释是：短语：子树的末端结点形成的符号串是相对于子树根的短语。直接短语：简单子树的末

16、端结点形成的符号串是相对于简单子树根的直接短语。句柄：最左简单子树的末端结点形成的符号串是句柄。2.5.1推导和语法树EE+TTT*FFiiFi短语:i*i+ii*i第一个i第二个i第三个i三个i都是直接短语第一个i是句柄注意:i+i不是句型的短语句子i*i+i2.5.1推导和语法树前例对文法G[S]=({S,A,B},{a,b},P,S)其中P为：可用语法树非常直观地求出句型baSb的全部短语，直接短语和句柄。SABAAa

17、bBBa

18、Sb2.5.1推导和语法树分析首先根据句型baSb的推导过程画出对应的语法树如下：S

19、b为句型的相对于B的短语、直接短语baSb为句型的相对于S的短语ba为句型的相对于A的短语a句型的相对于B的短语、直接短语和句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbBSba由语法树可知2.5.2文法的二义性从前面的讨论可以看出，对于文法G中任一句型