第三章文法和语言

第3章文法和语言3.1文法的直观概念文法：描述语言的语法结构的形式规则（即语法规则）。1）描述单词单词的组成规则 BNF范式、正规式2）描述语句 语句的组成规则BNF范式、语法图3.1文法的直观概念例如：判断“我是大学生”是否为句子

文法如下：<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=我|你|他<名词>::=王明|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词>“我是大学生”的推导过程：<句子>-><主语><谓语>-><代词><谓语>->我<谓语>->我<动词><直接宾语>->我是<直接宾语>我是<名词>->

我是大学生

依次可以推导出句子“王明是大学生”、“我学习英语”等等文法作用（1）定义句子的结构；（2）用适当条数的规则把语言的全部句子描述出来，以有穷集合刻划无穷集合。3.2符号和符号串一、基本概念1.字母表符号的非空有穷集合用符号Σ或V表示。例如：Σ={a，b，c}和V={0，1}都是字母表相当于语言中的字符集2.符号语言中不可再分的基本单位3.符号串字母表中的符号组成的任何有穷序列。说明（1）符号的顺序，如ab与ba不同；（2）符号串长度：符号串内所含符号的个数其中不含任何符号的符号串称为空符号串ε，长度|ε|＝03.2符号和符号串4.句子字母表上符合某种规则构成的串包含单词和语句5.语言句子的集合3.2符号和符号串二、符号串的计算1.符号串的连接设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如：x=abc，y=def，则xy=abcdef2.符号串的方幂设x是符号串，把x自身连接n次得到的符号串z，即z=xx…xx，称为符号串x的方幂，记作z=xn，即把符号串x重复地写n次。例如：x0=ε，x1=x，x2=xx，x3=xxx…设x=ab则x3=ababab当n>0时，xn＝xxn-1=xn-1x3.2符号和符号串三、符号串集合的运算

连接（乘积）：设符号串集合A、B，则AB＝{xy|x∈A且y∈B}例如： A={a,b}，B={c,d}，则集合AB={ac,ad,bc,bd}{ε}A=A{ε}=A；一般而言，AB≠BA，但(AB)C=A(BC)注意：1)串集自身的连接称为串集的方幂2）A0={ε}3）字母表A的n次方幂表示字母表A上长度为n的字符串集3.2符号和符号串四、字母表的闭包和正闭包1.字母表Σ的闭包

Σ*＝Σ0∪Σ1∪Σ2∪…∪Σn

即由Σ上所有符号串组成的符号串集（包含空串）2.字母表Σ的正闭包Σ+＝Σ1∪Σ2∪…∪Σn

即由Σ上所有符号串组成的符号串集（不包含空串）显然有Σ*＝Σ0∪Σ+; Σ+=ΣΣ*=Σ*Σ对所有Σ，有ε∈Σ*。3.3文法和语言的形式定义规则，也称为产生式或生成式如一个产生式的形式是α→β（或α::=β)，其中“→”读为“是”或“定义为”；非终结符：在规则中用<>括起来非终结符用VN表示终结符语言中不可再分的字符串终结符用VT表示定义3.1文法G是一个四元式组G=(VT，VN，S，P)其中VT：终结符集合（非空、有穷）VN：非终结符集合（非空、有穷），且VT

VN=S：文法的开始符号，SVNP：产生式集合(非空、有穷)，产生式的形式是α→β

α和β属于(VT

VN)*开始符S至少必须在某个产生式的左部出现一次。3.3文法和语言的形式定义例：文法G=（VN，VT，P，S）VN＝{标识符，字母，数字}，VT＝{a,b,c,…,x,y,z,0,1,…,8,9}

P={

<标识符>→<字母>|<标识符><字母>|<标识符><数字><字母>→a|b|c|…|x|y|z<数字>→0|1|2|…|8|9

}S=<标识符>注意：有时不用将文法G的四元组显示的表示出来，而只写产生式约定：第一个产生式的左部是开始符号可将G写成G[S]，S为文法G的开始符号下面是一个文法的等价写法1）G={{S,A},{a,b},P,S}其中P：S->aAbA->abA->aAbA->ε2）G:S->aAbA->abA->aAbA->ε3）G[S]:S->aAbA->abA->aAbA->ε4）G[S]:A->aAb|ab|εS->aAb

