程序设计语言常用语法与翻译.ppt

《程序设计语言常用语法与翻译.ppt》由会员分享，可在线阅读，更多相关《程序设计语言常用语法与翻译.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理编译原理刘向菊刘向菊QQ:8064793信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室 第四章第四章 程序设计语言常用的程序设计语言常用的 语法与翻译方法语法与翻译方法信息学院软件工程教研室信息学院软件工程教研室4.1 逆波兰表示法逆波兰表示法n n逆波兰表示表达式逆波兰表示表达式 高级语言表示表达式高级语言表示表达式n n ab*a*bn n ab*c+a*b+cn n abcd/+*a*(b+c/d)n n ab*cd*+a*b+c*d信息学院软件工程教研室信息学院软件工程教研室n n高级语言表达式高级语言表达式高级语言表达式高级语言表达式

2、E E的逆波兰表示法可这样定义：的逆波兰表示法可这样定义：的逆波兰表示法可这样定义：的逆波兰表示法可这样定义：n n（1）若）若E是高级语言中的一个变量或常数，则是高级语言中的一个变量或常数，则E的逆波兰表示式仍是的逆波兰表示式仍是E。n n（2）若高级语言中的表达式为）若高级语言中的表达式为E1 op E2，其中，其中，op是一个二元算符，是一个二元算符，E1、E2也是表达式，则逆也是表达式，则逆波兰式表示为波兰式表示为E1 E2 op，其中，其中，E1是是E1的逆波的逆波兰式，兰式，E2是是E2的逆波兰式。的逆波兰式。n n（3）若高级语言中的表达式为（）若高级语言中的表达式为（E），则逆

3、波兰），则逆波兰表示式为去掉括号的表示式为去掉括号的E，E为为E的逆波兰表示式。的逆波兰表示式。信息学院软件工程教研室信息学院软件工程教研室n n三地址代码是由下面一般形式的语句构成的序列。三地址代码是由下面一般形式的语句构成的序列。三地址代码是由下面一般形式的语句构成的序列。三地址代码是由下面一般形式的语句构成的序列。n n x:=y op z x:=y op zn n其中其中其中其中x x、y y、z z是变量名或编译时产生的临时变量名；是变量名或编译时产生的临时变量名；是变量名或编译时产生的临时变量名；是变量名或编译时产生的临时变量名；y y、z z还可以是常数；还可以是常数；还可以是常

4、数；还可以是常数；opop代表某种操作符。这种中间代表某种操作符。这种中间代表某种操作符。这种中间代表某种操作符。这种中间语言的特点有两个。语言的特点有两个。语言的特点有两个。语言的特点有两个。n n（1 1）非常接近汇编语言形式，包括汇编语言中最基）非常接近汇编语言形式，包括汇编语言中最基）非常接近汇编语言形式，包括汇编语言中最基）非常接近汇编语言形式，包括汇编语言中最基本的操作。本的操作。本的操作。本的操作。n n（2 2）每个语句中赋值号的右边只有一个操作符，使）每个语句中赋值号的右边只有一个操作符，使）每个语句中赋值号的右边只有一个操作符，使）每个语句中赋值号的右边只有一个操作符，使得

5、句子意义最小且不可分。例如，源语言表达式得句子意义最小且不可分。例如，源语言表达式得句子意义最小且不可分。例如，源语言表达式得句子意义最小且不可分。例如，源语言表达式x+y*zx+y*z可被翻译成如下的句子序列：可被翻译成如下的句子序列：可被翻译成如下的句子序列：可被翻译成如下的句子序列：n nT1:=y*zT1:=y*zn nT2:=x+T1T2:=x+T14.2 4.2 三地址代码三地址代码三地址代码三地址代码信息学院软件工程教研室信息学院软件工程教研室n n三地址代码的语句形式可分为两类：三地址代码的语句形式可分为两类：n n一类是带有各种运算操作的赋值语句一类是带有各种运算操作的赋值语

6、句n n第二类是转移语句第二类是转移语句 n n三地址码语句可看成是一种中间代码的三地址码语句可看成是一种中间代码的抽象形成，在编译程序中，三地址代码抽象形成，在编译程序中，三地址代码的具体实现常以记录的形式表示，通常的具体实现常以记录的形式表示，通常有有3种表示方法：四元式、三元式、间接种表示方法：四元式、三元式、间接三元式三元式 信息学院软件工程教研室信息学院软件工程教研室4.3 4.3 程序设计语言常用语法程序设计语言常用语法程序设计语言常用语法程序设计语言常用语法n n4.3.1 表达式语法（算术）n n4.3.2 赋值语句n n4.3.3 if语句n n4.3.4 循环语句n n4.

