编译原理课件Chapt2.ppt_163文库

资源描述

1、第二章第二章高级语言及其语法描述高级语言及其语法描述常用的高级语言常用的高级语言 FORTRANFORTRAN数值计算数值计算 COBOL COBOL事务处理事务处理 PASCAL PASCAL结构程序设计结构程序设计 ADA ADA大型程序、嵌入式实时系统大型程序、嵌入式实时系统 PROLOG PROLOG逻辑程序设计逻辑程序设计 ALGOL ALGOL算法语言算法语言 C/C+ C/C+系统程序设计系统程序设计 Java JavaInternetInternet程序设计程序设计与机器语言或汇编语言比较与机器语言或汇编语言比较，高级语言高级语言的优点：的优点：较接近于数学语言和工程语言

2、较接近于数学语言和工程语言，比较直观、比较直观、自然和易于理解自然和易于理解; ;便于验证其正确性便于验证其正确性，易于改错易于改错; ;编写效率高编写效率高; ;易于移植易于移植. .2.12.1 程序语言的定义程序语言的定义程序语言由两方面定义：程序语言由两方面定义：语法语法语义语义语用语用一一. 语法语法程序本质上是一定字符集上的字符串。程序本质上是一定字符集上的字符串。语法语法：一组规则：一组规则，用它可以形成和产生一用它可以形成和产生一个个合式合式(well-formed)的程序的程序。语语法法词法规则词法规则：单词符号的形成规则：单词符号的形成规则。单词符号是语言中具有独

3、立意义的最基本结构单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界一般包括：常数、标识符、基本字、算符、界符等。符等。描述工具：有限自动机描述工具：有限自动机语法规则语法规则：语法单位的形成规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、语法单位通常包括：表达式、语句、分程序、过程、函数、程序等过程、函数、程序等; ;描述工具：上下文无关文法描述工具：上下文无关文法 Ei EiEE+EEE+EEEEE* *E EE(E)E(E) 语法规则和词法规则定义了程序的的形语法规则和词法规则定义了程序的的形式结构。定义语法单位的意义属于语义式结构。定

4、义语法单位的意义属于语义问题。问题。二二. . 语义语义语义语义：一组规则：一组规则，用它可以定义一个程用它可以定义一个程序的意义序的意义。描述方法：描述方法：自然语言描述：隐藏错误、二义性和不完整自然语言描述：隐藏错误、二义性和不完整性性形式描述：形式描述：F 操作语义操作语义(PL/1)(PL/1)F 指称语义指称语义(ADA)(ADA)F 代数语义代数语义(PASCAL)(PASCAL)三程序语言的基本功能和层次结构三程序语言的基本功能和层次结构程序语言的基本功能：描述数据和对数据程序语言的基本功能：描述数据和对数据的运算。的运算。所谓程序，本质上说是描述一定数据的处所谓程序，本

5、质上说是描述一定数据的处理过程。理过程。程序的层次结构程序的层次结构程序程序| |子程序或分程序、过程、函数子程序或分程序、过程、函数| |语句语句| |表达式表达式| |数据引用数据引用算符算符函数调用函数调用程序语言每个组成成分的逻辑和实现意义程序语言每个组成成分的逻辑和实现意义抽象的逻辑的意义抽象的逻辑的意义数学意义数学意义计算机实现的意义计算机实现的意义具体实现具体实现2.2 2.2 高级语言的一般特性高级语言的一般特性高级语言的分类高级语言的分类强制式语言强制式语言(Imperative Languge)(Imperative Languge)也称过程式语言：命令驱动，也

6、称过程式语言：命令驱动，面向语句面向语句 FORTRANFORTRAN、C C、PascalPascal，Ada Ada 应用式语言应用式语言（Applicative LanguageApplicative Language）：注重程序所表示的功能，）：注重程序所表示的功能，而不是一个语句接一个语句地执行而不是一个语句接一个语句地执行 LISPLISP、ML ML 基于规则的语言基于规则的语言（Rule-based LanguageRule-based Language）：检查一定的条件，当）：检查一定的条件，当它满足值，则执行适当的动作它满足值，则执行适当的动作 Prolog Prolog

