清华大学软件学院编译原理课件pdf

1.1 什么是编译程序(COMPILER)
高级语言
书写的程序
术语
编译程序
低级语言程序
编译程序的源语言 (源程序)
编译程序的目标语 言(目标程序) 编译程序的实现语 言
S I
O
S I
T
1.1 什么是编译程序(COMPILER)
三、编译系统
按编译方式在计算机上执行高级语言编写的程序需 经过两个阶段： 1、编译阶段 2、运行阶段
参考书
第一章 编译概述
编译程序是计算机系统中重要的 系统软件,是高级语言的支撑基础。编 译原理这门课程主要介绍设计和构造 编译程序的基本原理和常用的技术和 方法。 本章重点介绍编译程序的基本概念。
2018/11/9
编译原理
7
第一章 编译概述
1.1 1.2 1.3 1.4 什么是编译程序 编译过程概述 编译程序的结构 编译阶段的组合
二、学习成果
理解和掌握编译过程各个阶段的工作原理 理解标准编译器各个组成部分的任务 熟悉编译过程各阶段所要解决的问题及其采用的方法和技术 应用一些标准的技术解决编译器构造过程中所产生的相关问 题

三、学时分配 授课学时36学时，实验12学时 实验一：词法分析器 实验二：语法分析器
五、学习方法
例：外文翻译和编译工作的比较
翻译外文
1.2
编译过程和编译程序的结构
编译源程序
阅读原文
分析 识别单词 分析句子 修辞加工 综合 写出译文
输入并扫描源程序
词法分析 语法分析 代码优化 目标代码生成
源程序
词法分析程序 单词符号 表 格 管 理 语法分析程序 语法单位 语义分析程序与中间代码生成程序 中间代码 出 错 处 理

f
a
b
-0 1 2
132
213
+3 3 3
状态转换表的行标表示状态，列标表示输入 符号，表元素表示f(W,a)的值。
19
定义4.6 字母表V上的状态图SG是如下有向图：
(1)至少有一个初始结点，用“－”标记； (2)至少有一个终止结点，用“＋”标记；
确定，可全体编为一类，称作“一字一类”） ②标识符：用户定义的常量名、变量名、过程名和
类型名（个数不确定，作为一类，称作“一符一 类”） ③常量：12,1997,4.14,‘A’,‘scnu’等（个数不 确定，按类型分类） ④运算符 ＋,－,＊,／, >,>=,<,<=,#等（个数 确定，“一符一类”） ⑤界限符 ；,（）等（个数确定，“一符一类”）
5
词法分析程序输出的单词符号通常用二元式 表示：（单词种别，单词自身的值）
单词种别：表示单词种类，常用整数编码， 它是语法分析需要的 单词自身的值：是编译中其他阶段所需要 的信息
6
(4)词法分析程序的设计过程
3G 3型文法 RE 正则表达式
3G RE
SG 状态图 εFA ε确定自动机
εDFA
εNFA ε非确定自动机
A→0S|1A|ε A=ε+0S+1A ② 解:
17
4.3 有穷自动机(FA)
(1)确定有穷自动机（DFA） 定义4.5 一个确定有限自动机(DFA)M是一个五元 组：M=(K,VT,f,S,Z) 其中 K：有穷状态集； VT：有穷的输入字母表； f：K×VT→K是状态转换函数，即f(W,a)=U
(ba)*b ={(ba)nb|n≥0} b(ab)* =(ba)*b
11

32
6.3 算符优先分析法
• 简单优先技术对符号表中的所有符号之间 建立优先关系。但是，有些情况下，不需 要对所有两个符号之间建立优先关系。 • 算符优先分析技术只在终结符号之间建立 优先关系。
33
算符优先分析法的基本思想
• 这种方法是效仿算术式的四则运算而建立 起来的。对于算术表达式，只需要按照运算符 之间的优先关系，就可以确定运算的顺序。不 需要考虑操作数就可以对表达式进行分析。 • 例如：E+T*F，只需要知道*的优先级高于 +，就可以知道T*F是句柄。 • 刚开始是对表达式文法进行分析，但是目 前已不限于此。在一般的文法中，终结符号的 地位相当于运算符号。 34
第6章 自底向上优先分析法
1
6.1 概 述
• 从推导的角度，从输入符号出发，试图 把它规约成识别符号。每一步都寻找特 定的某个类型的短语（一般是简单短语） 进行归约。在分析过程中，每次归约的 都是最左边的简单短语（或其它短语）。 • 从语法树的角度，以输入符号为树的叶 子结点，试图向根结点方向往上构造语 法树。
定理6.4的证明(续)
• 如果t=j-1，那么, 由句柄1，Sj-1 ◄ Sj；
由句柄2， Sj-1 = Sj 或者Sj-1 ► Sj；矛盾！
• 如果t=i+1，由句柄1，Si ► Si+1；
由句柄2，Si ◄ Si+1 或者 Si = Si+1。
• 如果i<= t <= j；那么
– Sj在句柄中：
– Si在句柄内部，但是Si+1在句柄之后，必然 有规则U→…Si，且存在规范句型…USi+1…。 – 如果Si+1在句柄内，而Si在句柄外，那么必 然存在规范句型…SiU…，且 有U→Si+1…。

当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只 含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子 的语言来讲，就存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规 则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是 由主语后随谓语而成，构成谓语的是动词和直接宾语。 任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集 （字母表）上的一个符号串。 对于自然语言来说，它们是定义在某个字母表上的句子的集合。 对于程序语言来说，它们也是定义在某个字母表上的句子的集合。这里 的句子，就是一个源程序。 通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。 这些语法成分统称为单词或单词符号。 单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法 规则所确定的，即词法规则规定了单词符号的形成规则。
2 在乔姆斯基（Chomsky）的文法类型中，为什么特别 关注上下文无关文法？ 3 文法的递归性、二义性等性质是什么？ 4 句子、句型和语言的定义是什么？ 5 推导和归约是什么？ 6 什么是语法分析？语法分析方法的分类？
7 如何确定一个输入符号串是否是所给文法的句子？
第3章:文法和语言
3.0 概述 3.1 形式语言基础 3.2 3.3 3.4 3.5 3.6 文法的直观理解 文法和语言的定义 文法的类型 语法树与二义性 句型的分析
4.符号串集合：由符号串构成的集合。
3.0 概述
用高级语言编程比用低级语言方便，但要解决两个问题： (1)计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目 标程序的转换。 (2)用什么方法来精确定义高级语言，即怎样精确描述高级语言。 要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法） 及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理 论或什么方法来描述的。 本章目的 为语言的语法描述寻求工具，该工具要对程序设计语言给出精 确无二义的语法描述。（严谨、简洁、易读） 形式工具----形式语言抽象地定义为一个数学系统。 “形式”----：语言的所有规则只以符号串能出现的方式来陈述。

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

17
Hale Waihona Puke 3、语义分析（1）语义
定义语言的单词符号和语法单位的意义.一个语言的 语义是指这样的一组规则，使用它可以定义一个程序的 意义.这些规则称为语义规则.
离开语义，语言只不过是一堆符号的集合.
语义分析阶段的主要任务
审查源程序有无语义错误，为代码生成阶段收集类型信 息.
18
3、语义分析（2）
例如： 类型审查、数组下标检查、强制类型转换等
2. 任何常数（整常数、实常数）是表达式。
3. 若表达式1和表达式2都是表达式，那么 ·表达式1+表达式2 ·表达式1*表达式2 ·（表达式1）
都是表达式。
16
程序结构（2）
语句的表示： 1. 标识符:=表达式 是语句。 2. while (表达式) do 语句 和
if (表达式) then 语句 else 语句 都是语句。
整数：10 界符：。
逗号：， 冒号：：
分号：； 赋值号：:= 加号：+ 乘号：*
机内码为：id1:=id2+id3*10
13
2、语法分析
❖ 任务：单词符号串 → 各类语法单位 在词法分析的基础上将单词序列分解成各类语法短语.通常 用语法树表示这种语法短语.
❖ 依据：语言的语法规则 ❖ 描述语法规则的工具：上下文无关文法、确定的下推自动机
任课教师：湛 燕 Email: zhanyan@
数学与计算机学院
1
教材与参考书
编译原理（第二版）. 张素琴，吕映芝，蒋维杜，戴桂兰编 著，清华大学出版社，2005.2.
名称 编译原理 编译原理 编译原理
作者 何炎祥 陈火旺等 蒋立源
出版社 华中理工大学 国防工业出版社 西北工业大学

+ + > - > * > / > > ( < ) > i > # <
> > > > > < > > <
* < < > > > < > > <
/ < < > > > < > > <

< < < < < < > > <
( < < < < < <
) > > > > > = > >
<
i # < > < > < > < > < > < > > < =
规定 若 S a…或 S Ca… 则 # < a 若 S …a 或 S …aC 则 a > #
在 OG文法 G 中，若任意两个终结符间至多有 一种算符优先关系存在，则称G 为算符优先文 法(OPG)。 注意：允许b>c, c>b; 不允许 b>c, b<c, b=c中任两个 同时存在。 b=c 不一定 c = b。 例7.1中：“（” = “）”，“）”<>“（”。
最左素短语为：T*F
T
E + T
句型T+T+i的素短语为： i
句型T+T+F的素短语为：T+T
分析程序模型
输入串#
总控程序 # 算符优先关系表

