第3章 文法和语言

第3章文法和语言3.0概述3.1形式语言基础3.2文法的直观理解3.3文法和语言的定义3.4文法的类型3.5语法树与二义性3.6句型的分析3.0概述显然，用高级语言编程比用低级语言来得方便，但要解决两个问题：1.计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目标程序的转换。2.用什么方法来精确定义高级语言，即怎样精确描述高级语言。要构造一个编译程序(翻译程序)，应深刻理解被编译的源语言的结构（即词法和语法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，就存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。对于自然语言来说，它们是定义在某个字母表上的句子的集合。对于程序语言来说，它们也是定义在某个字母表上的句子的集合。这里的句子，就是一个源程序。通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。这些语法成分统称为单词或单词符号。单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。“我是大学生”。是汉语的一个句子。〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉主语谓语用语法来描述：有了一组规则以后，按照如下方式用它们导出句子：开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成：〈句子〉〈主语〉〈谓语〉然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并使用规则〈主语〉∷=〈代词〉来处理，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉重复做下去:句子：“我是大学生”的全部动作过程是：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉

我〈动词〉〈直接宾语〉

我是〈直接宾语〉

我是〈名词〉

我是大学生

〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。语言概述语言是由句子组成的集合，或说是由一组符号串所构成的集合。汉语——所有符合汉语语法的句子的全体英语——所有符合英语语法的句子的全体程序设计语言——所有该语言的源程序的全体每个句子构成的规律研究语言每个句子的含义每个句子和使用者的关系研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax语义Semantics语用Pragmatics语法——表示构成语言句子的各个记号之间的组合规律。语义——表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用——表示在各个记号所出现的行为中，它们的来源、使用和影响。每种语言都具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。3.1形式语言基础基本概念:一、字母表和符号串1.字母表：符号的非空有限集合。例：={a，b，c}2.符号：字母表中的元素。例：a，b，c3.符号串：符号的有穷序列。例：a,aa,ac,abc，..特别地,空符号串：无任何符号的符号串,记为ε。

有字母表，定义：（1）ε是上的符号串；（2）若x是上的符号串，且a，则ax或xa是上的符号串；（3）y是上的符号串，当且仅当y可由（1）和（2）产生。二、符号串和符号串集合的运算4.符号串集合：由符号串构成的集合。符号串的形式定义

5.符号串相等：若x、y是集合上的两个符号串，则x＝y当且仅当组成x的每一个符号和组成y的每一个符号依次相等。

6.符号串的长度：x为符号串，其长度|x|等于组成该符号串的符号个数。例：x＝STV，|x|=3

特别地,|ε|=07.符号串的联接：若x、y是定义在Σ之上的符号串，且x＝ab，y＝bc，则x和y的联接xy＝abbc也是Σ上的符号串。注意：一般xy≠yx，而εx＝xε＝x例：A＝{a,b},B={c,d},AB=？符号串集合的乘积运算：令A、B为符号串集合，定义AB＝{xy|x∈A，y∈B}。

{ac，ad，bc，bd}

因为εx＝xε＝x，所以{ε}A=A{ε}=A注:{ε}为空串集。9.空集:不包含任何元素的集合称为空集合，记为Φ。即Φ={}。对任一集合A，有ΦA=AΦ=Φ。注：εΦ，即{ε}Φ。符号串集合的方幂有任一符号串集合A，定义:

A0={ε},A1=A,A2=AA,A3=AAA,…An＝An-1A=AAn-1＝AA…An个其中:n≥0符号串的方幂有任一符号串X，定义:X0=εX1=XX2=XXX3=XXX…Xn=XX…Xn个其中:n≥010.方幂运算：11.符号串集合的闭包运算：设A是符号串集合，定义A＋=A1∪A2∪A3∪……∪An∪…… 称为集合A的正则闭包。

A*=A0∪A1∪A2∪A3∪……∪An∪……=A0∪A＋

称为集合A的星闭包。例：A={x,y}A＋＝？

A*＝？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A1

A2

A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A0A1

A2

A3

为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B为单词集B={begin,end,if,then,else,for,…+,－,×,_/,(,),……}则BA*。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C3.2文法的直观理解1.什么是文法：

文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。例：有一句子：“我是大学生”。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的合法性？有穷语言无穷语言

2.语法规则：