7、面向对象语言面向对象语言（Object-Oriented LanguageObject-Oriented Language）：）：封装性封装性、继承性继承性和和多态性多态性 SmalltalkSmalltalk，C+C+，Java Java 2.3 2.3 程序语言的语法描述程序语言的语法描述 2.2 2.2 高级语言的一般特性高级语言的一般特性2.2.2 2.2.2 程序结构程序结构 FORTRAN FORTRAN一个程序由一个主程序段和若干辅程序段组成。一个程序由一个主程序段和若干辅程序段组成。辅程序段可以是子程序、函数段或数据块。辅程序段可以是子程序、函数段或数据块。每个程序段有一系列的

8、说明语句和执行语句组成。每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译。各段可以独立编译。模块结构，没有嵌套和递归模块结构，没有嵌套和递归各程序段中的名字相互独立各程序段中的名字相互独立，同一个标识符在不，同一个标识符在不同的程序段中代表不同的名字同的程序段中代表不同的名字。主程序主程序 PROGRAM PROGRAM end end辅程序辅程序1 SUBROUTINE 1 SUBROUTINE end end辅程序辅程序2 FUNCTION 2 FUNCTION end end PASCAL PASCAL程序本身可以看成是一个操作系程序本身可以看成是一个操作系统所调用的过程，

9、过程可以嵌套和递归。统所调用的过程，过程可以嵌套和递归。一个一个PASCAL过程：过程：过程头；过程头；说明段（由一系列的说明语句组成）；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；执行体（由一系列的执行语句组成）；end作用域作用域：一个名字能被使用的区域范围：一个名字能被使用的区域范围称作这个名字的作用域。称作这个名字的作用域。允许同一个标识符在不同的过程中代表允许同一个标识符在不同的过程中代表不同的名字。不同的名字。名字作用域规则名字作用域规则-最近嵌套原则最近嵌套原则一个在子程序一个在子程序B1中说明的名字中说明的名字X只在只在B1中中有效（局部于

10、有效（局部于B1）；）；如果如果B2是是B1的一个内层子程序且的一个内层子程序且B2中对中对标识符标识符X没有新的说明，则原来的名字没有新的说明，则原来的名字X在在B2中仍然有效。如果中仍然有效。如果B2对对X重新作了说明，重新作了说明，那么，那么，B2对对X的任何引用都是指重新说明的任何引用都是指重新说明过的这个过的这个X。program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A

11、(integer)PASCAL提供了丰富的数据类型和运算提供了丰富的数据类型和运算方式，它允许用户动态地申请和退还存方式，它允许用户动态地申请和退还存贮空间。贮空间。 ADA 程序包程序包(package)：把数据和操作代码封装在：把数据和操作代码封装在一起，支持数据抽象。一起，支持数据抽象。一个程序包分为两部分：一个程序包分为两部分：可见的规范说明部分，它定义了程序包外面可以访可见的规范说明部分，它定义了程序包外面可以访问的对象。问的对象。程序包体，它实际定义程序包的实现细节。程序包体，它实际定义程序包的实现细节。package STACKS is type ELEM is priva

12、te; type STACK is limited private; procedure push (S: in out STACK; E: in ELEM); procedure pop (S: in out STACK; E: out ELEM); end STACK;package body STACKS is procedure push(S: in out STACK; E: in ELEM); begin 实现细节实现细节 end push; procedure pop (S: in out STACK; E: out ELEM); begin 实现细节实现细节 end pop;e

13、nd; JAVA Java是一种面向对象的高级语言是一种面向对象的高级语言类（类（Class）继承继承(Inheritance) 多态性多态性(Polymorphism)和动态绑定和动态绑定(Dynamic binding)class Car int color_number; int door_number; int speed; push_break ( ) add_oil ( ) class Trash_Car extends car double amount; fill_trash ( ) 2.2.3 2.2.3 数据类型与操作数据类型与操作一个数据类型通常包括以下三种要素：一

