当前位置：文档之家 › 109编译原理和技术课件@中科大Intermediate Code Generation

109编译原理和技术课件@中科大Intermediate Code Generation

  • 格式：pdf
  • 大小：520.14 KB
  • 文档页数：68

下载文档原格式

  / 68

合集下载

编译原理与技术讲义.ppt

编译原理与技术讲义.ppt

《编译原理与技术》讲义
20
编译程序的组成结构
符号表管理
名称 类型
…
position float
initial float
rate float
2020/10/20
《编译原理与技术》讲义
11
编译程序的组成结构
词法分析阶段 语法分析阶段 语义分析、中间代码生成 优化阶段 目标代码生成
2020/10/20
《编译原理与技术》讲义
12
编译程序的组成结构
后端
back end 与目标机相关
program
scanner parser semantics
2020/10/20
《编译原理与技术》讲义
19
编译程序的组成结构
代码生成 与目标机器有密切联系，如指令选择，寄存 器的使用等。
movf rate, R1 mulf #60.0, R1 movf initial, R2 addf R2, R1 movf R1, position
2020/10/20
目标程序 T （机器语言）
初始数据
2020/10/20
目标程序 T 运行系统 计算机
计算结果
《编译原理与技术》讲义
8
什么是编译程序？
源语言（程序）到目标语言（程序）的映射 转换或者翻译过程
系列转换（翻译）过程
源语言S
T1
…
Tn
中间语言
目标语言T
2020/10/20
《编译原理与技术》讲义
9
解释程序与汇编程序
fact(n) = n * fact( n-1 ) // n! == n * (n-1)!
伪语言描述 fact(n) = if n ≤ 0 then 1 else n*fact(n-1)

编译原理课件

编译原理课件
3
参考书目： 1.编译原理及实践，Kenneth C.Louden，机械工业出版 社 2.编译原理，吕映芝，清华大学出版社 3.编译原理. (美)阿霍(Aho, A. V.)等著. 李建中等译. 北京: 机械工业出版社, 2003.8 4.现代编译程序设计. (荷)格伦(Grune, D.) 等著. 冯博琴 等译. 北京:人民邮电出版社, 2003.9 5.陈意云，编译原理和技术（第二版），中国科大出版社， 1997 6.陈意云、张昱，编译原理习题精选，中国科大出版社， 2002
12
1.2 编译过程概述
翻译外文资料与编译源程序进行类比
翻译外文资料 分析 编译源程序
识别单词 词法分析 分析句子语法结构 语法分析
初步翻译句子含意 语义分析及中间代码产生
综合
译文修饰 写出译文
代码优化 目标代码生成
13
第一阶段 词法分析(Lexical analysis) 输入源程序，对构成源程序的字符串进行扫描和分解，识 别出一个个单词（也称单词符号，或简称符号）并转换成 内部形式。 输入：源程序中的字符流 输出：等长的内部形式，即属性字。 在词法分析阶段工作所依循的是语言的词法规则。描述词 法规则的有效工具是正规式和有限自动机。
14
词法分析举例
例子，hoo.c： main() { float position, initial, rate; position = initial + rate * 60; } position = initial + rate * 60 scanner id1 = id2 +
标识符
字符流
id3
*
60
记号流
赋值运算符 标识符 加运算符 标识符 乘运算符 整型常量

《编译原理》课件

