编译原理前后文无关文法和语言

编译原理前后文无关文法和语言第一页，共五十一页，编辑于2023年，星期五本章内容2.1语言的概述2.2文法和语言的定义第二页，共五十一页，编辑于2023年，星期五2.1语言的概述什么是语言自然语言(NaturalLanguage)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics)——易于形式化：严格语言是用来交换信息的工具——功能性描述第三页，共五十一页，编辑于2023年，星期五2.1语言概述语言的描述方法——现状自然语言：自然、方便-非形式化数学语言（符号）：严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。第四页，共五十一页，编辑于2023年，星期五2.1语言概述语言——形式化的内容提取单词(Token)：满足一定规则字符(Character)串句子(Sentence)：满足一定规则单词序列语言(Language)：满足一定条件的句子集合语言是字和组合字的规则——结构性描述例：一译开天第课今始编节上今天开始上第一节编译课第五页，共五十一页，编辑于2023年，星期五程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合程序(Program)：满足语法规则的语句序列语句(Sentence)：满足语法规则的单词序列单词(Token)：满足词法规则的字符串例变量=表达式if条件then语句while条件do语句call过程名(参数表)2.1语言概述第六页，共五十一页，编辑于2023年，星期五语言描述形式——文法语法——语句语句的组成规则描述方法：BNF（巴科斯范式：BackusNormalForm

）范式、语法(描述)图词法——单词单词的组成规则描述方法：BNF范式、正规式2.1语言概述第七页，共五十一页，编辑于2023年，星期五遗憾的是，对于自然语言来说，目前尚无能够完全刻划一语言全部句子的结构的方法。然而，对大多数程序设计语言来说，此问题已被解决。1960年，P.Naur&J.Backus（巴科斯--瑙尔）首先用BNF（Backus-Naur-Formal（范式））对ALGOL语言进行了描述。应指出，BNF成功地解决了程序设计语言的语法描述问题，但描述其语义，还必须借助自然语言。复习：巴科斯范式

（BNF--BackusNormalForm）第八页，共五十一页，编辑于2023年，星期五通常，可用如下方式表示或定义一种语言：（1）若语言的句子有限时，可用枚举法。

例如，只含两个句子的语言：

{“Iamateacher”,“Youarestudents”};（2）制定有限条规则，用于产生所要描述的语言的全部句子（可无限多），这些规则构成了该语言的文法。（3）建立一种装置（算法或过程），它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为自动机。第九页，共五十一页，编辑于2023年，星期五巴科斯范式（BNF

