Skip to main content

Compiler Basic Notes

Basic Concepts

Definition of compilers

  • program_code ---compiler---> executable
  • data ---executable---> output

e.g Fortran(formula translation) 1 project

Structure of compilers

front-end to back-end:

  • front-end: src ---lexical analysis---> tokens ---parsing/syntax analysis---> AST(Abstract Syntax Tree) ---semantic analysis---> intermediate
  • back-end: intermediate ---...---> ... ---...---> ... ---code generation---> dist

details:

  • lexical analysis(词法分析)
  • parsing/syntax analysis(语法分析)
  • semantic analysis(语义分析): type and scope
  • optimization
  • code generation: translate to other high level language/assembly code/machine code

文法与语言

符号与符号串

  • 字母表/符号集: 元素的非空有穷集合
  • 符号串: 字母表中的符号组成的任何有穷序列
  • 固有头/尾: 非空首/尾子串
  • 闭包: Σ* = Σ0 U Σ1 U ... U Σn ....
  • 正闭包: Σ* = Σ1 U ... U Σn ....

文法与语言的形式化表示

  • 文法 (Grammar): G = (Vn, Vt, P, S), 非终结符集, 终结符集, 规则/产生式集, 开始符号.
  • 语言 (Language): L(G) = {x | S -> x, x <- Vt} 文法 G 一切句子的集合.
  • 句型: rhs of P, 句子: 不含非终结符的右部
  • 直接推导: v -> w, 闭包推导: v -*> w, 正闭包推导: v -+> w.

乔姆斯基文法体系

  • ((((3)2)1)0)
  • 0 型文法: 任意文法
  • 1 型文法: 上下文有关文法(context sensitive) αAβ -> αηβ
  • 2 型文法(语法工具): 上下文无关文法 A -> α
  • 3 型文法(词法工具): 正规文法

上下文无关文法

文法表示

G = (S, N, T, P):

  • S: 开始符
  • N: 非终结符集合
  • T: 终结符集合
  • P: 产生式规则集合 X -> beta1, beta2, ..., betaN, X <- N, beta <- N+T

形式化表示

简易表示
Sentence -> Noun Verb Noun
Noun -> sheep
| tiger
| grass
| water
Verb -> eat
| drink

S: Sentence, N: Sentence/Verb/Noun, T: sheep/tiger/grass/water/eat/drink

E -> num
|id
|E + E
|E `*` E

S: E, N: E, T: num/id/+/*.

巴科斯范式

Backus-Naur Form:

  • ::=: 被定义为.
  • word: 字符本身.
  • 双引号外的字: 语法部分.
  • 尖括号(< >): 必选项(非终结符).
  • 方括号([ ]) : 0/1.
  • 大括号({ }) : 0/n.
  • 竖线(|) : OR.

正规文法

正规文法可与正则语言相互转化:

  • A -> aB|Ba
  • A -> a

正则语言(Regular Expressions)

基本定义

对于给定的字符集 C:

  • 空串 "\0" 是正则表达式.
  • 任意 char <- C 是正则表达式.
  • M, N 是正则表达式, 则 M|N = {M, N}, MN = {mn|m <- M, n <- N}, M* = {"\0", M, MM, MMM, ...} (选择/连接/闭包) 也是正则表达式.

形式表示

# 具有顺序性
e -> "\0" # basic definition
| c # basic definition
| e | e # recursive definition
| ee # recursive definition
| e* # recursive definition

正则语法糖(Syntax Sugar)

  • [a-z] : a|...|z
  • c? : 0/1 个 c
  • c+ : 1/n 个 c
  • c{i, j} : i-j 个 c
  • "a*" : a* 自身(非 Kleene Closure)
  • . : 除 ‘\n’ 外的任意字符
// 标识符
const identifier = /[a-z_]\w*/gi

// decimal integer
const integer = /(\+|-)?(0|[1-9]\d*)/g

// decimal float
const float = /(\+|-)?(0|[1-9]\d*)?\.\d+/g

分析树

进行文法推导时生成的树:

  • 根 : 开始符
  • 内部结点 : 非终结符
  • 叶子结点 : 终结符
  • 层 : 一步推导(优先级影响推导顺序)
  • 叶子结点串: 最终表达式
  • 后序遍历 : 最终结果

推导类型

  • 最左推导(leftmost)
  • 最右推导(rightmost)(规范推导)

句型分析

  • 短语: 若 S -*> Aβ, A -+> α, 则称 α 是句型 αβ 相对于非终结符 A 的短语
  • 直接短语: S -*> Aβ, A -> α.
  • 一个右句型的直接短语称为该句型的句柄(用于自下而上的归约分析)
  • 最左归约: 归约最左的句柄, 最右归约: 归约最右的句柄

meaning function(多对一)

L(syntax) = semantic: 多个语法对应一个语义(不同形式的表达式对应同一个意思)

二义性文法(一对多)

  • 最左推导与最右推导得出的分析树不一致
  • 若给定文法 G, 对于句子 s, 其有 2 种不同的分析树, 则称 G 是二义性文法
  • 若一个上下文无关语言的所有文法都是二义性文法, 则称此语言是先天二义语言
文法重写
E -> E + T
|T
T -> T * F
|F
F -> num
|id

消除 + 与 * 的二义性, 如 3+4*5

优先级与结合性

声明优先级与结合性可在一定程度上消除文法的二义性

文法规则

  • 有害规则: 使文法产生二义性的规则
  • 多余规则: 不可达/不可终止的规则
  • 2 型文法的 ε 规则: 当语言中不含有 ε 符号串, 则一定存在终结符集不含有 ε 的等价文法(代入法消除 ε)
  • 保证非终结符 A 的有效性: S -*> αAβ, A -+> t.

Lexical Analysis

Tokenizer - 词法分析器

  • Maximal match
  • Higher priority match

转移图算法

token nextToken(void) {
char c = getChar();
switch(c) {
case '<':
c = getChar();
switch (c) {
case '=':
return LE;
case '>':
return NE;
default:
rollback();
return LT;
}

case '=':
return EQ;
case '>':
c = getChar();
switch (c) {
case '=':
return GE;
case '<':
return NE;
default:
rollback();
return GT;
}
}
}

关键字(keyword)处理

  • 根据 完美哈希算法(无冲突哈希函数) , 建立所有关键字对应的关键字完美哈希表
  • 读入有效标识符(字符串型)后, 查询关键字哈希表, 检查当前标识符是否为关键字
#define KEYWORD_MAX_LEN 10

hash_one(char *str, int len) {
unsigned int keyValue = 0;

for (int i = 0; i < len; i++) {
keyValue += str[i] * ((int)pow(33, len - i));
}

keyValue = (keyValue * 3 + 7) % KEYWORD_MAX_LEN;
return keyValue;
}
#define KEYWORD_HASH_SEED 131

hash_two(char *str, int len) {
unsigned int keyValue = 0,
hash = 0;

for (int i = 0; i < len; i++) {
hash = hash * KEYWORD_HASH_SEED + str[i];
}

keyValue = hash & 0x7fffffff;
return keyValue;
}

有限状态自动机(Finite Automaton)

确定有限状态自动机(Deterministic Finite Automaton)

  • Only a transition for a state with a input
  • No epsilon moves

M = (AlphaSet/InputSet, StateSet, currentState, FiniteStateSet, transferFunction)

A = {a, b}, SS = {0, 1, 2}, cS = 0, FS = {2},
transferFunction = {
(cS0, a) -> cS1, (cS0, b) -> cS0,
(cS1, a) -> cS2, (cS1, b) -> cS1,
(cS2, a) -> cS2, (cS2, b) -> cS2,
}
状态转移表实现 DFA
状态\字符ab
010
121
222

非确定有限状态自动机(Nondeterministic Finite Automaton)

transferFunction 中的次态不确定/不唯一(为一个开集合):

  • Multiple transitions for a state with a input
  • can epsilon moves

(cS0, a) -> {cS1, cS2}

自动词法分析器

RegExp --Thompson 算法--> NFA --子集构造算法--> DFA --Hopcroft 最小化算法--> 词法分析器代码

Thompson 算法

RegExp --> NFA:

  • 直接构造基本 RegExp
  • 递归构造复合 RegExp
  • epsilon : i --epsilon--> f
  • RegExp : i --NFA(RegExp)--> f
  • 选择 : i --NFA(RegExp1)--> f, i --NFA(RegExp2)--> f
  • 连接 : i --NFA(RegExp1)--> m --NFA(RegExp2)--> f
  • 闭包 : i --epsilon--> m --epsilon--> f, m --RegExp--> m

子集构造算法

NFA --> DFA:

由 Thompson 算法生成的 NFA, 当且仅当输入为 epsilon 时, 次态不唯一

  • 将所有可达到次态作为一个集合 s, 视为单一次态 s
  • delta(Sigma) + epsilon-closure(深度/广度优先遍历找寻可达到次态边界)
DFA subset_construction(NFA nfa) {
s0 = eps_closure(n0);

StateSet += s0;
enqueue(s0);

while (work_queue != []) {
dequeue(s);

foreach (ch in InputSet) {
next_state = eps_closure(delta(s, ch));
Fn[s, ch] = next_state; // DFA 中的转移函数

if (next_state not in StateSet) {
StateSet += next_state;
enqueue(next_state);
}
}
}

return DFA(StateSet, Fn);
}

Hopcroft 算法

最小化 DFA(数字逻辑中的最简状态表), 合并等价状态(等价类)

split(StateSet S) {
foreach (char ch) {
if (ch can split S) {
split S into S1, ..., Sk;
}
}
}

hopcroft(DFA) {
split all nodes into InitStateSet and FiniteStateSet (Two State Sets);

while (set is still changes) {
split(S);
}
}

实现

DFA
有向图
转移表
  • 行: 现态
  • 列: 输入
  • 值: 次态/ERROR/-1

驱动代码: table 用于实现 switch/case, stack 用于实现最长匹配

next_token() {
state = 0;
stack = [];

while (state != ERROR) {
c = getChar();

if (state is ACCEPT/FINITE) {
clear(stack);
}

push(state);
state = table[state][c];
}

while (state is not ACCEPT/FINITE) {
state = pop();
rollback();
}
}

Syntax Analysis(语法分析)

Tokens + Grammar --Syntax Analysis--> AST(Abstract Syntax Tree)

自顶向下分析

  • 从开始符号出发推导任意句子 t, 与给定句子 s 进行比较分析
  • 利用分析树进行逐叶子匹配, 若匹配失败则进行回溯
bool top_down_parsing(tokens[]) {
i = 0;
stack = [S];

while (stack != []) {
if (stack[top] is a terminal t) {
t == tokens[i] ? pop(i++) : backtrack();
} else if (stack[top] is a non_terminal T) {
pop();
push(T next expansion); // 自右向左压栈, e.g pop(S), push(N_right), push(V), push(N_left)
} else {
throw new SyntaxError();
}
}

return i >= tokens.length && is_empty(stack) ? true : false;
}

避免回溯

利用前看符号避免回溯

Sentence -> Noun Verb Noun
Noun -> sheep
| tiger
| grass
| water
Verb -> eat
| drink

tiger eat water: 向前看非终结符推导出的所有终结符中匹配 tiger 的终结符; 不向前看,则先推导 N, 再推导 n, 但 n 不一定匹配 tiger, 则需进行回溯; 向前看一个字符, 直接推导 N --> n, 同时直接找寻匹配 tiger 的终结符

S -> N V N
N -> (sheep)tiger
V -> eat
N -> (sheep-tiger-grass)water

递归下降分析算法(Recursive Descent/预测分析算法)

  • 分治算法: 每个非终结符构造一个分析函数
  • 前看符号: 用前看符号指导产生式规则的选择(expansion)
parse_S(tokens[]) {
parse_N(tokens[0]);
parse_V(tokens[1]);
parse_N(tokens[2]);
}

parse_N(token) {
if (token == s|t|g|w) {
return true;
} else {
throw new SyntaxError();
}
}

