郑州大学编译原理课件第2章.ppt

1、第二章 高级语言及其语法描述,概述程序语言的结构和主要的共同特征 介绍程序语言的语法描述方法,学习构造编译程序，必须掌握如下内容： 源语言 （词法、语法、语义） 目标语言 （硬件系统结构、指令集合、 操作系统的功能 ） 编译方法,2.1 程序语言的定义,程序语言是一个记号系统，主要有语法、语义和语用等三方面定义。 语法 定义语言的词法和语法的形式规则 语义 定义语言的单词符号和语法单位的意义 语用 定义程序设计技术和语言成分的使用方法，它使语言的基本概念与语言的外界联系起来,2.1.1 语法, 一个语言的语法规则定义了程序的形式结构。, 任何语言程序都可看成是一定字符集上的一个字符串（有限序列

2、）。, 语法规则是指这样的一组规则，用它可以形成和产生一合式（合法）的程序。这些规则的一部分称为词法规则，另一部分称为语法规则（或产生规则）。,例如： 字符串 0.5*x+c,单词符号： 0.5 x c * + 语法单位： 0.5*x+c （表达式）,单词符号,单词符号 是语言中具有独立意义的最基本结构。 词法规则 定义了程序中单词符号的形成规则。即字母表中的哪些字符可以构成一个合法的单词。 单词符号种类：常量、标识符、基本字、 界符、运算符 描述词法规则的有效工具： 正规式、正规文法、 有限自动机,语法规则,语法规则 规定了如何从单词符号串中形成更大的结构（即语法单位）。它是语法单位的形成规

3、则。 语法单位包括： 表达式、语句、分程序、函数、 过程、程序。 描述语法规则的有效工具： 上下文无关文法,2.1.2 语义,语义规则 是指这样的一组规则，使用它可以定义一个程序的意义。 描述语义规则的工具： 基于属性文法的语法制导下的翻译方法,对于一个语言来说，不仅要定义它的词法、语法规则，而且还要定义它的单词符号和语法单位的意义。这就是语义问题。 离开语义，语言只不过是一堆符号的集合。,2.1.3 程序,所谓程序，是描述一定数据的处理过程，即包括描述数据和对数据的运算两个功能。 程序结构： 程序 子程序 或 分程序 语句 表达式 数据引用 算符 函数调用,2.2 高级语言的一般特性,高级语

4、言的分类,从语言范型来分，程序设计语言分四类： 强制式语言 （Imperative Language） 应用式语言 （Applicative Language） 基于规则的语言（Rule-based Language） 面向对象语言 （Object-Oriented Language）,程序结构,一个高级语言程序通常由若干子程序段（过程、函数）构造。许多语言还引入了类、程序包等更高级的结构。,一、FORTRAN 一个Fortran程序由一个主程序和若干个辅程序段组成。 PROGRAM MAIN END SUBROUTINE SUB1 END SUBROUTINE SUB1 END,二、Pasc

5、al,Pascal是一个允许子程序嵌套的语言。 Program EX 说明部分 procedure P1; procedure p11; begin end; begin end; Begin 执行语句部分 End.,三、Ada,在Ada语言中引入了程序包（Package），它可以把数据和操作代码封装在一起，支持数据抽象。 一个程序包有两部分： 可见的规范说明： 定义程序包外面可以访问的对象。 程序包体： 定义程序包的实现细节。 见P17,四、JAVA,Java 是一种面向对象的高级程序语言，它很重要的方面是类（Class）及继承（Inheritance）的概念。同时支持多态性（Polymor

6、phism）和动态绑定（Dynamic binding）等特性。 见P18,数据类型与操作,一个数据类型通常包括以下三个要素： 用于区别这种类型的数据对象的属性； （类型名，作用域） 这种类型的数据对象可以具有的值； （ 取值范围 ） 可以作用于这种类型的数据对象的操作。 （运算符）,一、初等数据类型 数值数据、逻辑数据、字符数据、指针类型,二、数据结构 数组、记录、字符串、表格、栈和队列,三、抽象数据类型 一个抽象数据类型包括： （1）数据对象的一个集合； （2）作用于这些数据对象的抽象运算的集合； （3）这种类型对象的封装。,语句与控制结构,一、表达式 表达式是由运算量和运算符组成的。运算