《编译原理》课件
代码生成
编译器可以将高级语言编写的源代码转换成机器语言或低级语言，以便在特定的硬件平台上运行。编 译器还可以生成可执行文件或动态链接库等二进制文件。
编译器在人工智能领域的应用
机器学习编译器
机器学习编译器可以将机器学习模型转换成可执行代码，以便在嵌入式设备或边缘计算 设备上运行。这种编译器可以优化模型的计算性能和内存占用，提高模型的运行效率。
3
缺点
对于某些复杂文法，可能导致大量的无用推导和 状态爆炸。
自底向上的语法分析
分析步骤
从输入符号序列的最后一个符号开始，逐步向上构建语法树，直 到找到与文法中的某个产生式右部匹配的符号串。
优点
可以充分利用已知信息，避免不必要的推导和状态爆炸。
缺点
对于某些复杂文法，可能导致大量的无用归约和状态爆炸。
04
中间代码生成
中间代码生成的定义和任务
定义
中间代码生成是编译器的一个阶段，将源代码转换成中间代码的过程。
任务
将源代码转换成一种中间表示形式，以便进行后续的优化和目标代码生成。
三地址代码的生成
01
三地址代码是一种中间代码形 式，由一系列的三元式组成。
02
三元式的形式为(op, arg1, arg2)，表示执行一个操作(op) 并产生一个结果，操作数arg1 和arg2来自寄存器、常数或之 前的计算结果。
语义分析
检查AST是否有语义错误，如类型错 误、未定义的变量等。
中间代码生成
将AST转换为中间代码，通常是三地 址代码。
代码优化
对中间代码进行优化，提高执行效 率。
代码生成
将中间代码转换为机器语言代码， 能够在特定硬件上执行。
编译器的分类

中国科技大学编译原理课程PDF精讲课件合辑(共1289页)

中国科技大学编译原理课程PDF精讲课件合辑(共1289页)

第二章 词法分析
记号(token) 源程序 词法分析器 取下一个记号 符号表 语法分析器
本章内容
– 词法分析器：把构成源程序的字符流翻译成 记号流，还完成和用户接口的一些任务 – 围绕词法分析器的自动生成展开 – 介绍正规式、状态转换图和有限自动机概念
2.1 词法记号及属性
2.1.1 词法记号、模式、词法单元
三地址中间代码
1.1 编译器概述
t1 = id3 * 60.0 id1 = id2 + t1 代码生成器 MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1
三地址中间代码
符 号 表 1 position . . . ... 2 initial ... 3 rate
1.2 编译器技术的应用
• 新计算机体系结构的设计
– 现在计算机系统的性能不仅仅取决于它的原始速 度，还取决于编译器是否能生成充分利用其特征 的代码 – 在现代计算机体系结构的研究中，在处理器的设 计阶段就开发编译器，并将编译生成的代码在模 拟器上运行，以评价拟采用体系结构的特征 – 编译器技术影响计算机体系结构设计的一个著名 例子是精简指令集计算机（RISC）的发明
60
语法树
= id, 1
1.1 编译器概述
+
id, 2 id, 3 语义分析器 = +
语法树
60 符 号 表 1 position . . . ... 2 initial ... 3 rate
id, 1
id, 2 语法树 inttofloat id, 3 60
1.2 编译器技术的应用
• 针对计算机体系结构的优化

编译原理第一章PPT课件

编译原理第一章PPT课件

掌握编译原理有助于提高程序员对程序性能、代码质量和软件
03
工程实践的理解。
编译原理的应用领域
编译器设计
编译原理的核心应用领域之一 是编译器设计，包括源代码到
目标代码的转换、优化等。
解释器设计
解释器是另一种将源代码转换 为机器码的程序，编译原理同 样适用于解释器的设计。
程序分析
编译原理中的一些技术可以用 于程序分析，例如静态分析、 动态分析和程序切片等。
从高级语言的设计开始，逐步向下设计低级语言和机器语言。
数据结构和算法选择
选择合适的数据结构和算法，提高编译器的性能和可维护性。
代码优化
在生成目标代码之前，对中间代码进行优化，以提高目标代码的性能 和质量。
04 语言与语法
语言的定义与分类
总结词
语言的定义与分类是编译原理的重要基础，它涉及到语言的语法、语义和语用等方面。
语言的语义分析
总结词
语义分析是编译过程中的重要环节，它涉及 到对语言意义的解释和理解。
详细描述
语义分析是对源代码进行静态分析的过程， 目的是理解源代码的意义和功能。在语义分 析阶段，编译器会检查源代码中是否有语法 错误、类型错误、逻辑错误等，并对其进行 相应的处理。同时，语义分析还会进行符号 表管理、类型检查、控制流分析等工作，以
详细描述
中间代码生成是编译过程的第三步，其主要任务是将抽象语法树转化为中间代码。中间代码是一种抽象的、与具 体机器无关的代码形式，通常采用三地址码、四元式等表示方式。中间代码的主要目的是为了方便后续的优化和 目标代码生成。
代码优化
总结词
对中间代码进行优化，提高执行效率。
详细描述
代码优化是编译过程中非常重要的一步，其主要任务是对中间代码进行优化，以提高生成的目标代码 的执行效率。常见的优化技术包括常量折叠、无用代码删除、循环展开等。

