第08章 语法制导翻译和中间代码生成
《编译原理》课后习题答案第八章
第 8 章 语法制导翻译和中间代码生成
第 1 题
给出下面表达式的逆波兰表示(后缀式)： (1)a*(-b+c)
(2) if(x+y)*z=0 then s∶=(a+b)*c else s∶=a*b*c 答案：
给出下面表达式的逆波兰表示(后缀式)： (1) ab-c+*
(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示 if-then-else 运算）
如果写成这样： xy+z*0=sab+c*:=sabc**:=￥，则是错误的，因为写表达式和赋值语句 的中间代码序列，或是写它们的代码生成过程，必须注意按照算符优先序进行，这实际上是 按照 LR 分析过程进行的。例如：写出赋值语句 a:=a+b*c*(d+e)的四元式中间代码,当前四元 式序号为 100。不能写成：
100 (+,d,e,t1) 101 (*,b,c,t2) 102 (*,t2,t1,t3) 103 (+,a,t3,t4) 104
(:=,t4,-,a) 应该写成：
100 101 102 103 104
(*,b,c,t1) (+,d,e,t2) (*,t1,t2,t3) (+,a,t3,t4) (:=,t4,-,a)
第 2 题
请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式、四元式序列、树形、 逆波兰，当前序号为 100。 答案：
三元式： 100 (+, a, b)
101 (+, c, d) 102 (* , (1), (2))
盛威网（）专业的计算机学习网站 1
《编译原理》课后习题答案第八章
103 104 105 106 (-, (3), /) (+, a, b) (+,(5),c) (- (4), (6))
编译原理语义分析与中间代码生成
在编译原理中，语义分析是编译器的重要组成部分之一，它负责验证和处理源代码中的语义信息，为后续的中间代码生成做准备。本文将介绍语义分析的基本概念和流程，并探讨中间代码生成的相关技术。
一、语义分析的基本概念和流程
语义分析是指对源代码进行语义检查和语义信息提取的过程。其主要目标是确保源代码在语义上是正确的，并从中提取出各种语义信息，以便后续阶段使用。
语义分析的基本流程如下：
1. 词法分析和语法分析：在进行语义分析之前，需要先对源代码进行词法分析和语法分析，以便将代码转化为具有结构的中间表示形式（如抽象语法树）。
2. 符号表的构建：符号表是语义分析的重要数据结构，用于存储程序中出现的各种标识符及其相关信息，如类型、作用域等。在语义分析阶段，需要构建符号表并实时更新。
3. 类型检查：类型检查是语义分析的核心任务之一。它通过对表达式、赋值语句、函数调用等进行类型推导和匹配，来验证程序是否存在类型错误。 4. 语义规则检查：除了类型检查外，语义分析还需要检查程序是否符合语言规范中的其他语义规则，如变量是否已声明、函数调用是否正确等。
5. 语义信息提取：语义分析还负责提取源代码中的各种语义信息，如函数调用关系、变量的定义和引用关系、控制流信息等。这些信息将为后续的代码优化和代码生成提供依据。
二、中间代码生成的相关技术
中间代码是指某种形式的中间表示形式，通常与源代码和目标代码之间存在一定的映射关系。它在编译过程中起到连接前后两个阶段的桥梁作用，并且可以进行一些优化。
常见的中间代码形式之一是三地址码。三地址码是一种低级的代码表示形式，每条指令最多包含三个操作数。它具有简洁明了的特点，适合进行后续的优化工作。
在进行中间代码生成时，需要考虑以下几个方面的技术：
1. 表达式的翻译：在将源代码转化为中间代码时，需要将源代码中的表达式进行翻译。这包括对表达式的计算顺序、运算符优先级等方面的处理。
第 1 页 共 15 页 第8章 语法制导翻译和中间代码生成（3学时，15分钟）
编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，它们的语法结构可以不同，但表达的结果应完全相同。
通常，在语法分析过程中，每当一个产生式获得匹配（自上而下分析）或用于归约（自下而上分析）时，就执行相应于该产生式的语义子程序进行语义处理，这个过程就是语法制导翻译。
编译中的语义处理是指两个功能：
第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义，也称为静态语义检查或静态审查。动态语义检查需要生成相应的目标代码，在运行时进行。
静态语义检查主要涉及以下几个方面：
（1）类型检查，如参与运算的操作数及类型应相容。
（2）控制流检查，用以保证控制语句有合法的转向点。如C语言中不允许goto转入case语句流；break语句需要寻找包含它的最小switch、while或for语句方可找到转向点，否则出错。
（3）一致性检查，如在相同作用域中标识符只能说明一次、case语句的标号不能相同等。
第二，如果静态语义正确，语义处理的工作是要执行真正的翻译，即生成程序的一种中间表示形式（中间代码），或者直接生成第 2 页 共 15 页 实际的目标代码。
虽然源程序可以直接翻译为目标语言代码，但是通常编译程序还是采用了独立于机器的、复杂性介于源语言与机器语言之间的中间语言。这样做的好处是：
（1）便于进行与机器无关的代码优化；
（2）使编译程序改变目标机更容易；
（3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。
静态语义检查和中间代码产生在编译程序中的位置如图所示：
需要指出的是：从单词符号序列的源程序到某种形式的中间代码，不像词法分析和语法分析那样有一套形式化的理论和算法（如自动机等），尽管已经有了一些形式语义系统，但大都没有得到公认。这就是说，语义的形式化描述要远比语法的形式化困难得多。目前较为常见的是用属性文法作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作。
编译原理中间代码生成
在编译原理中，中间代码生成是编译器的重要阶段之一、在这个阶段，编译器将源代码转换成一种中间表示形式，这种中间表示形式通常比源代码抽象得多，同时又比目标代码具体得多。中间代码既能够方便地进行优化，又能够方便地转换成目标代码。
为什么需要中间代码呢？其一，中间代码可以方便地进行编译器优化。编译器优化是编译器的一个核心功能，它能够对中间代码进行优化，以产生更高效的目标代码。在中间代码生成阶段，编译器可以根据源代码特性进行一些优化，例如常量折叠、公共子表达式消除、循环不变式移动等。其二，中间代码可以方便地进行目标代码生成。中间代码通常比较高级，比目标代码更具有表达力。通过中间代码，编译器可以将源代码转换成与目标机器无关的形式，然后再根据目标机器的特性进行进一步的优化和转换，最终生成目标代码。
中间代码生成的过程通常可以分为以下几步：
1.词法分析和语法分析：首先需要将源代码转换成抽象语法树。这个过程涉及到词法分析和语法分析两个步骤。词法分析将源代码划分成一个个的词法单元，例如标识符、关键字、运算符等等。语法分析将词法单元组成树状结构，形成抽象语法树。
2.语义分析：在语义分析阶段，编译器会对抽象语法树进行静态语义检查，以确保源代码符合语言的语义规定。同时，还会进行类型检查和类型推导等操作。 3.中间代码生成：在中间代码生成阶段，编译器会将抽象语法树转换成一种中间表示形式，例如三地址码、四元式、特定的中间代码形式等。这种中间表示形式通常比较高级，能够方便进行编译器的优化和转换。
4.中间代码优化：中间代码生成的结果通常不是最优的，因为生成中间代码时考虑的主要是功能的正确性，并没有考虑性能的问题。在中间代码生成之后，编译器会对中间代码进行各种优化，以产生更高效的代码。例如常量折叠、循环优化、死代码删除等等。
5.中间代码转换：在完成了中间代码的优化之后，编译器还可以对中间代码进行进一步的转换。这个转换的目的是将中间代码转换成更具体、更低级的形式，例如目标机器的汇编代码。
