第2章 文法和语言

编译系统原理电气与信息学院

王艳§2.1字母表和符号串§2.2文法§2.3推导§2.4句型和句子§2.5语言§2.6递归规则与递归定义§2.7短语、简单短语和句柄§2.8语法树§2.9子树与短语§2.10由树构造推导过程§2.11文法的二义性§2.12有关文法的实用限制§2.13文法和语言的分类第二章文法和语言语言的组成语言：句子的集合句子：多个单词按一定规则组成单词：多个字符按一定规则组成程序设计语言编程语言程序的语句集合语句：多个单词按语法规则组成单词：多个字符按词法规则组成程序设计语言和自然语言的组成结构语言定义的方法枚举方法一个语言中的句子有限（非形式化描述）形式化描述方法（文法）一组数学符号（形式化描述）产生语言中全部句子的有限个规则自动机方法识别某字母表上所有符号串是否是该语言句子的一种装置（算法或过程）产生的观点识别的观点§2.1字母表和符号串2.1.1

字母表元素的非空有限集合，字母表中的每个元素称为符号，字母表也称符号表。例：={a，b，c}

={0，1}={a，b，c，+，*}

={begin,end,if,then,else}§2.1字母表和符号串字母表辨析：

例：1={aa，bb，cc}

2={a,a’,b,b’}3={a，b，a}4={}解析：1和2是字母表，体现了字母表的整体性和可辨认性；3中有相同的符号；4也不是字母表，因为要求字母表非空。§2.1字母表和符号串2.1.2

符号串由字母表中的0个或多个符号组成的任何有穷序列例：Σ={a,b}ε,a,b,aa,ab,aabba…都是上的符号串

空符号串：无任何符号的符号串,记为ε§2.1字母表和符号串2.1.3符号串及其集合的运算1.符号串的长度：x为字母表上的字符串，则长度指x中所含符号的个数，记为|x|。例：|abc|=|abccba|=|ε|=363§2.1字母表和符号串2.1.3符号串及其集合的运算2.符号串相等：x、y为上的两个符号串，当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。例：x=abbc，y=abbc，x’=ab，y’=ba则xy，x’y’=≠§2.1字母表和符号串2.1.3符号串及其集合的运算3.符号串的前缀和后缀：从符号串x的末尾删除0个或多个符号后得到的符号串称为x的前缀；从x的开头删除0或多个符号后得到的符号串称为x的后缀。例：设z=abc,z的前缀是ε，a，ab，abc；

z的后缀是ε，c，bc，abc。

§2.1字母表和符号串2.1.3符号串及其集合的运算4.符号串的子串：指从符号串x的开头和结尾删除0个或多个符号后得到的符号串。例：z=abc，其中b及前缀、后缀都是abc的子串。§2.1字母表和符号串2.1.3符号串及其集合运算5.字符串的连接：设x和y是两个字符串，则xy被称为符号串x与y连接。εx=xε=x(xy)z=x(yz)|xy|=|x|+|y|例：x=ST，y=abu，则xy=STabu，可看出|x|=2，|y|=3，|xy|=56.字符串A与B的乘积：设A和B为符号串集合，则

A与B的乘积定义为AB=xy|xA且yB例：若集合A=ab,cde集合B=0,1

则AB=ab0,ab1,cde0,cde1

对于空集合{ε}有{ε}A=A{ε}=A§2.1字母表和符号串2.1.3符号串及其集合运算7.符号串的幂运算：即把x重复写n次，记为z=xn。

例：若x=AB则:

x0=εx1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n>0)对于m,n≥0xmxn=xm+n(xm)n=xmn§2.1字母表和符号串2.1.3符号串及其集合运算8.集合的幂运算：设A为符号串集合，则A的幂运算定义为A0={ε}，A1=A，A2=AA，…,An=AAn-1=An-1Ax(n>0)

例：若A={a,b}则:

A0=εA1={a,b}A2={aa,ab,ba,bb}…§2.1字母表和符号串2.1.3符号串及其集合运算9.字符串集合的正闭包：设A为集合，则A+=A1∪A2∪…∪An，n>1例：若∑=0,1

则∑+=0,1,00,01,10,11,000,001,…

注：指定字母表A后，可用An表示A上所有长度为n的串的集合。§2.1字母表和符号串2.1.3符号串及其集合运算10.字符串集合的闭包(星闭包)：设A为集合，则A*=A0∪A1∪A2∪…∪An,n≥0A*可表示A上所有有穷长的串的集合；A*=A0∪A+A+=AA*=A*AA*=A+∪{ε}，A+=A*-{ε}例：若∑=0,1,则∑*=ε,0,1,00,01,10,11,…§2.1字母表和符号串2.1.3符号串及其集合运算

若A为某语言的基本字符集

A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B为单词集

B={begin,end,if,then,…,<标识符>,<常量>,……}

则BA*

。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C

为什么对符号、符号串、符号串集合以及它们的运算感兴趣？§2.2文法2.2.0文法的直观理解1.什么是文法

文法是对语言结构的定义与描述，即从形式上描述和规定语言结构，也称为语法。

例：句子：“我是大学生”。该句子的结构（称为语法结构）是由它的语法决定的。

如何定义该句子的语法结构呢？

——语法规则2.语法规则

通过建立一组规则（产生式），来描述句子的语法结构。规定用“::=”表示“由…组成”或“定义为…”。<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=你|我|他<名词>::=

王民|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词>§2.2文法2.2.0文法的直观理解3.由产生式推导句子推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。§2.2文法2.2.0文法的直观理解<句子>

<主语><谓语>

<代词><谓语>

我<谓语>

我<动词><直接宾语>

我是<直接宾语>

我是<名词>

我是大学生<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=你|我|他<名词>::=

王民|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词>推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。例：给定一组语法规则，考察一个句子：“我是大学生”的推导过程。4.语法树<句子><主语><谓语><代词><动词><直接宾语><代词>我大学生语法成分（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)是§2.2文法2.2.0文法的直观理解

定义:文法G[S]定义为一个四元组，

G[S]=（Vn，Vt，P，Z）

Vn

：非终结符号集

Vt

：终结符号集

P：产生式或规则的集合

Z：开始符号（识别符号）,S∈VN其中:①非终结符号：出现在产生式的左部或右部,且能推出符号或符号串，用来表示语言的语法成分。②终结符号：不出现在产生式的左部,且不能推出符号或符号串，是组成语言的基本单位。Vt∪Vn

是字母表。③产生式：产生式是一个有序对(α,β),通常写为:α::β

或αβ；读作“定义为”。§2.2文法2.2.1文法形式定义2型文法：上下文无关文法。产生式的左部都是非终结符，右部是终结符和非终结符组成的有穷符号串。这样只需给出产生式集合，并指定识别符即可。§2.2文法2.2.1文法形式定义例2-1形式化描述P14页文法

文法G=（Vn，Vt，P，Z）Vn={句子,主语,谓语,冠词,名词,动词,直接宾语}Vt={the,ate,banana,monkey}P:

Z：<句子><句子>→<主语><谓词><主语>→<冠词><名词><冠词>→the<谓语>→<动词><直接宾语><动词>→ate<直接宾语>→<冠词><名词><名词>→banana<名词>→monkey§2.2文法2.2.1文法形式定义<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=你|我|他<名词>::=

王民|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词>练习：

文法G=（VN，VT，P，Z）VN={句子,主语,代词,名词,谓语,动词,直接宾语}VT={你,我,他,农民,大学生,工人,英语,是,学习}P:Z：<句子>§2.2文法2.2.1文法形式定义<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=你|我|他<名词>::=

王民|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词><无符号整数>→<数字串>；<数字串>→<数字串><数字>；<数字串>→<数字>；<数字>→0；

<数字>→1；

…………<数字>→9；