编译原理与技术讲义-第3章

编译原理与技术讲义-第3章

2
在自顶向下的语法分析中，通常使用预测分析法 或移进-规约分析法进行语法分析。
3
预测分析法基于预测分析表进行语法分析，而移 进-规约分析法则使用一个栈和一个规约机进行语 法分析。
自底向上的语法分析
自底向上的语法分析是一种与自顶向下 的语法分析相反的方法，其基本思想是 从源程序的叶子节点开始，逐步向上构 建语法树。
在自底向上的语法分析中，通常使用LR(0)、 SLR(1)、LALR(1)等算法进行语法分析。
自底向上的语法分析方法在处理左 递归和不确定的文法时具有优势， 但在处理右递归文法时可能会出现 问题。
03
中间代码生成
中间代码生成概述
中间代码定义
01
中间代码是源代码和目标代码之间的代码，通常是一种抽象的、
语法分析的主要目标是理解源程序的语法结构，并构建一棵语法树，以表 示程序中的各个语句和表达式的层次结构。
语法分析是编译过程中最复杂的部分之一，需要仔细设计和实现，以确保 能够正确地解析源程序。
自顶向下的语法分析
1
自顶向下的语法分析是一种常见的语法分析方法， 其基本思想是从源程序的根节点开始，逐步向下 分析各个子节点。
利用数据流方程来分析程序中 的数据依赖关系，从而进行优 化。例如，通过数据流分析确 定无用代码并进行删除。
05
目标代码生成
目标代码生成概述
01
目标代码生成是编译器的重要 阶段，它将中间代码转换为特 定机器上的目标代码。
02
目标代码生成需要考虑机器的 指令集、寻址方式、寄存器分 配等因素，以确保生成的代码 能够正确、高效地运行。
Java等。
02
实现词法分析器需要编写相应的词法分析器代码，并

《编译原理》课件

《编译原理》课件
了解中间代码生成的概念和它在编译过程中的角色。 学习四元式和三地址码的表示和生成方式，以及中间代码优化的技巧。
六、代码生成
了解目标机器的指令系统和存储结构，以及它们对代码生成的影响。 学习寄存器分配和目标代码生成的基本原理和方法。
七、附录
参考文献提供了进一步学习编译原理的资源。 课程总结将回顾课程中学到的重要知识，并概述关键概念和技术。 问题解答将回答学生在课程学习中提出的问题。 课程评价将收集学生对课程的反馈和评价，以便对将来的课程进行改进。
《编译原理》PPT课件
编译原理PPT课件将带您深入了解编译原理的重要概念和技术。这个课程介绍 了编译原理的意义以及编译过程的概述。
一、引言
课程介绍编译原理的重要性，让您理解为什么编译原理对于软件开发非常关 键。 编译过程的概述将带您了解传统的编译过程中涉及的各个阶段和任务。
二、词法分析
词法分析是编译过程中的第一步，了解词法分析的作用以及它在编译器中的 实现。 掌握正则表达式和有限自动机的概念，这些是实现词法分骤，理解它的作用和不同的语法分析方法。 学习上下文无关文法以及LL(1)语法分析器和LR(1)语法分析器的实现原理。
四、语义分析
语义分析是编译过程中的重要一环，了解它的作用和涉及的任务。 学习语义动作、符号表管理和类型检查，以及如何进行语法制导翻译。
五、中间代码生成

编译原理与技术讲义

编译原理与技术讲义

编译原理与技术讲义编译原理与技术是计算机科学中的一门重要课程，它主要研究编译器的设计与实现。

