《编译原理前后文无关文法和语言精选文档.ppt》由会员分享，可在线阅读，更多相关《编译原理前后文无关文法和语言精选文档.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理前后文无关文法和语言本讲稿第一页，共五十一页本本章章内内容容2.1语言的概述语言的概述2.2文法和语言的定义文法和语言的定义本讲稿第二页，共五十一页2.1语言的概述语言的概述u什么是语言什么是语言自然语言自然语言(NaturalLanguage)是人与人的通讯工具是人与人的通讯工具语义语义(Semantics):环境、背景知识、语气、二义性环境、背景知识、语气、二义性难以形式化难以形式化计算机语言计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具严格的语法严格的语法(Grammar)、语义、语义(Semantics)易于易于形式化：严
2、格形式化：严格语言是用来交换信息的工具语言是用来交换信息的工具功能性描述功能性描述本讲稿第三页，共五十一页2.1语言概述语言概述u语言的描述方法语言的描述方法现状现状自然语言自然语言：自然、方便：自然、方便-非形式化非形式化数学语言数学语言（符号）：严格、准确（符号）：严格、准确-形式形式化化形式化描述形式化描述高高度度的的抽抽象象，严严格格的的理理论论基基础础和和方方便便的计算机表示。的计算机表示。本讲稿第四页，共五十一页2.1语言概述语言概述u语言语言形式化的内容提取形式化的内容提取单词单词(Token)：满足一定规则字符：满足一定规则字符(Character)串串句子句子(Sentenc
3、e)：满足一定规则单词序列：满足一定规则单词序列语言语言(Language)：满足一定条件的句子集合：满足一定条件的句子集合u语言是字和组合字的规则语言是字和组合字的规则结构性描述结构性描述例：一译开天第课今始编节上例：一译开天第课今始编节上今天开始上第一节编译课今天开始上第一节编译课本讲稿第五页，共五十一页u程序设计语言程序设计语言形式化的内容提取形式化的内容提取程序设计语言程序设计语言(ProgrammingLanguage)：组成：组成程程序的所有语句的集合序的所有语句的集合程序程序(Program)：满足语法规则的语句序列：满足语法规则的语句序列语句语句(Sentence)：满足语法规
4、则的单词序列：满足语法规则的单词序列单词单词(Token)：满足词法规则的字符串：满足词法规则的字符串u例例变量变量=表达式表达式if条件条件then语句语句while条件条件do语句语句call过程名过程名(参数表参数表)2.1语言概述语言概述本讲稿第六页，共五十一页u语言描述形式语言描述形式文法文法语法语法语句语句语句语句的的组成规则组成规则描述方法：描述方法：BNF（巴科斯范式：巴科斯范式：BackusNormalForm ）范式范式、语法语法(描述描述)图图词法词法单词单词单词单词的组成规则的组成规则描述方法：描述方法：BNF范式范式、正规式正规式2.1语言概述语言概述本讲稿第七页，共
5、五十一页u遗憾的是，对于遗憾的是，对于自然语言自然语言来说，目前尚无能够完全刻划一语言全来说，目前尚无能够完全刻划一语言全部句子的结构的方法。部句子的结构的方法。u然而，对大多数然而，对大多数程序设计语言程序设计语言来说，此问题已被解决。来说，此问题已被解决。1960年，年，P.Naur&J.Backus（巴科斯巴科斯-瑙尔瑙尔）首先用）首先用BNF（Backus-Naur-Formal（范式）对（范式）对ALGOL语言进行了描述。应指出，语言进行了描述。应指出，BNF成成功地功地解决了程序设计语言的语法描述问题解决了程序设计语言的语法描述问题，但描述其语义，但描述其语义，还必须借助自然语言。
6、还必须借助自然语言。复习：巴科斯范式复习：巴科斯范式（BNF-BackusNormalForm）本讲稿第八页，共五十一页通常，可用如下方式表示或定义一种语言：通常，可用如下方式表示或定义一种语言：（1）若语言的句子）若语言的句子有限时有限时，可用，可用枚举法枚举法。例如，只含两个句子的语言：例如，只含两个句子的语言：“Iamateacher”,“Youarestudents”;（2）制定）制定有限条规则有限条规则有限条规则有限条规则，用于产生所要描述的语言的全部，用于产生所要描述的语言的全部句子（可无限多），这些规则构成了该语言的文法。句子（可无限多），这些规则构成了该语言的文法。（3）建立一
7、种）建立一种装置（算法或过程）装置（算法或过程）装置（算法或过程）装置（算法或过程），它以某字母表上的符它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此号串为输入，判别该符号串是否为所描述语言的句子。此装置称为装置称为自动机。自动机。本讲稿第九页，共五十一页巴科斯范式巴科斯范式 （BNFBNF ）例子：例子：1.1.The big elephant ate the peanut.(The big elephant ate the peanut.(大象吃花生大象吃花生）2.2.The little boy ran quickly.(The little boy ran qui
8、ckly.(小男孩跑得快）小男孩跑得快）3.3.The man has a dog.(The man has a dog.(这人有一条狗）这人有一条狗）以上都是符合英语语法规则的句子，即它们是在以上都是符合英语语法规则的句子，即它们是在英语英语语法规则语法规则中成立的中成立的句子句子。如何描述一个给定的如何描述一个给定的句子句子在给定规则下是否成立呢？在给定规则下是否成立呢？本讲稿第十页，共五十一页句子句子=主语主语谓语谓语 主语主语=冠词冠词形容词形容词名词名词 冠词冠词=the 形容词形容词=big谓语谓语=动词动词宾语宾语动词动词=ate宾语宾语=冠词冠词名词名词 名词名词=elepha
9、nt|peanut我们把这种描述语法规则方法称巴科斯范式，也称我们把这种描述语法规则方法称巴科斯范式，也称巴科巴科斯斯-瑙尔范式瑙尔范式(BackusNormalForm)，简称，简称BNF。那么上面叙述那么上面叙述的的语法规则语法规则可写为：可写为：本讲稿第十一页，共五十一页步骤步骤推导推导 所用规则所用规则1谓语谓语2形容词形容词名词名词谓语谓语3the形容词形容词名词名词谓语谓语4thebig名词名词谓语谓语5thebigelephant谓语谓语6thebigelephant动词动词7thebigelephantate8thebigelephantate冠词冠词9thebigelepha
10、ntatethe10thebigelephantatethepeanut可见句子可见句子thebigelephantatethepeanut成立成立。当然我们还可以推导出其它的句子，如当然我们还可以推导出其它的句子，如thebigpeanutatetheelephant，在这里，我们只，在这里，我们只考虑句子的考虑句子的语法语法，而不考虑句子的，而不考虑句子的语义语义。根据以上根据以上根据以上根据以上规则规则规则规则，可以，可以，可以，可以推导推导推导推导出句子出句子出句子出句子 The big elephant ate The big elephant ate the peanut.the
11、peanut.过程如下过程如下过程如下过程如下：本讲稿第十二页，共五十一页用用巴科斯范式巴科斯范式描述描述语言语言能给研究问题带来很大方便。能给研究问题带来很大方便。如下面如下面9个句子都是正确的：个句子都是正确的：WeranHeranIranWeateHeateIateWesatHesatIsat如果我们用巴科斯范式来描述上面如果我们用巴科斯范式来描述上面9个句子只要个句子只要几条规则几条规则就行了。就行了。句子句子=主语主语谓语谓语 主语主语=We|He|I谓语谓语=ran|ate|sat可见，如果一个语言有可见，如果一个语言有无穷多个句子无穷多个句子，那么用上述规则来描述，那么用上述规则
12、来描述更有实际意义更有实际意义.它用它用一组规则一组规则来代替来代替枚举法枚举法，用，用有穷来描述无限有穷来描述无限。本讲稿第十三页，共五十一页2.2文法和语言的定义文法和语言的定义本节主要内容本节主要内容基本概念和术语（字母表，符号串等）；基本概念和术语（字母表，符号串等）；规则；规则；文法的定义；文法的定义；推导；推导；句型与句子；句型与句子；文法和语言的等价转换等文法和语言的等价转换等本讲稿第十四页，共五十一页2.2.1 2.2.1 基本概念和术语基本概念和术语1。字母表（符号表、符号集）字母表（符号表、符号集）由若干元素（符号、字母）由若干元素（符号、字母）组成的有限非空集合。组成的有
13、限非空集合。2。符号串符号串用字母表中符号所组成的任何有限序列。用字母表中符号所组成的任何有限序列。符号串的长度符号串的长度=符号串中所含符号的个数符号串中所含符号的个数例：例：aba的长度为的长度为3。记为：。记为：|aba|=3 空串空串不含任何符号的符号串，记为不含任何符号的符号串，记为。显然，。显然，|=0。本课约定本课约定用用A、B、C、等表示字母表或符号串集；用等表示字母表或符号串集；用a,b,c,S,T,U等表等表示符号；用示符号；用s,t,u,x,y,z,等表示符号串。等表示符号串。3。符号串的前（后）缀及子串符号串的前（后）缀及子串设设,，x是符号串，若是符号串，若x=，则称
14、，则称 是是x的的子串子串；特别地，当特别地，当=（=）时，称）时，称 是是x的的前（后）缀前（后）缀。本讲稿第十五页，共五十一页2.2.1 基本概念和术语4。符号串的连接和方幂符号串的连接和方幂 连接连接 设设x,y是符号串，将是符号串，将y直接地拼接到直接地拼接到x之后所得的新符之后所得的新符号串称为号串称为x与与y的连接，记为的连接，记为xy 注意，一般说来，注意，一般说来，xy 不等于不等于 yx；但；但 x=x =x 方幂方幂 符号串符号串x与其自身的与其自身的n-1次连接称为次连接称为x的的n次方幂，次方幂，记为记为本讲稿第十六页，共五十一页2.2.1 基本概念和术语5。符号串集合
15、的和与积符号串集合的和与积设设A，B为两个符号串之集，定义为两个符号串之集，定义和和A+B（或（或A B）=w|w A，或，或 w B积积AB（或（或 AB）=xy|x A,y B显然，显然，A+=+A=A；A=A=；A=A=A6。符号串集的方幂与闭包符号串集的方幂与闭包本讲稿第十七页，共五十一页例例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
16、，b，c，d*=，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc，本讲稿第十八页，共五十一页2.2.1 基本概念和术语u当我们把字母（符号）表视为由长度为当我们把字母（符号）表视为由长度为1的符号串构成的符号的符号串构成的符号串集时，就可定义字母表上的串集时，就可定义字母表上的连接、积、方幂连接、积、方幂等运算。等运算。u例例A=a,b,c本讲稿第十九页，共五十一页2.2.2 文法和语言的形式定义 我们从我们从“产生语言产生语言”的角度出发的角度出发,讨论讨论文文法和语言的形式定义法和语言的形式定义。u产生语言产生语言指制
17、定出有限条规则，借指制定出有限条规则，借助它们就能产生出些语言的句子。助它们就能产生出些语言的句子。u我们以几个英语句子构成的语言为例进行我们以几个英语句子构成的语言为例进行讨论。并设每个句子都是讨论。并设每个句子都是“主主-谓谓-宾宾”结结构。构。u语法规则见右。其中，每个用语法规则见右。其中，每个用括起括起来的部分是所要定义语言中的一个来的部分是所要定义语言中的一个语法实语法实体体（称为语法单位、语法结构、语法范（称为语法单位、语法结构、语法范畴、语法变量等）。畴、语法变量等）。“:=:=”是用于定是用于定义语法结构的符号，其含义（并读作）义语法结构的符号，其含义（并读作）“定义为定义为”
18、。语法规则也称为产生式语法规则也称为产生式(Production)Production):=the:=:=:=monkey:=banana:=eat:=has:=the:=a本讲稿第二十页，共五十一页 现在，我们讨论如何用上述规则现在，我们讨论如何用上述规则推导推导出相应语言的全出相应语言的全部部句子句子。u推导推导：从语言最大的一个：从语言最大的一个语法范畴语法范畴（本例中是（本例中是 ）开始，反复用）开始，反复用语法规则中语法规则中“:=:=”右侧的符号串取代其左侧符号，直到所得的符右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换号串中不再含有可被替换语法范畴语法范畴。每次替
19、换称为一步（直接）。每次替换称为一步（直接）推导推导，并用符号，并用符号“”表示。表示。例如，我们首先用规则例如，我们首先用规则进行第一步推导进行第一步推导(derivationderivation)，就可得到，就可得到 ，记为：记为：所得的符号串所得的符号串 含有两个含有两个语法范畴语法范畴，可对其中，可对其中任一个（例如对任一个（例如对 ）进行新的）进行新的推导推导（替换）：（替换）：u重复上述过程，可得到一个推导序列（见下页）。重复上述过程，可得到一个推导序列（见下页）。本讲稿第二十一页，共五十一页用语法规则进行推导所得的推导序列推导步骤推导步骤所用规则所用规则所得的符号串所得的符号串1
20、 2 3 the the 4 4 the the 5 the monkey the monkey 6 6 the monkey eat the monkey eat 7 the monkey eat a the monkey eat a 8 the monkey eat a banana the monkey eat a banana本讲稿第二十二页，共五十一页2.2.2 2.2.2 文法和语言的形式定义文法和语言的形式定义u从前面的推导看，从 出发，经8 8步推导步推导得到了一个英语句子。故前面的推导称为长度为长度为8 8的推的推导导。u若不关心推导的中间过程，可将从一符号串到另一符号串的推
21、导用记号本讲稿第二十三页，共五十一页规则的简化表示规则的简化表示u在前面的语法规则定义中，有些语法范畴（如、）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号“|”（读作或或）隔开。如、的定义规则可简记为uu:=monkey|banana:=monkey|bananauu:=eat|has:=eat|hasuu:=the|a本讲稿第二十四页，共五十一页语法规则及其产生的语言u前面的语法规则可以产生16个不同的句子，由这16个句子组成的集合，就是该规则所定义（或所产生）的语言。u应指出，所产生的句子中，有些句子的含义是荒谬的（如 the banan
22、a eat a monkey和the banana eat the banana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。本讲稿第二十五页，共五十一页2.2.2 文法和语言的形式定义u为得到文法的严格定义，我们对前面的规则进行如下的概括：为得到文法的严格定义，我们对前面的规则进行如下的概括：本讲稿第二十六页，共五十一页1、文法、文法G的形式定义的形式定义1 1文法文法G G为一个为一个四元组四元组:=(=(T T，N N，)T T：终结符终结符(Terminal)(Terminal)集集 N N：非终结符非终结符(Variable)(Variable)集，集，T TN
23、N=语法范畴语法范畴某个语言结构某个语言结构 ：开始符号开始符号(Start Symbol)(Start Symbol)，SSN N至少在产生式左侧出现一次至少在产生式左侧出现一次规定：规定：（1）VN，VT，P是有穷非空集合；是有穷非空集合；（2）VNVT（不含公共元素）（不含公共元素）本讲稿第二十七页，共五十一页：产生式产生式(Product)集合集合，被称为产生式（定义式），读作：，被称为产生式（定义式），读作：定义为定义为。其中：。其中：(TN)+，且，且中至少有中至少有N中元素的中元素的一个出现。一个出现。(TN)*。称为产生式称为产生式的的左部左部(LeftPart)，称为称为产生
24、式产生式的的右部右部(RightPart)。本讲稿第二十八页，共五十一页例：算术表达式的文法例：算术表达式的文法P:EE+EEE-EEE*EEE/EE(E)EidG=（id，+，-，*，/，(，)，E，P，E）约定：只写产生式。约定：只写产生式。可简写为可简写为：EE+E|E-E|E*E|E/E|(E)|id本讲稿第二十九页，共五十一页产生式的简写产生式的简写u对一组有对一组有相同左部相同左部的产生式的产生式1，2，n可以简单地记为：可以简单地记为：1|2|n读作：读作：定义为或者定义为或者1，或者，或者2，或者，或者n。并且称它们为并且称它们为产生式产生式。1，2，n称为称为候选式候选式(C
25、andidate)。本讲稿第三十页，共五十一页例、例、文法文法G=（VN，VT，P，S），），其中：其中：VN=S，VT=0，1，P=S0S1，S01。开始符号是开始符号是SS0S1 00S11 0n-1S1n-1 0n1n 所以描述的语言为：所以描述的语言为：L=0n1n|n1本讲稿第三十一页，共五十一页例：例：文法文法G=（VN，VT，P，S）其中其中：VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9S=P=|a|b|z0|1|9本讲稿第三十二页，共五十一页1、文法的定义、文法的定义文法的文法的第二种第二种表示法：表示法：上例上例1改为：改为：G:S 0S
26、1 S 01文法的文法的第三种第三种表示法：表示法：上例上例1改为：改为：GS:S 0S1 S 01一般约定，第一条产生式的左部是开始符号；用尖一般约定，第一条产生式的左部是开始符号；用尖括号括起来的括号括起来的是非终结符号是非终结符号，不用尖括号括起来的是，不用尖括号括起来的是终结符号终结符号，或者用大写字母表示，或者用大写字母表示非终结符号非终结符号，小写字，小写字母表示母表示终结符号终结符号。本讲稿第三十三页，共五十一页2、直接推导的定义、直接推导的定义如：有文法如：有文法G:EE+E|E*E|(E)|iE(E)(E+E)(i+E)(i+i)（称这样一串替换序列是从（称这样一串替换序列是
27、从E推出推出(i+i)的一个的一个推导推导)（1）定义：）定义：称称 A 直接推出直接推出 ，即：，即：A 仅当仅当A 是一个产生式，是一个产生式，且且、(VNVT)*本讲稿第三十四页，共五十一页例：例：GS:S0S1,S01S0S100S11000S11100001111可有：可有：A=00S11,=000S111(相当相当A=S,=0S1)本讲稿第三十五页，共五十一页 A=S，0S1直接推导：直接推导：S0S1 A=0S1，=00S11直接推导：直接推导：0S100S11例：例：A 0S1，=0011直接推导：直接推导：0S10011使用规则：使用规则：S 01 0，1，AS，01 规则：
28、规则：S 0S1 ，AS，0S1 规则：规则：S 0S1 0 ，1AS，0S1 本讲稿第三十六页，共五十一页(3)若有若有 1 n，或，或 1=n,则记作则记作 1 n 例：例：在例在例1中存在序列：中存在序列：10S100S11000S11100001111 n 记作：记作：0S1000011110S100001111+*一样的一样的(2)若存在直接推导的序列：若存在直接推导的序列：1 2 3 n(n1)则则称称 1推导推导 n(或或 n规约到规约到 1)，记，记 1 n+本讲稿第三十七页，共五十一页（多步）推导（多步）推导u012n记为记为0nn(恰用恰用n步步)0+n（至少一步）（至少一
29、步）0*n（若干步（若干步:零步或多步）零步或多步）本讲稿第三十八页，共五十一页id+id*id的不同推导的不同推导EE+E|E*E|(E)|idE E E E E E+E+E+E+E id+id+id+id+E E id+id+E E E E*E*E*E*E id+id*id+id*E E E E id+id*idid+id*idid+id*idid+id*idE E E+E+E E E E E+E*E+E*E+E*E+E*E E E+E+E E E E*id*id E E E E+id*id+id*id+id*id+id*id id+id*idid+id*idid+id*idid+id*i
30、dE E E E E E E E*E*E*E*E E+E+E E E E*E*E*E*E E E E E+id*E+id*E+id*E+id*E id+id*id+id*id+id*id+id*E E E E id+id*idid+id*id不做限制不做限制不做限制不做限制句型句型句型句型 (sentential Form)(sentential Form)(sentential Form)(sentential Form)（归约（归约（归约（归约）EE*id+id*idid+id*idid+id*idid+id*id施于最施于最施于最施于最右右右右变量变量变量变量右句型右句型右句型右句型/规
31、范句型规范句型规范句型规范句型 (canonical)(canonical)(canonical)(canonical)(最左最左最左最左/规范归约规范归约规范归约规范归约)E E E E+id+id*idid+id*idid+id*idid+id*id施于最施于最施于最施于最左左左左变量变量变量变量左句型左句型左句型左句型(left-)(left-)(left-)(left-)（最右归约）（最右归约）（最右归约）（最右归约）E E5 5 id+id*idid+id*id本讲稿第三十九页，共五十一页例：算术表达式例：算术表达式GE:EE+T|TTT*F|FF(E)|a可可推导推导出：出：EE+
32、TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a表示文法表示文法GE能推导出用符号能推导出用符号a,+,*,(和和)构成的所有算术表达式构成的所有算术表达式本讲稿第四十页，共五十一页3、句型与句子、句型与句子句型句型：设：设GS是文法，若是文法，若Sx，且，且x V*,则称则称x是文是文法法GS的句型的句型句子句子：设设GS是文法，若是文法，若Sx，且，且x VT*,则称则称x是文法是文法GS的句子的句子（句子是句型的特殊）（句子是句型的特殊）结论结论句子一定是句型，句型不一定是句子。句子一定是句型，句型不一定是句子。例：例：GS:S 0S1,S 01 S 0S1 00S11 00
33、0S111 00001111 S,0S1,00S11,000S111,00001111都是句型，都是句型，只有只有00001111是是G的句子的句子*本讲稿第四十一页，共五十一页4、文法、文法G产生的语言产生的语言u定义：定义：L(G)=x Sx，S为文法开始符号，为文法开始符号，x VT*L(G)是文法是文法GS描述的语言，也是该文法能推导出所有描述的语言，也是该文法能推导出所有句子的集合。句子的集合。文法文法EE+E|E*E|(E)|id可以派生出多少个句子？可以派生出多少个句子？文法文法G的作用的作用语言的有穷描述语言的有穷描述以以有限有限的规则描述的规则描述无限无限的语言现象的语言现象
34、有限有限:产生式集合、终结符集合、非终结符集合产生式集合、终结符集合、非终结符集合无限：无限：可以导出可以导出无穷多个句子无穷多个句子（注：（注：L也可是有穷）也可是有穷）本讲稿第四十二页，共五十一页例：例：GS:S 0S1,S 01L(G)0n1n n 1因为因为S0S100S11 0n1n重复利用规则重复利用规则S0S1本讲稿第四十三页，共五十一页例：文法例：文法G:SbAAaA|a考虑该文法定义的语言。考虑该文法定义的语言。SbASbAbaAbaaSbAbaAbaaAbaaaSbAbaAbaa所以：所以：L(G)=ban|n 1本讲稿第四十四页，共五十一页例例 考虑文法考虑文法G:G:E
35、(E)E(E)a a 这个文法有这个文法有1 1个非终结符个非终结符E E、3 3个终结符个终结符(,),a(,),a这个文法生成语言这个文法生成语言:L(G)=a,(a),(a),(a),.L(G)=a,(a),(a),(a),.，即：串由零个或多个左括号、后接一个即：串由零个或多个左括号、后接一个a a，以及，以及后面是与左括号相同数量的右括号组成。作为这些串后面是与左括号相同数量的右括号组成。作为这些串的一个推导示例，我们给出的一个推导示例，我们给出(a)(a)的一个推导：的一个推导：E E(E)(E)(E)(E)(a)(a)本讲稿第四十五页，共五十一页练习：文法练习：文法GS：（1）S
36、aSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee答：答：L（G）=anbnen|n1 本讲稿第四十六页，共五十一页（1 1）已知语言描述，写出文法）已知语言描述，写出文法 应满足：应满足：所描述语言的任何句子都能由该文法产生；所描述语言的任何句子都能由该文法产生；该文法推导不出不是已知语言的任何句子。该文法推导不出不是已知语言的任何句子。（2 2）已知文法，写出语言描述）已知文法，写出语言描述 应满足：应满足：u该文法能推导出的任何句子都包含在所描述的语言该文法能推导出的任何句子都包含在所描述的语言中；中；u 所描述的语言中不包含任何该文法推导不出的
37、句子。所描述的语言中不包含任何该文法推导不出的句子。总结：语言和文法总结：语言和文法本讲稿第四十七页，共五十一页下面是语言文法的构造示例下面是语言文法的构造示例:一般采用一般采用“凑规则凑规则”的方法来构造语言的文法。其步骤如下：的方法来构造语言的文法。其步骤如下：(1)找出语言的若干典型句子。找出语言的若干典型句子。(2)分析句子的特点。分析句子的特点。(3)根据句子的特点凑规则。根据句子的特点凑规则。(4)得到文法。得到文法。(5)检查文法。文法应满足如下要求：检查文法。文法应满足如下要求：a.语言的所有句子都能由文法的开始符号推导得到。语言的所有句子都能由文法的开始符号推导得到。b.由文
38、法开始符号推导出的所有终结符号串都是语言的句由文法开始符号推导出的所有终结符号串都是语言的句子。子。本讲稿第四十八页，共五十一页例：构造描述语言例：构造描述语言L(GS)=(n)n|n0的文法。的文法。解解：(1)找出语言的一些典型句子：找出语言的一些典型句子：n=0,x=n=1,x=()n=2,x=().所以，所以，L(GS)=,(),(),(2)分析句子的特点：分析句子的特点：只含有只含有(和和)；(和和)的个数相同且对称出现；句子中符号的个数的个数相同且对称出现；句子中符号的个数可无限，句子的个数可无限。可无限，句子的个数可无限。本讲稿第四十九页，共五十一页(3)凑规则：凑规则：由由S()|得到得到 和和()。由。由A(S)得到得到()。分析。分析()与与()可可见，见，()是是()的两边再加上一对的两边再加上一对()得到的，得到的，()是是()的两边再的两边再加上一对加上一对()得到的得到的,所以产生式合并为：所以产生式合并为：S(S)|(4)得到文法得到文法GS:S(S)|(5)检验检验(略略)本讲稿第五十页，共五十一页u习题：习题：写一文法，使其语言是偶数的集合，但不允写一文法，使其语言是偶数的集合，但不允许有以许有以0居首的偶整数居首的偶整数本讲稿第五十一页，共五十一页