7、3.5 说明语句n n4.3.6 函数的定义与调用n n4.3.7 程序语句序列文法信息学院软件工程教研室信息学院软件工程教研室4.3.1 4.3.1 表达式语法（算术）表达式语法（算术）表达式语法（算术）表达式语法（算术）n n根据算术表达式的定义，一般算术表达式记为根据算术表达式的定义，一般算术表达式记为根据算术表达式的定义，一般算术表达式记为根据算术表达式的定义，一般算术表达式记为E E，其文法被定义为：，其文法被定义为：，其文法被定义为：，其文法被定义为：n nE EE E op op E E （op op 为双目操作符）为双目操作符）为双目操作符）为双目操作符）n nE Eop op

8、 E E （op op 为单目操作符）为单目操作符）为单目操作符）为单目操作符）n nE EDD|idid （DD为数字，为数字，为数字，为数字，idid为标识符号）为标识符号）为标识符号）为标识符号）n n这是一个无法直接使用的二义性文法，必须使这是一个无法直接使用的二义性文法，必须使这是一个无法直接使用的二义性文法，必须使这是一个无法直接使用的二义性文法，必须使用前述两种消除二义性文法的策略将文法中的用前述两种消除二义性文法的策略将文法中的用前述两种消除二义性文法的策略将文法中的用前述两种消除二义性文法的策略将文法中的二义性表达加以限制或改写。二义性表达加以限制或改写。二义性表达加以限制或

9、改写。二义性表达加以限制或改写。信息学院软件工程教研室信息学院软件工程教研室n n对这种表达式保留文法的二义性也有好对这种表达式保留文法的二义性也有好处。不过在作语法分析时要规定算符间处。不过在作语法分析时要规定算符间的优先关系和结合顺序，这样才能确定的优先关系和结合顺序，这样才能确定语句的最终意义。这就是常用于表达式语句的最终意义。这就是常用于表达式语法分析的算符优先分析法。语法分析的算符优先分析法。信息学院软件工程教研室信息学院软件工程教研室n n无二义的表达式文法一般定义为：无二义的表达式文法一般定义为：n n n n无论采用哪一种文法形式，只要最终语无论采用哪一种文法形式，只要最终语句

10、的意义是确定、不含糊的，并且是统句的意义是确定、不含糊的，并且是统一的，那么同一个语句所对应的抽象语一的，那么同一个语句所对应的抽象语法树就是相同的。法树就是相同的。信息学院软件工程教研室信息学院软件工程教研室4.3.2 4.3.2 赋值语句赋值语句赋值语句赋值语句n n赋值语句的文法最简单，定义为：n n n n其中，是一个名字,它表示各种类型的变量，包括下标变量（数组）。“=”是赋值号，E是表达式，赋值语句的语义是把赋值号右边表达式的值放到赋值号左边名字所指的地址中去。信息学院软件工程教研室信息学院软件工程教研室n n对赋值语句文法定义的句子而言，相应对赋值语句文法定义的句子而言，相应的抽

11、象语法树如图所示。的抽象语法树如图所示。信息学院软件工程教研室信息学院软件工程教研室4.3.3 if4.3.3 if4.3.3 if4.3.3 if语句语句语句语句n nif语句是控制语句的一种，它的文法被定语句是控制语句的一种，它的文法被定义为：义为：n n这个语法有两个候选式，这两个候选式这个语法有两个候选式，这两个候选式的前半部分是一样的，即：。也就是说，的前半部分是一样的，即：。也就是说，在一个符号串之后可能紧跟一个或跟其在一个符号串之后可能紧跟一个或跟其他的符号串。由于可选的影响，这个文他的符号串。由于可选的影响，这个文法有二义性的，即所谓法有二义性的，即所谓“悬挂问题悬挂问题”。信