parse_V(token) {
if (token == e|d) {
return true;
} else {
throw new SyntaxError();
}
}
算法实现
  • tip one: use save pointer to implement roll back
  • tip two: use logical OR expression to replace nested if-else structure
bool term(TOKEN tok) {
return *next++ == tok;
}

bool E1(void) {
return T();
}

bool E2(void) {
return T()
&& term(PLUS)
&& E();
}

bool E(void) {
// roll back pointer
TOKEN *save = next;

return (next = save, E1())
|| (next = save, E2());
}

bool T1(void) {
return term(INT);
}

bool T2(void) {
return term(INT)
&& term(TIMES)
&& T();
}

bool T3(void) {
return term(OPEN)
&& E()
&& term(CLOSE);
}

bool T(void) {
// roll back pointer
TOKEN *save = next;

return (next = save, T1())
|| (next = save, T2())
|| (next = save, T3());
}
// X -> a
// | XX
// | aXXX
// | aXXXXb
parse_X() {
token = nextToken();

switch (token) {
case ...: // i: token == atom_char or parse_XX();
case ...: // j: token == atom_char, token = nextToken(), parse_XXX();
// k: token == atom_char, token = nextToken(),
// parse_XXXX(), token=nextToken(), token == b
case ...:
default: throw new SyntaxError();
}
}

LL(1)分析算法

  • 从左(L)向右读入程序(left to right scan)
  • 最左(L)推导: 优先推导最左侧非终结符(leftmost derivation)
  • 一个(1)前看符号(look ahead)
  • 分治算法: 每个非终结符构造一个first set 和一个 follow set, 最后为每个规则构造一个 select set
  • 分析表驱动(由 first sets/follow sets/select sets 推导分析表)
bool ll1_parsing(tokens[]) {
i = 0;
stack = [S];

while (stack != []) {
if (stack[top] is a terminal t) {
t == tokens[i] ? pop(i++) : throw new SyntaxError();
} else if (stack[top] is a non_terminal T) {
pop();
// push(T correct expansion);
// 自右向左压栈, e.g pop(S), push(N_right), push(V), push(N_left)
push(select_table[T][tokens[i]] 对应项(规则编号)所对应规则的右边式子);
} else {
throw new SyntaxError();
}
}

return i >= tokens.length && is_empty(stack) ? true : false;
}
nullable sets
  • 存在规则: X -> epsilon.
  • 或者: X -> Y1Y2...Yn, 且存在规则 Y1 -> epsilon, ..., Yn -> epsilon.
  • 即 : X -*> epsilon (epsilon <- first(X)).
nullable = {};

while (nullable is still changing) {
foreach (production p: X -> beta) {
if ((beta == epsilon) || (beta == Y1...Yn
&& Y1 <- nullable && ... && Yn <- nullable)) {
nullable += X;
}
}
}
first sets

first(X) = {t | X -_> talpha} U {epsilon | X-_>epsilon} :

  • first(t) = {t}
  • epsilon <- first(X): X -> epsilon or X -> A1...An, epsilon <- first(Ai)
  • first(alpha) <- first(X): X -> A1..Analpha, epsilon <- first(Ai)

first sets 不动点算法:

foreach (non_terminal N) {
first(N) = {};
}

while (some sets is changing) {
foreach (production p: N->beta1...beta_n) {
foreach (beta_i from beta1 up to beta_n) {
if (beta_i == a) {
// e.g N->abX: first(N) += {a}
first(N) += {a};
break;
} else if (beta_i == M) {
first(N) += first(M);
if (M is not in nullable) {
break;
} // else continue this loop to add first(beta_next) into first(N)
}
}
}
}
NonTerminalFirst Set
S{s, t, g, w}
N{s, t, g, w}
V{e, d}
follow sets

follow(X) = {t | S -*> beta X t epsilon}:

  • for X -> AB:
    • first(B) <- follow(A), follow(X) <- follow(B).
    • if B -*> epsilon: follow(X) <- follow(A).
  • for A -> alpha X beta: first(beta) - {epsilon} <- follow(X).
  • $ <- follow(S).

follow sets 不动点算法:

foreach (non_terminal N) {
follow(N) = {};
}

while (some sets is changing) {
foreach (production p: N->beta1...beta_n) {

// temp: follow(left) <- follow(right)
temp = follow(N);

foreach (beta_i from beta_n down to beta1) {
if (beta_i == a) {
temp = {a};
} else if (beta_i == M) {
follow(M) += temp
temp = (M is not nullable) ? (first(M)) : (temp + first(M))
}
}
}
}
select sets
  • 当 N -> Y1...Yn 右边 Y 全为 nullable 时, select(p) += follow(N)

select sets 不动点算法:

foreach (production p) {
select(p) = {}
}

calculate_select_set(production p: N->beta1...beta_n) {
foreach (beta_i from beta1 up to beta_n) {
if (beta_i == a) {
select(p) += {a};
break;
} else if (beta_i == M) {
select(p) += first(M);
if (M is not in nullable) {
break;
}
}
}

// all betas are in nullable (当前规则的所有右边符号都是可空集)
// 故, select(p) 必须包括 follow(M) (当推导出右边符号都为空时, first(p) 即为 follow(M))
if (i > n) {
first(N) += follow(N);
}
}
分析表
  • 结合 nullable sets 准确求出 first sets
  • 再利用 first sets 准确求出 follow sets
  • 再利用 first sets, 并结合 follow sets(全空集修正) 准确求出 分析表:
0: z -> d
1: | X Y Z
2: Y -> c
3: |
4: X -> Y
5: | a

nullable = {X, Y}

XYZ
first{a, c}{c}{a, c, d}
follow{a, c, d}{a, c, d}{}
production012345
select{d}{a, c, d}{c}{a, c, d}{a, c, d}{a}
Non-Terminalacd
Z110, 1
Y32, 33
X4, 544

数字为规则编号

解决冲突(分析表某项有多个编号)

通过文法重写消除左递归, 使文法适应 L(最左推导):

  • 改写成右递归文法
  • 规定优先级与结合性
  • 提取左公因式(Common Prefix)
E -> T+E
|T

E -> TX
X -> +E
|epsilon
消除直接左递归
S -> Salpha1
|Salpha2
...
|Salpha_n
|beta1
|beta2
...
|beta_m

S -> beta1S'
|beta2S'
...
|beta_nS'
S'-> alpha1S'
|alpha2S'
...
|alpha_nS'
|epsilon
消除间接左递归
  • 把文法 G 的所有非终结符按任一顺序排列, e.g A1, A2, …, An
  • 消除 Ai 规则中的直接左递归: 把形如 Ai→Ajγ 的产生式 改写成 Ai→δ1γ /δ2γ /…/δkγ(其中 Aj→δ1 /δ2 /…/δk 是关于的 Aj 全部规则)
  • 去掉多余的规则(不可达规则)
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

struct WF {
string left; //定义产生式的左部
string right; //定义产生式的右部
};

/*
* count: number of non-terminal symbols
*/
void Removing(WF *p,char *q,int n,int count) {

int count1 = n;
int flag = 0;

// 判断第一个非终结符是否存在直接左递归 if(p[i].left[0]==q[0])
for (int i = 0; i < n; i++) {
if (p[i].left[0] == p[i].right[0]) {
flag++;
}
}

// 如果存在直接左递归则消除直接左递归
if (flag != 0)
{
for (int i = 0; i < n; i++) {
if (p[i].left[0] == q[0]) {
if (p[i].left[0] == p[i].right[0]) {
string str;
str = p[i].right.substr(1,int (p[i].right.length())); // 取右部第二位开始的字串赋给str

// E->E+T => E'->+TE'
string temp = p[i].left;
string temp1 = "'";
p[i].left = temp+temp1;
p[i].right = str+p[i].left;
} else {
// E->T => E->TE'
string temp=p[i].left;
string temp1="'";
temp=temp+temp1;
p[i].right=p[i].right+temp;
}
}
}

string str="'";
p[count1].left=p[0].left[0]+str;
p[count1].right="ε";
}

// 对每一个非终结符迭代
for ( int i = 0; i <= count; i++) {

// 对每一个小于 i 的非终结符
for (int j = 0; j < i; j++) {

// 对每一个产生式
for (int g = 0; g < n; g++) {

// i 非终结符与第 g 产生式左边第一个字母相等
if (q[i] == p[g].left[0]) {

// g 产生式右边产生式第一个符号与第 j 个非终结符相等
if (p[g].right[0] == q[j]) {
for (int h = 0; h < n*n; h++) {
if (p[h].left[0] == q[j]
&& int (p[h].left.length()) == 1) {
string str;
str = p[g].right.substr(
1,
int (p[g].right.length ()));
p[++count1].left = p[g].left;
p[count1].right = p[h].right + str;
}
}

p[g].left="";
p[g].right="";
}
}
}
}
}

// 去除间接递归产生式
for(int i = 0; i <= count; i++) {
flag = 0;

for (int j = 0; j < n*n; j++) {
if (p[j].left[0] == q[i]) {
if(p[j].left[0] == p[j].right[0]) {
flag++;
}
}
}

if (flag != 0) {
for (int j = 0; j <= n*n; j++) {
if (p[j].left[0] == q[i]) {
if (p[j].left[0] == p[j].right[0]) {
string str;
str = p[j].right.substr(1,int (p[j].right.length()));
string temp = p[j].left;
string temp1 = "'";
p[j].left = temp + temp1;
p[j].right = str + p[j].left;
} else {
string temp = p[j].left;
string temp1 = "'";
temp = temp + temp1;
p[j].right = p[j].right + temp;
}
}
}

string str = "'";
p[++count1].left = q[i] + str;
p[count1].right = "ε";
}
}
}

int Delete(WF *p,int n) {
return 0;
}

int main() {
ofstream OutFile("result.txt");

int i,
j,
flag = 0,
count = 1,
n;

cout<<"请输入文法产生式个数n:"<<endl;
cin>>n;
WF *p=new WF[50];
cout<<"请输入文法的个产生式:"<<endl;

// input productions
for (i = 0; i < n; i++) {
cin>>p[i].left;
cout<<"->"<<endl;
cin>>p[i].right;
cout<<endl;
}
cout<<endl;
OutFile<<"即输入的文法产生式为:"<<endl;

// cout<<"即输入的文法产生式为:"<<endl;
for (i = 0; i < n; i++) {
// cout<<p[i].left<<"-->"<<p[i].right<<endl;
OutFile<<p[i].left<<"-->"<<p[i].right<<endl;
}
OutFile<<"*********************"<<endl;

// cout<<"*********************"<<endl;
char q[20]; // 对产生式的非终结符排序并存取在字符数组q
q[0] = p[0].left[0]; // 把产生式的第一个非终结符存入q中

// 对非终结符排序并存取
for (i = 1; i < n; i++) {
flag = 0;
for (j = 0; j < i; j++) {
// 根据j<i循环避免重复非终结符因此由标志位判断
if(p[i].left==p[j].left) {
flag++;
}
}

if(flag==0) {
// 没有重复加入q数组中
q[count++]=p[i].left[0];
}
}
count--;

// 调用消除递归子函数
Removing(p,q,n,count);
// 删除无用产生式
Delete(p,n);

OutFile<<"消除递归后的文法产生式为:"<<endl;
// cout<<"消除递归后的文法产生式为:"<<endl;
for (i = 0; i <= count; i++) {
for (int j = 0; j <= n*n; j++) {
if ((p[j].left[0] == q[i]) && int (p[j].left.length ()) == 1) {
OutFile<<p[j].left<<"-->"<<p[j].right<<endl;
// cout<<p[j].left<<"-->"<<p[j].right<<endl;
} else {
continue;
}
}

for (j = 0; j <= n*n; j++) {
if((p[j].left[0] == q[i]) && int (p[j].left.length ()) == 2) {
OutFile<<p[j].left<<"-->"<<p [j].right<<endl;
// cout<<p[j].left<<"-->"<<p[j].right<<endl;
} else {
continue;
}
}
}
return 0;
}
非 LL(1) 文法/语言
  • ambiguous grammar
  • left recursive grammar
  • not left factored grammar(未提取展开式的公因子)

