《第二章高级语言及其语法描述》由会员分享，可在线阅读，更多相关《第二章高级语言及其语法描述（58页珍藏版）》请在金锄头文库上搜索。
1、程序设计语言程序设计语言编编 译译 原原 理理主讲：张永梅主讲：张永梅翻译程序扫描所输入的源程序，并将其转翻译程序扫描所输入的源程序，并将其转换为目标程序。换为目标程序。翻译程序翻译程序源程序源程序目标程序目标程序源程序是用高级语言或汇编语言编写的，而目标程序则源程序是用高级语言或汇编语言编写的，而目标程序则是用目标语言表示的。是用目标语言表示的。汇编程序汇编程序汇编语言程序汇编语言程序机器语言程序机器语言程序编译程序编译程序高级语言程序高级语言程序低级语言程序低级语言程序汇编程序与编译程序都是汇编程序与编译程序都是翻译程序翻译程序，主要区别是加工对，主要区别是加工对象的不同。象的不同。编译程
2、序总框编译程序总框源程序源程序单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码目标代码目标代码 表表 格格 管管 理理出出错错处处理理语法分析器语法分析器语义分析与中间代码产生器语义分析与中间代码产生器 优化器优化器目标代码生成器目标代码生成器词法分析器词法分析器 编译过程阶段划分编译过程阶段划分是一种典型的分法，事是一种典型的分法，事实上并非所有的编译程实上并非所有的编译程序都包括这几个阶段。序都包括这几个阶段。 有些编译程序为了有些编译程序为了加快编译速度，加快编译速度，中间代中间代码生成阶段码生成阶段可以去掉。可以去掉。有些编译程序对优化没有些编译程序对优化没有要求，有要
3、求，优化阶段优化阶段即可即可省去。有些最简单的编省去。有些最简单的编译程序只有词法分析，译程序只有词法分析，语法分析，语义分析和语法分析，语义分析和目标代码生成，如目标代码生成，如PL/0语言编译程序。语言编译程序。一遍扫描即可完成整个编译工作的称为一遍扫描即可完成整个编译工作的称为一遍扫描编译程序一遍扫描编译程序 其结构为其结构为：词法分析词法分析语法分析语法分析语义分析及代码语义分析及代码生成生成源程序源程序语法成分语法成分返回分析结果返回分析结果整理目标程序整理目标程序 停机停机目标程序目标程序取单词取单词返回单词返回单词课程安排课程安排内内 容容讲授课时讲授课时实验课时实验课时第一章第
4、一章 引引 论论2第二章第二章 高级程序语言及其语法描述高级程序语言及其语法描述2第三章第三章 词法分析词法分析实验一实验一 词法分析器（第词法分析器（第6、7、8、9周）周）108第四章第四章 语法分析语法分析-自上而下分析自上而下分析8第五章第五章 语法分析语法分析-自下而上分析自下而上分析实验二实验二 语法分析器（第语法分析器（第13、14、15、16周）周）88第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译8第七章第七章 语义分析及中间代码产生语义分析及中间代码产生8第八章第八章 优优 化化2合合 计计4816第二章第二章 高级语言及其语法描高级语言及其语法描述述2.1 程
5、序语言的定义程序语言的定义2.2 高级语言的一般特性高级语言的一般特性2.3 程序语言的语法描述程序语言的语法描述了解：了解：形式语言概述形式语言概述熟悉：熟悉：语法、语义语法、语义掌握：掌握：上下文无关文法上下文无关文法, 语法分析树与二义性语法分析树与二义性第二章第二章 高级语言及其语法描高级语言及其语法描述述作业：作业： 2.6，2.7，2.8，2.9第二章第二章 高级语言及其语法描高级语言及其语法描述述2.6 令文法令文法G6为为 ND ND D0 1 2 3 4 5 6 7 8 9（1）G6的语言的语言L(G6)是什么？是什么？（2）给出句子）给出句子0127、34和和568的最左推
6、导和最右推导。的最左推导和最右推导。2.7 写一个文法，使其语言是奇数集，且每个奇数不以写一个文法，使其语言是奇数集，且每个奇数不以0开头。开头。2.8 令文法为令文法为 ET E+ T E-T TF T*F T/F F(E) i（1）给出）给出i+i*i、i*(i+i)的最左推导和最右推导；的最左推导和最右推导；（2）给出）给出i+i+i、i+i*i和和i-i-i的语法树。的语法树。2.9 证明下面的文法是二义的：证明下面的文法是二义的： SiSeS iS i第二章第二章 高级语言及其语法描高级语言及其语法描述述常用的高级语言常用的高级语言 FORTRAN数值计算数值计算 COBOL事务处理
7、事务处理 PASCAL结构程序设计结构程序设计 ADA大型程序、嵌入式实时系统大型程序、嵌入式实时系统 PROLOG逻辑程序设计逻辑程序设计 ALGOL算法语言算法语言 C/C+系统程序设计系统程序设计 JavaInternet程序设计程序设计第二章第二章 高级语言及其语法描高级语言及其语法描述述与机器语言或汇编语言比较与机器语言或汇编语言比较，高级语言高级语言的优点的优点：较接近于数学语言和工程语言较接近于数学语言和工程语言，比较直观、比较直观、自然和易于理解自然和易于理解;便于验证其正确性便于验证其正确性，易于改错易于改错;编写效率高编写效率高;易于移植。易于移植。2.1 程序语言的定义程
8、序语言的定义程序语言由两方面定义：程序语言由两方面定义：语法语法语义语义语用语用语法是描述程序的结构，根据它可以产生正确的程语法是描述程序的结构，根据它可以产生正确的程序。（词法规则、语法规则）序。（词法规则、语法规则）语义是语言成分的含义，由程序执行的效果来说明。语义是语言成分的含义，由程序执行的效果来说明。语用是语言的实际应用。语用是语言的实际应用。 如：如： x=a+b*c一、语法一、语法程序本质上是一定字符集上的字符串。程序本质上是一定字符集上的字符串。语法语法：一组规则：一组规则，用它可以形成和产生一个用它可以形成和产生一个合式合式(well-formed)的程序的程序。一、语法一、
9、语法词法规则词法规则：单词符号的形成规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本单词符号是语言中具有独立意义的最基本结构结构。一般包括：常数、标识符、基本字、一般包括：常数、标识符、基本字、算符、界符等。算符、界符等。描述工具：有限自动机描述工具：有限自动机语法规则语法规则：语法单位的形成规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程语法单位通常包括：表达式、语句、分程序、过程、函数、程序等序、过程、函数、程序等;描述工具：上下文无关文法描述工具：上下文无关文法 EiEE+EEE*EE(E)语法规则和词法规则语法规则和词法规则定义了程序的的形定义了程序的的形式
10、结构。定义式结构。定义语法单位的意义语法单位的意义属于语义属于语义问题。问题。语义：语义：是指这样的规则，使用它可以定义一个程序的意是指这样的规则，使用它可以定义一个程序的意义。义。语义描述的方法语义描述的方法：属性文法的语法制导翻译方法。：属性文法的语法制导翻译方法。该方法接近形式化方法。该方法接近形式化方法。相同语句不同含义的例子：相同语句不同含义的例子： Z=X+Y可以表示整数相加和实数相加等不同的语义。可以表示整数相加和实数相加等不同的语义。编译程序就是要从基本的单词符号和语法单位分编译程序就是要从基本的单词符号和语法单位分析程序的语义。析程序的语义。二、语义二、语义高级语言的分类高级
11、语言的分类 程序结构程序结构数据类型与操作数据类型与操作初等数据类型初等数据类型数据结构数据结构抽象数据类型抽象数据类型语句与控制结构语句与控制结构2.2 高级语言的一般特性高级语言的一般特性2.2 高级语言的一般特性高级语言的一般特性高级语言分类：高级语言分类：过程式语言过程式语言-命令驱动，面向语句，如命令驱动，面向语句，如C语言等。语言等。函数式语言函数式语言-从功能出发构造函数，如从功能出发构造函数，如LISP等。等。基于规则的语言基于规则的语言-检查一定的条件，当满足条件检查一定的条件，当满足条件时，则执行适当的动作，如时，则执行适当的动作，如Prolog语言。语言。面向对象的语言面
12、向对象的语言-支持封装、继承和多态性等。支持封装、继承和多态性等。2.3 程序语言的语法描述程序语言的语法描述语言特征语言特征自然语言自然语言(Natural Language)是人与人的通讯工具是人与人的通讯工具语义语义(semantics):环境、背景知识、语气、环境、背景知识、语气、二义性二义性难以形式化难以形式化计算机语言计算机语言(Computer Language)计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具严格的语法严格的语法(Grammar)、语义、语义(semantics) 易于形式化：严格易于形式化：严格2.3 程序语言的语法描述程序语言的语法描述语言的描述方法
13、语言的描述方法现状现状自然语言：自然、方便自然语言：自然、方便-非形式化非形式化数学语言（符号）：严格、准确数学语言（符号）：严格、准确-形形式化式化形式化描述形式化描述高高度度的的抽抽象象，严严格格的的理理论论基基础础和和方方便便的计算机表示。的计算机表示。2.3 程序语言的语法描述程序语言的语法描述语言语言形式化的内容提取形式化的内容提取语言语言(Language)：满足一定条件的句子集合：满足一定条件的句子集合句子句子(Sentence)：满足一定规则的单词序列：满足一定规则的单词序列单词单词(Token)：满足一定规则的字符：满足一定规则的字符(Character)串串程序设计语言程序
14、设计语言形式化的内容提取形式化的内容提取程序设计语言程序设计语言(Programming Language)：组成程：组成程序的所有语句的集合。序的所有语句的集合。程序程序(Program)：满足语法规则的语句序列。：满足语法规则的语句序列。语句语句(Sentence) ：满足语法规则的单词序列。：满足语法规则的单词序列。单词单词(Token) ：满足词法规则的字符串。：满足词法规则的字符串。2.3 程序语言的语法描述程序语言的语法描述描述形式描述形式文法文法语法语法语句语句语句的组成规则语句的组成规则描述方法：描述方法：BNF范式、语法范式、语法(描述描述)图图词法词法单词单词单词的组成规则
15、单词的组成规则描述方法：有限自动机、正规式描述方法：有限自动机、正规式形式语言与自动机理论的产生与作用形式语言与自动机理论的产生与作用语言学家语言学家Chomsky最初从产生语言的角度研究语言。最初从产生语言的角度研究语言。1956年，通过抽象，他将语言形式地定义为是由一个年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表字母表中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（上按照一定的规则定义一个文法（Grammar），该），该文法所能产生的所有句子组成的集合就是该文法产生文法所能产生的所有句子组成的集合就是该文法产生的语言。的语言
16、。克林克林（Kleene）在）在1951年到年到1956年间，年间，从识别语言的角从识别语言的角度研究语言，度研究语言，给出了语言的另一种描述。给出了语言的另一种描述。克林是在研究神经细胞中，建立了自动机，他用这种克林是在研究神经细胞中，建立了自动机，他用这种自动机来识别语言：对于按照一定的规则构造的任一自动机来识别语言：对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成。该自动机所能识别的所有句子组成。形式语言与自动机理论的产生与作用形式语言与自动机理论的产生与作用1959年，年，Chomsk
17、y通过深入研究，将他本人的研究成通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅确定了文法和果与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且自动机分别从生成和识别的角度去表达语言，而且证证明了文法与自动机的等价性明了文法与自动机的等价性。 20世纪世纪50年代，人们用年代，人们用巴科斯范式巴科斯范式（Backus Nour Form 或或 Backus Normal Form，简记为，简记为BNF）成功地）成功地对高级语言对高级语言ALGOL-60进行了描述。实际上，巴科斯进行了描述。实际上，巴科斯范式就是上下文无关文法（范式就是上下文
18、无关文法（Context Free Grammar）的一种表示形式。这一成功，使得形式语言在的一种表示形式。这一成功，使得形式语言在20世纪世纪60年代得到了大力的发展。年代得到了大力的发展。 2.3 程序语言的语法描述程序语言的语法描述基本概念：基本概念：是是一一个个有有穷穷字字母母表表，它它的的每每个个元元素素称称为为一一个个符号。符号。上上的的字字(也也叫叫符符号号串串) ：是是指指由由中中的的符符号号所所构构成的一个有穷序列。成的一个有穷序列。：不包含任何符号的序列称为空符号串。：不包含任何符号的序列称为空符号串。*：表示：表示上所有字的集合，其中包括空符号串上所有字的集合，其中包括空
19、符号串。: 不包含任何元素的集合，不包含任何元素的集合，= 例如例如: 设设 =a, b，则，则*=,a,b,aa,ab,ba,bb,aaa,.*的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U & V 设：设：U a, aa V b, bb 那么：那么：UV= ab, abb, aab, aabb 2.3 程序语言的语法描述程序语言的语法描述*的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U & V V自身的自身的 n次积记为次积记为Vn=VVV规定规定V0= ，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包;记记 VVV* ，称，称V+是是V
20、的的正正(规规)闭包闭包。2.3 程序语言的语法描述程序语言的语法描述2.3 程序语言的语法描述程序语言的语法描述设：设：U a, aa 那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, U U 1 U 2 U 3 U n 称为集合称为集合U 的的正闭包正闭包。 U * U 0 U 称为集合称为集合U 的的闭包闭包。2.3.1 上下文无关文法上下文无关文法文法：文法：描述语言的语法结构的形式规则。描述语言的语法结构的形式规则。特点：特点：这些规则必须是准确的，易于理解的，而且，应这些规则必须是准确的，易于理解的，而且，应当有相当强的描述
21、能力，足以描述各种不同的结当有相当强的描述能力，足以描述各种不同的结构。构。例如：例如：-He gave me a book.上下文无关文法：上下文无关文法：它它所所定定义义的的语语法法范范畴畴是是完完全全独独立立于于这这种种范范畴畴可可能能出现的环境的。出现的环境的。一个上下文无关文法一个上下文无关文法G包括四个组成部分：包括四个组成部分：一组终结符号一组终结符号一组非终结符号一组非终结符号一个开始符号一个开始符号一组产生式一组产生式2.3.1 上下文无关文法上下文无关文法终结符号终结符号：是是组组成成语语言言的的基基本本符符号号，在在程程序序语语言言中中就就是是以以前前屡屡次次提提到到的的
22、单单词词符符号号，如如基基本本字字、标标识识符符、常常数数、算符和界符等。算符和界符等。非终结符号非终结符号：用来代表语法范畴。如：语句、表达式等。用来代表语法范畴。如：语句、表达式等。开始符号开始符号：是是一一个个特特殊殊的的非非终终结结符符号号，它它代代表表所所定定义义的的语语言言中中我我们们最最终终感感兴兴趣趣的的语语法法范范畴畴，这这个个语语法法范范畴畴通通常称为常称为“句子句子”或是或是“程序程序”。2.3.1 上下文无关文法上下文无关文法产生式产生式：是定义语法范畴的一种书写规则。是定义语法范畴的一种书写规则。一个产生式的形式是一个产生式的形式是A或或A:=A：是非终结符号：是非终
23、结符号：是是由由终终结结符符号号或或与与非非终终结结符符号号组组成成的的一一个个符符号串。号串。2.3.1 上下文无关文法上下文无关文法例如：一个简单的算术表达式文法：例如：一个简单的算术表达式文法：EiEE+EEE*E (2-1)E(E)终结符号：终结符号：i，+，*，(，)非终结符号：非终结符号：E开始符号：算术表达式开始符号：算术表达式E产生式：产生式：(2-1)2.3.1 上下文无关文法上下文无关文法形式化定义：形式化定义：一个上下文无关文法是一个四元式（一个上下文无关文法是一个四元式（VT ,VN ,S ,）VT是一个非空有限集，它的每个元素称为终结符号；是一个非空有限集，它的每个元
24、素称为终结符号；VN是是一一个个非非空空有有限限集集，它它的的每每个个元元素素称称为为非非终终结结符符号，号，VTVN=；S是一个非终结符号，称为开始符号；是一个非终结符号，称为开始符号；SVN。是是一一个个产产生生式式集集合合（有有限限），每每个个产产生生式式的的形形式式是是P。其其中中，PVN ，（VTVN） 。开开始始符符号号S至至少少必须在某个产生式的左部出现一次。必须在某个产生式的左部出现一次。P1|2|n。其其中中，i称称为为是是P的的一一个个候候选选式式。 读作读作“定义定义”，直竖读为，直竖读为“或或”,它是元语言符号。它是元语言符号。2.3.1 上下文无关文法上下文无关文法上
25、下文无关文法语言：上下文无关文法语言：从从文文法法的的开开始始符符号号出出发发，反反复复使使用用产产生生式式，对对非非终结符施行替换和展开。终结符施行替换和展开。例子：求解文法例子：求解文法2-1的语言？的语言？E (E)(E+E)(i+E)(i+i)推导：推导：称称 A 直直接接推推出出 ，即即： A ，仅仅当当A 是产生式，且是产生式，且 、(VT VN) * 2.3.1 上下文无关文法上下文无关文法2.3.1 上下文无关文法上下文无关文法 表示一个文法时，通常只给出开始符号和产生式，表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：如上例，可表示为：G(E)： E i | E
26、+E | E*E | (E)例如：一个简单的算术表达式文法：例如：一个简单的算术表达式文法：EiEE+EEE*E (2-1)E(E)终结符号：终结符号：i，+，*，(，)非终结符号：非终结符号：E开始符号：算术表达式开始符号：算术表达式E产生式：产生式：(2-1)2.3.1 上下文无关文法上下文无关文法定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式， 且且 ， (VT VN)* 。如果如果 1 2 n，则我们称这个序列是从，则我们称这个序列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可可以以
27、推导推导出出 n 。对文法对文法G(E)： E i | E+E | E*E | (E)E (E) (E+E) (i+E) (i+i) 用用 表示：从表示：从 1出发，经过出发，经过0步或步或若干步，可以推出若干步，可以推出 n。 所以所以 ： 即即 或或q定义：假定定义：假定G是一个文法，是一个文法，S 是开始符号。是开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含。仅含终结符号的句型是一个终结符号的句型是一个句子句子。文法。文法G所产生的所产生的句子的全体是一个句子的全体是一个语言语言，将它记为，将它记为 L(G)。通常，用通常，用 表示：从表示：从 1出发，出发，经过一步或若干
28、步，可以推出经过一步或若干步，可以推出 n。例：例： (i*i+i)是文法是文法G(E)： E i | E+E | E*E | (E)的一个句子。的一个句子。 证明：证明： E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E，(E)，(E+E)，(E*E+E)，(i*i+i)是句型。是句型。2.3.1 上下文无关文法上下文无关文法例：文法例：文法G1(A)： A c|AbG1(A)的语言的语言?L(G1)=c，cb，cbb，以以c开头，后继若干个开头，后继若干个bL(G1)=cbn|n=02.3.1 上下文无关文法上下文无关文法2.3.1 上下文无关文法
29、上下文无关文法例：文法例：文法G2(S)： S AB A aA|a B bB|bG2(S)的语言的语言?L(G2)=ambn|m,n = 12.3.1 上下文无关文法上下文无关文法例：给出产生语言为例：给出产生语言为anbn|n 1的文法。的文法。 G3(S)： S aSb S ab例：例： abna | n1，构造其文法。，构造其文法。 定义定义 G和和G是两个不同的文法，若是两个不同的文法，若 L(G) = L(G) , 则则G和和G为为等价文法等价文法。 G1Z：ZaBa, Bb | bB2.3.1 上下文无关文法上下文无关文法 G2Z： ZaBa, Bb | Bbi+i*i的不同推导的
30、不同推导 EE+E|E*E|(E)|iE E E E+E+E i+i+E E i+i+E E*E*E i+i*i+i*E E i+i*ii+i*iE E E+E+E E E+E*E+E*E E E+E+E E*i*i E E+i*i+i*i i+i*ii+i*iE E E E*E*E E+E+E E*E*E E E+i*E+i*E i+i*i+i*E E i+i*ii+i*i不做限制不做限制不做限制不做限制施于最右施于最右施于最右施于最右非终结非终结符号符号( (最右推导最右推导最右推导最右推导) )施于最左施于最左施于最左施于最左非终非终结符号结符号（最左（最左（最左（最左推导）推导）推导）
31、推导） 一个句型的推导往往不唯一一个句型的推导往往不唯一。最左推导最左推导：任任何何一一步步=都都是是对对中中的的最最左左非非终终结结符符号号进行替换的。进行替换的。最右推导最右推导：任任何何一一步步=都都是是对对中中的的最最右右非非终终结结符符号号进行替换的。进行替换的。2.3.1 上下文无关文法上下文无关文法2.3.2 语法分析树与二义性语法分析树与二义性用一张图表示一个句型的推导用一张图表示一个句型的推导,称为称为语法树语法树。(i*i+i)的语法树的语法树E (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E (E)(E+E)(E+i)(E*E+i)(E*i+i
32、)(i*i+i)一棵语法树是不同推导过程的共性抽象。一棵语法树是不同推导过程的共性抽象。G(E)： E i | E+E | E*E | (E)(i*i+i)树与推导树与推导句型推导过程句型推导过程 该句型语法树的生长过程该句型语法树的生长过程 由推导构造语法树由推导构造语法树从开始从开始符号符号开始，开始，自左向右自左向右建立建立推导推导序列。序列。由由根结点根结点开始，开始，自上而下自上而下建立建立语法树语法树。2.3.2 语法分析树与二义性语法分析树与二义性如果使用最左如果使用最左(右右)推导，则一个最左推导，则一个最左(右右)推导与推导与语法树一一对应。语法树一一对应。一个句型是否只对应
33、唯一一棵语法树？一个句型是否只对应唯一一棵语法树？2.3.2 语法分析树与二义性语法分析树与二义性一个句子有两棵不同的语法树。一个句子有两棵不同的语法树。定义：如果一个文法存在某个句子对应定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个两颗不同的语法树，则说这个文法是二文法是二义的义的。 G(E)： E i|E+E|E*E|(E) 是二义文法。是二义文法。2.3.2 语法分析树与二义性语法分析树与二义性二义文法二义文法G(E)： E i|E+E|E*E|(E)表达式表达式 项项|表达式表达式+项项项项 因子因子 | 项项*因子因子因子因子 (表达式表达式) | i无二义文法无二义文
34、法G(E)： E T | E+T T F | T*F F (E) | i2.3.2 语法分析树与二义性语法分析树与二义性)EFEFFTTTTi+*(EFiiE T F (E) (E+T) (T+T) (T*F+T) (F*F+T) (i*F+T) (i*i+T) (i*i+F) (i*i+i)考虑句子考虑句子(i*i+i)2.3.2 语法分析树与二义性语法分析树与二义性上下文无关文法的限制：上下文无关文法的限制：文法中不含任何下面形式的产生式文法中不含任何下面形式的产生式 PP 每个非终结符每个非终结符P必须都有用处。即：必须存必须都有用处。即：必须存在含在含P的句型，并且对于的句型，并且对于
35、P不存在永不终结不存在永不终结的回路。的回路。2.3.2 语法分析树与二义性语法分析树与二义性2.3.3 形式语言鸟瞰形式语言鸟瞰乔姆斯基（乔姆斯基（Chomsky）把文法分四类：）把文法分四类：0型、型、1型、型、2型和型和3型。型。其其描描述述能能力力的的强强度度有有下下列列关关系系：0型型强强于于1型、型、1型强于型强于2型、型、2型强于型强于3型。型。0型文法型文法：设设G=（VT,VN,S,），对对每每个个产产生生式式有有（VNVT）* 且且至至少少含含有有一一个个非非终终结结符；符；（VNVT）*对对0型文法的型文法的产生式产生式分别施加以下第分别施加以下第i条限制，就条限制，就得
36、到得到i型文法型文法： 1.每个产生式为每个产生式为均满足均满足| |;仅仅 S 例外，但例外，但S不得出现在任何产生式的右部。不得出现在任何产生式的右部。2.G为任何产生式为为任何产生式为A，AVN ，（VNVT） * 。 3.G的任何产生式为的任何产生式为(1) AB 或或A (2) AB 或或A 其中其中VT * ，A、BVN。(1)式为右线性文法；式为右线性文法；(2)式为左线性文法。式为左线性文法。2.3.3 形式语言鸟瞰形式语言鸟瞰文法说明：文法说明：1型型文文法法也也称称上上下下文文有有关关文文法法。这这种种文文法法意意味味着着，对对非非终终结结符符进进行行替替换换时时务务必必考
37、考虑虑上上下文，并且，一般不允许替换成空串下文，并且，一般不允许替换成空串。2型文法型文法也称也称上下文无关文法上下文无关文法。3型文法型文法也称线性文法，或称为也称线性文法，或称为正规文法正规文法。2.3.3 形式语言鸟瞰形式语言鸟瞰2.3.3 形式语言鸟瞰形式语言鸟瞰* G是是0型文法，型文法，L(G)是是0型语言；型语言； -其能力相当于图灵机其能力相当于图灵机(TM)* G是是1型文法，型文法，L(G)是是1型语言型语言; -其识别系统是线性界限自动机其识别系统是线性界限自动机(LBA)* G是是2型文法，型文法，L(G)是是2型语言型语言; -其识别系统是不确定的下推自动机其识别系统是不确定的下推自动机(PDA)*G是右线性文法，是右线性文法，L(G)是是3型语言型语言G是左线性文法，是左线性文法，L(G)是是3型语言型语言 -其识别系统是有限自动机其识别系统是有限自动机(FA)2.3.3 形式语言鸟瞰形式语言鸟瞰四种文法之间的关系是将产生式作进一步限制而定义的四种文法之间的关系是将产生式作进一步限制而定义的四种文法之间的逐级四种文法之间的逐级“包含包含”关系如下：关系如下：