我们通过建立一组规则（产生式），来描述句子的语法结构。规定用“::=”表示“由……组成”。<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=你|我|他<名词>::=王民|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词>由产生式推导句子：

<句子><主语><谓语><主语><谓语>

<代词><谓语> …………这种推导一直进行下去，直到所有带<>的符号都由终结符号替代为止。有了一组产生式之后，可以按照一定的方式用它们去推导或产生句子。

推导方法：从一个初始的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。<句子>

<主语><谓语>

<代词><谓语>

我<谓语>

我<动词><直接宾语>

我是<直接宾语>

我是<名词>

我是大学生<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=你|我|他<名词>::=王民|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词>推导方法：从一个初始的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。例：给定一组语法规则，考察一个句子：“我是大学生”的推导过程。上述推导可写成<句子>我是大学生+说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。(2)从一组产生式可推出不同的句子，如以上产生式还可推出“大学生是我”、“我学习英语”、“英语学习我”等句子，它们在语法上都正确，但在语义上不是都正确。所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。3.3.1文法的定义3.3文法和语言的形式定义定义1:文法是产生式的有穷集合,通常定义为四元组:G=（VN，VT，P，Z）

VN：非终结符号集

VT：终结符号集 P：产生式或规则的集合Z：开始符号（识别符号）Z∈VN其中:①产生式：产生式是一个有序对(U,x),通常写为:U::x或Ux；|U|=1|x|0②非终结符号：出现在产生式的左部,且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为VN

。③终结符号：不出现在产生式的左部,且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为VT

。V＝VN∪VT称为文法的字汇表产生式：U::xU∈VN,x∈V*P={<无符号整数>→<数字串>；<数字串>→<数字串><数字>；<数字串>→<数字>；

<数字>→0；

<数字>→1；

…………

<数字>→9；}Z=<无符号整数>；例：无符号整数的文法： G[<无符号整数>]=（VN，VT，P，Z） VN＝{<无符号整数>,<数字串>,<数字>} VT={0,1,2,3,……9}几点说明：产生式左边符号构成集合VN，且Z∈VN有些产生式具有相同的左部，可以合在一起例、<无符号整数>→<数字串>；<数字串>→<数字串><数字>|<数字>；<数字>→0|1|2|3|……|9文法的BNF表示元语言符号：::(即→)读为“定义为”或者“生成为”|读为“或者”

给定一个文法，实际只需给出产生式集合，并指定开始符号例:G[<无符号整数>]<无符号整数>→<数字串>；<数字串>→<数字串><数字>|<数字>；<数字>→0|1|2|3|……|9例3.6:用文法G1来定义下面的集合：L1={n|n是非负整数}。解题思路：显而易见，该集合不能用枚举法来定义。∵非负整数是一种数字串的集合，故离不开数字；不妨先定义：D→0|1|2|3|……|9显然DL1，若xL1，则xDL1。这样L1可按下法构造出来：N→DN→NDD→0|1|2|3|……|9∴有解：G1=（VN，VT，P，N）其中：VN={N，D}，VT={0，1，2，3，……，9}P：N→ND|D，D→0|1|2|3|……|9作业：§3练习（P48）3,4,5题3.3.2推导与归约定义2：直接推导：设有文法G，x＝αUβ，y＝αuβ,其中α、β∈V*,

，U∈VN,u∈V*,若U::u∈P，则xy

，即αUβαuβ。

x直接推导出y

。