14、个数据类型通常包括以下三种要素：用于区别这种类型数据对象的属性用于区别这种类型数据对象的属性这种类型的数据对象可以具有的值这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作可以作用于这种类型的数据对象的操作2.2.3 2.2.3 数据类型与操作数据类型与操作一初等数据类型一初等数据类型数值类型：整型、实型、复数、双精度，数值类型：整型、实型、复数、双精度，运算：运算：+ +，- -，* *，/ /等等逻辑类型：布尔运算：逻辑类型：布尔运算：，字符类型：符号处理字符类型：符号处理指针类型指针类型标识符与名字标识符与名字标识符标识符：以字母开头的：以字母开头的，由字母数字

15、组成由字母数字组成的字符串的字符串。标识符标识符与与名字名字两者有本质区别：两者有本质区别：标识符标识符是语法概念是语法概念名字名字有确切的意义和属性有确切的意义和属性Jordan ?标识符！?标识符与名字标识符与名字名字：名字：值：单元中的内容值：单元中的内容属性：类型和作用域属性：类型和作用域名字的性质的说明方式：名字的性质的说明方式：由说明语句来明确规定的由说明语句来明确规定的隐含说明：隐含说明：FORTRAN FORTRAN 以以I,J,K,I,J,K,N N为首的名字为首的名字代表整型，否则为实型。代表整型，否则为实型。动态确定：走到哪里，是什么，算什么动态确定：走到哪里，是什

16、么，算什么二二数据结构数据结构1 1 数组数组逻辑上，数组是由同一类型数据所组成逻辑上，数组是由同一类型数据所组成的某种的某种n n维矩形结构，沿着每一维的距离，维矩形结构，沿着每一维的距离，称为称为下标下标。数组可变与不可变：编译时能否确定其存数组可变与不可变：编译时能否确定其存贮空间的大小。贮空间的大小。访问：给出数组名和下标值访问：给出数组名和下标值存放方式存放方式: : 按行存放按行存放, ,按列存放按列存放数组元素地址计算数组元素地址计算数组数组A10,20A10,20的的A1A1，11为为a a，各维下标，各维下标为为1 1，按行存放，那么按行存放，那么AiAi，jj地址为

17、：地址为：a+(i-1)a+(i-1)* *20+(j-1)20+(j-1) 数组元素地址计算公式数组元素地址计算公式内情向量内情向量把数组的有关信息记录在一个把数组的有关信息记录在一个“内情向内情向量量”中，每个数组的内情向量必须包括：中，每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及维数，各维的上、下限，首地址，以及数组（元素）的类型。数组（元素）的类型。l1 u1 d1 l2 u2 d2 ln un dn n C type a 2 2 记录记录逻辑上说，记录结构由已知类型的数据组逻辑上说，记录结构由已知类型的数据组合在一起的一种结构。合在一起的一种结构。record

18、char NAME20; integer AGE; bool MARRIED; CARD1000 访问：复合名访问：复合名 CARDk.NAME CARDk.NAME 存储：连续存放存储：连续存放域的地址计算：相对于记录结构起点的相域的地址计算：相对于记录结构起点的相对数对数OFFSETOFFSET。3 3 字符串、表格、栈字符串、表格、栈字符串：符号处理、公式处理字符串：符号处理、公式处理表格：本质上是一种记录结构表格：本质上是一种记录结构线性表：一组顺序化的记录结构线性表：一组顺序化的记录结构栈：一种线性表，后进先出，栈：一种线性表，后进先出，POP, PUSHPOP, PUSH

19、三三抽象数据类型抽象数据类型一个抽象数据类型包括：一个抽象数据类型包括：数据对象的一个集合；数据对象的一个集合；作用于这些数据对象的抽象运算的集合；作用于这些数据对象的抽象运算的集合；这种类型对象的封装，即，除了使用类型中所定义这种类型对象的封装，即，除了使用类型中所定义的运算外，用户不能对这些对象进行操作。的运算外，用户不能对这些对象进行操作。程序设计语言对抽象数据类型的支持程序设计语言对抽象数据类型的支持 Ada语言通过程序包（语言通过程序包（package）提供了数据封装）提供了数据封装的支持的支持 Smalltalk、C+和和Java语言则通过类（语言则通过类（Class）对

20、）对抽象数据类型提供支持。抽象数据类型提供支持。 2.2.4 2.2.4 语句与控制结构语句与控制结构一表达式一表达式表达式由运算量（也称操作数，即数据引用或表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。函数调用）和算符（操作符）组成。形式：中缀、前缀、后缀形式：中缀、前缀、后缀 X X* *Y -A PY -A P表达式形成规则表达式形成规则算符的优先次序算符的优先次序一般的规定一般的规定PASCALPASCAL：左结合：左结合A+B+C=(A+B)+CFORTRANFORTRAN：对于满足左、右结合的算符可任：对于满足左、右结合的算符可任取一种，如取一种，如A+

21、B+CA+B+C就可以处理成就可以处理成(A+B)+C(A+B)+C，也，也可以处理成可以处理成A+(B+C)A+(B+C)。注意两点：注意两点：代数性质能引用到什么程度视具体的语言代数性质能引用到什么程度视具体的语言不同而不同；不同而不同；在数学上成立的代数性质在计算机上未必在数学上成立的代数性质在计算机上未必完全成立。完全成立。二语句二语句赋值语句：赋值语句： A := B A := B 名字左值名字左值：该名字代表的那个单元（地址）称：该名字代表的那个单元（地址）称为该名字的左值。为该名字的左值。( (所代表的存贮单元的地址所代表的存贮单元的地址) )右值右值：一个名字的值称为该名字

22、的右值。：一个名字的值称为该名字的右值。( (所所代表的存贮单元的内容代表的存贮单元的内容) ) 控制语句：控制语句： l无条件转移语句无条件转移语句 goto Ll条件语句条件语句 if B then S if B then S1 else S2l循环语句循环语句 while B do S repeat S until B for i:=E1 step E2 until E3 do Sl过程调用语句过程调用语句 call P(X1, X2, . ,Xn)l返回语句返回语句 return (E) 说明语句：定义各种不同数据类型的变量说明语句：定义各种不同数据类型的变量或运算，定义名字的性质。或

23、运算，定义名字的性质。简单句和复合句简单句和复合句简单句：不包含其他语句成分的基本句简单句：不包含其他语句成分的基本句复合句：句中有句的语句复合句：句中有句的语句复习：程序语言的定义复习：程序语言的定义程序语言由两方面定义：程序语言由两方面定义：语法语法：一组规则：一组规则，用它可以形成和产生一个合用它可以形成和产生一个合式式(well-formed)的程序的程序词法规则词法规则：单词符号的形成规则：单词符号的形成规则。常数、标识符、基本字、算符、界符等。常数、标识符、基本字、算符、界符等。有限自动机有限自动机语法规则语法规则：语法单位的形成规则：语法单位的形成规则。表达式、语句、分

24、程序、过程、函数、程序等表达式、语句、分程序、过程、函数、程序等; ;上下文无关文法上下文无关文法语义语义: :一组规则一组规则，用它可以定义一个程序的意用它可以定义一个程序的意义义复习：程序语言的基本功能和层次结构复习：程序语言的基本功能和层次结构程序语言的基本功能：描述数据和对数据的运算。程序语言的基本功能：描述数据和对数据的运算。所谓程序，本质上说是描述一定数据的处理过程。所谓程序，本质上说是描述一定数据的处理过程。程序程序| |子程序或分程序、过程、函数子程序或分程序、过程、函数| |语句语句| |表达式表达式| |数据引用数据引用算符算符函数调用函数调用复习：复习：高级语言的

25、一般特性高级语言的一般特性高级语言的分类高级语言的分类程序结构程序结构数据类型与操作数据类型与操作初等数据类型初等数据类型数据结构数据结构抽象数据类型抽象数据类型语句与控制结构语句与控制结构2.32.3 程序语言的语法描述程序语言的语法描述基本概念(一、术语)元素的非空有穷集合。元素的非空有穷集合。例如，例如，= a, b, c 1. 字母表字母表根据字母表的定义，根据字母表的定义，是字母表，它由是字母表，它由a a、b b、c c三个元素组成。三个元素组成。基本概念(一、术语) 是一个字母表，由是一个字母表，由0 0、1 1两个元素组成。两个元素组成。注意注意:例如，例如，

26、 =0, 1 (2) 字母表中的元素字母表中的元素, 可以是字母、数可以是字母、数字或其他符号。字或其他符号。(1) 字母表中至少包含一个元素。字母表中至少包含一个元素。基本概念(一、术语) 字母表中的元素称为符号或称为字符。字母表中的元素称为符号或称为字符。例如，前述例子中例如，前述例子中2. 符号（字符）符号（字符）a、b、c 是字母表是字母表中的符号；中的符号；0、1 是字母表是字母表中的符号。中的符号。基本概念(一、术语) 例如，设有字母表例如，设有字母表= a, b, c 符号的有穷序列称为符号串。符号的有穷序列称为符号串。符号串总是建立在某个特定字母表上的且符号串总是建立在某个特

27、定字母表上的且只由字母表上的有穷多个符号组成。只由字母表上的有穷多个符号组成。则有符号串则有符号串 a a，b b，abab，baba， cbacba，abcabc 3. 符号串（字）符号串（字）基本概念(一、术语)说明说明: :不包含任何符号的符号串不包含任何符号的符号串, , 称为空符号串，称为空符号串，用用表示。表示。符号串中符号的顺序是很重要的。符号串中符号的顺序是很重要的。abab和和baba是字母表是字母表上上的两个不同的符号串。的两个不同的符号串。空符号串由空符号串由0 0个符号组成，其长个符号组成，其长度度| |=0|=0基本概念(二、运算) 设设x和和y是符号串，则串是符号

28、串，则串xy称为它们的连结。称为它们的连结。则则XYABC10A，YX10AABC。注意：对任意一个符号串注意：对任意一个符号串x，1. 符号串的连结符号串的连结例如，设例如，设XABC，Y10A我们有我们有 xxx。基本概念(二、运算)2. 集合的乘积集合的乘积设设A和和B是符号串的集合是符号串的集合, 则则A和和B的乘积的乘积定义为：定义为：集合的乘积是满足于集合的乘积是满足于 xA, yB的所的所有符号串有符号串 xy 所构成的集合。所构成的集合。AB=xy | xA, yB A=A =A基本概念(二、运算)例如：例如：设设A= a, b , B= c, d 则则AB= ac, a

29、d, bc, bd 由于对任意的符号串由于对任意的符号串x，总有，总有 x=x =x所以所以, 对任意集合对任意集合A, 我们有我们有:基本概念(二、运算) 特别指出的是，特别指出的是，是符号串是符号串, 不是集合，不是集合，而而表示由空符号串表示由空符号串所组成的集合所组成的集合, 但这样但这样的集合不是空集合的集合不是空集合= 。基本概念(二、运算) 3. 符号串的幂运算符号串的幂运算设设x是符号串是符号串, 则则x的幂运算定义为：的幂运算定义为： x0= x1= x x2= xx x3= xxx xn= xx x=x xn-1(n0)n注意：注意：x0 1基本概念(二、运算)例如

30、例如, 设设 xabc 则则x0= x1=abcx2=xx=abcabc 基本概念(二、运算) 4. 集合的幂运算集合的幂运算设设A是符号串的集合，则集合是符号串的集合，则集合A的幂运算定的幂运算定义为：义为：A0= A1=AA2=AA An= AA A=AAn-1(n0)n基本概念(二、运算)例如，设例如，设A= a, b ，则，则A0= A1=A= a, b A2=AA= aa, ab, ba, bb A3=AAA=A2A= aaa, aab, aba, abb, baa, bab, bba, bbb 基本概念(二、运算)5. 集合集合A的正则闭包的正则闭包A与自反闭包与自反闭包A* 设

31、设A是符号串的集合，则是符号串的集合，则A的正则闭包的正则闭包A和和A的的自反闭包自反闭包A*的定义为的定义为:A+=A1A2 An A*= A0 A1A2 An =A+基本概念(二、运算) 可见可见, ,集合集合A的正则闭包表示的正则闭包表示A上元素上元素a, ,b构构成的所有符号串的集合成的所有符号串的集合, ,集合集合A的自反闭包比集的自反闭包比集合合A的正则闭包多含一个空符号串的正则闭包多含一个空符号串。例如，设例如，设A= a, b , 则：则：A+= a, b, aa, ab, ba, bb, aaa, aab, A*= , a, b, aa, ab, ba, bb, aaa,