7、量亦称操作数，即数据引用或函数调用；运算符有算术运算符、逻辑运算符、关系运算符等，运算符之间有规定的优先级和结合性。,表达式的形成规则： （1）变量、常量是表达式； （2）若E1，E2为表达式，是二元运算符， 则 E1 E2 也是表达式； （3）若E为表达式，是一元运算符，则 E (或E ) 也 是表达式； (4) 若E为表达式,则 ( E )也是表达式。,二、语句,1、赋值句 2、控制语句 无条件转移语句 条件语句 循环语句 过程（或函数）调用语句 返回语句 3、说明句 4、简单句和复合句,2.3 程序语言的语法描述,本节介绍高级语言语法结构的形式化描述问题,基本概念 设是一个有穷字母表，它

8、的每个元素称为一个符号。 上的一个符号串是指由中的符号所构成的一个有穷序列。不包含任何符号的序列称为空字，记为 。 *表示上的所有符号串组成的集合。空字也包括在其中。 表示不含任何元素的空集 。, *的子集U和V的（连接）积定义为 UV = | U & V 即集合UV中的符号串是由U和V的符号串连接而成的。 V自身的n次积（连接）记为 Vn = VV V 规定 V0 = V* = V0 U V1 U V2 U V3 U 称 V* 是V的闭包。 V + = VV* 称 V+是V的正则闭包。 例如 若 = a , b 则 * = ,a,b,aa,ab,ba,bb,aaa , ,上下文无关文法,文法

9、是描述语言语法结构的形式规则，即语法规则。 语法规则必须是正确的，且易于理解。 上下文无关文法是这样一种文法，它所定义的语法范畴是完全独立于这种范畴所可能出现的环境的。 以后，凡“文法”一词若无特别说明，则均指上下文无关文法。,例如：英文的语法规则, He | me a gave book,“ ”表示“由组成”或“定义为”。 有时，“” 也用 “ := ”表示，后者为巴科斯范式（BNF），前者为其简化表示。,例如: 判断He gave me a book.是否为正确句子,方法一： He gave me a book,若能利用语法规则，画出其语法分析树，则证明是正确的句子。,方法二：利用规则进行

10、推导。,句子 He He He gave He gave He gave me He gave me He gave me a He gave me a book,上下文无关文法定义,归纳起来，一个上下文无关文法包括四个组成部分： 一组终结符号 如：me ,book,gave 等 一组非终结符号 如：， 等 一个开始符号 如: 一组产生式 如： ,上下文无关文法定义,形式上说，一个上下文无关文法G是一个四元式： G=（VT，VN，S，），其中： VT是一个非空有限集，它的每个元素为终结符号； VN是一个非空有限集，它的每个元素为非终结符号 且VTVN= S 是一个非终结符号，称为开始符号； 是

11、产生式有限集合，形如 A 其中：A VN， (VT U VN)*。 注： 开始符号S是一个特殊的非终结符号，它至少必须在某个产生式的左部出现一次。,若产生式的左部相同，则可以合并。,例如： P 1 P 2 P n 可合并为： P1|2| |n 其中：每个i 称为P的一个侯选式 “ ” 读为 “定义为” “|” 读为 “或”,约定,1. 大写字母A、B、C或汉语词组通常代表非终结符； 2. 小写字母a、b、c代表终结符； 3. 、代表(VT U VN)*,例如：下面是一个上下文无关文法。 G(E): E i | EAE A * | +,例如：算术表达式的定义,1.常量5、变量i是算术表达式； 2

12、.若E1，E2是算术表达式，则 E1+E2,E1*E2,(E1)也是算术表达式。,用产生式来描述 G(E)： E E + E E EE E (E) E i E 5,EE+E | E*E | (E) | i | 5,一个上下文无关文法是如何定义一个语言呢?,从开始符号出发,反复连续使用产生式,对非终结符施行替换和展开,直到推导的字符串全由终结符组成（即 句子），所有句子的集合即为该文法定义的语言。,例如：文法 G(S): S AB A a | aA B b | Bb,则该文法定义的语言为： L(G)= ambn | m , n 0 ,例题 证明 i+5 是一个算术表达式,证明： E = E+E

13、( EE+E),= i+E ( E i ),= i+5 ( E 5 ),故 i+5 是算术表达式。,解释：= 仅表示使用一次规则的一步推导。,术语,1. 称串A能直接推出，即： A 仅当 A 是一个产生式。,2. 如果 1 2 n 则称从1可推导出n,3.用 1 n 表示从1出发，经过一步或多步， 可推导出 n,4. 用 1 n 表示从 1出发，经过0步或多步， 可推导出n 即 1 n 意味着1 = n 或 1 n,5. 若 S 是开始符号，且 S 则称 是文法的一个句型 若 VT* ，则称 为文法的一个句子。,术语,术语,例题2.1 设文法G1如下，求所定义的语言？ SbA Aa | aA,