编译器是将一种高级语言程序翻译成机器语言的程序，它在计算机科学中具有重要的地位和作用。

本讲义将介绍编译原理与技术的基本概念、原理和常见的实现方法。

一、编译原理与技术的基本概念1.1编译器的定义与功能编译器是一种将高级语言程序转化为机器语言程序的软件工具。

它的主要功能包括语法检查、词法分析、语义分析、中间代码生成、代码优化和目标代码生成等。

1.2编译过程的基本流程编译过程主要包括源程序的词法分析、语法分析、语义分析和代码生成等阶段。

其中，词法分析将源程序转化为词法单元，语法分析将词法单元转化为语法树，语义分析将语法树转化为语义树，而代码生成将语义树转化为目标代码。

1.3语言处理器的组成与原理语言处理器包括编译器和解释器两种，它们都是将高级语言翻译成机器语言的软件工具。

编译器是将整个高级语言程序一次性地翻译成机器语言，而解释器是逐行地将高级语言程序翻译成机器语言并立即执行。

二、词法分析与语法分析2.1词法单元的定义与识别词法单元是编程语言中的一个基本单位，它由一个或多个字符组成，用于表示程序中的各种标识符、常量和运算符等。

词法分析的主要任务是将源程序中的字符序列划分为一系列的词法单元。

2.2正则表达式与有限自动机正则表达式是一种描述字符序列模式的特殊字符串，它常用于词法分析中的模式匹配。

有限自动机是一种描述正则表达式匹配过程的数学模型，它可以用于实现词法分析器。

2.3语法分析的基本原理与方法语法分析的主要任务是对词法单元序列进行分析，判断其是否符合给定的文法规则。

常用的语法分析方法有LL(1)文法分析、LR(1)文法分析和LALR(1)文法分析等。

三、语义分析与中间代码生成3.1语义分析的基本概念与原理语义分析的主要任务是对语法树进行分析，判断其是否符合给定的语义规则。

语义分析的过程包括类型检查、作用域分析和语义错误检查等。

编译原理与技术.ppt

编译原理与技术.ppt

动作
移进a 移进b 归约：Ab 移进b 移进c
2019/10/28
《编译原理与技术》讲义
12
移进－归约分析
e.g.17 用栈来实现串abbcde$的分析（2）
分析栈 $aAbc $aA $aAd $aAB $aABe $S
2019/10/28
输入串
动作
de$ de$ e$ e$ $
移进c 归约: AAbc 移进d 归约：Bd 移进e
《编译原理与技术》讲义
28
e.g.21 表达式文法G2的LR分析表（续）
状
action
态 id + * ( ) $
7 s5
s4
8
s6
s11
9
r1 s7
r1 r1
10
r3 r3
r3 r3
11
r5 r5
r5 r5
goto ETF
10
2019/10/28
《编译原理与技术》讲义
29
e.g.21 id*(id+id)$的移进-归约分析过程
输入串 )$ )$ )$ $ $ $ $ $
输出 r6:Fid r4:TF r1:EE+T s11:移进) r5:F(E) r3:TT*F r2:ET acc
2019/10/28
《编译原理与技术》讲义
32
识别活前缀的DFA
活前缀（viable prefix）
$
r: SaABe
分析成功！
《编译原理与技术》讲义
13
移进－归约分析
四种分析动作（action）
∙ 移进（shift）－将当前输入符号移入栈顶top
（why？）
∙ 归约（reduce）－当“句柄”出现在栈顶（从栈

《编译原理课件》PPT课件