自底向上分析

0: S -> E
1: E -> E + T
2: | T
3: T -> T * F
4: | F
5: F -> n
2 + 3 * 4
=> F + 3 * 4
=> T + 3 * 4
=> E + 3 * 4
=> E + T * 4
=> E + T * F
=> E + T
=> E
=> S

最右推导(优先推导最右侧非终结符)逆过程

LR(0) 分析算法

移进-归约 (Reduce) 算法:

  • 从左向右读入程序 (left to right scan), 逆向最右推导 (rightmost derivation), 不用前看符号.
  • 添加伪开始符号: S' -> . S$, $ 表示 tokens/file 结束符.
  • 移进 : 读入记号 push(token[i]).
  • 归约 (Reduce): pop(right expansion) push(left expansion).
短语

Handles:

S -*> αXω -> αβω

β 是 αβω 的一个短语 (Handle).

分析表构造

LR(0) 分析表构造算法: (原理同于 Hopcroft 算法)

  • E -> A, A -> B, B -> C ... : Recursively, right hand side of C production will be reduced to E finally
closure(production_set p) {
while (p is still changing) {
foreach (p's item i: A -> b . B ...) {
p += {B -> . y...}
}
}
}

goto(production_set p, token x) {
temp = {}

foreach (p's item i: A -> b . x...) {
temp += {A -> bx . ...}
}

return closure(temp)
}
p0 = closure(S'' -> . S $)
(production_with_dot_)set = {p0}
Q = enqueue(p0)

while (Q is not empty) {
p = dequeue(Q)

foreach (x <- NonTerminal||Terminal) {
q = goto(p, x)

if (x <- Terminal) {
ACTION[p, x] = q
} else {
GOTO[p, x] = q
}

if (q not <- set) {
set += {q}
enqueue(q)
}
}
}
驱动代码

LR(0) 驱动算法:

stack[];
push($)
push(state1)

while (true) {
token t = nextToken()
state s = stack[top]

if (ACTION[s, t] == shift_i) {
push(t)
push(state_i)
} else if (ACTION[s, t] == reduce_j) {
// X is the left side of production j: X->beta
// beta is the right side of production j: X->beta

// pop up right side
pop(beta && bundle state variables)

// current state after pop up all bundle state(of beta)
state s = stack[top]

// push left side
push(X)

// transfer state after reduce
push(GOTO[s, X])
} else {
throw new SyntaxError();
}
}
解决冲突

SLR, LR(1), LALR, 采取与 first/follow/select sets 以及 前看符号 类似策略:

  • production_with_dot_set 中的 item 修改为 X -> [beta1 . beta_n..., a] 二元组
  • closure(production_set p) 中闭包规则从 X -> [a . Y beta,a] 修改为 Y -> [.y, b] b <- select(beta a)

LALR-K

LALR(k)

SLR

Simple LR: improves LR(k) shift/reduce heuristic

New reduce rule:

  • state contains item X -> β.
  • next_token <- follow(X)
SLR 实现
  • stack pair: <input, state>
  • state i: if has item X -> α.aβ , goto[i, a] = j then action[i, a] = shift j(shift then to state j)
  • state i: if has item X -> α. , a <- follow(X) then action[i, a] = reduce(X -> α)
  • state i: if has item S' -> S then action[i, $] = accept
  • otherwise: action[i, a] = error

抽象语法树

语法制导翻译(Syntax-Directed Translation)

在进行归约(reduce)的同时, 进行语义动作:

  • 给每条产生规则附加一个语义动作
exp : exp '+' exp { $$ = $1 + $3; }
;
  • 在分析栈中压入 symbol, value, state (原本只压入 symbol, state)
push(right side symbol);
push(right side value);
push(next state);

抽象语法

  • 表达语法结构的内部表示, 作为前端(词法语法分析)和后端(代码生成)的中间件, tokens --语法分析器--> 抽象语法(树) --代码生成器--> 目标代码
  • 抽象语法无需考虑左/右递归, 左公因子提取, 分隔符等
// 具体语法
E: E + T
| T
;
T: T * F
| F
;
F: n
| (E)
;

// 抽象语法
E: n
| E + E
| E * E

AST 的实现

数据结构
E: n
| E + E
| E * E
enum kind {
E_INT,
E_ADD,
E_TIMES
};

struct exp {
enum kind kind;
};

struct exp_int {
enum kind kind;
int value;
};

struct exp_add {
enum kind kind;
struct exp *left;
struct exp *right;
};

struct exp_times {
enum kind kind;
struct exp *left;
struct exp *right;
};

struct exp_int *new_exp_int(int value) {
struct exp_int *p = (struct exp_int *)malloc(sizeof(struct exp_int));
if (!p) throw new Error();
p->kind = E_INT;
p->value = value;
return p;
}

struct exp_add *new_exp_add(exp *left, exp *right) {
struct exp_add *p = (struct exp_add *)malloc(sizeof(struct exp_add));
if (!p) throw new Error();
p->kind = E_ADD;
p->left = left;
p->right = right;
return p;
}

struct exp_times *new_exp_times(exp *left, exp *right) {
struct exp_times *p = (struct exp_times *)malloc(sizeof(struct exp_times));
if (!p) throw new Error();
p->kind = E_TIMES;
p->left = left;
p->right = right;
return p;
}
相关算法
int nodes_num(exp *e) {
switch (e->kind) {
case E_INT:
return 1;
case E_ADD: // fall through
case E_TIMES:
return 1 + nodes_num(e->left) + nodes_num(e->right);
default:
throw new SyntaxError("compile bug");
}
}
int pretty_print(exp *e) {
switch (e->kind) {
case E_INT:
printf("%d", e->value);
return 1;
case E_ADD:
printf("(");
pretty_print(e->left);
printf(")");
printf("+");
printf("(");
pretty_print(e->right);
printf(")");
return 1;
case E_TIMES:
printf("(");
pretty_print(e->left);
printf(")");
printf("*");
printf("(");
pretty_print(e->right);
printf(")");
return 1;
default:
throw new SyntaxError();
break;
}
}
构造算法