例2-2：如下规则集，给出终结符号、非终结符和识别符号：§2.2文法2.2.1文法形式定义G=（VN，VT，P，S）VN＝{<无符号整数>,<数字串>,<数字>}VT={0,1,2,3,……9}Z：<无符号整数>（1）元符号“|”，表示或，用于具有相同左部的一系列规则。例如：<数字>→0；

<数字>→1；

…………<数字>→9；上述表示文法的方式称为BNF（巴克斯—诺尔范式）。EBNF为扩充的BNF表示，采用一些元符号来提高文法规则的表达能力。§2.2文法2.2.2文法的EBNF表示表示为：<数字>→0|1|2|3|4|5|6|7|8|9（2）元符号“<”和“>”，用于括起由中文字组成的非终结符或由多个字母组成的符号。例如：<数字>，<monkey>§2.2文法2.2.2文法的EBNF表示（3）元符号“{”和“}”，表示可重复性连接。表示符号串t可连接n~m次，而{t}表示符号串t可连接0到无穷次。*<无符号整数>→<数字>|<数字><数字>|<数字><数字><数字>*E→E+T|T*以字母开头，后面跟数字或字母的不超过8个字符的标识符*<无符号整数>→*E→T+{T}*<标识符>→<字母>（4）元符号“[”和“]”，[t]表示其中的符号串t可有可无。例如：<if语句>→if<布尔表达式>then<语句>[else<语句>]§2.2文法2.2.2文法的EBNF表示（5）元符号“（”和“）”，表示括号内的成分优先，常用于在规则中提取公因子。例如：U→xy|xw|…|xz可写成U→x（y|w|…|z）α→β是文法G的产生式，现有符号串xαy，其中xy是该文法的任意符号串（可为空），推导就是利用α→β，将xαy中α替换为β。xαyxβy，称xαy直接推导（产生）xβy，也称xβy直接归约到xαy。

例1：文法G[S]:S→0S1，S→01

有直接推导0S10011

§2.3推导2.3.1直接推导/直接规约例2：文法G[S]:S→0S1，S→01

有直接推导S0S1

§2.3推导2.3.1直接推导/直接规约例3：文法G[S]:S→0S1，S→01

有直接推导0S100S11

若存在直接推导序列

w0w1...wn，（n>0）

+

则记为w0

wn，称w0推导出（产生）wn，或wn归约到w0

。

§2.3推导2.3.2推导/规约

说明：当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在产生式左部，所以将在产生式左部出现的符号称为非终结符号。例：G[N]：N→ND|DD→0|1|2|3|4|5|6|7|8|9

NNDNDDND9N09D09109

§2.3推导2.3.2推导/规约+*

如果v

w，或v

w，则记作v

w

。

例：

S0S100S11000S11100001111

+

则有S00001111

*

S00001111§2.3推导2.3.2推导/规约例：无符号整数的文法G[{<无符号整数>]:<无符号整数>→<数字串>；

<数字串>→<数字串><数字>；

<数字串>→<数字>；

<数字>→0|1|2|…|9；

如整数10的推导过程：

<无符号整数><数字串><数字串><数字>

<数字串>0<数字>010§2.3推导2.3.2推导/规约§2.3推导2.3.3规范推导也叫最右推导，即每步推导只变换符号串中最右边的非终结符。xαyxβy，若y只包含终结符号或为空，那么这种推导称为规范推导，记作xαyxβy，其中y∈Vt*。若x只包含终结符或空，则称最左推导。若α0

αn的每一步都是规范的，那么α0

αn称为规范的。记作α0

αn。+++§2.4句型和句子1.句型

*有文法G[Z]，若Zx，则称x是文法G的句型。例：G[S]：S→0S1，S→01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111等

G的句子00001111,01等2.句子

对文法G[Z]，若Zx，且x∈VT*，则称x是文法G的句子。+§2.4句型和句子注意：

（1）句子是特色的句型

（2）规范推导产生的句型为规范句型

（3）每个句子都有一个规范推导

（4）并非每一个句型都有规范推导§2.5语言例：G[S]：S→0S1，S→01S0S100S110n-1S1n-10n1n

L(G)={0n1n|n≥1}

文法G生成的语言记为L(G(Z))，它是文法G(Z)的一切句子的集合:

L(G(Z))={x|Zx，且x∈VT*}+注意：给定一文法，就能从结构上唯一的确定其语言；给定一种语言，能确定其文法，但不唯一。例：G[A]:A→0RA→01R→A1L(G(A))={0n1n|n≥1}

G和G'是两个不同的文法，若L(G)=L(G'),