第五章 自顶向下语法分析方法
学习目标: ➢掌握：LL(1)文法的判别，预测分析
法，递归子程序的构造方法 ➢理解：LL（1）文法 ➢了解：不确定的自顶向下分析
语法分析的作用是识别由词法分析给出的单词序 列是否是给定文法的正确句子
分类:
语法分析
自顶向下分析 自底向上分析
确定的
不确定的 算法优先分析（第六章）
进行推导，类似地LL(k)文法需要向前看K个符号才 可以确定选用哪个产生式。
例 有文法G[S]为：
S→aAS
SELECT(S→aAS)= {a}
S→b
SELECT(S→b)= {b}
A→bA
SELECT(A→bA)= {b}
A→ε
SELECT(A→ε)=Follow(A)= {a,b}
Hale Waihona Puke 由于SELECT(A→bA)∩SELECT(A→ε)={b}≠Φ，
此外若可能导出空串，A自动获得匹配，输入符a 有可能与A后的一个符号匹配，所以当a应属于 Follow(A)时，选择产生式A→也是可以的。
直观上说某产生式A→α的选择集合是指遇到哪些输 入符号（包括#）时选用该产生式向下推导。
例 G3[S]: 若α≠>*ε,则SELECT(A→α)=FIRST(α) S→aA 若α=>*ε, 则SELECT(A→α)
例文法G2[S]: S→Ap FIRST(Ap)={a,c}
S→Bq FIRST(Bq)={b,d}
A→a
FIRST(a)={a }
A→cA FIRST(cA)={c}
B→b
FIRST(b)={b}
B→dB FIRST(dB)={d}
由于同一非终结符的两个产生式的右部推导出来的 开始符号集不相交，因此可根据当前输入符属于哪 个产生式右部的开始符号集而决定选哪个产生式进 行推导，可以进行确定的自顶向下分析

文法：是语言语法的描述工具，实现用 有穷的规则把语言的无穷句子集描述出 来。
例:“我是大学生”是汉语的一个句子 用EBNF来表示汉语句子的构成规则： 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷= 我｜你｜他 〈名词〉∷= 王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷= 是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉
第三章
文法和语言
学习目标: 掌握：自上而下与自下而上的分析方法 理解：文法的形式定义，推导，归约，句 型，句子，语言，上下文无关文法，规范 句型，语法树，短语，直接短语，句柄 了解：文法的类型，文法使用中的限制， 文法的二义性
3.1 3.2 3.3 3.4 3.5 3.6 3.7
语言和文法的直观概念 符号和符号串 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 句型的分析 有关文法实用中的一些说明
文法类别产生式形式产生的语言说明0型文法短语文法v且至少含一个非终结符v0型语言对产生式基本无限制1型文法上下文有关文法1或avavnv1型语言上下文有关语言将a替换成时必须考虑a的上下文2型文法上下文无关文法aavnv2型语言上下文无关语言无需考虑a在上下文中的出现情况3型文法正规文法aab或aaabvnavt3型语言正规语言产生式全部是规定的形式四种文法之间的逐级包含关系2型文法1型文法3型文法0型文法35上下文无关文法及其语法树1
3.3 文法和语言的形式定义
1．文法的定义 2．文法的简化表示法 3．推导与归约 4．句型、句子、语言的定义 5．文法的等价
பைடு நூலகம்
1．文法的定义
产生式（规则） 产生式是一个有序对(α,β)，通常写作 α→β（或α::=β ） 文法定义: 文法G(Grammar)定义为四元组（VN，VT，P，S） VN (Nonternimal)：非终结符集 VT (Terminal)：终结符集 P (Production)： 产生式（规则）集合 S： 开始符号或识别符号

词法分析程序自动构造的典型过程
− 步骤二 自动构造工具将每一个正规表达式转 换成有限自动机的形式，比如使用 Thompson 构造法将正规表达式转换成 ε-NFA
词法分析程序的自动构造
《编译原理》
词法分析程序自动构造的典型过程
− 步骤三(可选) 增加一个新的开始状态，从该 状态引一条 ε-转移边到上述每一个 ε-NFA 的 初态，得到一个新的 ε-NFA
词法分析程序的自动构造
《编译原理》
词法分析程序自动构造的典行过程
− 步骤六 若执行过第3步，那么就模拟单个完整 的自动机；否则，自动构造工具按照一定的控 制策略生成词法分析程序中扫描程序的代码， 该扫描程序可以选择对每一类词法单元所对应 的有限自动机依次模拟运行，并从当前输入符 号序列中识别下一个单词，然后返回相应的单 词记录
词法分析程序的自动构造
《编译原理》
词法分析程序自动构造的典型过程
− 步骤四 必要时自动构造工具会将这些 ε-NFA 确定化，比如使用子集构造法得ຫໍສະໝຸດ DFA词法分析程序的自动构造
《编译原理》
词法分析程序自动构造的典型过程
− 步骤五 必要时，自动构造工具会将有限自动 机最小化，得到等价拥有状态数目最少的DFA
> > > > > >
词法分析程序的设计与实现 《编译原理》
实例: PL/0 语言词法分析程序的设计
− 词法分析子程序 getsym( )
从当前输入符号起扫描下一个词法单位，即单词 通过下列变量传递单词记号 public Symbol sym;
• 通过下列变量传递标识符单词的属性值
public String id; 通过下列变量传递常量单词的属性值 public int num;