32、aab, *的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U & V 例：设：例：设：U a, aa V b, bb 那么：那么：UV= ab, abb, aab, aabb *的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U & V V自身的自身的 n次积记为次积记为Vn=VVV 规定规定V0= ，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包; 记记 VVV* ，称，称V+是是V的正规闭包。的正规闭包。设：设：U a, aa 那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, 2.3.

33、1 2.3.1 上下文无关文法上下文无关文法文法文法：描述语言的语法结构的形式规则描述语言的语法结构的形式规则 He gave me a book. He He me me book book a a gave gave He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book 终结符号终结符号【VT 】：从语法角度看，终结符是一个语言的不可再分的基本符号。如：基本字、标识符、常数、算符和界符等。非终结符号（语法变量）非终结符号（语法变量）【VN 】：用来代

34、表语法单位。如“算术表达式”、“布尔表达式”、“赋值句”、“子程序”、“函数”等。一个非终结符代表一个一定的语法概念，是一个类（集合）记号，而不是一个个体记号。上下文无关文法的定义：上下文无关文法的定义：一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(V G=(VT T，V VN N，S S，P)P)，其中，其中V VT T：终结符集合：终结符集合( (非空非空) )V VN N：非终结符集合：非终结符集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的开始符号，：文法的开始符号，S S V VN NP P：产生式集合：产生式集合( (有

35、限有限) )，每个产生式形式为，每个产生式形式为P P， P P V VN N， ( (V VT T V VN N) )* *开始符开始符S S至少必须在某个产生式的左部出现至少必须在某个产生式的左部出现一次。一次。几点规定：几点规定： “ ”也可以用也可以用“:=表示，表示，这种表示称为巴这种表示称为巴科斯范式科斯范式(BNF) P 1 P 2 可缩写为可缩写为 P 1| 2| n P n 其中，其中，“|”读成读成“或或”，称为，称为P的一个候选式。的一个候选式。表示一个文法时，通常只给出开始符号和产生式，表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：如上例，可表示为

36、：G(E)： E i | E+E | E*E | (E) 例，定义只含例，定义只含+，*的算术表达式的文法的算术表达式的文法 G=，其中，其中，P由下列产生式组成：由下列产生式组成：E iE E+EE E*EE (E) 定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式，且且， (VT VN)* 。如果如果 1 2 n，则我们称这个序，则我们称这个序列是从列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n 。对文法对文法G(E)： E i | E+E | E*E |

37、 (E)E (E) (E+E) (i+E) (i+i)n*1 用用表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步，可以推出若干步，可以推出 n n。* 所以所以：即即或或*S ,|)(*TV SGLq定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。如果如果，则，则称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全所产生的句子的全体是一个体是一个语言语言，将它记为，将它记为 L(G)L(G)。通常，用通常，用表示：从表示：从 1 1出发，经过一出发，经过

39、语言为例：给出产生语言为anbn|n 1的文法。的文法。 G3(S)： S aSb S abq例：给出产生语言为例：给出产生语言为ambn|1nm2n的的文法。文法。 G4(S)： S aSb | aaSb S ab | aab 从一个句型到另一个句型的推导往往不唯从一个句型到另一个句型的推导往往不唯一。一。 E+Ei+Ei+i E+EE+ii+i 最左推导最左推导：任何一步：任何一步都是对都是对中的最中的最左非终结符进行替换。左非终结符进行替换。最右推导最右推导：任何一步：任何一步都是对都是对中的最中的最右非终结符进行替换。右非终结符进行替换。递归规则与递归文法递归规则是指那些在

40、规则的右部含有与规则左部相同符号的规则。例如：UxUy，右部含有与规则左部相同符号U，那么就是递归规则。如果这个相同的符号出现在右部的最左端，则为左递归规则。如 UUy 如果这个相同的符号出现在右部的最右端，则为右递归规则。如 UxU 若文法中至少包含一条递归规则,则称文法是直接递归的。若文法中不含递归规则，但有推导过程 U xUy，所以该文法为间接递归文法。递归文法使我们能用有穷的文法刻画无穷的语言。 2.3.2 2.3.2 语法树与二义性语法树与二义性用一张图来表示一个句型的推导，有助于理解句子语法结构的层次。定义：设文法G=(VN,VT,P,S ),对于文法G的任意一个句型都存

41、在一棵相应的语法树：结点由符号组成。根结点对应于开始符号。只有非终结符号对应的结点有子结点。一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。用一张图表示一个句型的推导用一张图表示一个句型的推导, ,称为语法树。称为语法树。 (i(i* *i+i)i+i)的语法树的语法树Ei+*()EiiEEEEE (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)(i*i+i) 一棵语法树是不同推导过程的共性抽象。一棵语法树是不同推导过程的共性抽象。G(E)： E i | E+E | E*E | (E)(i*i+i)

42、如果使用最左如果使用最左( (右右) )推导，则一个最左推导，则一个最左( (右右) )推导与语法树一一对应。推导与语法树一一对应。一个句型是否只对应唯一一棵语法树？一个句型是否只对应唯一一棵语法树？Ei+*()EiiEEEEE+*()EiEEiiEE 定义：如果一个文法存在某个句子对应两定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个颗不同的语法树，则说这个文法是二义的文法是二义的。G(E)： E i|E+E|E*E|(E) 是二义文法。是二义文法。语言的二义性：一个语言的二义性：一个语言是二义性的语言是二义性的，如，如果对它不存在无二义性的文法。果对它不存在无二义性的文法

44、 F | T*F F (E) | i)EEEFFTTTTi+*(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) 描述程序设计语言时，对于上下文无关文描述程序设计语言时，对于上下文无关文法的限制法的限制：1 1 不含不含P PP P形式的产生式形式的产生式2 2 每个非终结符每个非终结符P P必须有用处必须有用处即：即：【对于P不存在永不终结的回路。必须存在终结符串VT*,使得P=】PS* TVrrP2.3.3 2.3.3 形式语言鸟瞰形式语言鸟瞰 Chomsk