有关推导的定义1、直接推导若αAβ直接推导出αγβ，即αAβ=>αγβ，当且仅当A→γ是一个产生式，且α、β∈(VN∪VT)*<注>符号‘=>’指推导一步，即推导每前进一步总是引用一条规则（产生式）2、长度为n（n≥1）的推导若存在直接推导序列a0a1…an，则称a0可推导出an。a0an表示：从a0出发经过一步或若干步，可推导出an。3、长度为n（n≥0）的推导a1an表示：从a1出发经过0步（a1＝an）或若干步，可推导出an。例：文法G：<标识符>→<字母>|<标识符><字母>|<标识符><数字><字母>→a|b|c|…|x|y|z<数字>→0|1|2|…|8|9句型、句子、语言例：证明终结符号串(i*i+i)是文法G：E→E+E|E*E|(E)|i的一个句子证明：∵E=>(E)=>(E+E)=>(E*E+E)=>(i*E+E)=>(i*i+E)=>(i*i+i)是从开始符号E到(i*i+i)的一个推导。其中E、(E)、(E+E)、(E*E+E)、(i*E+E)、(i*i+E)、(i*i+i)都是这个文法的一个句型1.句型：设G[S]是一个文法，S是它的开始符号，若Sα,则称α是文法G[S]的句型。2.句子：仅含终结符的句型是一个句子，即Sα，α∈VT*,则α是句子。3.语言：文法G所产生的句子的全体是一个语言，记作L(G)L(G)={α|Sα,且α∈VT*}语言的例子例：文法G2：A→bA|cc，证明cc、bcc、bbcc、…属于L(G2)。证明：VT={b,c}，VN={A}，S=AAcc，AbAbcc，AbAbbAbbcc……∴cc、bcc、bbcc、……是属于L(G2)的例：文法G[S]为(1)S→0S1；(2)S→01,G[S]的语言是什么。解：通过对第一个产生式使用n-1次，然后使用第二个产生式一次，得到：S0S100S11……0n-1S1n-10n1n因此L(G)={0n1n|n≥1}

文法的等价若L(G1)=L(G2)，则称文法G1和G2是等价的例如:文法G1=(VN,VT,P,S)，VN={S}，VT={0,1}，P由下列产生式组成：

(1)S→0S1；(2)S→01；

文法G2=(VN,VT,P,S)，VN={A,R}，VT={0,1}，P由下列产生式组成：(1)A→0R;(2)A→01;(3)R→A13.4文法的类型乔姆斯基建立的形式语言对计算机科学的发展具有深刻的意义。他把文法分成四种类型：0型、1型、2型和3型。它们的差别在于对产生式施加不同的限制。0型文法（或称短语文法）

G=(VN,VT,P,S)是0型文法是指：若它的每个产生式α→β是这样一种结构:

α∈(VN∪VT)*且至少含有一个非终结符，β∈(VN∪VT)*。0型文法又称为短语文法。

0型文法的能力相当于图灵机（计算机的一种简单的理论模型）。1型文法（或称上下文有关文法）如果对0型文法分别加以以下的限制，则可得到1型文法。设G=(VN,VT,P,S)为一文法，若G的任何产生式α→β均满足|α|≤|β|(指符号串的长度)，仅仅S→ε例外。上下文有关就是对非终结符进行替换时必须考虑上下文例如：1型文法G的产生式也可写成αAβ→αγβ，其中α、β、γ都在(VN∪VT)*中，且γ≠ε，A∈VN

，则说明了非终结符A必须在α、β这样一个上下文环境中才可以替换。

2型文法（或称上下文无关文法）设G=(VN,VT,P,S)为一文法，若G的任何产生式形似α→β，其中α∈VN，β∈(VN∪VT)*。例：G=({S,A,B},{a,b},P,S)，其中P由下列产生式组成S→aB|bAA→a|aS|bAAB→b|bS|Abb例：G=(VN,VT,P,S)，VN={S}，VT={0,1}，P由下列产生式组成：

