Compiler Implementation

Teacher: 刘忠鑫

研究方向：智能化软件开发

参考书

教材 - 虎书
工具书 - 龙书
……（反正我也不会看）

成绩构成

hw - 10%（十次）
quiz - 10%（四次）
期中 - 15%（第九周）
lab - 25%（五次）
期末 - 40%

实验要求

目标：SysY -> RISC-V 汇编
实验指导
实验框架
除 lab0 外需要实验报告，占 10%，验收和测试占 90%
Bonus（Bonus+实验+Quiz <= 35%）
- 优质测试用例
- 手写 Lexer & Parser
- 支持更多语言特性
- 编译优化

Chapter 1: Introduction

What - 编译器是把源程序转化为等价目标程序的程序
Why - ……
How - Techniques/Data Structures/Alogrithm

Modules & Interface

alt text

分成多个阶段的原因：易于实现+模块重用

每个阶段的具体作用

Lex - 将源程序的字符流转换为 token 流
Parse - 语法分析
Parsing Action - 为每个短语构造抽象语法树
Semantic Anaysis -语义分析，分析抽象语法树，如类型检测
Frame Layout - 把变量放到活动记录（栈帧）中
Translate - 产生 IR trees 的目标表示（解耦）
Canonicalize - 规范化，消除分支
Instruction Selection - 将 IR 树节点分组，与机器指令对应
Control Flow Analysis - 控制流分析
Dataflow Analysis - 数据流分析
Register Allocation - 寄存器分配（不同时活跃的变量可以使用同一个寄存器）
Code Emission - 把临时变量替换成真正的机器寄存器

简单寄存器可能没有 Control Flow Analysis、Dataflow Analysis、Register Allocation

Tools & Software

抽象化

Regular expressionsfor lexical analysis
Context-free grammarsfor parsing

Chapter 2: Lexical Analysis

编译过程：将源语言分解，理解结构和含义，再组合成目标语言（better use high-powered formalisms and tools）

front end - analysis

back end - synthesis

二者由 IR generation 分隔

2.1 Lexical Token

Lexical Analysis 将源程序的字符流转换为 token 流，忽略空格和注释

A lexical token - A sequence of characters & A unit in the grammar

类型有限，数量无限
类型 - A finite set of token types
- 保留字（不能作为标识符） e.g., IF, VOID, RETURN
non-tokens: 注释/预处理指令/宏/空格，制表符，换行符等
preprocessor - 把 non-token 替换掉，再把新的字符流给词法分析器

example

float match0(char* s)/* find a zero */
{ 
    if(!strncmp(s, "0.0", 3));
    return 0;
}

产生下面的 token：

alt text

括号中 - attached semantic values，辅助信息

需求

接受程序字符串
产生 token
忽略空格和注释

词法分析器的接口 - 一个函数 getToken, 被调用时返回下一个 token

实现

法一 - 根据需求手写
法二 - 利用正则表达式和 DFA（simpler and more readable）

2.2 Regular Expression

基本语法

语言 - 一个字符串的集合
字符串 - 一个 symbol 的有限序列
symbol - 从一个字母表中取得

每个正则表达式表示一个正则语言

正则表达式 a - 表示只含一个 a 的正则语言
\(\epsilon\) - 空字符，L(\(\epsilon\)) = {""}
M|N - L(M|N) = { s | s∊L(M) or s∊L(N) }
M*N - L(M · N) ={st | s∊L(M) and t∊L(N) }
M* - 0 个或多个 M 的串联

Example

(0|1)*0 - 能被 2 整除的所有二进制数

b(abb)*(a|ε) - 由 a 和 b 组成的没有连续的 a 的字符串

(a|b)aa(a|b) - 由 a 和 b 组成的有连续的 a 的字符串

扩展语法（不影响表达能力）

M? - M 出现 0 或 1 次
M+ - (M·M*)
[abcd] - (a|b|c|d)
[b-g] - [bcdefg]
[b-gM-Qkr] - [bcdefgMNOPQkr]
. - 除换行符外的所有字符
"a.+*" - 匹配本身，如小数点

用正则表达式表示 token： alt text

防止歧义

最长前缀匹配 - if8 返回 ID
优先级（比如 IF 比 ID 高，匹配 IF 后直接返回）- if 返回 IF

2.3 Finite Automata

正则表达式确定语法规范很方便，但需要用有限状态机变成电脑程序

有限状态机包括

有限个状态
上面有 label 的边（一个来自字母表的 symbol）
- 多个 label 是多条平行边的聚合
一个初始状态
一个或多个终止状态

alt text

合并

把每个终止状态用返回类型打上标签
合并状态中有一个是终止状态，合并后也是终止状态

alt text

表驱动的 DFA 实现

状态转移数组
找到最长匹配需要记录两个变量 - Last-Final（上一个终止状态的 state）和 Input-Position-at-Last-Final
进入 error 时回退到 Input-Position-at-Last-Final，返回 token 类型

alt text

2.4 NFA

alt text

正则表达式不好转换，先转换为 NFA

Recall: NFA 与 DFA 的区别（同一个输入可以有多条边，可以空字符转换）

RE -> NFA

正则表达式的抽象：RE M -> NFA with a tail(start edge) and head(ending state)
基本操作转化为 NFA
- Thompson’s Construction

alt text

NFA -> DFA：闭包

加速方法：先将所有可能的状态集合暴力搜索，再转换

ε-closure：closure(S) 表示状态 S 不消耗任何输入可以到达的所有状态的集合
- 算法：
- 单调有界，所以一定能终止
DFAedges：DFAedge(d,c) 表示 d 中的每一个状态，消耗 c 后可以到达的状态集合

状态等价：以其为起始状态的 DFA 能接收的字符串的集合一样
充分条件：
- 两个状态都是终止状态或非终止状态，且
- 对任意输入 c，trans[s1,c]=trans[s2,c]
Distinguishable state：等价状态的反面，输入同一个串，一个接收，一个不接收

DFA -> Minimal DFA

先分成终止状态和非终止状态两种（一个接受空串一个不接收）
遍历 symbol 作为一个组的输入，如果到达不同组的状态，划分成两个组
重复直到划分后的和划分前的分组一致

s1 和 s2 等价，化简方法：将所有指向 s2 的箭头指向 s1，删去 s2

区分接受 token 的类型时，把不同的 token 终止状态初始就划分开来

2.5 Lex

lexical-analyzer generator：自动把正则表达式翻译成 DFA

{ definitions  }
%%
{ rules }
%%
{ auxiliary routines}

%{
/* a Lex program that changes all numbers from decimal to hexadecimal 
notation, printing a summary statistic to stdeer
*/ 
#include <stdlib.h>
#include <stdio.h>
int count = 0;
%}
digit [0-9]
number {digit}+
%%
{ number } { int n = atoi (yytext);
            printf(“%x”, n);
            if (n > 9) count ++; }
%%
main( )
{ 
    yylex ( );
    fprintf(stdeer, “number of replacements = %d”, count);
    return 0;
}