-短语直接短语和句柄.pptx

2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄则称则称是是直接短语直接短语。直接短语直接短语SA*且且A令令G是一个文法，是一个文法，S是文法的开始符是文法的开始符号，假定号，假定是文法是文法G的一个句型，如果的一个句型，如果有有2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄注意：注意：短语和直接短语的区别短语和直接短语的区别在于第二个条件在于第二个条件,直接短语中的第直接短语中的第二个条件表示有文法规则二个条件表示有文法规则A，因此，每个直接短语都是因此，每个直接短语都是某规则右某规则右部部。2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄句柄句柄一个句型的一个句型的最左直接短语最左直接短语称为该句称为该句型的句柄。型的句柄。句柄特征：句柄特征：(1)它是它是直接短语直接短语，即某规则右部。，即某规则右部。(2)它具有它具有最左最左性。性。2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄注注意意:短短语语、直直接接短短语语和和句句柄柄都都是是针针对对某某一一句句型型的的，都都是是指指句句型型中中的的哪哪些些符符号号串串能能构构成成短短语语和和直直接接短短语语，离离开开具具体体的的句句型型来来谈谈短短语语、直直接短语和句柄是无意义的接短语和句柄是无意义的。2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄例如例如设有文法设有文法GS=(S,A,B,a,b,P,S)其中其中P为为：求句型求句型baSb的全部的全部短语短语、直接短语直接短语和和句柄句柄。SABAAa|bBBa|Sb2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄对文法，首先建立该句型的推导过程：对文法，首先建立该句型的推导过程：最左推导最左推导:最右推导最右推导:SABAAa|bBBa|SbSABASb bBSbbaSbSABbaBbaSbbBB分析分析根据短语定义，可以从句型根据短语定义，可以从句型的推导过程的推导过程中找出其全部短语、直接短中找出其全部短语、直接短语和句柄。语和句柄。句型句型baSb2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄句型句型baSb中的子串中的子串Sb，是是(相对相对于非终结符于非终结符B)句型句型baSb的短语，的短语，且为且为直接短语直接短语。SABbBBbaBbaSb(2)SbaB*BSb(1)SS*SbaSb+句型本身是句型本身是(相对于非终结符相对于非终结符S)句型句型baSb的短语。的短语。根据最左推导根据最左推导:SA*+A2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄句型句型baSb中的子串中的子串a，是是(相对相对于非终结符于非终结符B)句型句型baSb的短语，的短语，且为且为直接短语、句柄直接短语、句柄。句型句型baSb中的子串中的子串ba，是是(相对相对于非终结符于非终结符A)句型句型baSb的短语。的短语。Ba(3)SbBSb*根据最右推导根据最右推导:SABASb bBSbbaSb(4)SASb*Aba+SA*+A2.5 2.5 语法树与文法的二义性语法树与文法的二义性 推导和语法树推导和语法树1.语法树语法树对句型的推导过程给出一种图形对句型的推导过程给出一种图形表示表示,这种表示称为语法树，也称推这种表示称为语法树，也称推导树。导树。2.5.1 2.5.1 推导和语法树推导和语法树例如例如设有文法设有文法GE:构造句型构造句型i*i+ii*i+i的语法树。的语法树。首先给出句型的推导过程首先给出句型的推导过程(最左推导最左推导)：EE+T|ET|TTT*F|T/F|FF(E)|iEE+TT+TT*F+TF*F+Ti*F+Ti*i+Ti*i+Fi*i+i2.5.1 2.5.1 推导和语法树推导和语法树根据推导过程构造句型根据推导过程构造句型i*i+i的语法树如下：的语法树如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+Tii*i+Tii*i+FFi*i+ii2.5.1 2.5.1 推导和语法树推导和语法树 由例可知，由例可知，语法树的构造过程是从语法树的构造过程是从文法的开始符号出发，构造一个推导的文法的开始符号出发，构造一个推导的过程。过程。因为文法的每一个句型因为文法的每一个句型(句子句子)都存在一都存在一个推导，所以文法的每个句个推导，所以文法的每个句型型(句子句子)都存在一棵对应的语法树。都存在一棵对应的语法树。EE+TE+FE+iT+iT*F+iT*i+iF*i+ii*i+i2.5.1 2.5.1 推导和语法树推导和语法树 对句型对句型i*i+i，还可给出最右推导：还可给出最右推导：EE+TTT*FFiiFi2.5.1 2.5.1 推导和语法树推导和语法树 这也就是说，这也就是说，一棵语法树表示了一棵语法树表示了一个句型的种种可能的一个句型的种种可能的(但未必是所但未必是所有的有的)不同推导过程不同推导过程,包括最左包括最左(最右最右)推导。推导。2 2.5.1 .5.1 推导和语法树推导和语法树 2.子树子树语法树的子语法树的子树是由某一结点树是由某一结点连同所有分枝组连同所有分枝组成的部分。成的部分。EE+TTT*FFiiFi2 2.5.1 .5.1 推导和语法树推导和语法树 3.简单子树简单子树语法树的语法树的简单子树是指简单子树是指只有单层分枝只有单层分枝的子树。的子树。EE+TTT*FFiiFi2.5.1 2.5.1 推导和语法树推导和语法树 句型的短语、直接短语和句柄的句型的短语、直接短语和句柄的直观解释直观解释是：是：短语：短语：子树子树的末端结点形成的的末端结点形成的符号串符号串是是相对于子树根的短语。相对于子树根的短语。直接短语：直接短语：简单子树简单子树的末端结点形成的的末端结点形成的符号串符号串是相对于简单子树根的直接短语。是相对于简单子树根的直接短语。句柄：句柄：最左简单子树最左简单子树的末端结点形成的的末端结点形成的符号串符号串是句柄。是句柄。2.5.1 2.5.1 推导和语法树推导和语法树EE+TTT*FFiiFi短语短语:ni*i+ii*i+ini*ii*in第一个第一个i in第二个第二个i in第三个第三个i in三个三个i i都是直接短语都是直接短语n第一个第一个i i是句柄是句柄注意注意:i+ii+i不是句型的短语不是句型的短语句子句子i*i+i2.5.1 2.5.1 推导和语法树推导和语法树 前例前例对文法对文法GS=(S,A,B,a,b,P,S)其中其中P为：为：可用语法树非常直观地求出句型可用语法树非常直观地求出句型baSb的全部短语，直接短语和句柄。的全部短语，直接短语和句柄。SABAAa|bBBa|Sb2.5.1 2.5.1 推导和语法树推导和语法树 分析分析首先根据句型首先根据句型baSb的推导过程画出对的推导过程画出对 应的语法树如下：应的语法树如下：Sb为句型的相对于为句型的相对于B的短语、的短语、直接短语直接短语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有两个不同的最左推导，有两个不同的最左推导，对应两棵不同的语法树。对应两棵不同的语法树。EE+E|E*E|(E)|i2.5.2 2.5.2 文法的二义性文法的二义性 最左推导最左推导1EE+EE*E+Ei*E+Ei*i+Ei*i+i最左推导最左推导2EE*Ei*Ei*E+Ei*i+Ei*i+iEE*EE+EiiiEE+EE*Eiii2.5.2 2.5.2 文法的二义性文法的二义性 如果一个文法存在某个句子对应如果一个文法存在某个句子对应两两棵不同的语法树棵不同的语法树，则说这个文法则说这个文法是是二义二义性的。性的。或者说，若一个文法中存在某个句或者说，若一个文法中存在某个句子，它有子，它有两个不同的最左两个不同的最左(最右最右)推导，推导，则这个文法则这个文法是二义性的是二义性的。EE+E|E*E|(E)|i2.5.3 2.5.3 文法二义性的消除文法二义性的消除 1.不改变文法中原有的语法规则不改变文法中原有的语法规则,仅加仅加进一些进一些非形式的非形式的语法规定。语法规定。EE+EE*Eiii2.5.3 2.5.3 文法二义性的消除文法二义性的消除2.构造构造一个等价的无二义性文法一个等价的无二义性文法。即。即 把排除二义性的规则合并到原有文法中把排除二义性的规则合并到原有文法中,改写原有的文法。改写原有的文法。例如，对于上例文法例如，对于上例文法GE，将运算符的将运算符的优先顺序和结合规则：优先顺序和结合规则：*优先于优先于;、*左结合加到原有文法中左结合加到原有文法中,可构造出无二义可构造出无二义性文法如下性文法如下：2.5.3 2.5.3 文法二义性的消除文法二义性的消除则句子则句子i*i+ii*i+i只有只有唯一一棵语法树：唯一一棵语法树：EE+T|TTT*F|FF(E)|iEE+TTT*FFiiFi2.5.3 2.5.3 文法二义性的消除文法二义性的消除 例例2定义某程序语言条件语句的文法定义某程序语言条件语句的文法G为为:试证明该文法是二义性的并消除之试证明该文法是二义性的并消除之。分析分析该文法的句子该文法的句子ifbifbAelseA对应下面两棵不同的语法树：对应下面两棵不同的语法树：SifbS|ifbSelseS|A(其它语句）其它语句）2.5.3 2.5.3 文法二义性的消除文法二义性的消除 所以该文法是二义的。所以该文法是二义的。SifbSbSSifAelseASbSSifAelseAifbSSifbS|ifbSelseS|A句子句子ifbifbAelseA2.5.3 2.5.3 文法二义性的消除文法二义性的消除 消除文法的二义性可采用下面两种方法：消除文法的二义性可采用下面两种方法：1.不改变已有规则不改变已有规则，仅，仅加进一非形式的语法规加进一非形式的语法规定：定：else与前面最接近与前面最接近的不带的不带else的的if相对应相对应。SifbSbSSifAelseA文法文法G的句子的句子ifbifbAelse只对应唯一的一棵语法树只对应唯一的一棵语法树，消除了二义性。消除了二义性。2.5.3 2.5.3 文法二义性的消除文法二义性的消除2.改写文法改写文法G为为GSS1|S2S1ifbS1elseS1|AS2ifbS|ifbS1elseS2G:SifbS|ifbSelseS|A(其它语句）其它语句）G:2.5.3 2.5.3 文法二义性的消除文法二义性的消除这是因为通过这是因为通过分析分析，得知引起二义，得知引起二义性的原因是性的原因是:if if-else else 语句的语句的 if if 后可是后可是ifif型，型，因此改写文法时规定因此改写文法时规定:ifif-elseelse之间只能是之间只能是ifif-elseelse语句或其他语句或其他语句语句。2.5.3 2.5.3 文法二义性的消除文法二义性的消除SS1|S2S1ifbS1elseS1|AS2ifbS|ifbS1elseS2ifbSbifAelseASS2S1S1S1对改写后的文法，句子对改写后的文法，句子ifbifbAelseA只对应唯一的一棵语法只对应唯一的一棵语法树。树。通常我们通常我们只说文法的二义性只说文法的二义性,而不而不说语言的二义性说语言的二义性,这是因为可能有两个这是因为可能有两个不同的文法不同的文法G和和G，而且其中一个是而且其中一个是二二义性的义性的，另一个是另一个是无二义性的无二义性的,但却有但却有L(G)=L(G),即这两个文法所产生的即这两个文法所产生的语语言是相同的言是相同的。2.5.3 2.5.3 文法二义性的消除文法二义性的消除 应该指出的是文法的二义性和语应该指出的是文法的二义性和语言的二义性是言的二义性是两个不同的概念两个不同的概念。2.5.3 2.5.3 文法二义性的消除文法二义性的消除 将一个语言说成是二义性的，将一个语言说成是二义性的，是是指对它指对它不存在无二义性的文法，不存在无二义性的文法，这样这样的语言称为先天二义性的语言。的语言称为先天二义性的语言。例如例如L=aibjck|i=j或或j=k且且i,j,k1便是这种语言。便是这种语言。2.6 2.6 文法和语言的分类文法和语言的分类 著名的语言学家著名的语言学家乔姆斯基乔姆斯基(Chomsky)将文法和语言分为四大类，即将文法和语言分为四大类，即0型、型、1型、型、2型、型、3型。划分的依据是对文法中的规型。划分的依据是对文法中的规则施加不同的限制。则施加不同的限制。为了容易理解，我们讲解时按照由简为了容易理解，我们讲解时按照由简到难的次序，和教材稍有不同。到难的次序，和教材稍有不同。2.6 2.6 文法和语言的分类文法和语言的分类 3型文法（正规文法）型文法（正规文法）右线性文法右线性文法和和左线性文法左线性文法都称为都称为3型文法。型文法。若文法若文法G=(VN,VT,P,S)中的每一条规则的形式中的每一条规则的形式为为AaB或或Aa,其中：其中：A,B VN,a VT*,则称则称G是是右线性文法右线性文法。若文法若文法G=(VN,VT,P,S)中的每一条规则的形式中的每一条规则的形式为为ABa或或Aa,其中：其中：A,B VN,a VT*,则称则称G是是左线性文法左线性文法。3型文法描述的语型文法描述的语言是言是3型语言。型语言。3型语言由有型语言由有穷自动机识别。穷自动机识别。3型文法也称型文法也称正规文法正规文法。正规文法产生的语言。正规文法产生的语言称为称为正规语言正规语言。例如，用左线性正规文法和右线性例如，用左线性正规文法和右线性正规文法定义标识符正规文法定义标识符2.6 2.6 文法和语言的分类文法和语言的分类 用用I代代表表标标识识符符;l代代表表任任意意一一个个字字母母;d代代表表任任意意一一个个数数字字;则则定定义义标标识识符符的文法为：的文法为：左线性文法左线性文法:P:Il|Il|Id右线性文法右线性文法:P:Il|lTTl|d|lT|dT例如，用左线性正规文法和右线性例如，用左线性正规文法和右线性正规文法定义无符号整数正规文法定义无符号整数2.6 2.6 文法和语言的分类文法和语言的分类 用用N代代表表无无符符号号整整数数;d代代表表任任意意一一个数字；则定义的无符号整数文法为：个数字；则定义的无符号整数文法为：左线性文法左线性文法:P:NNd|d右线性文法右线性文法:P:NdN|d2.6 2.6 文法和语言的分类文法和语言的分类 2型文法（上下文无关文法）型文法（上下文无关文法）2型文法又称上下文无关文法，其产生的型文法又称上下文无关文法，其产生的 语言又称为语言又称为上下文无关的语言上下文无关的语言。若文法若文法G=(VN,VT,P,S)中的每一条规则的中的每一条规则的形式为形式为A,其中：其中：A VN,(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,bP=SaB|bAAa|aS|bAABb|bS|aBB2.6 2.6 文法和语言的分类文法和语言的分类 2.6 2.6 文法和语言的分类文法和语言的分类 1型文法（上下文有关文法）型文法（上下文有关文法）1型文法也称为上下文有关文法，型文法也称为上下文有关文法，相应相应的语言又称为的语言又称为上下文有关语言上下文有关语言。若文法若文法G=(VN,VT,P,S)中的每一条规则的中的每一条规则的形式为形式为A,其中：其中：,(VNVT)*,A VN,则称则称G是是1型文法型文法。1型文法描述的型文法描述的语言是语言是1型语言。型语言。1型语言由线性型语言由线性界限自动机识别。界限自动机识别。(VNVT)+2.6 2.6 文法和语言的分类文法和语言的分类 例如，有例如，有1型文法型文法G=(VN,VT,P,S)其中：其中：VN=S,A,B,VT=a,b,cP:SaSAB|abBBABABAAAAAABbAbbbBbccBcc其描述的其描述的1型语言为型语言为L1(GS)=anbncn|n12.6 2.6 文法和语言的分类文法和语言的分类 0型文法（无限制文法）型文法（无限制文法）若文法若文法G=(VN,VT,P,S)中的每条规则中的每条规则是这样一种结构：是这样一种结构：而且而且中至少含一个非终结符中至少含一个非终结符,则称则称G是是0型文法型文法。(VNVT)+,(VNVT)*0型文法描述的语言是型文法描述的语言是0型语言。型语言。0型文法没有加任何限制条件，又称为型文法没有加任何限制条件，又称为无限制性文法，相应的语言称为无限制性文法，相应的语言称为无限制无限制性语言性语言。0型语言由型语言由图灵机识别。图灵机识别。2.6 2.6 文法和语言的分类文法和语言的分类 例如，有例如，有0型文法型文法G=(VN,VT,P,S)其中：其中：VN=A,B,S,VT=0,1其描述的其描述的0型语言为型语言为L0(GS)=P:S0AB1B0BSA|01A1SB1A0S0B2.6 2.6 文法和语言的分类文法和语言的分类 由上述四类文法的定义可知由上述四类文法的定义可知,从从0型文法到型文法到3型文法型文法,是逐渐增加对规则的是逐渐增加对规则的限制条件而得到的，限制条件而得到的，因此因此每一种正规文每一种正规文法都是上下文无关的文法，法都是上下文无关的文法，每一种上下每一种上下文无关的文法都是上下文有关的文法，文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是而每一种上下文有关的文法都是0型文型文法法,而由它们所定义的语言类是依次缩而由它们所定义的语言类是依次缩小的，小的，有有L0 L1 L2 L3。2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 文法是用来描述程序设计语言的，在文法是用来描述程序设计语言的，在 实际应用中需要对文法加一些限制条件。实际应用中需要对文法加一些限制条件。1.文法中不能含有形如文法中不能含有形如AA的规则。的规则。这种规则我们称之为这种规则我们称之为有害规则有害规则。对文法的实用限制有以下两点：对文法的实用限制有以下两点：2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 2.文法中不能有文法中不能有多余规则多余规则。所谓多余。所谓多余规则是指文法中出现以下两种规则：规则是指文法中出现以下两种规则：(1)某条规则某条规则A的左部符号的左部符号A不在不在所属文法的任何其他规则所属文法的任何其他规则右部右部出现，即出现，即在推导文法的所有句子中始终都不可能在推导文法的所有句子中始终都不可能用到的规则。用到的规则。(2)对文法中的某个非终结符对文法中的某个非终结符A，无法无法从它推出任何终结符号串来。从它推出任何终结符号串来。2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 例如例如设有文法设有文法GS:P:SBdAAd|dBCd|AeCCeDe删除多余规则后的删除多余规则后的文法变换为文法变换为:P:SBdAAd|dBAe 2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 若程序设计语言的若程序设计语言的文法含有多余规则文法含有多余规则，其中其中必定必定有错误存在有错误存在，因此检查文法中是，因此检查文法中是否含有多余规则对我们来说是很重要的。否含有多余规则对我们来说是很重要的。本章重点介绍了语言的语法结构的形式描述、本章重点介绍了语言的语法结构的形式描述、语法树以及文法的二义性语法树以及文法的二义性,主要内容有：主要内容有：1.设计一个文法定义一个已知的语言设计一个文法定义一个已知的语言(1)文法是一个四元组文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则文法四大要素中，关键是一组规则,它定义它定义（或描述）了一个语言的结构。（或描述）了一个语言的结构。从文法定义可知从文法定义可知,文法对于程序设计者来文法对于程序设计者来说，文法给出了语言的精确定义和描述。说，文法给出了语言的精确定义和描述。本章小结本章小结(2)分析已知语言分析已知语言句子的结构特征句子的结构特征,设计设计出相应的一组规则，但不唯一。出相应的一组规则，但不唯一。(4)若语言是若语言是无穷集合无穷集合,设计该语言的文设计该语言的文法一定是法一定是递归的递归的。本章小结本章小结(3)设计的文法必须能定义已知的语言设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。不能超出或缩小所定义语言的范围。分析分析根据语言句子的结构特征，设计出相根据语言句子的结构特征，设计出相应规则应规则例例1.给出语言给出语言L2=anbm|mn1的文法的文法P2:SABL2=ab,abb,abbb,aabb,aabbb,aabbbb,aaabbb,aabbbb，AaAb|abBbB|本章小结本章小结分析分析根据语言句子的结构特征，设计出相根据语言句子的结构特征，设计出相应规则应规则例例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|CcC|BbB|C本章小结本章小结L4=2,4,6,8,10,12,14,16,18,20,22,24,26,例例4.写一个写一个文法文法,使其语言是正偶数的集合使其语言是正偶数的集合,每每个偶数不以个偶数不以0 0开头。开头。P4:NE|AEN2|4|6|8|BN或或分析分析不以不以0开头的偶数集合中串的结构特征开头的偶数集合中串的结构特征:AD|ADE0|2|4|6|8D1|2|3|9D0|1|2|3|9B1|2|3|9|B0P4:E2|4|6|8NBN|0|2|4|6|8本章小结本章小结A0A1|P:S1S0|0A1|例例5.给出语言给出语言L=1n0m1m0n|n,m0的的文法。文法。分析分析根据语言句子的结构特征根据语言句子的结构特征,设计设计出相应规则出相应规则L=,01,0011,10,1100,1010,100110,110100,11001100本章小结本章小结P:Sa|0S0|1S1例例6.给出语言给出语言L=WaWt|W0|1*，其中其中 W Wt t表示表示W W的逆的文法的逆的文法。分析分析根据语言句子的结构特征，设计根据语言句子的结构特征，设计出相应规则出相应规则L=a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,W=,0,1,01,10,00,11,101,110,100,111,本章小结本章小结2.已知一个文法，确定该文法所定义的已知一个文法，确定该文法所定义的语言。语言。(2)给定一个文法，可根据语言和推导定给定一个文法，可根据语言和推导定义推导出文法的句子，从而确定出该文法义推导出文法的句子，从而确定出该文法所定义的语言。所定义的语言。(1)文法所定义的语言文法所定义的语言L(GS)=x|Sx且且xVT*本章小结本章小结自然语言描述。自然语言描述。例如例如,L=x|xa,b+且且x中中a,b个数相同个数相同式子描述。例如式子描述。例如L=a2nbb|n0。正规式描述。正规式描述。(3)语言可用语言可用本章小结本章小结例例1文法文法GA=(A,a,b,AbA|a,A)所生成的语言是什么？所生成的语言是什么？分析分析AbAbbAbbbAbnAbnaL(GA)=bna|n0本章小结本章小结例例2文法文法GN为为:NND|DD0|1|2|3|4|5|6|7|8|9(1)GN所生成的语言是什么？所生成的语言是什么？(2)给出句子给出句子0127的最左的最左、最右推导最右推导。本章小结本章小结L(GN)=|0,1,2,9+=|为可带前导为可带前导0的正整数的正整数=|为数字串为数字串最左推导最左推导:NNDN7ND7N27ND27N127D1270127最右推导最右推导:NNDNDDNDDDDDDD0DDD01DD012D0127NND|DD0|1|2|3|4|5|6|7|8|9本章小结本章小结例例3.已知文法已知文法GS=(A,B,a,b,c,d,P,S),其中其中P为为:分析分析SABaAbBa2Ab2Ban-1Abn-1BanbnBanbncBdanbnc2Bd2anbncm-1Bdn-1anbncmdmL(GS)=anbncmdm|n,m1该文法该文法所生成的语言是什么？所生成的语言是什么？AaAb|abBcBd|cdSAB本章小结本章小结3.求句型的短语、直接短语和句柄求句型的短语、直接短语和句柄(1)短语、直接短语和句柄是对某句短语、直接短语和句柄是对某句型而言的。型而言的。(2)短语总是句型的某个子串，它对应短语总是句型的某个子串，它对应子树未端结点形成的符号串。子树未端结点形成的符号串。(3)直接短语是某条规则右部，它对应直接短语是某条规则右部，它对应简单子树未端结点形成的符号串。简单子树未端结点形成的符号串。(4)最左边的直接短语是句柄。最左边的直接短语是句柄。本章小结本章小结例例1 已已知知文文法法GE：证证明明 E+T*F是是它它的的一一个个句句型型,指指出出这这个个句句型的短语型的短语 直接短语和句柄。直接短语和句柄。EE+TE+T*F短语短语:E+T*F、T*FE+T*F是它的一个句型是它的一个句型。画出该句型的语画出该句型的语法树法树:句柄句柄:T*F直接短语直接短语:T*FETFT+E*EE+T|E-T|TTT*F|T/F|FF(E)|i本章小结本章小结例例2已知文法已知文法GS：试找出符号串试找出符号串(a)和和(A(SaA)(b)的短语的短语 直接短语和句柄直接短语和句柄(如果有的话如果有的话)。S(AS)|(b)A(SaA)|(a)符号串符号串(a)不是不是文法的句型，因此文法的句型，因此它它没有没有短语短语 直接短语和句柄。直接短语和句柄。分析分析S(AS)(a)S)(a)/本章小结本章小结S(AS)(A(AS)(A(A(b)(A(SaA)(b)符号串符号串(A(SaA)(b)是文法的句型，是文法的句型，画出该句型的语法树如下图：画出该句型的语法树如下图：S(AS)|(b)A(SaA)|(a)本章小结本章小结从句型的语法树求从句型的语法树求 短语短语:(A(SaA)(b)(SaA)(b)(SaA)(b)直接短语：直接短语：(SaA)、(b)句柄：句柄：(SaA)SA(S)A(S)(S aA)b(S(AS)|(b)A(SaA)|(a)对于句型对于句型(A(SaA)(b)本章小结本章小结4文法二义性的判断文法二义性的判断一个文法存在某个句子一个文法存在某个句子对应两棵不对应两棵不同同的语法树或对应的语法树或对应两个不同的两个不同的最左最左（最（最右）右）推导推导，则该文法是二义性的。，则该文法是二义性的。本章小结本章小结例例1设有文法设有文法GS:SiSeS|iS|i试证明文法试证明文法GS有二义性。有二义性。分析分析因为对文法的句子因为对文法的句子iiiei有如下有如下两两棵不同的语法树与之对应棵不同的语法树与之对应，所以该文法，所以该文法是二义的是二义的本章小结本章小结SiSeS|iS|i句子句子iiiei对应下面两颗语法树：对应下面两颗语法树：SSie SiSiiSiSiSie Si本章小结本章小结NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|91.试证明文法试证明文法GN有二义性。有二义性。2.此文法所描述的语言是什么？此文法所描述的语言是什么？3.试写出另一文法试写出另一文法G使使L(G)=L(G)且且G是无二义性的。是无二义性的。例例2设有文法设有文法GN:本章小结本章小结分析分析因为对文法的因为对文法的句子句子10有两棵不同的有两棵不同的语法树与之对应，所语法树与之对应，所以该文法是以该文法是二义的二义的NES0D1NE01NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9本章小结本章小结该文法所描述的语言是所有该文法所描述的语言是所有无符号偶数无符号偶数的集合的集合(可以可以0开头开头)。改写后的文法改写后的文法GS为为:NSE|ESSD|DE0|2|4|6|8D0|1|2|3|4|5|6|7|8|9NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9本章完本章完