(1)S→0S1；(2)S→01；

上下文无关文法的说明上下文无关，顾名思义就是非终结符的替换可以不必考虑上下文。由于这种文法对程序已基本可以描述，因此，上下文无关文法常简称为文法。

3型文法（或称正规文法）设G=(VN,VT,P,S)为一文法，若G的任何产生式A→α或A→αB，其中A、B∈VN，α∈VT*。例：文法G=({S,A,B},{0,1},P,S)，其中P由下列产生式组成S→0A|1B|0A→0A|1B|0SB→1B|1|0例：设G=(VN,VT,P,S)，VN={S,B,E}，VT={a,b,e}，P由下列产生式组成：(1)S→aSBE；(2)S→aBE;(3)EB→BE;(4)aB→ab;(5)bB→bb;(6)bE→be;(7)eE→ee;判断以下文法属于哪类文法？3.5上下文无关文法及其语法树一、语法树（推导树）直观定义：用图表示上下文无关文法句型推导的直观方法。2.形式定义给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之相关联的语法树，这棵语法树满足以下4个条件：（1）根结点由开始符号S所标记；（2）每个结点都有一个标记，此标记是V(即VN∪VT)的一个符号；（3）若结点n至少有一个除它自己以外的子孙结点，并且有标记A，则A在VN中；（4）如果结点n的直接子孙，从左到右的次序是结点n1,…,nk，其标记为A1,A2,…,Ak，那么A->A1A2…Ak一定是P中的一个产生式。从根结点S开始推导，当非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生出下一代新结点，候选式中自左向右的每个符号对应一个新结点，并用这些符号标记其相应的新结点。每个新结点与其父结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的末端结点自左向右排列起来就是一个句型。语法树构造的过程E(根)（E）E++EE*Eiii层次12345例1文法G=({E},{+,*,i,(,)},P,E)，其中P为：E→E+E|E*E|(E)|i对该文法关于(i*i+i)的推导的语法树如下所示：例2：G=（{S，A}，{a,b},P,S),其中P为：(1)S→aAS(2)A→SbA(3)S→a(4)A→ba

求文法G的句型aabbaa的推导树。最左推导/最右推导/规范句型最左推导是指：任何一步α=>β都是对α中的最左非终结符进行替换。同样，可定义最右推导（又称规范推导）：任何一步α=>β都是对α中的最右非终结符进行替换。由规范推导所得到的句型称为规范句型。注意：从一个句型到另一个句型的推导过程往往是不唯一的。例如E+Ei+i（a）E+E=>E+i=>i+i——最右推导（b）E+E=>i+E=>i+i——最左推导一个句型是否只对应唯一的一棵语法树？例如对于文法G[E]：E→E+E|E*E|(E)|i，对于句子(i*i+i)存在语法树：E(根)（E）E++EE*EiiiE(根)（E）E*EE+Eiii定义：一个文法的某个句子对应两棵不同的语法树，则这个文法是二义的。或一个文法的某个句子有两个不同的最左（右）推导，则这个文法是二义的。二义性

二义性其它问题人们已证明，二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切地判断一个文法是否是二义的。我们所能做的就是为无二义性寻找一些充分条件例如对文法G[E]：E→E+E|E*E|(E)|i修改，规定运算符“+”与“*”的优先关系和结合规则，设“*”的优先性高于“+”，且服从左结合。G’:E→T|E+TT→F|T*FF→(E)|i3.6句型的分析句型分析的任务就是按文法的产生式，识别输入的符号是否是该文法的句型。我们把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。分析算法又分为：从左到右分析算法；从右到左分析算法；自上而下的分析法自下而上的分析法3.6.1自上而下的分析法基本思想：从文法的开始符号出发，反复使用各种产生式，寻找“匹配”输入符号串的推导。即对任何输入符号串，从文法的开始符号（根结）出发，自上而下地为输入串建立一棵语法树，直到语法树结果正好是输入的符号串为止。例如：文法G[S]:S→xAyA→**|*，识别输入串x*y是否是该文法的一个句子。解：SSSSxAy(2)SSSxAy(3)*(1)缺陷关键：回溯问题；（∵其分析过程是一种试探过程）回溯问题是从各种可能的候选式中任选一个，进行推导后发现该候选式是错误的，则退回去重新选择候选式的方式。例如上例中的(3)。SSSxAy(3)—选用第1个候选式*回溯的产生使算法代价极高，效率很低。*3.6.2自下而上的分析法基本思想：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。即从语法树的末端开始，步步向上“归约”，直到根结。归约：若V=γαδ，W=γβδ，α→β是文法的产生式，如有V=>W，则W直接归约到V。例：文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d识别abbcde是否为文法S的一个句子。解题思想：扫描abbcde，从中找出一个子串，该子串与某一产生式的右部相匹配。解：abbcde(1)abbcdeAA(2)abbcdeAA(3)abbcdeAA(4)BabbcdeAA(5)BAS例：文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d自下而上分析法存在的问题可归约串的问题；该分析的每一步就是从当前串中找一个子串（称“可归约串”），将它归约到某个非终结符号