45、y于于1956年建立形式语言体系，年建立形式语言体系，他把文法分成四种类型：他把文法分成四种类型：0，1，2，3型。型。与上下文无关文法一样，它们都由四部与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。分组成，但对产生式的限制有所不同。0型型(短语文法，图灵机短语文法，图灵机)：产生式形如：产生式形如：其中：其中： (VT VN)*且至少含有一个非终结且至少含有一个非终结符；符； (VT VN)*1型型(上下文有关文法，线性界限自动机上下文有关文法，线性界限自动机)：产生式形如：产生式形如：其中：其中：| | | |，仅，仅 S 例外。例外。2型型(上下文无关文法

46、，非确定下推自动机上下文无关文法，非确定下推自动机)：产生式形如：产生式形如： A 其中：其中：A VN； (VT VN)*。3型型(正规文法，有限自动机正规文法，有限自动机)：产生式形如：产生式形如： A B 或或 A 其中：其中： VT*；A，B VN 产生式形如：产生式形如： A B 或或 A 其中：其中： VT*；A，B VN右线性文法右线性文法左线性文法左线性文法四种类型描述能力比较四种类型描述能力比较0型1型2型3型 L5=anbn|n 1 不能由正规文法产生，但不能由正规文法产生，但可由上下文无关文法产生：可由上下文无关文法产生： G5(S)： S aSb| ab L6=an

47、bncn|n 1不能由上下文无关文法产不能由上下文无关文法产生，但可由上下文有关文法产生：生，但可由上下文有关文法产生： G6(S)： S aSBC| aBC CB BC aB ab bB bb bC bc cC cc 程序设计语言不是上下文无关语言，甚至程序设计语言不是上下文无关语言，甚至不是上下文有关语言。不是上下文有关语言。 L7= c | (a|b)*不能由上下文无关文不能由上下文无关文法产生，甚至连上下文有关文法也不能产法产生，甚至连上下文有关文法也不能产生，只能由生，只能由0 0型文法产生。型文法产生。标识符引用标识符引用过程调用过程中，过程调用过程中，形形- -实参数地对应性实参数地对应性(如如个数，顺序和类型一致性个数，顺序和类型一致性) ) 现今程序设计语言的语言结构，用上下文现今程序设计语言的语言结构，用上下文无关文法描述就足够了。无关文法描述就足够了。作业 P36-6，7，8，9，10，11

展开阅读全文