则G和G’为等价文法。§2.5语言

给定文法G[A]：A→bA|cc，下面的符号串中，为该文法句子的是：①cc②bcbc③bcbcc④bccbcc⑤bbbcc练习√√注意：

已知文法求语言，通过推导；

已知语言构造文法，全凭经验。已知句子L(G)={abna|n≥1}，构造文法。练习G1[S]：S→aBa，B→b|BbG2[S]：S→aBa，B→b|bB2.6.1递归规则§2.6递归规则与递归文法指在规则右部含有规则左部相同符号的规则，例如U→xUy；U→Uy称左递归规则；U→xU称右递归规则。2.6.2递归文法直接递归：包含至少一条递归规则间接递归：经过几步推导，造成文法的递归性§2.6递归规则与递归文法2.6.2递归文法递归文法：对文法中的任一非终结符号，若能建立一个推导过程，推导所得的符号串中又出现了该终结符号，则称文法是递归的，否则是非递归的。*递归文法使人们能用有穷的文法刻画无穷语言例：判定如下文法描述的语言是否是有穷的Z→aBaB→bB|b§2.7短语、简单短语和句柄对文法G[Z]，w=xuy是文法的一个句型。如

果有ZxUy且Uu，U∈Vn，u∈V+则称u

是句型

w相对于非终结符U的短语。如有Uu，则称u是句型w相对于非终结符U的直接短语，也称简单短语。一个句型的最左简单短语称为该句型的句柄。§2.7短语、简单短语和句柄例2-7：对于文法G[<无符号整数>]，确定句型<数字串1>的所有短语、简单短语和句柄推导过程：<无符号整数><数字串><数字串><数字><数字串>1（1）<无符号整数><无符号整数><无符号整数><数字串>1<数字串>1是相对<无符号整数>的短语（2）<无符号整数><数字串><数字串><数字串>1<数字串>1是相对<数字串>的短语（3）<无符号整数><数字串><数字><数字>11是相对<数字>的短语，简单短语，句柄§2.8语法树