自下而上分析法的关键就是找哪个子串是“可归约串”，哪个不是“可归约串”。例：上例中的(3)abbcdeAA(3)—用产生式(2)而非(3)，则不能归约到S因此必须精确定义“可归约串”

3.6.3句型分析的有关问题在自上而下的分析方法中，存在的缺陷是“回溯”，如何确定用哪个右部代替左部？在自下而上的分析方法中，解决的关键问题是“可归约串”。短语、直接短语、句柄1、短语：令文法G，开始符号为S，αβδ是G的句型（即Sαβδ），如果SαAδ且Aβ，则称β是句型αβδ相对于非终结符A的短语。如果有A=>β，则称β是句型相对于规则A→β的直接短语。3、句柄一个句型的最左直接短语称为该句型的句柄。解题方法例：文法G[E]:E→T|E+TT→F|T*FF→(E)|i证明i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。证明：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i接上例语法树：EE+TTT*FFFi3i1i2第1层i1+i2*i3—相对于E第2层i1—相对于E;i2*i3—相对于T第3层i1,i2—相对于T;i3—相对于F第4层i1,i2—相对于F(F→i直接短语)第5层i+i*i是G的一个句型，其中i1,i2,i3,i2*i3,i1+i2*i3都是句型i1+i2*i3的短语，且i1,i2,i3为直接短语，i1为句柄分析说明(2)作为“短语”的两个条件是不可缺少的，仅仅有Aβ，未必意味着β就是句型αβδ的一个短语，因为还需要有SαAδ这个条件。例如：上例中有Ei1+i2，但i1+i2并不是该句型的一个短语，因为不存在从E（开始符号）到E*i3的推导。(1)短语、直接短语、句柄是针对某一句型（Sα）而言的;3.7有关文法实用中的一些说明在实际应用中对文法提出一些限制对文法进行扩充3.7.1有关文法实用限制在实用中，主要是在文法中不得含有有害规则和多余规则。1、不含有害规则有害规则是指形如P→P的产生式，因为这样的产生式除了引起二义外，没有任何用处。2、不含多余规则(1)不可到达的即文法中的某些非终结符不在任何规则的右部出现，则任何句子推导不可能用到它。也就是说对非终结符P，不存在SαPβ，α,β∈

(VN∪VT)*

3.7.1有关文法实用限制(2)不可终止的即文法中的某些非终结符不能够从它推出终结符串。也就是说对非终结符P，不存在Pt，t∈

VT*

若文法均满足以上两个条件，则称这个文法为简化了的文法。文法G[S]：

(1)S→Be

(2)B→Ce

(3)B→Af

(4)A→Ae

(5)A→e

(6)C→Cf

(7)D→f（7）、（6）、（2）多余规则3.7.2上下文无关文法的ε规则自学例1：证明文法G[E]是二义的:(1)E→EOE|(E)|v|d(2)O→+|*

3.8典型例题例1：证明文法G[E]是二义的:(1)E→EOE|(E)|v|d(2)O→+3.8典型例题3.8典型例题例2：考虑以下语言L1={anb2ncm|n,m>0}L2={anbmc2m|n,m>0}通过分别给出上述语言的文法来证明这些语言都是上下文无关