换句话说，设x和y是符号串，若使用一次产生式可以从x变换出y，则称x直接推导出y(或者说y是x的直接推导），记为xy。若α＝β＝ε，有U::u，则Uu；称U直接推导出u。当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在产生式左部，所以将在产生式左部出现的符号称为非终结符号。例如：G[N]：N→ND|DD→0|1|2|3|4|5|6|7|8|9NNDNDDND9N09D09109

(6)

(1)

(3)(4)

(2)(5)

＋N

109定义3：+推导：x和y是符号串，若使用一次或多次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导），记为xy。＋例：则有：定义4：

*推导：x和y是符号串，若使用0次或多次产生式可以从x变换出y，则称x*推导出y(或者说y是x的*推导），记为xy。**N

109则有：*N

N或者说：若有直接推导序列：x=U0

U1

U2

……

Un=y，则x

y。+NNDNDDND9N09D09109

(6)

(1)

(3)(4)

(2)(5)

定义5：

最右推导：若符号串α中有两个以上的非终结符时，在推导的每一步坚持把α中的最右非终结符进行替换，称为最右推导（也称为规范推导）。

最左推导：若符号串α中有两个以上的非终结符时，在推导的每一步坚持把α中的最左非终结符进行替换，称为最左推导。定义6：推导的逆过程称之为归约。例：x

y,可称为x直接推导出y，也可称为y直接归约出x。＋x

y,可称为x推导出y，也可称为y归约出x。3.3.3语言的形式定义文法G[Z]所产生的所有句子的集合定义7：给定文法G[Z] （1）句型：x是句型

Zx,且x∈V*；**（2）句子：x是句子

Zx,且x∈VT*；*（3）语言：L（G[Z]）={x|Zx，x∈VT*}；即：句型是由文法开始符号推导出来的由终结符和非终结符组成的符号串。即：句子是由文法开始符号推导出来的由终结符组成的符号串。例：{abna|n≥1},构造其文法G1[Z]：Z→aBa, B→b|bBG2[Z]：Z→aBa, B→b|Bb定义8:G和G'是两个不同的文法，若L(G)=L(G'),

则G和G'为等价文法。编译感兴趣的问题是:给定串x和文法G,求xL(G)?x算法1算法2xL(G)?Gyn出错处理停机3.3.4递归文法1.递归产生式：产生式右部有与左部相同的符号 对于U→

xUy，称为递归产生式； 若x=ε,即U→

Uy，左递归产生式； 若y=ε,即U→

xU，右递归产生式；2.递归文法：文法G，存在U

∈VNifU

…U…,则G为递归文法；

ifU

U…,则G为左递归文法；

ifU

…U,则G为右递归文法；+++4.递归文法的优点：可用有穷条产生式，定义无穷语言例：对于前面给出的无符号整数的文法是有递归文法，用13条产生式就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条产生式呢？!3.左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）3.4文法分类

形式语言：用文法或自动机描述语法的语言。文法定义：乔姆斯基将所有文法都定义为一个四元组： G=（VN，VT，P，Z） VN：非终结符号集；

VT：终结符号集； P：产生式或规则的集合； Z：开始符号（开始符号）Z∈VN。语言定义：L（G[Z]）={x|Z

x,x∈VT*}。*文法和语言分类：0型、1型、2型、3型这几类文法的差别在于对产生式施加不同的限制。定义9：0型文法：对于文法G，P：α::=β

其中α∈V*

且至少含有一个非终结符，β∈V*。 0型语言：L0这种语言可以用图灵机(Turing)接受。 0型文法称为短语结构文法。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。定义10：1型文法：对于文法G，P：xαy::=xβy其中αVN，x、y、βV*且xβy≥xαy。1型语言：L1这种语言可以由一种线性界限自动机接受。 称为上下文敏感或上下文有关。也即α只有在x、y这样的上下文中才能把α改写为β。定义11：2型文法：对于文法G，P：α::=β； 其中α∈VN，β∈V*。2型语言：L2这种语言可以由下推自动机接受。称为上下文无关文法。也即把α改写为β时，不必考虑上下文。注意：2型文法与BNF表示相等价。（右线性）

P：A::=a； 或A::=Ba；其中A、B∈VN，a∈VT。3型语言：L3又称正则语言、正则集合， 这种语言可以由有穷自动机接受。3型文法又被称为正则文法。它是对2型文法进行进一步限制。（左线性）

P：A::=a； 或A::=aB；其中A、B∈VN，a∈VT。定义12：3型文法：对于文法G，3.5语法树与二义性文法3.5.1推导与语法树（1）语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。

结点：符号 根结点：开始符号 中间结点：非终结符 叶结点：终结符或非终结符

有向边：表示结点间的派生关系。

ZUVabcd

注意一个重要事实：文法所能产生的句子，可以用不同的推导原则（使用产生式顺序不同）将其推导出来。语法树的生成规律不同，但最终生成的语法树形状完全相同。某些文法有此性质，而某些文法不具此性质。(2)句型的推导及语法树的生成（自顶向下）给定G[Z]，句型w：可建立推导序列，Zw*可建立语法树，以Z为树根结点，每步推导时语法树向下生成一层分支，最终可生成一棵语法树，其树叶从左到右排列起来构成一句型w

。一般推导：

<无符号整数><数字串><数字串><数字><数字>1(1)(3)(5)(4)0(2)(3)子树与简单子树子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。简单子树：只有单层分枝的子树称为简单子树。

<无符号整数><数字串><数字串><数字><数字>1(1)(2)(3)(5)(4)0(4)树与推导句型推导过程

句型语法树的生长过程 由推导构造语法树1从开始符号开始，自左向右建立推导序列。由根结点开始，自上而下建立语法树。例：给定文法G[<无符号整数>]和句型10,考察语法树与推导过程。规范推导[<无符号整数>]<无符号整数><数字串><数字串>R<数字串><数字><数字串><数字>R<数字串>0R0<数字><数字>0R110R 由语法树构造归约2自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。从句型开始，自右向左地逐步进行归约，建立归约序列。规范归约与规范推导互为逆过程[<无符号整数>]<数字串><数字串><数字>0<数字>1<无符号整数><数字串>R<数字串><数字>R<数字串>0R<数字>0R10R定义14：通过规范推导或规范归约所得到的句型称为规范句型。不是规范推导在上例中，<数字><数字>就不是规范句型，因为：<无符号整数><数字串> <数字串><数字>

<数字><数字>RR3.5.2文法的二义性定义14.1：若对于一个文法的某一句子产对于同一种推导存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。换而言之，无二义性文法的句子对于同一种推导只有一棵语法树，尽管推导过程可以不同。下面举一个二义性文法的例子：G[E]: E::=E+E|E*E|(E)|i

VN

={E}

VT={+,*,(,),i}对于句子i＋i*i∈L（G[E]），存在不同的规范推导：EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(1)EE+EE+E*EE+E*iE+i*ii＋i*iRRRRR(2)EE*EE*iE+E*iE+i*ii＋i*iRRRRRG[E]: E::=E+E|E*E|(E)|i若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。由于无二义性文法比较简单，我们也可以采用另一种解决办法：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。<条件语句>::=If<布尔表达式>then<语句><条件语句>::=If<布尔表达式>then<语句>else<语句><语句>::=<条件语句>|<非条件语句>|…….例:Pascal语言条件语句的文法S→ifBthenS1S→ifBthenS1elseS1S1→id:=E其中：B为布尔表达式，E为表达式（产生式省略），id为标识符

显然，ifBthenifBthenS1elseS1是一个句型，若假设其中的B，S1均为终结符，则上述句型可以看作为一个句子，他对应两棵语法树（最左推导）：显然，ifBthenifBthenS1elseS1是一个句型，若假设其中的B，S1均为终结符，则上述句型可以看作为一个句子，它对应两棵语法树（最左推导）：SifBthenSifBthenSelseSSifBthenSifBthenSelseS即可理解为：ifBthen（ifBthenS1elseS1）也可理解为：ifBthen（ifBthenS1）elseS1因此该文法是二义性文法。3.6句型的分析任务：给定G[Z]:S∈VT*,判定是否有S

L(G[E])?

这是词法分析和语法分析所要做的工作，具体实现将在第四、五章中详细介绍。3.6.1句型的短语、简单短语和句柄定义15:给定文法G[Z],αuβ∈V+，为该文法的句型,若ZαUβ,且Uu,则u是句型αuβ相对于U的短语；其中U∈VN，u∈V+，α,β∈V*＋*直观理解：短语是前面句型中的某个非终结符所能推出的符号串。或短语定义:设G[Z]是给定文法,αuβ

∈V+，为该文法的句型,如果满足下面两个条件:①ZαUβ；②Uu；则称句型αuβ中的子串u是句型αuβ的短语。*＋定义17.任一句型的最左简单短语称为该句型的句柄。给定句型找句柄的步骤： 短语 简单短语句柄

注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语和多个简单短语，而句柄只能有一个。定义16:给定文法G[Z],αuβ∈V+

，为该文法的句型,若ZαUβ,且U

u,则u是句型αuβ相对于U的简单短语。其中U∈VN，u∈V+，α,β

∈V**例：给定文法G：E→T|E+T|E－TT→F|T*F|T／FF→i|(E)符号串（T+i）*i－F是文法G的一个句型，求其短语、简单短语和句柄。E

E－T

T－T

T－F

T*F－F

F*F－F(E)*F－F(T+T)*F－F(T+F)*F－F(T+i)*F－F(T+i)*i－F(T+i)*i－F解：短语有8个：1.E

E，E（T+i）*i－F则有：（T+i）*i－F2.E

T－F，T