第2章(2)白底黑字

2.4短语、直接短语和句柄短语令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有则称β是相对于非终结符A的,句型αβδ的短语。SαAδ*+且Aβ2.4短语、直接短语和句柄则称β是直接短语。直接短语SαAδ*且Aβ令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有2.4短语、直接短语和句柄短语和直接短语的区别:直接短语中的第二个条件表示有文法规则Aβ，因此，每个直接短语都是某规则右部。2.4短语、直接短语和句柄句柄一个句型的最左直接短语称为该句型的句柄。句柄特征：(1)它是直接短语，即某规则右部。(2)它具有最左性。2.4短语、直接短语和句柄短语、直接短语和句柄都是针对某一句型的，都是指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。2.4短语、直接短语和句柄例如设有文法G[S]=({S,A,B},{a,b},P,S)其中P为：求句型baSb的全部短语、直接短语和句柄。SABAAa|bBBa|Sb2.4短语、直接短语和句柄对文法，首先建立该句型的推导过程：最左推导:最右推导:SABAAa|bBBa|SbSAB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的短语，且为直接短语、句柄。句型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|E–T|TTT*F|T/F|FF(E)|iEE+TT+TT*F+T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推导和语法树对句型i*i+i，还可给出最右推导：EE+TTT*FFiiFi2.5.1推导和语法树一棵语法树表示了一个句型的种种可能的不同推导过程,包括最左(最右)推导。2.5.1推导和语法树2.子树语法树的子树是由某一结点连同所有分枝组成的部分。EE+TTT*FFiiFi2.5.1推导和语法树3.简单子树语法树的简单子树是指只有单层分枝的子树。EE+TTT*FFiiFi2.5.1推导和语法树句型的短语、直接短语和句柄的直观解释是：短语：子树的末端结点形成的符号串是相对于子树根的短语。直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。句柄：最左简单子树的末端结点形成的符号串是句柄。2.5.1推导和语法树EE+TTT*FFiiFi短语:i*i+ii*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|bBBa|Sb2.5.1推导和语法树分析首先根据句型baSb的推导过程画出对应的语法树如下：Sb为句型的相对于B的短语、直接短语baSb为句型的相对于S的短语ba为句型的相对于A的短语a句型的相对于B的短语、直接短语和句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbBSba由语法树可知2.5.2文法的二义性对于文法G中任一句型的推导序列,我们总能为它构造一棵语法树。问题：文法的某个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左(最右)推导呢？2.5.2文法的二义性例如设有文法G[E]：句子i*i+i有两个不同的最左推导，对应两棵不同的语法树。EE+E|E*E|(E)|i2.5.2文法的二义性最左推导1EE+EE*E+Ei*E+Ei*i+Ei*i+i最左推导2EE*Ei*Ei*E+Ei*i+Ei*i+iEE*EE+EiiiEE+EE*Eiii2.5.2文法的二义性如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义性的。EE+E|E*E|(E)|i2.5.3文法二义性的消除1.不改变文法中原有的语法规则,仅加进一些非形式的语法规定。EE+EE*Eiii2.5.3文法二义性的消除2.构造一个等价的无二义性文法。即把排除二义性的规则合并到原有文法中,改写原有的文法。例如，对于上例文法G[E]，将运算符的优先顺序和结合规则：*优先于＋;＋、*左结合加到原有文法中,可构造出无二义性文法如下：2.5.3文法二义性的消除则句子i*i+i只有唯一一棵语法树：EE+T|TTT*F|FF(E)|iEE+TTT*FFiiFi2.5.3文法二义性的消除例2定义某程序语言条件语句的文法G为:试证明该文法是二义性的并消除之。分析该文法的句子ifbifbAelseA对应下面两棵不同的语法树：SifbS|ifbSelseS|A(其它语句）2.5.3文法二义性的消除所以该文法是二义的。SifbSbSSifAelseASbSSifAelseAifbSSifbS|ifbSelseS|A句子ifbifbAelseA2.5.3文法二义性的消除消除文法的二义性可采用下面两种方法：1.不改变已有规则，仅加进一非形式的语法规定：else与前面最接近的不带else的if相对应。SifbSbSSifAelseA文法G的句子ifbifbAelse只对应唯一的一棵语法树，消除了二义性。2.5.3文法二义性的消除2.改写文法G为G'SS1|S2S1ifbS1elseS1|AS2ifbS|ifbS1elseS2G':SifbS|ifbSelseS|A(其它语句）G:2.5.3文法二义性的消除这是因为通过分析，得知引起二义性的原因是:if-else语句的if后可是if型，因此改写文法时规定:if-else之间只能是if-else语句或其他语句。2.5.3文法二义性的消除SS1|S2S1ifbS1elseS1|AS2ifbS|ifbS1elseS2ifbSbifAelseASS2S1S1S1对改写后的文法，句子ifbifbAelseA只对应唯一的一棵语法树。可能有两个不同的文法G和G'，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G'),即这两个文法所产生的语言是相同的。2.5.3文法二义性的消除文法的二义性和语言的二义性是两个不同的概念。2.5.3文法二义性的消除一个语言是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。例如L={aibjck|i=j或j=k且i,j,k≥1}便是这种语言。2.6文法和语言的分类著名的语言学家乔姆斯基(Chomsky)将文法和语言分为四大类，即0型、1型、2型、3型。划分的依据是对文法中的规则施加不同的限制。为了容易理解，我们讲解时按照由简到难的次序，和教材稍有不同。2.6文法和语言的分类3型文法（正规文法）右线性文法和左线性文法都称为3型文法。若文法G=(VN,VT,P,S)中的每一条规则的形式为AaB或Aa,其中：A,BVN,aVT*,则称G是右线性文法。若文法G=(VN,VT,P,S)中的每一条规则的形式为ABa或Aa,其中：A,BVN,aVT*,则称G是左线性文法。3型文法描述的语言是3型语言。3型语言由有穷自动机识别。3型文法也称正规文法。正规文法产生的语言称为正规语言。2.6文法和语言的分类例如，用左线性正规文法和右线性正规文法定义标识符用I代表标识符;l代表任意一个字母;d代表任意一个数字;则定义标识符的文法为：左线性文法:P:I→l|Il|Id右线性文法:P:I→l|lTT→l|d|lT|dT2.6文法和语言的分类例如，用左线性正规文法和右线性正规文法定义无符号整数用N代表无符号整数;d代表任意一个数字；则定义的无符号整数文法为：左线性文法:P:N→Nd|d右线性文法:P:N→dN|d2.6文法和语言的分类2型文法（上下文无关文法）2型文法又称上下文无关文法，其产生的语言又称为上下文无关的语言。若文法G=(VN,VT,P,S)中的每一条规则的形式为Aβ,其中：AVN,β(VN∪VT)*则称G是2型文法。2型文法描述的语言是2型语言。2型语言由下推自动机识别。例如前面描述算术表达式的文法G[E]:EE+E|E*E|(E)|i2.6文法和语言的分类其描述的语言为？L2(G[S])={}例如，有2型文法G=(VN,VT,P,S)其中：VN={S,A,B},VT={a,b}P={SaB|bAAa|aS|bAABb|bS|aBB}2.6文法和语言的分类其描述的语言为L2(G[S])={x|x{a,b}+且x中a和b的个数相同}例如，有2型文法G=(VN,VT,P,S)其中：VN={S,A,B},VT={a,b}P={SaB|bAAa|aS|bAABb|bS|aBB}2.6文法和语言的分类2.6文法和语言的分类1型文法（上下文有关文法）1型文法也称为上下文有关文法，相应的语言又称为上下文有关语言。若文法G=(VN,VT,P,S)中的每一条规则的形式为αAβαμβ,其中：α,β(VN∪VT)*,AVN,则称G是1型文法。1型文法描述的语言是1型语言。1型语言由线性界限自动机识别。μ(VN∪VT)+2.6文法和语言的分类例如，有1型文法G=(VN,VT,P,S)其中：VN={S,A,B},VT={a,b,c}P:SaSAB|abBBABA'BA'AA'AA'ABbAbbbBbccBcc其描述的1型语言为L1(G[S])={？}2.6文法和语言的分类例如，有1型文法G=(VN,VT,P,S)其中：VN={S,A,B},VT={a,b,c}P:SaSAB|abBBABA'BA'AA'AA'ABbAbbbBbccBcc其描述的1型语言为L1(G[S])={anbncn|n≥1}2.6文法和语言的分类0型文法（无限制文法）若文法G=(VN,VT,P,S)中的每条规则αβ是这样一种结构：而且α中至少含一个非终结符,则称G是0型文法。α(VN∪VT)+,β(VN∪VT)*0型文法描述的语言是0型语言。0型文法没有加任何限制条件，又称为无限制性文法，相应的语言称为无限制性语言。0型语言由图灵机识别。2.6文法和语言的分类例如，有0型文法G=(VN,VT,P,S)其中：VN={A,B,S},VT={0,1}其描述的0型语言为L0(G[S])={？}P:S0AB1B0BSA|01A1SB1A0S0B2.6文法和语言的分类由上述四类文