设文法G=(VN,VT,P,Z)，若一棵树满足下列4个条件，则此树称作G的语法树(推导树或分析树）：每个结点都有一个标记，此标记是V的一个符号根的标记是Z如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式树的叶结点符号从左至右恰好构成句型推导过程用图表示，即语法树，也叫推导树§2.8语法树语法树的画法

方法：把开始符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。例如：推导SABAcBdAccddabccddSBBdbaAcdc§2.8语法树语法树的用途

用于描述句型和句子的语法结构。句型的推导过程对应于语法树的构造过程。例:G[S]:S→aAS|a A→SbA|SS|ba构造句型aabbaa的语法树

从左到右读出语法树的叶子标记连接成的文法符号串，为G[S]的句型。SSaAASbaaba§2.8语法树练习：<无符号整数><数字串><数字串><数字><数字串>3<数字串><数字>3<数字串>23<数字>23123无符号整数数字串数字串数字数字串数字数字123§2.9子树和短语子树：由该树的某个结点(子树的根)连同它所有的后裔构成，子树与短语一一对应。例:根据G[<无符号整数>]，找句子123的短语，简单短语和句柄子树1：树根<无符号整数>，短语123子树2：树根<数字串>，短语123子树3：树根<数字串>，短语12子树4：树根<数字串>，短语1子树5：树根<数字>，短语1，简单短语，句柄子树6：树根<数字>，短语2，简单短语子树7：树根<数字>，短语3，简单短语短语为123,12,1,2,3；简单短语1,2,3；句柄1。§2.10由树构造推导过程复习：最左推导和最右推导

如果在推导的任何一步αβ，其中

α、β是句型，都是对α中的最左

（右）非终结符进行替换，则称为最左

（右）推导。在形式语言中，最右推导常被称作规范

推导。由规范推导所得的句型称为规范

句型。§2.10由树构造推导过程从上到下：从根开始，由上逐层向下，用子结点代替父

结点。当一层中有两棵子树时，原则上选择

哪棵都可以，若每步都对右边树根进行替换，

则构造出的推导为规范推导。从下而上：由下而上逐层修剪子树末端结点，当有两棵

子树时，原则上选择哪棵都可以，若每次总

是修剪最左边的子树，称规范规约。规范推导与规范规约互为逆过程§2.10由树构造推导过程例：对下图语法树自底向上及自上向下建立推导过程<无符号整数><数字串><数字串><数字><数字串>3<数字串><数字>3<数字串>23<数字>23123123

<数字>23<数字串>23<数字串><数字>3<数字串>3<数字串><数字><数字串><无符号整数>§2.11文法的二义性

若一个文法存在某个句子或句型，它存在两棵不同的语法树，则称该句子或句型是二义性的，对应的文法也是二义性的。

例：有文法G[E]，E::=i|(E)|E*E|E+E，分析该文法是否具有二义性。EE+EE*EiiiEE*EiE+Eii考虑句子i*i+i的语法树该文法具有二义性§2.11文法的二义性练习:<语句>::=if<布尔表达式>then<语句>|if<布尔表达式>then<语句>else<语句>|<其它>说明该文法是二义性文法提示：if<布尔表达式>thenif<布尔表达式>then<语句>else<语句>§2.11语法树和二义性

以上是自顶向下来看文法的二义性，我们还可以自底向上来看文法的二义性。语法的二义性意味着句型的句柄不唯一。如句型E+E*i。EEE+EE*iEEE*EE+i§2.11文法的二义性

若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。EE*EiE+Eii§3.4语法树和二义性四、文法的二义性SifE1thenSifE2thenS1elseS2SifE1thenSelseS2ifE2thenS1EE+EE*Eiii§2.12有关文法的实用限制有害规则：形如U→U的产生式。会引起文法的二义性，若有，则删去。

例如存在U::=U，U::=a|b,则有两棵语法树：UaUUa§2.12有关文法的实用限制多余规则：指文法中任何句子的推导都不会用到的规则，若有，则删去。文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。§2.12有关文法的实用限制例：G[Z]：

1）Z→Aa 2)A→Ca|Bb 3)B→Ba|a 4)C→Cb 5)D→b

多余规则，C为不可终止非终结符多余规则，D为不可到达非终结符多余规则§2.12有关文法的实用限制

练习：G[S]：1)S→Be 2)B→Ce 3)B→Af 4)A→Ae 5)A→e 6)C→Cf 7)D→f

推不出终结符号串，为多余规则推不出终结符号串，为多余规则。C为不可终止的非终结符。D不在右部出现，为多余规则。D为不可到达的非终结符。§2.13文法的分类Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法0型语言或短语结构语言1型文法1型语言或上下文有关语言2型文法2型语言或上下文无关语言3型文法3型语言或正则（正规）语言§2.13文法的分类

对任一产生式α→β，都有α∈V+，β∈V*，即α，β均是V上的符号序列，但α不能为空，β可为空。1、0型文法(短语结构文法)说明：对产生式基本无限制例：文法G，其中VN={A,B,S}VT={0,1}P={S→0AB1B→0B→SA|01A1→SB1A0→S0B}§2.13文法的分类有如下形式规则：αUβ→αuβ，其中U∈Vn，α,β∈V*,u∈V+,左部可为符号序列，其中U为非终结符号且只有左右为α,β的环境下U可