12、息学院软件工程教研室信息学院软件工程教研室n n考虑以下符号串:n n其中，符号E1、E2、S1、S2都是由终结符组成的符号串。n n这个串有两个分析树该语法树把看作与其最近的同属一层 该语法树把看作与整句之首的同属一层 信息学院软件工程教研室信息学院软件工程教研室n n改写的文法如下：改写的文法如下：n n这个文法用非终结符这个文法用非终结符这个文法用非终结符这个文法用非终结符MM单独定义可嵌套的单独定义可嵌套的单独定义可嵌套的单独定义可嵌套的ifelseifelse语句。它是无二义的，只是有些累赘，语句。它是无二义的，只是有些累赘，语句。它是无二义的，只是有些累赘，语句。它是无二义的，只是

13、有些累赘，也不太容易理解。实际上，并不是所有的语句也不太容易理解。实际上，并不是所有的语句也不太容易理解。实际上，并不是所有的语句也不太容易理解。实际上，并不是所有的语句文法一定会存在悬挂，有些语言的设计就避免文法一定会存在悬挂，有些语言的设计就避免文法一定会存在悬挂，有些语言的设计就避免文法一定会存在悬挂，有些语言的设计就避免了这个问题。如果所有的语句都有结尾，或其了这个问题。如果所有的语句都有结尾，或其了这个问题。如果所有的语句都有结尾，或其了这个问题。如果所有的语句都有结尾，或其他类似符号结尾，就不存在这个问题了。他类似符号结尾，就不存在这个问题了。他类似符号结尾，就不存在这个问题了。他

14、类似符号结尾，就不存在这个问题了。信息学院软件工程教研室信息学院软件工程教研室n n语句又称分支语句。在语句又称分支语句。在C中，它的语义是中，它的语义是根据表达式的值决定是否执行语句根据表达式的值决定是否执行语句S或执或执行两个语句行两个语句S中的某一个。仔细分析一下中的某一个。仔细分析一下语句的符号串，真正有可执行意义的符语句的符号串，真正有可执行意义的符号只有号只有E和和S两个非终结符，其他终结符两个非终结符，其他终结符只是标记符号串的结构形式。因此，在只是标记符号串的结构形式。因此，在建立抽象语法树的时候，我们可以摆脱建立抽象语法树的时候，我们可以摆脱那些没有意义的符号。那些没有意义的

15、符号。信息学院软件工程教研室信息学院软件工程教研室上图所示是语句抽象语法树的结构。上图所示是语句抽象语法树的结构。这是一棵有三棵子树的抽象语法树，这是一棵有三棵子树的抽象语法树，最左边的子树是表达式，最左边的子树是表达式，这里一般都是关系表达式和逻辑表达这里一般都是关系表达式和逻辑表达式，式，但是有些语言里也用算术表达式。但是有些语言里也用算术表达式。最右边的子树是可选句子，最右边的子树是可选句子，所以用虚线连接。所以用虚线连接。信息学院软件工程教研室信息学院软件工程教研室4.3.4 4.3.4 循环语句循环语句循环语句循环语句n n循环语句也有各种不同的情况，但实质循环语句也有各种不同的情况

16、，但实质是一样的，其一般的语法形式也很简单，是一样的，其一般的语法形式也很简单，如下：如下：n n对应的抽象语法树如图所示。对应的抽象语法树如图所示。信息学院软件工程教研室信息学院软件工程教研室n n说明语句用以定义各种名字的数据类型。与说明语句用以定义各种名字的数据类型。与表达式和控制语句不同的是，说明语句不会表达式和控制语句不同的是，说明语句不会被翻译成可执行代码，因此也不会被翻译成被翻译成可执行代码，因此也不会被翻译成中间代码。说明语句实质是为名字确定存储中间代码。说明语句实质是为名字确定存储空间或过程、函数的起始地址。说明语句也空间或过程、函数的起始地址。说明语句也可以生成语法树，通过

17、语法树来确定各个名可以生成语法树，通过语法树来确定各个名字的类型。由于说明语句没有嵌套，所以没字的类型。由于说明语句没有嵌套，所以没有层次。因此它的抽象语法树蜕化成一个链有层次。因此它的抽象语法树蜕化成一个链表。所谓类型，其实质就是存储控制。表。所谓类型，其实质就是存储控制。信息学院软件工程教研室信息学院软件工程教研室4.1.5 4.1.5 说明语句说明语句说明语句说明语句n n名字本身则与存储地址或过程函数入口名字本身则与存储地址或过程函数入口地址关联，说明语句的语法为：地址关联，说明语句的语法为：n n这里，这里，这里，这里，DD可理解为说明语句。可理解为说明语句。可理解为说明语句。可理解

