程序设计语言常用语法与翻译.ppt
信息学院软件工程教研室,编译原理,刘向菊QQ:8064793信息学院软件工程教研室,信息学院软件工程教研室,第四章 程序设计语言常用的 语法与翻译方法,信息学院软件工程教研室,4.1 逆波兰表示法,逆波兰表示表达式 高级语言表示表达式 ab*a*b ab*c+a*b+c abcd/+*a*(b+c/d)ab*cd*+a*b+c*d,信息学院软件工程教研室,高级语言表达式E的逆波兰表示法可这样定义：（1）若E是高级语言中的一个变量或常数，则E的逆波兰表示式仍是E。（2）若高级语言中的表达式为E1 op E2，其中，op是一个二元算符，E1、E2也是表达式，则逆波兰式表示为E1 E2 op，其中，E1是E1的逆波兰式，E2是E2的逆波兰式。（3）若高级语言中的表达式为（E），则逆波兰表示式为去掉括号的E，E为E的逆波兰表示式。,信息学院软件工程教研室,三地址代码是由下面一般形式的语句构成的序列。x:=y op z其中x、y、z是变量名或编译时产生的临时变量名；y、z还可以是常数；op代表某种操作符。这种中间语言的特点有两个。（1）非常接近汇编语言形式，包括汇编语言中最基本的操作。（2）每个语句中赋值号的右边只有一个操作符，使得句子意义最小且不可分。例如，源语言表达式x+y*z可被翻译成如下的句子序列：T1:=y*zT2:=x+T1,4.2 三地址代码,信息学院软件工程教研室,三地址代码的语句形式可分为两类：一类是带有各种运算操作的赋值语句第二类是转移语句 三地址码语句可看成是一种中间代码的抽象形成，在编译程序中，三地址代码的具体实现常以记录的形式表示，通常有3种表示方法：四元式、三元式、间接三元式,信息学院软件工程教研室,4.3 程序设计语言常用语法,4.3.1 表达式语法（算术）4.3.2 赋值语句4.3.3 if语句4.3.4 循环语句4.3.5 说明语句4.3.6 函数的定义与调用4.3.7 程序语句序列文法,信息学院软件工程教研室,4.3.1 表达式语法（算术）,根据算术表达式的定义，一般算术表达式记为E，其文法被定义为：EE op E（op 为双目操作符）Eop E（op 为单目操作符）ED|id（D为数字，id为标识符号）这是一个无法直接使用的二义性文法，必须使用前述两种消除二义性文法的策略将文法中的二义性表达加以限制或改写。,信息学院软件工程教研室,对这种表达式保留文法的二义性也有好处。不过在作语法分析时要规定算符间的优先关系和结合顺序，这样才能确定语句的最终意义。这就是常用于表达式语法分析的算符优先分析法。,信息学院软件工程教研室,无二义的表达式文法一般定义为：无论采用哪一种文法形式，只要最终语句的意义是确定、不含糊的，并且是统一的，那么同一个语句所对应的抽象语法树就是相同的。,信息学院软件工程教研室,4.3.2 赋值语句,赋值语句的文法最简单，定义为：其中，是一个名字,它表示各种类型的变量，包括下标变量（数组）。“=”是赋值号，E是表达式，赋值语句的语义是把赋值号右边表达式的值放到赋值号左边名字所指的地址中去。,信息学院软件工程教研室,对赋值语句文法定义的句子而言，相应的抽象语法树如图所示。,信息学院软件工程教研室,4.3.3 if语句,if语句是控制语句的一种，它的文法被定义为：这个语法有两个候选式，这两个候选式的前半部分是一样的，即：。也就是说，在一个符号串之后可能紧跟一个或跟其他的符号串。由于可选的影响，这个文法有二义性的，即所谓“悬挂问题”。,信息学院软件工程教研室,考虑以下符号串:其中，符号E1、E2、S1、S2都是由终结符组成的符号串。这个串有两个分析树,该语法树把看作与其最近的同属一层,该语法树把看作与整句之首的同属一层,信息学院软件工程教研室,改写的文法如下：这个文法用非终结符M单独定义可嵌套的ifelse语句。它是无二义的，只是有些累赘，也不太容易理解。实际上，并不是所有的语句文法一定会存在悬挂，有些语言的设计就避免了这个问题。如果所有的语句都有结尾，或其他类似符号结尾，就不存在这个问题了。,信息学院软件工程教研室,语句又称分支语句。在C中，它的语义是根据表达式的值决定是否执行语句S或执行两个语句S中的某一个。仔细分析一下语句的符号串，真正有可执行意义的符号只有E和S两个非终结符，其他终结符只是标记符号串的结构形式。因此，在建立抽象语法树的时候，我们可以摆脱那些没有意义的符号。,信息学院软件工程教研室,上图所示是语句抽象语法树的结构。这是一棵有三棵子树的抽象语法树，最左边的子树是表达式，这里一般都是关系表达式和逻辑表达式，但是有些语言里也用算术表达式。最右边的子树是可选句子，所以用虚线连接。,信息学院软件工程教研室,4.3.4 循环语句,循环语句也有各种不同的情况，但实质是一样的，其一般的语法形式也很简单，如下：对应的抽象语法树如图所示。,信息学院软件工程教研室,说明语句用以定义各种名字的数据类型。与表达式和控制语句不同的是，说明语句不会被翻译成可执行代码，因此也不会被翻译成中间代码。说明语句实质是为名字确定存储空间或过程、函数的起始地址。说明语句也可以生成语法树，通过语法树来确定各个名字的类型。由于说明语句没有嵌套，所以没有层次。因此它的抽象语法树蜕化成一个链表。所谓类型，其实质就是存储控制。,信息学院软件工程教研室,4.1.5 说明语句,名字本身则与存储地址或过程函数入口地址关联，说明语句的语法为：这里，D可理解为说明语句。T是类型标识集合，L是变量表，是变量名。说明语句常与符号表配合使用，所谓符号表就是名字登记表，那里保存着与名字相关的信息。,信息学院软件工程教研室,4.3.7 程序语句序列文法,程序是由语句序列组成的，语句序列的文法可表示为：这是用分号分隔开的语句序列。由于语句间的并列意义，故仍以链表表示为最好，对应的结构如下图所示。,信息学院软件工程教研室,其中，三角形表示潜在的子树。由前文可知，各种各样的语句经语法分析后都有与之对应的语法树。实际上，每个程序在语法分析之前可看成一个长长的词串，而在语法分析之后就变成一棵整体的语法树。下面通过一个例子来说明。P45-列4.1,信息学院软件工程教研室,4.4 中间代码的翻译,4.4.1 表达式中间代码4.4.2 if语句中间代码生成4.4.3 布尔表达式代码生成4.4.4 循环语句中间代码4.4.5 综合实例,信息学院软件工程教研室,1逆波兰式的生成,4.4.1 表达式中间代码,信息学院软件工程教研室,2四元式的生成表达式的四元式变换如下所示：,是编译过程中的临时变量，用以存储中间结果。,其中，,信息学院软件工程教研室,4.4.2 if语句中间代码生成,if语句翻译成中间代码时，变成对布尔表达式的判断与转移组合。所生成的四元式中间代码由两条基本语句组成：,信息学院软件工程教研室,语句有两种形式：形式1：(E)S,信息学院软件工程教研室,形式2：,信息学院软件工程教研室,根据这个语义的关系将其相应的抽象语法图翻译为固定的四元式格式。(E的四元式，值存入T)next：(后续程序四元式),信息学院软件工程教研室,在语句 中，表达式E的作用是提供选择执行语句S1还是S2的判断。因此不必保留E的值，而是将计算结果表示为程序执行流程的转移。此时E的值只需有两个即可。所以E被视为布尔表达式。E的真值被转换为一个条件转移，称为“真出口”。E的假值被转换为一个无条件转移，称为“假出口”。,信息学院软件工程教研室,最简单的情况E是一个布尔变量a，那么有：,真出口,假出口,信息学院软件工程教研室,另外，布尔量间的运算除了一般的布尔代数运算外，还有一种运算方法，称为“短路布尔操作”。它的意义是：对于一个二元布尔操作，如果根据第1个布尔量的值就可以判断这个布尔结果，那么就不必计算第2个布尔量了。就是说，在某种情况下第2个布尔量被短路了。,信息学院软件工程教研室,例如，对于二元操作a and b，如果a是假，不管b 是什么，a and b 的结果都是假。所以b就不用计算了。再如，二元操作a or b，如果a是真，不管b是什么，a or b的结果都是真。所以b就可以被短路掉，这种短路的操作对代码来说是很重要的。有些时候，没被短路的操作会引起错误。例如：,信息学院软件工程教研室,这是C语言中常见的语句，但如果出现p=NULL 时还要对 求值将引起内存错误。,信息学院软件工程教研室,短路的布尔操作类似于if语句，它们经常用if表达式定义，例如：,将E1的真出口转移至E2的第1个四元式的假出口与全句假出口并联（相同），E2的真出口就是全句的真出口，E2的假出口也是全句的假出口。,将E1的真出口与全句的真出口并联，E1的假出口转移至E2的第1个四元式，E2的真出口是全句的真出口，E2的假出口是全句的假出口。,信息学院软件工程教研室,4.4.4 循环语句中间代码,循环语句的一般语法为：,信息学院软件工程教研室,信息学院软件工程教研室,循环语句生成的四元式序列的结构如下：,next:(后续程序四元式),信息学院软件工程教研室,4.4.5 综合实例,【例】有语句如下：While(AB or CD)if(x=0)x=y*z;else x=y+z;求四元式序列（翻译）。,信息学院软件工程教研室,解：（1）求出该句的语法树,信息学院软件工程教研室,（2）生成一个按标记转移的四元式序列：,wnext:（112）(后续程序四元式序列)（wF）,信息学院软件工程教研室,（3）由上面四元式序列可得各标记的实际地址为：,信息学院软件工程教研室,（4）根据所求地址回填各转移目标地址,可得：,信息学院软件工程教研室,（接上）,