《编译原理课件》PPT课件
它是源程序的一种内部表示形式。 设计中间代码的原则：一是容易生成，二是
容易翻译成目标代码。 常用的中间代码有三地址码、四元式、三元
式、间接三元式、逆波兰表示（后缀式）、 树形表示等。
14
中间代码：四元式
例： id1:=id2+id3*10
sum:=first+count*10 翻译为四元式中间代码的形式：
5
1.2 编译程序的工作过程与结构
一个编译程序的整个工作过程是划分成阶段 进行的，每个阶段将源程序从一种表示形式 转换成另一种表示形式。
编译阶段的典型划分方法是划分为5个基本阶 段：词法分析、语法分析、语义分析产生中 间代码、代码优化、代码生成。
掌握编译过程的5个基本阶段，是学习编译原 理课程的基本内容。
29
自编译：T形图表示
PASCAL2
A代码
PASCAL2
A代码
PASCAL1 PASCAL1
A代码 A代码
用PASCAL1语言 编写的功能更
强的PASCAL2语 言编译程序的
Ａ代码
已有的PASCAL1 语言的编译程序
自编译得到
功能更强的
PASCAL2语言 的编译程序
源程序
注意：T形图的组合规则：① ②
Java语言的操作平台无关性的实现就是如此。
26
1.3 编译程序的开发
构造编译程序，可以：
1. 使用机器语言或汇编语言作工具构造 2. 使用高级语言作工具构造 3. 使用机器语言或汇编语言构造编译程序的核心
部分，使用高级语言构造编译程序的扩充部分 4. 使用编译程序自动生成工具构造
使用高级语言作工具构造编译程序可以大大节 省程序设计的时间，并且编译程序易于阅读、 维护和移植。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