18、为说明语句。T T是类型标识集是类型标识集是类型标识集是类型标识集合，合，合，合，L L是变量表，是变量名。说明语句常与符是变量表，是变量名。说明语句常与符是变量表，是变量名。说明语句常与符是变量表，是变量名。说明语句常与符号表配合使用，所谓符号表就是名字登记表，号表配合使用，所谓符号表就是名字登记表，号表配合使用，所谓符号表就是名字登记表，号表配合使用，所谓符号表就是名字登记表，那里保存着与名字相关的信息。那里保存着与名字相关的信息。那里保存着与名字相关的信息。那里保存着与名字相关的信息。信息学院软件工程教研室信息学院软件工程教研室4.3.7 4.3.7 程序语句序列文法程序语句序列文法程序

19、语句序列文法程序语句序列文法n n程序是由语句序列组成的，语句序列的程序是由语句序列组成的，语句序列的文法可表示为：文法可表示为：n n这是用分号分隔开的语句序列。由于语这是用分号分隔开的语句序列。由于语句间的并列意义，故仍以链表表示为最句间的并列意义，故仍以链表表示为最好，对应的结构如下图所示。好，对应的结构如下图所示。信息学院软件工程教研室信息学院软件工程教研室其中，三角形表示潜在的子树。其中，三角形表示潜在的子树。由前文可知，各种各样的语句经语法分析由前文可知，各种各样的语句经语法分析后都有与之对应的语法树。后都有与之对应的语法树。实际上，每个程序在语法分析之前可看成实际上，每个程序在语

20、法分析之前可看成一个长长的词串，而在语法分析之后就变成一个长长的词串，而在语法分析之后就变成一棵整体的语法树。一棵整体的语法树。下面通过一个例子来说明。下面通过一个例子来说明。P45-列列4.1信息学院软件工程教研室信息学院软件工程教研室4.4 4.4 中间代码的翻译中间代码的翻译中间代码的翻译中间代码的翻译n n4.4.1 表达式中间代码表达式中间代码n n4.4.2 if语句中间代码生成语句中间代码生成n n4.4.3 布尔表达式代码生成布尔表达式代码生成n n4.4.4 循环语句中间代码循环语句中间代码n n4.4.5 综合实例综合实例信息学院软件工程教研室信息学院软件工程教研室n n1

21、逆波兰式的生成逆波兰式的生成 4.4.1 4.4.1 表达式中间代码表达式中间代码表达式中间代码表达式中间代码信息学院软件工程教研室信息学院软件工程教研室n n2四元式的生成四元式的生成n n表达式的四元式变换如下所示：表达式的四元式变换如下所示：是是编译过程中的程中的临时变量，用以存量，用以存储中中间结果。果。其中，信息学院软件工程教研室信息学院软件工程教研室4.4.2 if4.4.2 if语句中间代码生成语句中间代码生成语句中间代码生成语句中间代码生成n nif语句翻译成中间代码时，变成对布尔表语句翻译成中间代码时，变成对布尔表达式的判断与转移组合。所生成的四元达式的判断与转移组合。所生成

22、的四元式中间代码由两条基本语句组成：式中间代码由两条基本语句组成：信息学院软件工程教研室信息学院软件工程教研室n n语句有两种形式语句有两种形式：n n形式形式1：(E)S信息学院软件工程教研室信息学院软件工程教研室n n形式2：信息学院软件工程教研室信息学院软件工程教研室n n根据这个语义的关系将其相应的抽象语根据这个语义的关系将其相应的抽象语法图翻译为固定的四元式格式。法图翻译为固定的四元式格式。n n(E E的四元式，值存入的四元式，值存入的四元式，值存入的四元式，值存入T T)n nnextnext：(后续程序四元式后续程序四元式后续程序四元式后续程序四元式)信息学院软件工程教研室信息