利用语法制导翻译, 在语法动作(action)/语法归约(reduce)中加入生成语法树的代码(自底(叶子)向上(根)构造函数)

E: E + E { $$ = new_exp_add($1, $3); }
| E * E { $$ = new_exp_times($1, $3); }
| n { $$ = new_exp_int($1); }
;

Semantic Analysis(语义分析)

  • 声明检查(identifiers declaration)
  • 定义检查:
    • class 仅可定义一次
    • method 在同一 class 中仅可定义一次
  • 类型检查(types)
  • 作用域检查
  • 继承关系(inheritance relationships)
  • 上下文相关分析(检查抽象语法树上下文相关的属性)

AST + semantic of programming language --semantic analysis--> intermediate

e.g 变量/函数必须先声明再使用; 每个表达式必须有合适类型(左值/右值); 函数调用与函数定义保持一致(函数签名)

P: D S
;

D: T id ';' D
|
;

T: int
| bool
;

S: id = E
| printi (E)
| printb (E)
;

E: n
| id
| true
| false
| E + E
| E && E
;

类型系统(type system)

Type Checking

├ e: T meas e 可计算为类型为 T 的值

Type Environments

  • Object(identifier) = Type
  • O Type environments 是一个函数, 将 object identifiers 映射成 types
  • O ├ e: T 表示在 O 函数作用下, 可证明 e 的类型为 T
// input x
// output T
O[T/x](x) = T

O[T/x](y) = O(y)
[Var]
O(x) = T
----------
O ├ x: T

[Let without Init]
O[T0/x] ├ e1: T1
--------------------
O ├ let x: T0 in e1: T1

Typing Methods

  • Method(ClassName, functionName) = (Type1, ..., Type_n, Type_n+1)
  • Type_n+1 为返回值的类型, 即方法自身的类型