）例子：Thebigelephantatethepeanut.(大象吃花生）Thelittleboyranquickly.(小男孩跑得快）Themanhasadog.(这人有一条狗）

以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立的句子。

如何描述一个给定的句子在给定规则下是否成立呢？第十页，共五十一页，编辑于2023年，星期五①〈句子〉∷=〈主语〉〈谓语〉②〈主语〉∷=〈冠词〉〈形容词〉〈名词〉③〈冠词〉∷=the④〈形容词〉∷=big⑤〈谓语〉∷=〈动词〉〈宾语〉⑥〈动词〉∷=ate⑦〈宾语〉∷=〈冠词〉〈名词〉⑧〈名词〉∷=elephant|peanut

我们把这种描述语法规则方法称巴科斯范式，也称巴科斯--瑙尔范式(BackusNormalForm)，简称BNF。那么上面叙述<句子>的语法规则可写为：第十一页，共五十一页，编辑于2023年，星期五步骤推导所用规则1<句子><主语>〈谓语〉①2<冠词>〈形容词〉〈名词〉〈谓语〉②3the〈形容词〉〈名词〉〈谓语〉③4thebig〈名词〉〈谓语〉④5thebigelephant〈谓语〉⑧6thebigelephant〈动词〉<宾语>⑤7thebigelephantate<宾语>⑥8thebigelephantate〈冠词〉<名词>⑦9thebigelephantatethe<名词>③10thebigelephantatethepeanut⑧

可见句子thebigelephantatethepeanut成立。当然我们还可以推导出其它的句子，如thebigpeanutatetheelephant，在这里，我们只考虑句子的语法，而不考虑句子的语义。根据以上规则，可以推导出句子Thebigelephantatethepeanut.过程如下：第十二页，共五十一页，编辑于2023年，星期五用巴科斯范式描述语言能给研究问题带来很大方便。如下面9个句子都是正确的：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat

如果我们用巴科斯范式来描述上面9个句子只要几条规则就行了。①〈句子〉∷=〈主语〉〈谓语〉②〈主语〉∷=We|He|I③〈谓语〉∷=ran|ate|sat

可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。第十三页，共五十一页，编辑于2023年，星期五2.2文法和语言的定义本节主要内容基本概念和术语（字母表，符号串等）；规则；文法的定义；推导；句型与句子；文法和语言的等价转换等第十四页，共五十一页，编辑于2023年，星期五2.2.1基本概念和术语1。字母表（符号表、符号集）由若干元素（符号、字母）组成的有限非空集合。2。符号串用字母表中符号所组成的任何有限序列。符号串的长度=符号串中所含符号的个数

例：aba的长度为3。记为：|aba|=3空串

不含任何符号的符号串，记为

。显然，||=0。本课约定

用A、B、C、等表示字母表或符号串集；用a,b,c,S,T,U等表示符号；用s,t,u,x,y,z,,,等表示符号串。3。符号串的前（后）缀及子串

设,,，x是符号串，若x=，则称是x的子串；特别地，当=（=）时，称是x的前（后）缀。第十五页，共五十一页，编辑于2023年，星期五2.2.1

基本概念和术语4。符号串的连接和方幂

连接

设x,y是符号串，将y直接地拼接到x之后所得的新符号串称为x与y的连接，记为xy

注意，一般说来，xy不等于yx；但x=x=x

方幂

符号串x与其自身的n-1次连接称为x

的n

次方幂，记为第十六页，共五十一页，编辑于2023年，星期五2.2.1

基本概念和术语5。符号串集合的和与积 设A，B为两个符号串之集，定义

和

A+B（或AB）

={w|wA，或wB}

积

A•B（或AB）={xy|xA,y

B}显然，A+=+A=A；A=A=；{}A=A{}=A6。符号串集的方幂与闭包第十七页，共五十一页，编辑于2023年，星期五例{0,1}+={0，1，00，01，11，000，001，010，011，100，……}{a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc……}

例{0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…}{a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…}第十八页，共五十一页，编辑于2023年，星期五2.2.1

基本概念和术语当我们把字母（符号）表视为由长度为1的符号串构成的符号串集时，就可定义字母表上的连接、积、方幂等运算。例 A={a,b,c}第十九页，共五十一页，编辑于2023年，星期五2.2.2文法和语言的形式定义我们从“产生语言”的角度出发,讨论文法和语言的形式定义。产生语言 指制定出有限条规则，借助它们就能产生出些语言的句子。我们以几个英语句子构成的语言为例进行讨论。并设每个句子都是“主-谓-宾”结构。语法规则见右。其中，每个用<>括起来的部分是所要定义语言中的一个语法实体（称为语法单位、语法结构、语法范畴、语法变量等）。“::=”是用于定义语法结构的符号，其含义（并读作）“定义为”。语法规则也称为产生式(Production)①<句子>::<主语短语><动词短语>②<主语短语>::=the<名词>③<动词短语>::=<动词><宾语短语>④<宾语短语>::=<冠词><名词>⑤<名词>::=monkey⑥<名词>::=banana⑦<动词>::=eat⑧<动词>::=has⑨<冠词>::=the⑩<冠词>::=a第二十页，共五十一页，编辑于2023年，星期五

现在，我们讨论如何用上述规则推导出相应语言的全部句子。推导：从语言最大的一个语法范畴（本例中是<句子>）开始，反复用语法规则中“::=”

右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换语法范畴。每次替换称为一步（直接）推导，并用符号“”表示。例如，我们首先用规则①进行第一步推导(derivation)，就可得到<主语短语><动词短语>，记为：

<句子><主语短语><动词短语>

所得的符号串<主语短语><动词短语>含有两个语法范畴，可对其中任一个（例如对<动词短语>）进行新的推导（替换）：<句子><主语短语><动词短语> <主语短语><动词><宾语短语>重复上述过程，可得到一个推导序列（见下页）。第二十一页，共五十一页，编辑于2023年，星期五用语法规则进行推导所得的推导序列推导步骤所用规则 所得的符号串

1 ① <句子><主语短语><动词短语>2 ③ <主语短语><动词><宾语短语>3 ② the<名词><动词><宾语短语>

4

④ the<名词><动词><冠词><名词>

5 ⑤ themonkey<动词><冠词><名词>6

⑦ themonkeyeat<冠词><名词>

7 ⑩ themonkeyeata<名词>

8 ⑥ themonkeyeatabanana第二十二页，共五十一页，编辑于2023年，星期五2.2.2文法和语言的形式定义从前面的推导看，从<句子>出发，经8步推导得到了一个英语句子。故前面的推导称为长度为8的推导。若不关心推导的中间过程，可将从一符号串到另一符号串的推导用记号第二十三页，共五十一页，编辑于2023年，星期五规则的简化表示在前面的语法规则定义中，有些语法范畴（如<名词>、<动词>）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号“|”（读作‘或’）隔开。如<名词>、<动词>、<冠词>的定义规则可简记为<名词>::=monkey|banana<动词>::=eat|has<冠词>::=the|a第二十四页，共五十一页，编辑于2023年，星期五语法规则及其产生的语言前面的语法规则可以产生16个不同的句子，由这16个句子组成的集合，就是该规则所定义（或所产生）的语言。应指出，所产生的句子中，有些句子的含义是荒谬的（如thebananaeatamonkey和thebananaeatthebanana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。第二十五页，共五十一页，编辑于2023年，星期五2.2.2文法和语言的形式定义为得到文法的严格定义，我们对前面的规则进行如下的概括：第二十六页，共五十一页，编辑于2023年，星期五1、文法G的形式定义〈1〉文法G为一个四元组:

Ｇ=(ＶT，ＶN，Ｐ，Ｓ)

ＶT：终结符(Terminal)集ＶN：非终结符(Variable)集，ＶT∩ＶN=Φ

语法范畴——某个语言结构Ｓ：开始符号(StartSymbol)，S∈ＶN至少在产生式左侧出现一次规定：（1）VN

，VT，P是有穷非空集合；（2）VN∩VT＝（不含公共元素）第二十七页，共五十一页，编辑于2023年，星期五Ｐ：产生式(Product)集合

α→β，被称为产生式（定义式），读作：α定义为β。其中：

α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一个出现。

β∈(ＶT∪ＶN)*。

α称为产生式α→β的左部(LeftPart)，β称为产生式α→β的右部(RightPart)。第二十八页，共五十一页，编辑于2023年，星期五例：算术表达式的文法P:E→E+EE→E-EE→E*EE→E/EE→(E)E→idG=（{id，+，-，*，/，(，)}，{E}，P，E）约定：只写产生式。可简写为：

E→E+E|E-E|E*E|E/E|(E)|id第二十九页，共五十一页，编辑于2023年，星期五产生式的简写对一组有相同左部的产生式

α→β1，α→β2…，α→βn

可以简单地记为：

α→β1|β2|…|βn

读作：α定义为或者β1，或者β2，…，或者βn。并且称它们为α产生式。β1，β2，…，βn称为候选式(Candidate)。第三十页，共五十一页，编辑于2023年，星期五例、文法G=（VN，VT，P，S），其中：VN={S}，VT={0，1}，

P={S→0S1，S→01}。开始符号是SS0S100S11…0n-1S1n-10n1n

所以描述的语言为：

L={0n1n|n≥1}第三十一页，共五十一页，编辑于2023年，星期五例：文法G=（VN，VT，P，S）其中：VN={标识符，字母，数字}VT={a,b,c,…,x,y,z,0,1,…,9}S=<标识符>

P={<标识符>→<标识符><字母>|<标识符><数字>|<字母><字母>→a|b|…|z<数字>→0|1|…|9}

第三十二页，共五十一页，编辑于2023年，星期五1、文法的定义<2>文法的第二种表示法：上例1改为：G:S→0S1S→01<3>文法的第三种表示法：上例1改为：G[S]:S→0S1S→01一般约定，第一条产生式的左部是开始符号；用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。第三十三页，共五十一页，编辑于2023年，星期五2、直接推导的定义如：有文法G:E→E+E|E*E|(E)|iE(E)(E+E)(i+E)(i+i)

（称这样一串替换序列是从E推出(i+i)的一个推导)（1）定义：称A直接推出，即：A

仅当A→是一个产生式，且、(VN∪VT)*第三十四页，共五十一页，编辑于2023年，星期五例：G[S]:S→0S1,S→01

S0S100S11000S11100001111

可有：A=00S11,=000S111(相当A=S,=0S1)第三十五页，共五十一页，编辑于2023年，星期五A=S，＝0S1直接推导：S0S1A=0S1，

=00S11直接推导：0S100S11例：A＝0S1，=0011直接推导：0S10011使用规则：S→01＝0，＝1，A＝S，

＝01

规则：S→0S1＝，＝A＝S，

＝0S1

规则：S→0S1

＝0，＝1A＝S，

＝0S1

第三十六页，共五十一页，编辑于2023年，星期五若有1

n

，或1=n,则记作1

n

例：在例1中存在序列：1＝0S100S11000S11100001111＝n

记作：0S1000011110S100001111＋+**一样的若存在直接推导的序列：

1

2

3

…n(n>1)则称1推导n(或n规约到1

)，记1

n

+第三十七页，共五十一页，编辑于2023年，星期五（多步）推导α0α1α2…αn记为α0nαn

(恰用n步)α0+αn

（至少一步）

α0*αn

（若干步:零步或多步）第三十八页，共五十一页，编辑于2023年，星期五id+id*id的不同推导E→E+E|E*E|(E)|idE

E+E

id+E

id+E*E

id+id*E

id+id*idE

E+E

E+E*E

E+E*id

E+id*id

id+id*idE

E*E

E+E*E

E+id*E

id+id*E

id+id*id不做限制句型

(sententialForm)（归约）E*

id+id*id施于最右变量右句型/规范句型 (canonical~)(最左/规范归约)E+

id+id*id施于最左变量左句型(left-~)（最右归约）

E5

id+id*id第三十九页，共五十一页，编辑于2023年，星期五例：算术表达式

G[E]:E→E+T|TT→T*F|FF→(E)|a

可推导出：

EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a

表示文法G[E]能推导出用符号a,+,*,’(‘和’)’构成的所有算术表达式第四十页，共五十一页，编辑于2023年，星期五3、句型与句子句型：设G[S]是文法，若Sx，且xV*,则称x是文法G[S]的句型

句子：设G[S]是文法，若Sx，且xVT*,则称x是文法G[S]的句子（句子是句型的特殊）〖结论〗句子一定是句型，句型不一定是句子。例：G[S]:S→0S1,S→01S0S100S11000S11100001111S,0S1,00S11,000S111,00001111都是句型，只有00001111是G的句子**第四十一页，共五十一页，编辑于2023年，星期五4、文法G产生的语言定义：L(G)={xSx，S为文法开始符号，xVT*}

L(G)是文法G[S]描述的语言，也是该文法能推导出所有句子的集合。文法E→E+E|E*E|(E)|id可以派生出多少个句子？文法G的作用——语言的有穷描述以有限的规则描述无限的语言现象有限:产生式集合、终结符集合、非终结符集合无限：可以导出无穷多个句子（注：L也可是有穷）第四十二页，共五十一页，编辑于2023年，星期五例：G[S]:S→0S1,S→01L(G)＝｛0n1n

n1｝因为S0S100S11…0n1n重复利用规则S0S1第四十三页，共五十一页，编辑于2023年，星期五例：文法G:S→bAA→aA|a

考虑该文法定义的语言。

SbASbAbaAbaaSbAbaAbaaAbaaa…SbAbaA…ba…a

所以：L(G)={ban|n1}第四十四页，共五十一页，编辑于2023年，星期五例考虑文法G:E→(E)｜a

这个文法有1个非终结符E、3个终结符{(,),a}这个文法生成语言: