郑州大学编译原理第2章

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

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

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

4、言的分类 从语言范型来分，程序设计语言分四类： 强制式语言 （imperative language） 应用式语言 （applicative language） 基于规则的语言（rule-based language） 面向对象语言 （object-oriented language） 一个高级语言程序通常由若干子程序段（过程、函数）构造。许多语言还引入了类、程序包等更高级的结构。一、fortran一个fortran程序由一个主程序和若干个辅程序段组成。program main endsubroutine sub1 endsubroutine sub1 end二、pascalpascal是一个

5、允许子程序嵌套的语言。 program ex 说明部分 procedure p1; procedure p11; begin end; begin end;begin 执行语句部分 end.三、ada 在ada语言中引入了程序包（package），它可以把数据和操作代码封装在一起，支持数据抽象。一个程序包有两部分： 可见的规范说明： 定义程序包外面可以访问的对象。 程序包体： 定义程序包的实现细节。 见p17 四、java java 是一种面向对象的高级程序语言，它很重要的方面是类（class）及继承（inheritance）的概念。同时支持多态性（polymorphism）和动态绑定（dyn

6、amic 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次积（连接）记为 v vn n = = vv vv v v规定 v0 = v* = v0 u v1 u v2 u v3 u 称 v* 是v的闭包。 v + = vv* 称 v+是v的正则闭包。例如 若若 = a , b = a , b 则则 * * = = ,a,b,aa,ab,ba,bb,aaa,a,b,aa,ab,ba,bb,aaa , , 文法文法是描述语言语法

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

10、me he gave me a he gave me a book上下文无关文法定义 归纳起来，一个上下文无关文法包括四个组成部分： 一组终结符号终结符号 如：me ,book,gave 等 一组非终结符号非终结符号 如：， 等 一个开始符号开始符号 如: 一组产生式产生式 如： 上下文无关文法定义形式上说，一个上下文无关文法g g是一个四元式： g=（vt，vn，s， ），其中：v vt t是一个非空有限集，它的每个元素为终结符号； v vn n是一个非空有限集，它的每个元素为非终结符号 且vtvn= s s 是一个非终结符号，称为开始符号； 是产生式有限集合，形如 aa 其中：a vn，

11、(vt u vn)*。注： 开始符号s是一个特殊的非终结符号，它至少必须在某个产生式的左部出现一次。若产生式的左部相同，则可以合并。例如： p 1 p 2 p n可合并为： pp1 1|2 2| | | |n n 其中：每个i 称为p的一个侯选式 “ ” 读为 “定义为” “| |” 读为 “或” 1. 大写字母a、b、c或汉语词组通常代表非终结符； 2. 小写字母a、b、c代表终结符； 3. 、代表(vt u vn)*下面是一个上下文无关文法。 g(e):g(e): e e i | eae i | eae a 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 5ee+e | e*e | (e) | i | 5 从开始符号出发,反复连续使用产生式,对非终结符施行替换和展开,直到推导的字符串全由终结符组成（即 句子），所有句子的集合即为该文法定义的语言。例如：文法 g(s):g(s): s s abab a a a | aa a | aa b b b | bb b | bb则该文法定义的语言为： l(g)= ambn | m , n 0 证明： e = e+e ( ee+e) = i+e ( e i

13、) = i+5 ( e 5 )故 i+5 是算术表达式。解释：= 仅表示使用一次规则的一步推导。1. 称串a能直接推出直接推出，即： 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 是开始符号，且 s s 则称 是文法的一个句型 若 vt* ，则称 为文法的一个句子。*+*设文法g1如下，求所定义的语言？ sba aa | aa6.文法g g所产生的句子的全体构成一个语言l

14、(g) l(g)= | s & vt* 分析： s = ba = ba s = ba =baa=baaa=.=baaa解：l(g1)= ban | n0 *分析过程：a= aa =aaa=aaaa=aab = bb =bbb=bbbb=.=bbs=ab=aabb文法g2: s s abab a a a | aaa | aa b b b | bbb | bb 求该文法定义的语言？解：g2定义的语言为： l(g2) = ambn | m,n0 误解：文法g3: s ab a a|aa b b|bb构造一个文法g3，使得 l(g3)= anbn | n0 正解：文法g3: s s asb |

15、 ab asb | ab构造一个文法g4，使得 l(g4)= anban | n0 正解：文法g4: sasa|b误解：文法g4: s aba a |aa 因为saba ba baa baaa baa 构造一个文法g4，使得 l(g4)= ambn | mn0 正解：文法g4: s sabab a aa|aaa|aa b babbabb| |下面两个推导都是正确的: (1) e+e e+ii+i (2) e+e i+ei+i 从一个句型到另一个句型的推导过程不是唯一的。 例如： e+e i+i 为了对句子的结构进行确定性的分析，往往只考虑最左推导和最右推导+最左推导:是指任何一步 推导都是对的

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

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

18、e(e+e* *e)e)(i+e(i+e* *e)e)(i+i(i+i* *e)e)(i+i(i+i* *i)i) 在一个文法中，若存在某个句子有两个不同的最左推导，则称该文法是二义的。或者说， 在一个文法中，若存在某个句子有两棵不同的语法树，则称该文法是二义的。注 文法的二义性问题是不可判断的。 文法的二义性与语言的二义性是两个不同的概念。注意：注意：例题2.4 对算术表达式构造一个无二义的文法。解：无二义的文法如下： et | e+t tf | t*f f(e) | i | 5提示： 考虑算符的优先性和结合性。 作为描述程序语言的文法，有以下几点限制：（1） 不能有任何产生式 : pp（2

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