编译原理ppt

《编译原理》课程信息
教学目的与要求：
编译程序是现代计算机系统的基本组成部
分之一。本课程重点讲述编译程序的设计
原理和常用实现技术。通过课程的学习和
实验的完成，应该清楚的理解一个编译程
序是如何工作的；如果在以后遇到了任何
一个程序设计语言，应该知道如何实现这
个语言的多数机制；应具有一定的使用编
译构造工具开发编译程序的经验；会将所
参考书:《程序设计语言 编译原理》（第3 版），陈火旺、刘春林等，国防工业出版社 2000
等等
2021/3/7
CHENLI
2
教学内容
1 编译程序概述 编译程序是现代计算机系统的基本组成部分之 一.编译程序一般由词法分析程序，语法分析程 序，语义分析程序，中间代码生成程序，目标 代码生成程序，代码优化程序，符号表管理程 序和错误处理程序等成分构成。本章概要介绍 编译成分的主要功能以及编译阶段的逻辑关系。
教学内容
5 语法分析程序的构造
自顶向下的语法分析。可以看作是为一个输入串寻找 一个最左推导的过程,也等价于从根开始,按前序生成 结点，为输入串构造分析树的过程。讨论一种有效的 无回溯的自顶向下分析程序,这种分析程序称为预测 分析程序。介绍对于一个文法类：LL（1）文法, 如 何自动的构造预测分析程序。
2 PL/0 编译程序剖析 给出一个简单的类Pascal语言，其编译程序用 高级语言（C和Pascal）实现。通过剖析该高 级语言程序以理解各编译成分的功能及手工实 现方法。
2021/3/7
CHENLI
3
教学内容
3 高级语言的认识
要学习和构造编译程序，理解和定义程序设计语言
是必不可少的。每个程序设计语言都有一定的规则用 以规定合适程序的语法结构，也需要有对一个程序的 含义的描述。上下文无关文法给出程序设计语言的精 确的,易于理解的语法说明。尚没有公认的形式系统 描述程序含义，但也有流行的描述语义规则的方法— 属性文法。

procedure SORT(CH);
{ case CH of ‘字母’:
‘字母’: call RECOGID(CH,TOKEN);
‘/’: call HANDLECOM(CH,TOKEN);
‘数字’: call RECOGDIG(CH,TOKEN);
‘’‘
call RECOGSTR(CH,TOKEN);
if TOKEN!=‘ ’ then call PRINTERR(‘注解未完’);
TOKEN:=‘ ';
return }
25
识别界限符(RECOGDEL) 输入：CH内含单界限符； 输出：各种界符的TOKEN字; procedure RECOGDEL(CH,TOKEN); { case CH of
otherwise call RECOGDEL(CH,TOKEN);
end case;
write TOKEN into TOKEN文件;
Return } 23
procedure RECOGID(CH,TOKEN);
{ WORD:= ‘ ’; WORD:=WORD||CH; Repeat {
call GETCH(CH);
%%
标识符 {入口地址=LOOKUP();}
%%
LOOKUP()
31
辅助过程是动作需要的，这些过程用C书 写，可以分别编译.例：LOOKUP()
32
28
声明 %% 翻译规则 %% 辅助过程
29
声明包括变量，符号常量和正规定义式。
翻译规则的形式为：
p1
{ 动作1}
p2
{ 动作2}
…
…
pn
{ 动作n}
30
每个pi是正规定义式的名子，每个{动 作i}是正规定义式pi识别某类单词时，词 法分析器应执行动作的程序段。用C书 写。

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

词法分析过程
输入
源程序的字符流。
01
输出
源程序的标记流。
02
1. 初始化
设置初始状态和缓冲区。
03
2. 循环
04 从缓冲区中取出一个字符，根
据当前状态和该字符确定下一 个状态和标记。
3. 输出
05 输出当前标记，并更新状态和
缓冲区。
4. 结束条件
06 当缓冲区为空且所有字符都被
处理时，结束词法分析。
三地址代码的生成
三地址代码定义
三地址代码是一种中间代码形式，由一系列的三元式组成，每个三 元式包含三个操作数和两个操作符。
三地址代码的特点
三地址代码具有简单、直观和易于优化的特点，能够清晰地表示程 序中的控制流程和数据流。
三地址代码的生成算法
常见的三地址代码生成算法包括递归下降分析法和语法制导翻译法 。
示中间代码，以便进行有效的优化和转换。
代码生成器的构造
代码生成器通常由指令选择、控制流优化、循环优化等 模块组成。
控制流优化模块负责对控制流进行分析和优化，如消除 冗余计算、消除无用代码等。
指令选择模块负责从中间代码中选择合适的机器指令， 并进行指令调度和并行化。
循环优化模块负责对循环结构进行优化，如循环展开、 循环合并等。
编译原理的应用非常广泛，如编译器设计、程序分析、软件工程等。
编译过程的基本概念
源程序
用高级语言编写的程序，也称为源代码。
目标程序
编译后的程序，也称为目标代码或机器代码。
编译程序
将源程序翻译成目标程序的软件。
编译过程
将源程序通过词法分析、语法分析、语义分析、中间代码生成、优化 、目标代码生成等阶段，最终生成目标程序的过程。

例有文法G[L]
(1)LE,L (2)LE (3)Ea (4)Eb
要求对输入串a,b,a进行分 析，即分析#a,b,a#
首先应给出LR分析表
为了节省空间，在实际应用中，将动作(Action) 表和状态转换(Goto)表中关于终结符的各列对 应进行合并。
10
例如，本来 Action(S0,a)= “移进”，表示 在状态S0下输入 a时，执行“移
进行分析时，对
为了构造分应析的动表作，是我把们符根据各项目的特点把项 目分成不同类型号，a移分进类符的号栈原。则是根据圆点所在位置
和圆点之后是终结符它还表是明非该状终态结等符进行的。
1.,移进V项*,目a：V圆T,它点此析对之时完待的应，毕后着分已，的为对析把状终非。已终态结分在结为符符移的B进项状目态, A；Sa.Aa.c,Be 2.待约项目：圆点栈之顶，后可为以非按终相结符的项目, A.B ，
(1)应用面广：能够用LR分析程序识别绝大多数的程 序设计语言的语法结构；
(2)实现效率高：虽构造方法复杂，但是实现（执行） 效率高。 (3)查错准确：LR分析器能够及时发现语法错误并准 确指出错误位置。
1
LR(k)分析方法中L是指自左(Left)向右扫描输入单词 串，R指分析过程是最右(Right)推导的逆过程(规 范归约)，k是指在决定当前分析动作时需向前察看 的输入符号个数。
输入符号进栈； 归约：用相应的产生
S0
移进
元素元为素空为白a表cc 示表出示错接受
式进行归约；
S1
r5
接受：当归约到只剩下
…
文法开始符号且输入串 结束时分析成功；
Sm
ac c
出错：当状态栈顶为某一状态下，出现了不该出现的