编译工程

《编译工程》课程学习笔记。随课堂进度持续更新中,欢迎大佬指正错误 (๓´╰╯`๓)♡
注:“参考补充”一栏的主要参考资料为机械工业出版社的黑皮书系列《编译原理·第二版》(龙书)。该部分基于龙书对课堂所讲内容做补充,如果是为了考试可以不看。

第一第二周:引论与词法分析。对应龙书 Ch01 Ch03。
第三周:语法分析。对应龙书 Ch04。

小声 bb:Ch10-Ch12 正是精彩的地方,这门课却不讲,可惜啊 ๑•́₃•̀๑

划重点

子集构造法

Ch01 Intro

一个例子

前自增(++i)是先自增,然后将结果用于计算;后自增(i++)是先参与计算,再增加。后自增对应的汇编是 lea,使用寄存器保存自增前的值;而前自增 (i++) 对应的则是直接对内存进行加。
LEA: load effective address
LEA ESI, [EBX + 8*EAX + 4] ; will load the address in ESI.

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>

int main(){

int i = 3;

int sum;
sum = ++i + ++i + ++i + ++i;
printf("sum is %d.\n",sum);

}

对应的汇编代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
0000000000400526 <main>:
400526: 55 push %rbp
400527: 48 89 e5 mov %rsp,%rbp
40052a: 48 83 ec 10 sub $0x10,%rsp
40052e: c7 45 f8 03 00 00 00 movl $0x3,-0x8(%rbp) //i = 3
400535: 83 45 f8 01 addl $0x1,-0x8(%rbp) //i = 4
400539: 83 45 f8 01 addl $0x1,-0x8(%rbp) //i = 5
40053d: 8b 45 f8 mov -0x8(%rbp),%eax //%eax = 5
400540: 8d 14 00 lea (%rax,%rax,1),%edx //%edx = %eax+%eax*1 = 10
400543: 83 45 f8 01 addl $0x1,-0x8(%rbp) //i = 6
400547: 8b 45 f8 mov -0x8(%rbp),%eax //%eax = 6
40054a: 01 c2 add %eax,%edx //%edx += %eax = 16
40054c: 83 45 f8 01 addl $0x1,-0x8(%rbp) //i = 7
400550: 8b 45 f8 mov -0x8(%rbp),%eax //%eax = 7
400553: 01 d0 add %edx,%eax //%eax +=%edx = 23
400555: 89 45 fc mov %eax,-0x4(%rbp)
400558: 8b 45 fc mov -0x4(%rbp),%eax
40055b: 89 c6 mov %eax,%esi

这东西结果是啥主要还是看编译器想怎么算 QAQ……反正看汇编源码就是了。

编译器结构

部分参考龙书。

由两部分构成:分析部分和综合部分。

同时,编译器多个步骤可以组织为“一趟 (pass)”。例如,前端步骤中的词法分析、语法分析、语义分析,以及中间代码生成可以被组织在一起成为一趟。代码优化可作为可选的一趟。然后有一个为特定目标机生成代码的后端趟。

实例:一个赋值语句的翻译

  1. 词法分析
    生成 <token-name, attribute-value> 格式的词法单元 (token) 作为输出。其中,token-name 是由语法分析步骤使用的抽象符号,而 attribute-value 则指向符号表中该词法单元对应的条目(标号)。
    符号表条目信息会被语义分析和代码生成步骤使用。
    i.e. 代码中 position 被映射为词法单元 <id, 1>
  2. 语法分析
    构建语法树。内部节点表示一个运算,该节点的子节点表示该运算的分量。
    使用上下文无关文法来描述程序设计语言的语法结构。
    语法制导翻译:面向文法的编译技术。
  3. 语义分析
    3.1. 使用语法树和符号表中的信息来检查原程序是否和语言定义的语义一致;
    3.2. 收集类型信息,做类型检查和自动类型转换。类型检查:检查每个运算符是否具有匹配的运算分量,若使用错误的数据类型则报错;自动类型转换:例如 3.2 × 6,编译器会自动生成 inttofloat(6)。
  4. 中间代码生成
    语法树就是一种中间表示。
    三地址代码。
    程序设计语言构造:表达式、控制流构造、过程调用。
  5. 代码优化
    本质上是运行效率(或其他优化目标)和编译速度的 trade-off。
  6. 代码生成
    以中间表示形式作为输入,目标语言作为输出。
    运行时刻的存储组织方式依赖于被编译的语言。编译器在中间代码生成或代码生成阶段作出有关存储分配的决定。

Ch02 词法分析

正则表达式

问号 ? 代表其前面的字符最多可出现一次(0 次 or 1 次)

正则匹配之转换图 —> 最长匹配

有限自动机

NFA
DFA

NFA 到 DFA 的转换 —> 子集构造法

为什么要将 NFA 转换为 DFA?DFA 状态确定,便于写代码。
NFA 中允许空边的存在,而 DFA 不允许。

转换步骤:根据 NFA 图来绘制状态转换表,然后将状态转换表转化为状态机即可。

DFA 的最小化

将不可区分状态压缩成一个状态。

1
2
3
4
5
6
7
8
9
START     ("/*") // 双引号表示匹配
END ("*/")
COMMENT (.*) // 任意字符出现一次或多次

%%
{START}{COMMENT}{END} printf("multiline comment");
# return 0;
. ECHO;
%%

NFA DFA 的区别还是没太搞清楚。


Ch03 语法分析

上下文无关文法

产生式:左部 –> 右部。举例来说,语句 stmt –> if (expr) stmt else stmt

一个上下文无关文法 (context-free grammar) 由四个元素组成:

  1. 一个终结符集合,即词法单元。终结符是该文法所定义的语言的基本符号的集合;
  2. 一个非终结符集合,即语法变量。每个非终结符表示一个终结符的集合;
  3. 一个产生式集合,左部为非终结符,右部为终结符/非终结符;
  4. 指定一个非终结符作为开始符号。

i.e. stmt –> if (expr) stmt else stmt 中,if else 是终结符,stmt expr 是非终结符。

上下文无关文法 与 正则表达式 的相互转换。
生成语法树
四型文法(依次包含)


Reference

[ 1 ] The difference between NFA and DFA


参考补充

Ch01. Intro

语言处理器

编译器:阅读 A 语言(源语言)编写的程序,并把该程序翻译成为一个等价的、用 B 语言(目标语言)编写的程序。其重要任务之一是报告它在翻译过程中发现的源程序中的错误。
解释器:直接利用用户提供的输入执行员程序中指定的操作。

优缺点:在把用户输入映射成为输出的过程中,由编译器产生的机器语言目标程序比解释器快很多。但是,解释器的错误诊断效果更好,因为它逐个语句地执行源程序。

一个语言处理系统的示例如下图所示:

Ch02. 一个简单的语法制导翻译器

暂跳过。

Ch03. 词法分析

小拓展:何谓哨兵?