7.2 声 明 语 句
P → M D; S {addWidth (top (tblptr), top (offset) ); pop(tblptr); pop (offset) } M→ε {t = mkTable (nil); push(t, tblprt); push (0, offset) } D → D1 ; D2 D → proc id ; N D1; S {t = top(tblptr); addWidth(t, top(offset) ); pop(tblptr); pop(offset); enterProc(top(tblptr), id.lexeme, t) } D→id :T {enter(top(tblptr), id.lexeme, T.type, top(offset)); top(offset) = top(offset) + T.width } N→ε {t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) }
7.1 中
间
语
言
• 三地址代码是语法树或DAG的一种线性表示 • 例 a = (−b + c∗d ) + c∗d 语法树的代码 DAG的代码 t1 = −b t1 = −b assign t2 = c ∗ d t2 = c ∗ d a + t3 = t1 + t2 t3 = t1 + t2 + t4 = c ∗ d t4 = t3 + t2 uminus ∗ c d t5 = t3 + t4 a = t4 b a = t5
7.1 中
间
语
言
• 后缀表示不需要括号 (8 − 5) + 2 的后缀表示是8 5 −2 + • 后缀表示的最大优点是便于计算机处理表达 式
计算栈 8 85 3 32 5 输入串 8 5 −2 + 5 −2 + −2 + 2+ +
7.1 中
间
语
言
• 后缀表示不需要括号 (8 − 5) + 2 的后缀表示是8 5 −2 + • 后缀表示的最大优点是便于计算机处理表达 式 • 后缀表示很容易拓广到含一元算符的表达式 • 后缀表示也可以拓广到表示赋值语句和控制 语句，但很难用栈来描述它的计算
7.1 中
间
语
言
7.1.2 图形表示 • 语法树是一种图形化的中间表示 • 有向无环图也是一种中间表示
assign a + + ∗ a assign +
+ ∗ ∗ c uminus d uminus c c d d b b (b) DAG (a) 语法树 a = (−b + c∗d) + c∗d的图形表示
7.2 声 明 语 句
P → M D; S {addWidth (top (tblptr), top (offset) ); pop(tblptr); pop (offset) } M→ε {t = mkTable (nil); push(t, tblprt); push (0, offset) } D → D1 ; D2 D → proc id ; N D1; S {t = top(tblptr); addWidth(t, top(offset) ); pop(tblptr); pop(offset); enterProc(top(tblptr), id.lexeme, t) } D→id :T {enter(top(tblptr), id.lexeme, T.type, top(offset)); top(offset) = top(offset) + T.width } N→ε {t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) }
7.2 声 明 语 句
本节介绍 • 为局部名字建立符号表条目 • 为它分配存储单元 • 符号表中包含名字的类型和分配给它的存储 单元的相对地址等信息
7.2 声 明 语 句
7.2.1 过程中的声明
7.2 声 明 语 句
计算被声明名字的类型和相对地址 P → {offset = 0} D; S D→D;D D → id : T {enter ( id.lexeme, T.type, offset); offset = offset + T.width } T → integer {T.type = integer; T.width = 4 } T→ real {T.type = real; T.width = 8 } T→ array [ num ] of T1 {T.type = array (num.val, T1.type); T.width = num.val × T1.width} T→ ↑T1 {T.type = pointer (T1.type); T.width = 4 }
7.2 声 明 语 句
7.2.3 记录的域名 T → record D end 记录类型单独建符号表，作为类型表达式的 主要部分，域的相对地址从0开始 T → record L D end {T.type = record (top(tblptr) ); T.width = top(offset); pop(tblptr); pop(offset) } L→ε {t = mkTable(nil); push(t, tblprt); push(0, offset) }
7.2 声 明 语 句
P → M D; S {addWidth (top (tblptr), top (offset) ); pop(tblptr); pop (offset) } M→ε {t = mkTable (nil); push(t, tblprt); push (0, offset) } D → D1 ; D2 D → proc id ; N D1; S {t = top(tblptr); addWidth(t, top(offset) ); pop(tblptr); pop(offset); enterProc(top(tblptr), id.lexeme, t) } D→id :T {enter(top(tblptr), id.lexeme, T.type, top(offset)); top(offset) = top(offset) + T.width } N→ε {t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) }
Hale Waihona Puke 7.1 中间语
言
构造赋值语句语法树的语法制导定义 修改构造结点的函数可生成有向无环图
产 生 式 S → id =E E → E1 +E2 E → −E1 E → (E1) F → id 语 义 规 则 S.nptr = mkNode(‘assign’, mkLeaf (id, id.entry), E.nptr) E.nptr = mkNode( ‘+’, E1.nptr, E2.nptr) E.nptr = mkUNode( ‘uminus’, E1.nptr) E.nptr = E1.nptr E.nptr = mkLeaf (id, id.entry)
7.2 声 明 语 句
符号表实例
图6.14的 Pascal程序 空 sort 表头 指向readarray 指向exchange quicksort 表头 k v partition partition a x readarray exchange quicksort exchange 表头
readarray 表头 i
第七章
记号 分析 流 器 本章内容
中间代码生成
中间 代码 中间 代码 生成 代码 生成 器 器
静态 检查 器
–介绍几种常用的中间表示：后缀表示、图形表示 和三地址代码 –用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间形式
7.1 中
间
语
言
7.1.1 后缀表示 表达式E的后缀表示可以如下归纳定义 • 如果E是变量或常数，那么E的后缀表示就是 E本身 • 如果E是形式为E1 opE2的表达式，那么E的后 缀表示是E1′ E2′ op，其中E1′和E2′分别是E1和 E2的后缀表示 • 如果E是形式为(E1)的表达式，那么E1的后缀 表示也是E的后缀表示
E → E1 ∗E2 E.nptr = mkNode( ‘∗’, E1.nptr, E2.nptr)
7.1 中
7.1.3 三地址代码 一般形式：x = y op z
间
语
言
• 例 表达式x + y ∗ z翻译成的三地址语句序列是 t1 = y ∗ z t2 = x + t1
7.1 中
间
语
言
• 三地址代码是语法树或DAG的一种线性表示 • 例 a = (−b + c∗d ) + c∗d 语法树的代码 t1 = −b t2 = c ∗ d t3 = t1 + t2 t4 = c ∗ d uminus t5 = t3 + t4 a = t5
7.2 声 明 语 句
计算被声明名字的类型和相对地址 P → {offset = 0} D; S D→D;D D → id : T {enter ( id.lexeme, T.type, offset); offset = offset + T.width } T → integer {T.type = integer; T.width = 4 } T→ real {T.type = real; T.width = 8 } T→ array [ num ] of T1 {T.type = array (num.val, T1.type); T.width = num.val × T1.width} T→ ↑T1 {T.type = pointer (T1.type); T.width = 4 }