23、学院软件工程教研室n n在语句在语句 中，表达式中，表达式E的作的作用是提供选择执行语句用是提供选择执行语句S1还是还是S2的判断。的判断。因此不必保留因此不必保留E的值，而是将计算结果表的值，而是将计算结果表示为程序执行流程的转移。此时示为程序执行流程的转移。此时E的值只的值只需有两个即可。所以需有两个即可。所以E被视为布尔表达式。被视为布尔表达式。E的真值被转换为一个条件转移，称为的真值被转换为一个条件转移，称为“真出口真出口”。E的假值被转换为一个无条件的假值被转换为一个无条件转移，称为转移，称为“假出口假出口”。信息学院软件工程教研室信息学院软件工程教研室n n最简单的情况最简单的情况

24、E是一个布尔变量是一个布尔变量a，那么，那么有：有：真出口真出口假出口假出口信息学院软件工程教研室信息学院软件工程教研室n n另外，布尔量间的运算除了一般的布尔另外，布尔量间的运算除了一般的布尔代数运算外，还有一种运算方法，称为代数运算外，还有一种运算方法，称为“短路布尔操作短路布尔操作”。它的意义是：对于。它的意义是：对于一个二元布尔操作，如果根据第一个二元布尔操作，如果根据第1个布尔个布尔量的值就可以判断这个布尔结果，那么量的值就可以判断这个布尔结果，那么就不必计算第就不必计算第2个布尔量了。就是说，在个布尔量了。就是说，在某种情况下第某种情况下第2个布尔量被短路了。个布尔量被短路了。信息

25、学院软件工程教研室信息学院软件工程教研室n n例如，对于二元操作例如，对于二元操作a and b，如果，如果a是假，是假，不管不管b 是什么，是什么，a and b 的结果都是假。的结果都是假。所以所以b就不用计算了。再如，二元操作就不用计算了。再如，二元操作a or b，如果，如果a是真，不管是真，不管b是什么，是什么，a or b的结果都是真。所以的结果都是真。所以b就可以被短路掉，就可以被短路掉，这种短路的操作对代码来说是很重要的。这种短路的操作对代码来说是很重要的。有些时候，没被短路的操作会引起错误。有些时候，没被短路的操作会引起错误。例如：例如：信息学院软件工程教研室信息学院软件工程

26、教研室n n这是这是C语言中常见的语句，但如果出现语言中常见的语句，但如果出现p=NULL 时还要对时还要对 求值将引求值将引起内存错误。起内存错误。信息学院软件工程教研室信息学院软件工程教研室n n短路的布尔操作类似于if语句，它们经常用if表达式定义，例如：将将E1的真出口转移至的真出口转移至E2的第的第1个个四元式的假出口与全句假出口并四元式的假出口与全句假出口并联（相同），联（相同），E2的真出口就是的真出口就是全句的真出口，全句的真出口，E2的假出口也的假出口也是全句的假出口。是全句的假出口。将将E1的真出口与全句的真出口并联，的真出口与全句的真出口并联，E1的假出口转移至的假出口转

27、移至E2的第的第1个四元式，个四元式，E2的真出口是全句的真出口，的真出口是全句的真出口，E2的假的假出口是全句的假出口。出口是全句的假出口。信息学院软件工程教研室信息学院软件工程教研室4.4.4 4.4.4 循环语句中间代码循环语句中间代码循环语句中间代码循环语句中间代码n n循环语句的一般语法为：信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室信息学院软件工程教研室n n循环语句生成的四元式序列的结构如下：循环语句生成的四元式序列的结构如下：next:(后续程序四元式后续程序四元式)信息学院软件工程教研室信息学院软件工程教研室4.4.5 4.4.5 综合实例综合实例综合实

28、例综合实例n n【例】有语句如下：n nWhile(AB or CD)n n if(x=0)n n x=y*z;n n elsen n x=y+z;n n求四元式序列（翻译）。信息学院软件工程教研室信息学院软件工程教研室n n解：n n（1）求出该句的语法树 信息学院软件工程教研室信息学院软件工程教研室n n（2）生成一个按标记转移的四元式序列：）生成一个按标记转移的四元式序列：wnext:（112）(后续程序四元式序列后续程序四元式序列)（wF）信息学院软件工程教研室信息学院软件工程教研室n n（3）由上面四元式序列可得各标记的实际地址为：信息学院软件工程教研室信息学院软件工程教研室n n（4）根据所求地址回填各转移目标地址）根据所求地址回填各转移目标地址,可得：可得：信息学院软件工程教研室信息学院软件工程教研室n n（接上）信息学院软件工程教研室信息学院软件工程教研室