[Dispatch]
O,M ├ e0: T0
O,M ├ e1: T1
...
O,M ├ en: Tn
M(T0, func) = (T1', ..., Tn', Tn+1')
Ti <= Ti'
----------
O,M ├ e0.func(e1, ..., en): Tn+1'

符号表(上下文相关)

用来存储程序中变量的相关信息:

  • 类型: 字典结构 (key, type)
  • 作用域:
    • 进入作用域, 插入元素(插入哈希表首, 屏蔽外部同名变量); 离开作用域, 删除元素
    • 进入作用域, 压入新符号表; 离开作用域, 弹出栈顶符号表
  • 访问控制权
  • 命名空间: 变量, 标签, 形参, 标号 各自拥有一类符号表

可将符号表实现为:

  • 哈希表: 查找时间复杂度 O(1);
  • 红黑树: 查找时间复杂度 O(lg N);
#ifndef XX_SEMANTIC_TABLE_H
#define XX_SEMANTIC_TABLE_H

typedef enum type type_t;
typedef char * key_t; // typedef int hash_t; typedef hash_t key_t;
typedef struct value {
type_t type;
scope_t scope;
} value_t;

typedef ... table_t;// 符号表数据结构

table_t new_table(void);
int table_insert(table_t table, key_t id, value_t info);
value_t table_search(table_t table, key_t id);

#endif

类型检查

  • table: 字典结构 (key, type) (Hash Table/Red Black Tree)
  • type environment(Object, Methods, Class) is passed from parent to child(down the tree)
  • types are passed from child to parent(up the tree)
TypeCheck(Environment/OMC, e1+e2) = {
T1 = TypeCheck(OMC, e1);
T2 = TypeCheck(OMC, e2);
Check T1 == T2 == Int;
return Int;
}

TypeCheck(OMC, let x: T <- e0 in e1) = {
T0 = TypeCheck(OMC, e0);
T1 = TypeCheck(OMC.add(O(x)=T), e1);
Check subtype(T0, T1); // T0 <= T1
return T1;
}
enum type {INT, BOOL};
table_t table;// symbol table

// dec_t, stm_t, exp_t: AST 中的结点

enum type check_prog(dec_t d, stm_t s) {
// 生成符号表
table = check_dec(d);
// 根据符号表检查语句
return check_stm(s);
}

// 生成符号表
table_t check_dec(dec_t d){
foreach(T id <- d) {
table_insert(table, id, T);
}
}

enum type check_stm(table_t table, stm_t s) {
switch (s->kind) {
case STM_ASSIGN:
t1 = table_search(table, id);
t2 = check_exp(table, s->exp);
if (t1 != t2) {
throw new SemanticError("type mismatch");
} else {
return t1;
}
case STM_PRINTI:
t = check_exp(s->exp);
if (t != INT) {
throw new SemanticError("type mismatch");
} else {
return INT;
}
case STM_PRINTB:
t = check_exp(s->exp);
if (t != BOOL) {
throw new SemanticError("type mismatch");
} else {
return BOOL;
}
}
}

enum type check_exp(exp_t e) {
switch (e->kind) {
case EXP_INT:
return INT;
case EXP_ID:
t = table_search(table, id);// 查询符号表, 得到变量类型
if (id not exist) {
throw new SemanticError("id not found");
} else {
return t;
}
case EXP_TRUE:
return BOOL;
case EXP_FALSE:
return BOOL;
case EXP_ADD:
enum type t1 = check_exp_type(e->left);
enum type t2 = check_exp_type(e->right);
if (t1 != INT || t2 != INT) {
throw new SemanticError();
break;
} else {
return INT;
}
case EXP_AND:
enum type t1 = check_exp_type(e->left);
enum type t2 = check_exp_type(e->right);
if (t1 != BOOL || t2 != BOOL) {
throw new SemanticError();
break;
} else {
return BOOL;
}
default:
throw new SemanticError();
break;
}
}

作用域检查

table:

  • 进入作用域, 插入元素(插入哈希表首, 屏蔽外部同名变量); 离开作用域, 删除元素
  • 进入作用域, 压入新符号表; 离开作用域, 弹出栈顶符号表

类型相容性

  • 名字不同但结构相同的类型是否相等
  • 面向对象的继承类: is-a 关系 Parent parent = child;

错误诊断

  • 准确的错误信息: 出错位置等
  • 大量的错误信息
  • 一定的自纠功能

Immediate Representation

IR:

  • 树与有向无环图(DAG)
  • 三地址码(3-address code)
  • 控制流图(CFG)
  • 静态单赋值形式(SSA)
  • 连续传递风格(CPS)

三地址码

  • 原子表达式
  • 简单控制流 cjmp/jmp
  • 抽象的机器代码(伪代码)

控制流图

Block

  • block_t: { label_t; stm_list; jmp_t; }
  • 扫描三地址码, 生成 blocks
  • 图论算法:结点为 blocks, 边为跳转边

死基本块删除优化:删除遍历不到的语句块

数据流分析与程序重写

  • 根据数据流分析得到的信息, 对三地址码/控制流图进行重写
  • 后端的每一个阶段都可进行数据流分析

常量传播优化: 将赋值语句右端变量直接替换为常量, 减少访存

数据分析方法
到达定义分析

分析变量的哪些定义点可以到达变量的使用点处, 若可达定义唯一则可进行常量传播优化:

  • in set = prior out set
  • out set = self set + in set - kill set(重复定义点)
活性分析
  • 寄存器分配优化 活跃区间不相交的变量可共用一个寄存器
  • 并行优化 使用区间并行的计算可并行执行

代码优化

组织管理

Activation Record and Frame

AR:

用于管理过程活性(procedure activation)的信息:

  • result: 置于记录的顶层, 便于访问此结果
  • argument
  • return address
  • control link: 指向调用者(上级)

全局变量

不存于 AR 中, 存于静态数据段

堆区

new/malloc 得到的变量/对象不存于 AR 中, 存于堆区

优化类型

  • Local optimizations
  • Global optimizations
  • Inter-procedural optimizations

局部优化

  • 常量折叠优化: 所有代入常量的地方全部代入常量 1 + 2 => 3
  • 代数化简优化: a=1*b => a=b 2*a=>a<<1 (all tips from CSAPP)
  • 复制传播(copy propagation)优化: 利用前面计算出来的结果, 直接替换后面所有出现在右边的已计算左式(寄存器)

全局优化

Dead Code Elimination

  • CFG 中(控制流分析) 死代码块删除优化

Constant Propagation

CFG 中(数据流分析-可达定义分析) 常量传播(constant propagation)优化:

  • forwards analysis
  • C(stm, x, in) = value of x before stm ; C(stm, x, out) = value of x after stm
  • bottom < c < top => C(stm, x, in) = least_upper_bound{ C(prev_stm_i, x, out) }:
    • C(prev_stm, x, out) = top(nondeterministic) => C(stm, x, in) = top
    • C(prev_stm1, x, out) != C(prev_stm2, x, out) => C(stm, x, in) = top
    • C(prev_stm_i, x, out) = c/bottom(dead code) => C(stm, x, in) = c
  • C(stm, x, in) = bottom => C(stm, x, out) = bottom
  • C(x := c, x, out) = c
  • C(x := f(), x, out) = top
  • init: set entry to C = top, set anywhere else to C = bottom

Liveness Analysis

CFG 中 数据流分析-活性分析(liveness analysis), 可用于复制传播优化与寄存器分配优化:

  • backwards analysis
  • L(stm, x, out) = V { L(next_stm, x, in) }
  • L(... := f(x), x, in) = true
  • L(x := e, x, in) = false
  • L(none x, x, in) = L(none x, x, out)
  • init: L(...) = false

寄存器分配

Register Allocation and Graph Coloring:

  • 当 t1 与 t2 同时具有活性时, 不可共享寄存器; 反之, t1 与 t2 不同时具有活性, 可以共享寄存器
  • 当 t1 与 t2 同时具有活性时, 添加一条边连接 t1 与 t2, 构建 register interference graph(RIG)
  • colors number = registers number, k-colorable problem

Code Generation(代码生成)

为数据分配计算资源:

  • 数据: 全局变量, 局部变量, 动态分配变量
  • 资源: 寄存器(register), 数据区(.data, .bss), 代码区(.code), 栈区(runtime stack), 堆区(user heap)

当前局部变量应该放在寄存器还是内存区?

为代码选择计算指令(等价性):

  • 代码: 表达式/语句/函数代码
  • 指令: 算术/比较/跳转/调用/返回指令
P: D S
;

D: T id ';' D
|
;

T: int
| bool
;

S: id = E
| printi (E)
| printb (E)
;

E: n
| id
| true
| false
| E + E
| E && E
;

递归下降代码生成算法

基于栈计算机

Mem + Stack + ALU

JVM(Java Virtual Machine)

s: push NUM
| load x
| store x
| add
| sub
| times
| div
;
gen_prog(dec_t d, stm_t s) {
gen_dec(d);
gen_stm(s);
}

gen_dec(T id; D) {
// stack_code(".int id")
gen_type(T);
emit(" id");

gen_dec(D);
}

gen_type(type_t t) {
switch(t-kind) {
case INT:// fall through
case BOOL:
emit(".int");
break;
}
}

gen_stm(stm_t s) {
switch (s->kind) {
STM_ASSIGN:
gen_exp(s->exp);
emit("store s->id");
break;
STM_PRINTI:
gen_exp(s->exp);
emit("printi");
break;
STM_PRINTB:
gen_exp(s->exp);
emit("printb");
break;
}
}

gen_exp(exp_t e) {
switch (e->kind) {
case EXP_INT:
emit("push e->value");// n
break;
case EXP_ID:
emit("load e->value");// id
break;
case EXP_BOOL:
emit("push e->value");// 1/0
break;
case EXP_ADD:
gen_exp(e->left);
gen_exp(e->right);
emit("add");
break;
case EXP_AND:
gen_exp(e->left);
gen_exp(e->right);
emit("and");
break;
}
}

基于寄存器计算机 (RISC)

Mem + Reg + ALU

MIPS ISA

// src -> dist
s: mov_n n, r
| mov r1, r2
| load [x], r
| store r, [x]
| add r1, r2, r3
| sub r1, r2, r3
| times r1, r2, r3
| div r1, r2, r3
void gen_prog(dec_t d, stm_t s) {
gen_dec(d);
gen_stm(s);
}

void gen_dec(T id; D) {
// reg_code(".int id")
// 为变量分配寄存器
gen_type(T);
emit(" id");

gen_dec(D);
}

void gen_type(type_t t) {
switch(t-kind) {
case INT:// fall through
case BOOL:
emit(".int");
break;
}
}

void gen_stm(stm_t s) {
switch (s->kind) {
STM_ASSIGN:
r = gen_exp(s->exp);
emit("mov r, e->id");
break;
STM_PRINTI:
r = gen_exp(s->exp);
emit("printi r");
break;
STM_PRINTB:
r = gen_exp(s->exp);
emit("printb r");
break;
}
}

reg_t gen_exp(exp_t e) {
switch (e->kind) {
case EXP_INT:
r = random_reg();
emit("mov_n e->value, r");// n
return r;
case EXP_ID:
r = random_reg();
emit("mov e->value, r");// id
return r;
case EXP_BOOL:
r = random_reg();
emit("mov_n e->value, r");// 1/0
return r;
case EXP_ADD:
r1 = gen_exp(e->left);
r2 = gen_exp(e->right);
r = random_reg();
emit("add r1, r2, r");
return r;
case EXP_AND:
r1 = gen_exp(e->left);
r2 = gen_exp(e->right);
r = random_reg();
emit("and r1, r2, r");
return r;
}
}

Garbage Collection

Mark and Sweep

  • mark phase: traces reachable objects (mark_bit |= 1)
let todo = {all roots}
while todo != nil do
pick v <- todo
todo -= {v}
if mark(v) == 0 then
mark(v) |= 1
let v1, ..., vn be the pointers contained in v
todo += {v1, ..., vn}
fi
od
  • sweep phase: collects garbage objects (mark_bit == 0)
p = bottom of heap
while p < top of heap do
if mark(p) == 1 then
mark(p) = 0
else
add block p...(p + sizeof(p) - 1) to freeList
fi
p += sizeof(p)
od

Stop and Copy

Copy all reachable objects in old space to new space(reserved for GC):

  • Copied objects
  • Scanned objects: pointers have been restored

Compilers Exercise

C Declaration Interpreter

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define MAX_TOKENS 100
#define MAX_TOKEN_LEN 64

enum type_tag {
IDENTIFIER,
QUALIFIER,
TYPE,
};

struct token {
char type;
char string[MAX_TOKEN_LEN];
};

int top = -1;
struct token stack[MAX_TOKENS];
struct token ts;

#define pop stack[top--]
#define push(s) stack[++top] = s

enum type_tag classify_string(void) {
char *s = ts.string;

if (!strcmp(s, "const")) {
strcpy(s, "read-only ");
return QUALIFIER;
}

if (!strcmp(s, "volatile")) return QUALIFIER;
if (!strcmp(s, "void")) return TYPE;
if (!strcmp(s, "char")) return TYPE;
if (!strcmp(s, "signed")) return TYPE;
if (!strcmp(s, "unsigned")) return TYPE;
if (!strcmp(s, "short")) return TYPE;
if (!strcmp(s, "int")) return TYPE;
if (!strcmp(s, "long")) return TYPE;
if (!strcmp(s, "float")) return TYPE;
if (!strcmp(s, "double")) return TYPE;
if (!strcmp(s, "struct")) return TYPE;
if (!strcmp(s, "union")) return TYPE;
if (!strcmp(s, "enum")) return TYPE;

return IDENTIFIER;
}

void get_token(void) {
char *p = ts.string;

/* 略过空白字符 */
while ((*p = getchar()) == ' ');

if (isalnum(*p)) {
/* 读入得标识符以a-Z,0-9开头 */
while (isalnum(*++p = getchar()));
ungetc(*p, stdin);
*p = '\0';
ts.type = classify_string();
return;
}

if (*p == '*') {
strcpy(ts.string, "pointer to");
ts.type = '*';
return;
}

ts.string[1] = '\0';
ts.type = *p;
return;
}

void read_to_first_identifier(void) {
get_token();

// read til identifier
while (ts.type != IDENTIFIER) {
push(ts);
get_token();
}

printf("%s is ", ts.string);
get_token();
}

void deal_with_arrays(void) {
while (ts.type == '[') {
printf("array ");
get_token();

/* 数字或']' */
if (isdigit(ts.string[0])) {
printf("0..%d ", atoi(ts.string) - 1);
get_token();
}

get_token();
printf("of ");
}
}

void deal_with_pointers(void) {
while (stack[top].type == '*')
{
printf("%s ", pop.string);
}
}

void deal_with_function_args(void) {
while (ts.type != ')') {
get_token();
}

get_token();
printf("function returning ");
}

void deal_with_declarator(void) {
/* 处理标识符之后可能存在的数组/函数 */

switch (ts.type) {
case '[':
deal_with_arrays();
break;
case '(':
deal_with_function_args();
break;
}

deal_with_pointers();

/* 处理在读入到标识符之前压入到堆栈中的符号 */
while (top >= 0) {
if (stack[top].type == '(') {
pop;
get_token(); //读取')'之后的符号
deal_with_declarator();
} else {
printf("%s", pop.string);
}
}
}

int main(void) {
/* 将标记压入堆栈中, 直到遇见标识符 */
read_to_first_identifier();
deal_with_declarator();
printf("\n");

system("pause");
return 0;
}

Cool Language

Classroom Object-Oriented Language:

Parser Implementation

// 返回下一个Token(只测试该Token,不向前移动Token List的offset指针)
Token Peek(void);
// 消费下一个Token
Token Next(void);
// void Expect(expectedToken)
if (Peek() != expectedToken) {
Error("expect %s, but got %s\n", expectedToken, Peek());
}
// void Try(expectedToken)
if (Peek() == expectedToken) {
Next(); // 消费之
return true;
}

return false;