14、6.文法G所产生的句子的全体构成一个语言L(G) L(G)= | S & VT* ,分析： S = bA = ba S = bA =baA=baaA=.=baaa,解：L(G1)= ban | n0 ,例题2.2,分析过程： A= aA =aaA=aaaA=aa B = Bb =Bbb=Bbbb=.=bb S=AB=aabb,文法G2: S AB A a | aA B b | Bb 求该文法定义的语言？,解：G2定义的语言为： L(G2) = ambn | m,n0 ,例题2.3,误解：文法G3: S AB A a|aA B b|bB,构造一个文法G3，使得 L(G3)= anbn | n0

15、,正解：文法G3: S aSb | ab,例题2.4,构造一个文法G4，使得 L(G4)= anban | n0 ,正解：文法G4: SaSa|b,误解：文法G4: S AbA A |aA,因为 SAbA bA baA baaA baa,例题2.5,构造一个文法G4，使得 L(G4)= ambn | mn0 ,正解：文法G4: SAB Aa|aA BaBb|,最左推导和最右推导,下面两个推导都是正确的: (1) E+E E+ii+i (2) E+E i+Ei+i,从一个句型到另一个句型的推导过程不是唯一的。 例如： E+E i+i,为了对句子的结构进行确定性的分析，往往只考虑最左推导和最右推导

16、。,最左推导:,是指任何一步 推导都是对的最左非终结符进行替换的。 最右推导： 是指任何一步 推导都是对的最右非终结符进行替换的。,例如：写出句型 (i+i*i) 的最左推导。,解：E (E)(E+E)(i+E) (i+E*E)(i+i*E)(i+i*i),2.3.2 语法分析树和二义性,语法分析树也可以描述一个句型的推导。 语法树的根由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时 ，就产生下一代新结，候选式中自左自右的每个字符对应一个新结。 在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末（叶子）自左自右排列起来就是一个句型。,一棵语法树表示了一个句型的种种

17、可能的不同推导过程，它有助于理解一个句子语法结构的层次。,E （ E ） E + E i E * E i i,例如： 画出句子(i+i*i)的语法树。, E ( E ),一棵语法树是一个句型的种种不同推导过程的共性抽象，是它们的代表。 一棵语法树完全等价于一个最左（右）推导。,文法的二义性,一个句型是否只对应唯一的一棵语法树呢？ 即，它是否只有唯一的一个最左推导？,不尽然。 例如：句子(i+i*i)就存在两个不同的最左推导：,(1) E(E)(E+E)(i+E)(i+E*E)(i+i*E)(i+i*i) (2)E(E)(E*E)(E+E*E)(i+E*E)(i+i*E)(i+i*i),在一个文

18、法中，若存在某个句子有两个不同的最左推导，则称该文法是二义的。或者说， 在一个文法中，若存在某个句子有两棵不同的语法树，则称该文法是二义的。,注 文法的二义性问题是不可判断的。 即，不存在一个算法，它能在有限步内判断一个文法是否是二义的。,文法的二义性,文法的二义性与语言的二义性是两个不同的概念。,注意：,例题2.4 对算术表达式构造一个无二义的文法。,解：无二义的文法如下： ET | E+T TF | T*F F(E) | i | 5,提示： 考虑算符的优先性和结合性。,约定,作为描述程序语言的文法，有以下几点限制： （1） 不能有任何产生式 : PP （2） 每个非终结符P必须都有用处。即

19、，必须存在含P的句型： S=P 且 P= VT*,2.3.3 形式语言鸟瞰（1）,自从Chomsky于1956年建立形式语言的描述以来，形式语言的理论发展得很快。这种理论对计算机科学有着深刻的影响，特别是对程序语言的设计、编译方法和计算复杂性等方面更有重大的作用。,Chomsky把文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别,在于对产生式的形式施加了不同的限制。从0型到3型依次增强，但它们表达语言的能力则依次减弱。,2.3.3 形式语言鸟瞰（2）,设G=（VT，VN，S，）是0型文法，如果它的每个产生式： 其中： , ( VTUVN )* 且中至少含有一个符号AVN, 0型文法又称为短语文法。,对0型文法施加第 i 条限制，就得