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

程序设计语言常用语程序设计语言常用语法与翻译法与翻译第1页，共44页，编辑于2022年，星期日 第四章第四章 程序设计语言常用的程序设计语言常用的 语法与翻译方法语法与翻译方法信息学院软件工程教研室信息学院软件工程教研室第2页，共44页，编辑于2022年，星期日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信息学院软件工程教研室信息学院软件工程教研室第3页，共44页，编辑于2022年，星期日n n高级语言表达式高级语言表达式高级语言表达式高级语言表达式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），则逆波兰表），则逆波兰表示式为去掉括号的示式为去掉括号的E，E为为E的逆波兰表示式。的逆波兰表示式。信息学院软件工程教研室信息学院软件工程教研室第4页，共44页，编辑于2022年，星期日n n三地址代码是由下面一般形式的语句构成的序列。三地址代码是由下面一般形式的语句构成的序列。三地址代码是由下面一般形式的语句构成的序列。三地址代码是由下面一般形式的语句构成的序列。n n x:=y op z x:=y op zn n其中其中其中其中x x、y y、z z是变量名或编译时产生的临时变量名；是变量名或编译时产生的临时变量名；是变量名或编译时产生的临时变量名；是变量名或编译时产生的临时变量名；y y、z z还可以是常数；还可以是常数；还可以是常数；还可以是常数；opop代表某种操作符。这种中间语言的代表某种操作符。这种中间语言的代表某种操作符。这种中间语言的代表某种操作符。这种中间语言的特点有两个。特点有两个。特点有两个。特点有两个。n n（1 1）非常接近汇编语言形式，包括汇编语言中最基本）非常接近汇编语言形式，包括汇编语言中最基本）非常接近汇编语言形式，包括汇编语言中最基本）非常接近汇编语言形式，包括汇编语言中最基本的操作。的操作。的操作。的操作。n n（2 2）每个语句中赋值号的右边只有一个操作符，使得）每个语句中赋值号的右边只有一个操作符，使得）每个语句中赋值号的右边只有一个操作符，使得）每个语句中赋值号的右边只有一个操作符，使得句子意义最小且不可分。例如，源语言表达式句子意义最小且不可分。例如，源语言表达式句子意义最小且不可分。例如，源语言表达式句子意义最小且不可分。例如，源语言表达式x+y*zx+y*z可被翻译成如下的句子序列：可被翻译成如下的句子序列：可被翻译成如下的句子序列：可被翻译成如下的句子序列：n nT1:=y*zT1:=y*zn nT2:=x+T1T2:=x+T14.2 4.2 三地址代码三地址代码三地址代码三地址代码信息学院软件工程教研室信息学院软件工程教研室第5页，共44页，编辑于2022年，星期日n n三地址代码的语句形式可分为两类：三地址代码的语句形式可分为两类：n n一类是带有各种运算操作的赋值语句一类是带有各种运算操作的赋值语句n n第二类是转移语句第二类是转移语句 n n三地址码语句可看成是一种中间代码的抽象三地址码语句可看成是一种中间代码的抽象形成，在编译程序中，三地址代码的具体实形成，在编译程序中，三地址代码的具体实现常以记录的形式表示，通常有现常以记录的形式表示，通常有3种表示方种表示方法：四元式、三元式、间接三元式法：四元式、三元式、间接三元式 信息学院软件工程教研室信息学院软件工程教研室第6页，共44页，编辑于2022年，星期日4.3 4.3 程序设计语言常用语法程序设计语言常用语法程序设计语言常用语法程序设计语言常用语法n n4.3.1 表达式语法（算术）n n4.3.2 赋值语句n n4.3.3 if语句n n4.3.4 循环语句n n4.3.5 说明语句n n4.3.6 函数的定义与调用n n4.3.7 程序语句序列文法信息学院软件工程教研室信息学院软件工程教研室第7页，共44页，编辑于2022年，星期日4.3.1 4.3.1 表达式语法（算术）表达式语法（算术）表达式语法（算术）表达式语法（算术）n n根据算术表达式的定义，一般算术表达式记为根据算术表达式的定义，一般算术表达式记为根据算术表达式的定义，一般算术表达式记为根据算术表达式的定义，一般算术表达式记为E E，其，其，其，其文法被定义为：文法被定义为：文法被定义为：文法被定义为：n nE EE E op op E E （op op 为双目操作符）为双目操作符）为双目操作符）为双目操作符）n nE Eop op E E （op op 为单目操作符）为单目操作符）为单目操作符）为单目操作符）n nE EDD|idid （DD为数字，为数字，为数字，为数字，idid为标识符号）为标识符号）为标识符号）为标识符号）n n这是一个无法直接使用的二义性文法，必须使用前述这是一个无法直接使用的二义性文法，必须使用前述这是一个无法直接使用的二义性文法，必须使用前述这是一个无法直接使用的二义性文法，必须使用前述两种消除二义性文法的策略将文法中的二义性表达加两种消除二义性文法的策略将文法中的二义性表达加两种消除二义性文法的策略将文法中的二义性表达加两种消除二义性文法的策略将文法中的二义性表达加以限制或改写。以限制或改写。以限制或改写。以限制或改写。信息学院软件工程教研室信息学院软件工程教研室第8页，共44页，编辑于2022年，星期日n n对这种表达式保留文法的二义性也有好处。对这种表达式保留文法的二义性也有好处。不过在作语法分析时要规定算符间的优先关不过在作语法分析时要规定算符间的优先关系和结合顺序，这样才能确定语句的最终意系和结合顺序，这样才能确定语句的最终意义。这就是常用于表达式语法分析的算符优义。这就是常用于表达式语法分析的算符优先分析法。先分析法。信息学院软件工程教研室信息学院软件工程教研室第9页，共44页，编辑于2022年，星期日n n无二义的表达式文法一般定义为：无二义的表达式文法一般定义为：n n n n无论采用哪一种文法形式，只要最终语句无论采用哪一种文法形式，只要最终语句的意义是确定、不含糊的，并且是统一的，的意义是确定、不含糊的，并且是统一的，那么同一个语句所对应的抽象语法树就是那么同一个语句所对应的抽象语法树就是相同的。相同的。信息学院软件工程教研室信息学院软件工程教研室第10页，共44页，编辑于2022年，星期日4.3.2 4.3.2 赋值语句赋值语句赋值语句赋值语句n n赋值语句的文法最简单，定义为：n n n n其中，是一个名字,它表示各种类型的变量，包括下标变量（数组）。“=”是赋值号，E是表达式，赋值语句的语义是把赋值号右边表达式的值放到赋值号左边名字所指的地址中去。信息学院软件工程教研室信息学院软件工程教研室第11页，共44页，编辑于2022年，星期日n n对赋值语句文法定义的句子而言，相应的对赋值语句文法定义的句子而言，相应的抽象语法树如图所示。抽象语法树如图所示。信息学院软件工程教研室信息学院软件工程教研室第12页，共44页，编辑于2022年，星期日4.3.3 if4.3.3 if4.3.3 if4.3.3 if语句语句语句语句n nif语句是控制语句的一种，它的文法被定义为：语句是控制语句的一种，它的文法被定义为：n n这个语法有两个候选式，这两个候选式的前这个语法有两个候选式，这两个候选式的前半部分是一样的，即：。也就是说，在一个半部分是一样的，即：。也就是说，在一个符号串之后可能紧跟一个或跟其他的符号串符号串之后可能紧跟一个或跟其他的符号串。由于可选的影响，这个文法有二义性的，。由于可选的影响，这个文法有二义性的，即所谓即所谓“悬挂问题悬挂问题”。信息学院软件工程教研室信息学院软件工程教研室第13页，共44页，编辑于2022年，星期日n n考虑以下符号串:n n其中，符号E1、E2、S1、S2都是由终结符组成的符号串。n n这个串有两个分析树该语法树把看作与其最近的同属一层 该语法树把看作与整句之首的同属一层 信息学院软件工程教研室信息学院软件工程教研室第14页，共44页，编辑于2022年，星期日n n改写的文法如下：改写的文法如下：n n这个文法用非终结符这个文法用非终结符这个文法用非终结符这个文法用非终结符MM单独定义可嵌套的单独定义可嵌套的单独定义可嵌套的单独定义可嵌套的ifelseifelse语句。它是无二义的，只是有些累赘，也不太容语句。它是无二义的，只是有些累赘，也不太容语句。它是无二义的，只是有些累赘，也不太容语句。它是无二义的，只是有些累赘，也不太容易理解。实际上，并不是所有的语句文法一定会易理解。实际上，并不是所有的语句文法一定会易理解。实际上，并不是所有的语句文法一定会易理解。实际上，并不是所有的语句文法一定会存在悬挂，有些语言的设计就避免了这个问题。存在悬挂，有些语言的设计就避免了这个问题。存在悬挂，有些语言的设计就避免了这个问题。存在悬挂，有些语言的设计就避免了这个问题。如果所有的语句都有结尾，或其他类似符号结尾，如果所有的语句都有结尾，或其他类似符号结尾，如果所有的语句都有结尾，或其他类似符号结尾，如果所有的语句都有结尾，或其他类似符号结尾，就不存在这个问题了。就不存在这个问题了。就不存在这个问题了。就不存在这个问题了。信息学院软件工程教研室信息学院软件工程教研室第15页，共44页，编辑于2022年，星期日n n语句又称分支语句。在语句又称分支语句。在C中，它的语义是根中，它的语义是根据表达式的值决定是否执行语句据表达式的值决定是否执行语句S或执行两或执行两个语句个语句S中的某一个。仔细分析一下语句的符中的某一个。仔细分析一下语句的符号串，真正有可执行意义的符号只有号串，真正有可执行意义的符号只有E和和S两两个非终结符，其他终结符只是标记符号串的个非终结符，其他终结符只是标记符号串的结构形式。因此，在建立抽象语法树的时候，结构形式。因此，在建立抽象语法树的时候，我们可以摆脱那些没有意义的符号。我们可以摆脱那些没有意义的符号。信息学院软件工程教研室信息学院软件工程教研室第16页，共44页，编辑于2022年，星期日上图所示是语句抽象语法树的结构。上图所示是语句抽象语法树的结构。这是一棵有三棵子树的抽象语法树，这是一棵有三棵子树的抽象语法树，最左边的子树是表达式，最左边的子树是表达式，这里一般都是关系表达式和逻辑表达式，这里一般都是关系表达式和逻辑表达式，但是有些语言里也用算术表达式。但是有些语言里也用算术表达式。最右边的子树是可选句子，最右边的子树是可选句子，所以用虚线连接。所以用虚线连接。信息学院软件工程教研室信息学院软件工程教研室第17页，共44页，编辑于2022年，星期日4.3.4 4.3.4 循环语句循环语句循环语句循环语句n n循环语句也有各种不同的情况，但实质是一循环语句也有各种不同的情况，但实质是一样的，其一般的语法形式也很简单，如下：样的，其一般的语法形式也很简单，如下：n n对应的抽象语法树如图所示。对应的抽象语法树如图所示。信息学院软件工程教研室信息学院软件工程教研室第18页，共44页，编辑于2022年，星期日n n说明语句用以定义各种名字的数据类型。与表达说明语句用以定义各种名字的数据类型。与表达式和控制语句不同的是，说明语句不会被翻译成式和控制语句不同的是，说明语句不会被翻译成可执行代码，因此也不会被翻译成中间代码。说可执行代码，因此也不会被翻译成中间代码。说明语句实质是为名字确定存储空间或过程、函数明语句实质是为名字确定存储空间或过程、函数的起始地址。说明语句也可以生成语法树，通过的起始地址。说明语句也可以生成语法树，通过语法树来确定各个名字的类型。由于说明语句没语法树来确定各个名字的类型。由于说明语句没有嵌套，所以没有层次。因此它的抽象语法树蜕有嵌套，所以没有层次。因此它的抽象语法树蜕化成一个链表。所谓类型，其实质就是存储控制。化成一个链表。所谓类型，其实质就是存储控制。信息学院软件工程教研室信息学院软件工程教研室第19页，共44页，编辑于2022年，星期日4.1.5 4.1.5 说明语句说明语句说明语句说明语句n n名字本身则与存储地址或过程函数入口地名字本身则与存储地址或过程函数入口地址关联，说明语句的语法为：址关联，说明语句的语法为：n n这里，这里，这里，这里，DD可理解为说明语句。可理解为说明语句。可理解为说明语句。可理解为说明语句。T T是类型标识集合，是类型标识集合，是类型标识集合，是类型标识集合，L L是变量表，是变量名。说明语句常与符号表配合是变量表，是变量名。说明语句常与符号表配合是变量表，是变量名。说明语句常与符号表配合是变量表，是变量名。说明语句常与符号表配合使用，所谓符号表就是名字登记表，那里保存着使用，所谓符号表就是名字登记表，那里保存着使用，所谓符号表就是名字登记表，那里保存着使用，所谓符号表就是名字登记表，那里保存着与名字相关的信息。与名字相关的信息。与名字相关的信息。与名字相关的信息。信息学院软件工程教研室信息学院软件工程教研室第20页，共44页，编辑于2022年，星期日4.3.7 4.3.7 程序语句序列文法程序语句序列文法程序语句序列文法程序语句序列文法n n程序是由语句序列组成的，语句序列的文法程序是由语句序列组成的，语句序列的文法可表示为：可表示为：n n这是用分号分隔开的语句序列。由于语句间这是用分号分隔开的语句序列。由于语句间的并列意义，故仍以链表表示为最好，对应的并列意义，故仍以链表表示为最好，对应的结构如下图所示。的结构如下图所示。信息学院软件工程教研室信息学院软件工程教研室第21页，共44页，编辑于2022年，星期日其中，三角形表示潜在的子树。其中，三角形表示潜在的子树。由前文可知，各种各样的语句经语法分析后都由前文可知，各种各样的语句经语法分析后都有与之对应的语法树。有与之对应的语法树。实际上，每个程序在语法分析之前可看成一个实际上，每个程序在语法分析之前可看成一个长长的词串，而在语法分析之后就变成一棵整体长长的词串，而在语法分析之后就变成一棵整体的语法树。的语法树。下面通过一个例子来说明。下面通过一个例子来说明。P45-列列4.1信息学院软件工程教研室信息学院软件工程教研室第22页，共44页，编辑于2022年，星期日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 综合实例综合实例信息学院软件工程教研室信息学院软件工程教研室第23页，共44页，编辑于2022年，星期日n n1逆波兰式的生成逆波兰式的生成 4.4.1 4.4.1 表达式中间代码表达式中间代码表达式中间代码表达式中间代码信息学院软件工程教研室信息学院软件工程教研室第24页，共44页，编辑于2022年，星期日n n2四元式的生成四元式的生成n n表达式的四元式变换如下所示：表达式的四元式变换如下所示：是是编译过编译过程中的程中的临时变临时变量，用以存量，用以存储储中中间结间结果。果。其中，信息学院软件工程教研室信息学院软件工程教研室第25页，共44页，编辑于2022年，星期日4.4.2 if4.4.2 if语句中间代码生成语句中间代码生成语句中间代码生成语句中间代码生成n nif语句翻译成中间代码时，变成对布尔表达式语句翻译成中间代码时，变成对布尔表达式的判断与转移组合。所生成的四元式中间代的判断与转移组合。所生成的四元式中间代码由两条基本语句组成：码由两条基本语句组成：信息学院软件工程教研室信息学院软件工程教研室第26页，共44页，编辑于2022年，星期日n n语句有两种形式语句有两种形式：n n形式形式1：(E)S信息学院软件工程教研室信息学院软件工程教研室第27页，共44页，编辑于2022年，星期日n n形式2：信息学院软件工程教研室信息学院软件工程教研室第28页，共44页，编辑于2022年，星期日n n根据这个语义的关系将其相应的抽象语法根据这个语义的关系将其相应的抽象语法图翻译为固定的四元式格式。图翻译为固定的四元式格式。n n(E E的四元式，值存入的四元式，值存入的四元式，值存入的四元式，值存入T T)n nnextnext：(后续程序四元式后续程序四元式后续程序四元式后续程序四元式)信息学院软件工程教研室信息学院软件工程教研室第29页，共44页，编辑于2022年，星期日n n在语句在语句 中，表达式中，表达式E的作用是的作用是提供选择执行语句提供选择执行语句S1还是还是S2的判断。因此不的判断。因此不必保留必保留E的值，而是将计算结果表示为程序的值，而是将计算结果表示为程序执行流程的转移。此时执行流程的转移。此时E的值只需有两个即可。的值只需有两个即可。所以所以E被视为布尔表达式。被视为布尔表达式。E的真值被转换的真值被转换为一个条件转移，称为为一个条件转移，称为“真出口真出口”。E的的假值被转换为一个无条件转移，称为假值被转换为一个无条件转移，称为“假出假出口口”。信息学院软件工程教研室信息学院软件工程教研室第30页，共44页，编辑于2022年，星期日n n最简单的情况最简单的情况E是一个布尔变量是一个布尔变量a，那么有：，那么有：真出口真出口假出口假出口信息学院软件工程教研室信息学院软件工程教研室第31页，共44页，编辑于2022年，星期日n n另外，布尔量间的运算除了一般的布尔代数另外，布尔量间的运算除了一般的布尔代数运算外，还有一种运算方法，称为运算外，还有一种运算方法，称为“短路布短路布尔操作尔操作”。它的意义是：对于一个二元布尔。它的意义是：对于一个二元布尔操作，如果根据第操作，如果根据第1个布尔量的值就可以判个布尔量的值就可以判断这个布尔结果，那么就不必计算第断这个布尔结果，那么就不必计算第2个布个布尔量了。就是说，在某种情况下第尔量了。就是说，在某种情况下第2个布尔个布尔量被短路了。量被短路了。信息学院软件工程教研室信息学院软件工程教研室第32页，共44页，编辑于2022年，星期日n n例如，对于二元操作例如，对于二元操作a and b，如果，如果a是假，是假，不管不管b 是什么，是什么，a and b 的结果都是假。所的结果都是假。所以以b就不用计算了。再如，二元操作就不用计算了。再如，二元操作a or b，如果如果a是真，不管是真，不管b是什么，是什么，a or b的结果都的结果都是真。所以是真。所以b就可以被短路掉，这种短路的操就可以被短路掉，这种短路的操作对代码来说是很重要的。有些时候，没被短作对代码来说是很重要的。有些时候，没被短路的操作会引起错误。例如：路的操作会引起错误。例如：信息学院软件工程教研室信息学院软件工程教研室第33页，共44页，编辑于2022年，星期日n n这是这是C语言中常见的语句，但如果出现语言中常见的语句，但如果出现p=NULL 时还要对时还要对 求值将引起求值将引起内存错误。内存错误。信息学院软件工程教研室信息学院软件工程教研室第34页，共44页，编辑于2022年，星期日n n短路的布尔操作类似于if语句，它们经常用if表达式定义，例如：将将E1的真出口转移至的真出口转移至E2的第的第1个四元个四元式的假出口与全句假出口并联（相同）式的假出口与全句假出口并联（相同），E2的真出口就是全句的真出口，的真出口就是全句的真出口，E2的假出口也是全句的假出口。的假出口也是全句的假出口。将将E1的真出口与全句的真出口并联，的真出口与全句的真出口并联，E1的假的假出口转移至出口转移至E2的第的第1个四元式，个四元式，E2的真出口的真出口是全句的真出口，是全句的真出口，E2的假出口是全句的假出的假出口是全句的假出口。口。信息学院软件工程教研室信息学院软件工程教研室第35页，共44页，编辑于2022年，星期日4.4.4 4.4.4 循环语句中间代码循环语句中间代码循环语句中间代码循环语句中间代码n n循环语句的一般语法为：信息学院软件工程教研室信息学院软件工程教研室第36页，共44页，编辑于2022年，星期日信息学院软件工程教研室信息学院软件工程教研室第37页，共44页，编辑于2022年，星期日n n循环语句生成的四元式序列的结构如下：循环语句生成的四元式序列的结构如下：next:(后续程序四元式后续程序四元式)信息学院软件工程教研室信息学院软件工程教研室第38页，共44页，编辑于2022年，星期日4.4.5 4.4.5 综合实例综合实例综合实例综合实例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求四元式序列（翻译）。信息学院软件工程教研室信息学院软件工程教研室第39页，共44页，编辑于2022年，星期日n n解：n n（1）求出该句的语法树 信息学院软件工程教研室信息学院软件工程教研室第40页，共44页，编辑于2022年，星期日n n（2）生成一个按标记转移的四元式序列：）生成一个按标记转移的四元式序列：wnext:（112）(后续程序四元式序列后续程序四元式序列)（wF）信息学院软件工程教研室信息学院软件工程教研室第41页，共44页，编辑于2022年，星期日n n（3）由上面四元式序列可得各标记的实际地址为：信息学院软件工程教研室信息学院软件工程教研室第42页，共44页，编辑于2022年，星期日n n（4）根据所求地址回填各转移目标地址）根据所求地址回填各转移目标地址,可可得：得：信息学院软件工程教研室信息学院软件工程教研室第43页，共44页，编辑于2022年，星期日n n（接上）信息学院软件工程教研室信息学院软件工程教研室第44页，共44页，编辑于2022年，星期日