编译器：将源语言程序翻译成目标语言程序
解释器：不翻译源程序，而是边解释边执行源程序
预处理器：把源程序聚合在一起，宏展开
汇编器：将汇编语言程序生成可重定位的机器码
链接器：解决外部内存地址问题，将多个目标文件和库文件链接到一起
加载器：把所有的可执行目标文件放到内存中执行

1.1.1：解释器是一条一条的解释执行源语言；编译器是把源代码整个编译成目标代码，执行时不在需要编译器，直接在支持目标代码的平台上运行
1.1.2：执行效率高；错误诊断更优
1.1.3：汇编语言更容易调试、检查bug。跨平台，可移植性强
1.1.4：C语言小巧灵活，通用性高，执行效率高
1.1.5：将汇编程序，翻译成机器指令

词法分析：
语法分析：
语义分析：
代码优化：
代码生成：

1.3.1：
	强制式的语言：C C++ Java
	声明式的语言：ML Haskell Prolog
	冯诺依曼式语言：Fortran C 
	面向对象的语言：C++ Java C# Smalltalk Ruby
	函数式的语言：ML Haskell scheme
	第三代语言：Fortran Gobol Lisp C C++ C# Java VB
	第四代语言：NOMAD SQL PostScript
	脚本语言：Awk JavaScript Perl PHP Python Ruby
	
高性能系统：并行性(指令级并行、处理器级并行)和内存层次结构(cache)
		
静态和动态：多态
作用域：public、private、protected
参数传递机制：传值、传引用、传名(类似宏)  
别名
1.6.1：w = 13, x = 11, y = 13, z = 11
1.6.2：w = 9, x = 7, y = 13, 11 
1.6.3：		w1: B1-B3-B4
			x1: B1-B2-B4
			y1: B1-B5
			z1: B1-B2-B5
			x2: B2-B3
			z2: B2
			w3: B3 
			x3: B3 
			w4: B4
			x4: B4 
			y5: B5
			z5: B5 
1.6.4：3\n 2\n 

语法分析：上下文无关文法--->产生式
2.2.1：1.S-->SS*-->(S)S*-->(SS+)S*-->(aS+)S*-->aa+a*	S-->SS*-->(S)a*-->(SS+)a*-->(Sa+)a*-->aa+a*	
	2.				S
					|
			S		S 	*
			|		|
		S 	S 	+	a
		|	|
		a 	a 
	3.文法生成的语言是以a为基本运算因子(factor)的+和*运算符表达式的后缀形式
2.2.2:(1).(0)^n(1)^n 	(2).基于a的前缀表达式	(3).对称括号对的串	
	(4).ab个数相等的字符串	(5).以a为factor的字符串，有+、*、()等符号
2.2.3：1、2无二义		3、4、5有二义
2.2.4：(1).S-->SS+|SS-|SS*|SS/|a	(2).S-->S,id|id 	(3).S-->id,S|id 
		(4).expr-->expr+expr|expr-expr|expr*expr|expr/expr|id|digit
		(5).expr-->expr+expr|expr-expr|expr*expr|expr/expr|id|digit|+expr|-expr 
2.2.5：(11)=3，(1001)=9，(num 0)=(num)*2，(num num)=(num)*2*2+(11)|(num)*16+(1001)。显然文法生成的所有的数字，都可以被3整数.(x0=3, x1=9, fnx=2x|4x+3|16x+9)
		不能生成所有的：3,6,9,12,15,18,24,27
2.2.6： RomanNum --> Thousands Hundreds Tens Ones
		Ones --> LowOnes|IV|V LowOnes|IX
		LowOnes --> epsilon|I|II|III
		Tens --> LowTens|XL|L LowTens|XC
		LowTens --> epsilon|X|XX|XXX
		Hundreds --> LowHundreds|CD|D LowHundreds|CM
		LowHundreds -->epsilon|C|CC|CCC
		Thousands --> M Thousands|epsilon
语法分析树：语义动作，后序遍历
2.3.1：S-->S1+S2  S.t='+'||S1.t||S2.t
		S-->S1-S2  S.t='-'||S1.t||S2.t
2.3.2：S-->S1S2+  S.t=S1.t||'+'||S2.t
		S-->S1S2-  S.t=S1.t||'-'||S2.t
2.3.3： u -> u + u | pn | n
		p -> 1 | 10 | 100
		n -> 1 | 5 | 10 | 50 | 100 | 500 | 1000
		1 -> I
		5 -> V
		10 -> X
		50 -> L
		100 -> C
		500 -> M
		1000 -> D
2.3.4：2.3.3相反的过程 
2.3.5：S-->S1S2+  S.t='+'||S1.t||S2.t
		S-->S1S2-  S.t='-'||S1.t||S2.t
向前看符号、预测分析器
左递归、右递归
2.4.1：
(1)	void S(){
		switch(lookhead){
			case '+':
				match('+');
				S();
				S();
				break;
			case '-':
				match('-');
				S();
				S();
				break;
			case 'a':
				match('a');
				break;
			default:
				report("syntax error");
		}
	}
	
	void match(Terminal t){
		if (lookhead == t){
			lookhead = nextTerminal;
		}
		else{
			report("syntax error");
		}
	}
(2).	void S(){
			if (lookhead == '('){
				S();
				match('(');
				S();
				match(')');
				S();
			}
			// epsilon
		}
(3).	void S(){
			switch (lookhead){
				case '0':
					match('0');
					S();
					match('1');
					break;
				case '1':
					break;
				default:
					report("syntax error");
			}
		}
词法分析：忽略空白符和换行符、抽取token(数字和标识符)
2.6.1： 2.6.2：2.6.3： 
public Token scan() throws IOException, SyntaxException{    
	for( ; ; peek = (char)stream.read()){
		if(peek == ' ' || peek == '\t'){        
			continue;      	
		}
		else if(peek == '\n'){
			line = line + 1;      
		}
		else{        
			break;      
		}    
	}
	
	// handle comment    
	if(peek == '/'){      
		peek = (char) stream.read();      
		if(peek == '/'){        // single line comment        
			for( ; ; peek = (char)stream.read()){          
				if(peek == '\n'){
					break;          
				}        
			}      
		}
		else if(peek == '*'){        // block comment        
			char prevPeek = ' ';        
			for( ; ; prevPeek = peek, peek = (char)stream.read()){
				if(prevPeek == '*' && peek == '/'){            
					break;          
				}        
			}
		}
		else{
			throw new SyntaxException();      
		}    
	}   
	
	// handle relation sign    
	if("<=!>".indexOf(peek) > -1){      
		StringBuffer b = new StringBuffer();      
		b.append(peek);      \
		peek = (char)stream.read();      
		if(peek == '='){        
			b.append(peek);      
		}      
		return new Rel(b.toString());    
	}
	
	// handle number, no type sensitive    
	if(Character.isDigit(peek) || peek == '.'){      
		Boolean isDotExist = false;      
		StringBuffer b = new StringBuffer();      
		do{
			if(peek == '.'){          
				isDotExist = true;        
			}        
			b.append(peek);        
			peek = (char)stream.read();      
		} while (isDotExist == true ? Character.isDigit(peek) : Character.isDigit(peek) || peek == '.');      
		
		return new Num(new Float(b.toString()));    
	}      
	
	// handle word
	if(Character.isLetter(peek)){      
		StringBuffer b = new StringBuffer();      
		do{        
			b.append(peek);        
			peek = (char)stream.read();      
		} while (Character.isLetterOrDigit(peek));
		
		String s = b.toString();      
		Word w = words.get(s);      
		if(w == null){        
			w = new Word(Tag.ID, s);        
			words.put(s, w);      
		}      
		return w;    
	}      
	
	Token t = new Token(peek);    
	peek = ' ';    
	return t;  
} 		

中间代码：抽象语法树、三地址代码
类型检查、自动类型转换
2.8.1：	class For extends Stmt{
			Expr e1;
			Expr e2;
			Expr e3;
			Stmt s;
			
			public For(Expr expr1, Expr expr2, Expr expr3, Stmt stmt){
				e1 = expr1;
				e2 = expr2;
				e3 = expr3;
				s = stmt;
			}
			
			public void gen(){
				e1.gen();
				Label start = new Label();
				Label end = new Label();
				emit("ifFalse " + e2.rvalue().toString() + " goto " + end);
				s.gen();
				e3.gen();
				emit("goto " + start);
				emit(end + " ");
			}
		}
2.8.2： emit("isFalse " + E.rvalue().toString() + " goto " + after); 
		emit("ifNotEqual " + E.rvalue().toString() + " 0 goto " + after); 
	OR	emit("isNotEqualZero " + E.rvalue().toString() + " goto " + after);

正则表达式 --> 不确定有穷状态自动机 --> 确定有穷状态自动机
词法分析器：读入源程序的字符串，将源程序中的字符组成一个个词素，生成对应的词法单元
3.1.1：
3.1.2：
正则表达式：* + ? [a-z]
3.3.1： 
	C：ASCII，标识符只能是(字母|下划线)开头的，(字母|下划线|数字)组成的字符串
	C++：Unicode，标识符只能是(字母|下划线)开头的，(字母|下划线|数字)组成的字符串
	C#：
	Fortran：
	Java：Unicode，标识符只能是(字母|下划线)开头的，(字母|下划线|数字)组成的字符串
	Lisp：
	SQL：
3.3.2： 
	(1).由a开头和结尾，中间有n个a或b构成的字符串
	(2).由b或者ab一起构成的字符串
	(3).ab构成的字符串，倒数第三位是a，其他位a|b 
	(4).有ab构成的字符串，有且仅有三个b
	(5).有偶数个a和偶数个b构成的字符串
3.3.3： n+1, n+1, n-1, (n-1)(n-2)/2+2, 2^n
3.3.4：(select) --> [sS][eE][lL][eE][cC][tT]
	大小写可以混合使用，说明大写字母和小写字母之间的关系是可选择的，但是必须选择其一。
3.3.5：
	(1).(a)+(e)+(i)+(o)+(u)+		uv=[b-df-hj-np-tv-z] uv*auv*euv*iuv*ouv*uuv*
	(2).(a)+(b)+...(y)+(z)+			a*b*c*....y*z*
3.3.6:
	(1).[a-jA-J]
	(2).[b-df-hj-np-tv-z]
	(3).[0-9a-f]
	(4).[,.!?]
3.3.7：
3.3.8：
3.3.9：
3.3.10：
3.3.11：
3.3.12：
状态转换图：词法分析
3.4.1： 
3.4.2：
3.4.3：
	(1).0 0 1 2 3 4 5 1 2
	(2).0 1 2 3 4 5
	(3).0 0 0 1 1 2 3
3.4.4： 
3.4.5： 
3.4.6：(1)是的，(2)不是的
3.4.7：
3.4.8：
3.4.9：
3.4.10：
3.4.11：
3.4.12：
词法分析器生成工具Lex
3.5.1： 
	(1).while {return(WHILE);}
3.5.2： 
3.5.3： 
3.5.4： 
3.5.5： 
NFA 和 DFA：词法分析器，实际模拟的都是DFA
3.6.1：
3.6.2：
3.6.3：
	(1).0-->(a)-->1-->(a)-->2-->(b)-->2-->b-->3   accept
	(2).0-->(a)-->0-->(a)-->0-->(b)-->0-->b-->0   no
	(3).0-->(a)-->0-->(a)-->1-->(b)-->1-->b-->1   no
	(4).0-->(a)-->1-->(a)-->2-->(b)-->2-->b-->2   no
	(5).0-->(a)-->1-->(a)-->2-->0-->(b)-->0-->b-->0   no
	(6).0-->(a)-->1-->(a)-->2-->(b)-->2-->0-->b-->0   no
3.6.4：
	(1).0-->(a)-->1-->0-->(a)-->1-->(b)-->2-->(b)-->3   accept
	(2).0-->(a)-->1-->0-->(a)-->1-->(b)-->2-->1-->(b)-->2   no
	(3).0-->(a)-->1-->0-->(a)-->1-->0-->3-->2-->(b)-->3-->2-->(b)-->3   accept
	(3).0-->(a)-->1-->0-->(a)-->1-->0-->3-->2-->1-->(b)-->2-->(b)-->3   accept
	(4).0-->(a)-->1-->0-->(a)-->1-->0-->3-->2-->1-->(b)-->2-->1-->(b)-->2   no
	(5).0-->(a)-->1-->0-->(a)-->1-->0-->3-->2-->(b)-->3-->2-->1-->(b)-->2   no
	(6).0-->3-->(a)-->0-->3-->(a)-->0-->3-->2-->(b)-->3-->2-->1-->(b)-->2   no
	(7).0-->3-->(a)-->0-->3-->(a)-->0-->3-->2-->1-->(b)-->2-->(b)-->3   accept
	...
3.6.5：
正则表达式 --> NFA --> DFA 
3.7.1：
3.7.2：
3.7.3：
3.8.1：0-->(i)-->1-->(f)-->((2))	0-->(epsilon)-->3-->(letter)-->((3))
3.8.2：0-->(epsilon)-->1-->(letter)-->2-->(letter|number)-->((2))
3.8.3：
3.8.4：
模式匹配器的优化：
	1.正则表达式直接生成DFA：Dstates, Dtransition
	2.DFA状态数量最小化：分组合并
	3.生成更加紧凑的转换表：矩阵、链表、四个数组base、default、next、check
3.9.1：
3.9.2：
3.9.3：
3.9.4：
3.9.5：
DFA 和 NFA区别：
	1.任何一个状态对与任何一个输入符号，有且只有一个转换; 2.不存在epsilon的转换
	2.DFA类似于状态转换图

词法分析器的实现理论，特别是词法分析器自动生成工具Lex

语法分析器
上下文无关文法：简称文法，由终结符号、非终结符号、开始符号、产生式组成
错误处理和错误恢复：
上下文无关语言：可由文法生成的语言
二义性：文法中的句子有多棵语法分析树
有穷自动机不能计数：{((a^n)(b^n))|n>=1}不能使用正则表达式表示
4.2.1：(1).S-->SS*-->SS+S*-->aS+S*-->aa+S*-->aa+a* 
	(2).S-->SS*-->Sa*-->SS+a*-->Sa+a*-->aa+a* 
	(3).
	(4).没有二义性
	(5).后缀加法，后缀乘法，a为基本符号元
4.2.2：(1)S-->0S1-->00S11-->000111	无二义性
4.2.3：
4.2.4：
4.2.5：
4.2.6：
4.2.7：
4.2.8：
消除二义性
消除左递归
提取左公因子
非上下文无关文法，均在语义分析阶段检查。
4.3.1：
4.3.2：
4.3.3：
LL(k)文法：L:从左向右扫描输入、L:表示产生最左推导、k:每一步需要向前看k个字符
错误恢复：恐慌模式、短语层次的恢复
4.4.1：
4.4.2：
4.4.3：
4.4.4：
4.4.5：
4.4.6：
4.4.7：
4.4.8：
4.4.9：
4.4.10：
4.4.11：
4.4.12：
移入-归约语法分析
LR(k)文法 
移入-归约语法分析冲突：移入/归约，归约/归约 
4.5.1：
4.5.2：
4.5.3：
LR(0)自动机
SLR
语法分析表：action goto 
可行前缀
4.6.1：
4.6.2：
4.6.3：
4.6.4：
4.6.5：
4.6.6：
4.6.7：
4.6.8：
4.6.9：
LR(1)
LALR：基于LR(0)，更加强大
4.7.1：
4.7.2：
4.7.3：
4.7.4：
4.7.5：
二义性文法：优先级、结合性
错误恢复方法：恐慌模式、短语层次的恢复
4.8.1：
4.8.2：
Yacc(yet another compiler-compiler)
Lex与Yacc：(结合生成编译器前端)
	lex first.l 
	yacc second.y 
	cc y.tab.c -ly -ll
4.9.1：
4.9.2：
4.9.3：
4.9.4：

语法分析器的实现理论，特别是词法分析器自动生成工具Yacc，文法分析如何实现，如何构建语法分析表等。
action和goto函数

L属性翻译方案(通用型)
S属性翻译方案(综合型)
SSD：注释语法树
5.1.1：
5.1.2：
5.1.3：
依赖图：语法分析树-->注释语法分析树(定义了一个节点求值顺序)
SDD
	S属性：综合属性
	L属性：综合属性+继承属性(必须是左边的或者上方的，不能使用右边的节点)
5.2.1：
5.2.2：
5.2.3：(1)L		(2)L 	(3)S L 	(4)L 
5.2.4：
5.2.5：
5.2.6：
Syntax Directed：类型检查、中间代码生成
抽象语法分析树：继承属性、综合属性、epsilon产生式
5.3.1：
5.3.2：
5.3.3：
SDT(syntax directed translation)：语义动作(产生式中的程序片段)
LR-->S属性的SDD		后缀翻译
LL-->L属性的SDD
SDD：语义规则；SDT：语义动作
5.4.1：
5.4.2：
5.4.3：
5.4.4：
5.4.5：
5.4.6：
5.4.7：
LL --> LR：自底向上的方式实现LL文法的L属性SDD(LR文法)
5.5.1：
5.5.2：
5.5.3：
5.5.4：
5.5.5：
5.5.6：

DAG(directed acyclic graph)：值编码(散列表)
6.1.1：
6.1.2：
三地址代码：四元式、三元式、间接三元式
静态单赋值
6.2.1：
6.2.2：
6.2.3：
类型是有结构的-->类型表达式：
	类比：类、构造函数；类有结构，构造函数就相当于类型构造算子
类型：类型检查、存储空间分配
6.3.1：
6.3.2：
数组元素寻址：addr = base + n*width
6.4.1:
6.4.2:
6.4.3:
6.4.4:
6.4.5:
6.4.6：
6.4.7：
6.4.8：
6.4.9：
类型综合、类型推导
类型转换：拓宽转换、窄化转换；自动类型转换、强制类型转换
置换、合一
6.5.1：
6.5.2：
布尔表达式：控制流跳转、布尔表达式求值
短路代码--> 布尔表达式的短路求值(跳转指令)
if False 优化
6.6.1：
6.6.2：
6.6.3：
6.6.4：
6.6.5：
6.6.6：
6.6.7：
6.6.8：
回填：一趟遍历即可完成
break、continue、goto
6.7.1：
6.7.2：
6.7.3：
switch、case
6.8.1：
函数调用中间代码
过程调用参数、返回值、运行时

存储结构：代码区、静态区、堆、栈
运行时刻栈
活动树
调用者、被调用者
7.2.1：
7.2.2：
7.2.3：
7.2.4：
7.2.5：2*a = 2*(3+1+2) = 12
7.2.6：3*c = 3*(4+1+2+3) = 30
访问链
显示表(哈希表原理)
7.3.1：
7.3.2：
堆区内存管理
存储管理器：分配、回收
存储结构层次：程序局部性(时间局部性、空间局部性)
碎片整理：best-fit next-fit first-fit
内存泄漏、悬空指针
7.4.1：(1)0, 14, 60, 50, 0, 20, 40
	   (2)80, 30, 60, 0, 0, 0, 8 
垃圾回收
	类型安全：Java等，(C/C++语言属于类型不安全的，内存地址可以任意的被访问)
	引用计数：循环数据结构(交叉引用)、开销大
	跟踪对象的可达性
7.5.1：
7.5.2：
基于跟踪的垃圾回收
	标记-清扫式垃圾回收
	Baker标记-清扫式垃圾回收 
	标记-压缩垃圾回收
	拷贝垃圾回收
7.6.1：
7.6.2：
7.6.3：
7.6.4：
时间划分：增量式垃圾回收
空间划分：部分垃圾回收
世代垃圾回收法
列车垃圾回收算法：单节车厢、恐慌模式
7.7.1：
7.7.2：
7.7.3：
7.7.4：
7.7.5：
并行：存在多个线程
并发：同时执行多个程序
C/C++语言垃圾回收：数据表记录分配的内存
弱化引用
7.8.1：

指令选择：RISC CISC
寄存器分配和指派问题(NP)：哪些指令分配寄存器，某个指令使用哪个寄存器
指令排序问题(NP)：最优的指令排序

汇编语言：
	LD、ST、ADD SUB MUL、BR BLTZ
8.2.1：
	1. LD R1, 1; ST x, R1
	2. LD R1, a; ST x, R1
	3. LD R1, a; ADD R1, R1, 1; ST x, R1 
	4. LD R1, a; LD R2, b; ADD R1, R1, R2; ST x, R1 
	5. LD R1, b; LD R2, c; MUL R1, R1, R2; LD R3, a; ADD R1, R1, R3; ST y, R1
8.2.2： 
	1. LD R1, i; MUL R1, R1, 4; LD R2, a(R1); ST x, R2 
		LD R1, i; MUL R1, R1, 4; LD R2, x; ST a(R1), R2 
8.2.3：
8.2.4：
8.2.5：
8.2.6：2+2+1+2、2+1+2+2、2+2+1+2、
静态分配，固定的绝对地址
栈分配，SP寄存器控制的
8.3.1：
8.3.2：
8.3.3：
基本块、流图
8.4.1：		
8.4.2：		
基本块的优化：
	1.消除公共子结点
	2.消除死代码
	3.常量求值替换
	4.代数恒等式的优化
8.5.1：
8.5.2：
8.5.3：
8.5.4：
8.5.5：
8.5.6：
8.5.7：
8.5.8：
寄存器描述符、地址描述符  -->两张表记录寄存器和变量的地址信息
getReg(I)：完成寄存器的选择和分配
8.6.1：
8.6.2：
8.6.3：
8.6.4：
8.6.5：
窥孔优化：
	1.消除冗余代码
	2.消除不可达代码
	3.控制流优化：尽量少采用无条件跳转
	4.代数化简、强度消减
	5.使用特殊机器指令
8.7.1：
8.7.2：
8.7.3：
寄存器分配和指派：图着色算法
8.8.1：
8.8.2：
树重写方案：
	LR语法分析方法
	定义树转换规则
	树匹配方法：
		前缀表示法
		自顶向下的方法
		动态规划算法：代价值
8.9.1：
8.9.2：
8.9.3：
8.9.4：
Ershov number：决定表达式求值需要的寄存器数目
寄存器数目和表达式求值算法关系
8.10.1：
8.10.2：
8.10.3：
8.10.4：
8.10.5：
8.10.6：
8.10.7：
连续求值(子树一棵棵计算完，非跳跃的)
动态规划算法 
代价数组C[i]
8.11.1：
8.11.2：

冗余消除：
	公共子表达式消除
	死代码消除
复制传播
常量折叠(常量代替表达式)
代码移动(循环内移到循环外)
强度消减(乘除-->加减)、归纳变量
9.1.1：
9.1.2：
9.1.3：
9.1.4：
数据流：
	数据流问题：对一组约束求解 --- 线性规划、最优解
	约束：传递函数约束、控制流约束
到达定值
活跃变量
可用表达式
	交汇运算：并集、交集
9.2.1：
9.2.2：
9.2.3：
9.2.4：
9.2.5：
9.2.6：
9.2.7：
9.2.8：
9.2.9：
9.2.10：
9.2.11：
半格
数据流框架迭代算法：前向、逆向
最大不动点 MFP  IDEAL MOP
9.3.1：
9.3.2：
9.3.3：
9.3.4：
9.3.5：
常量传播框架的数据流值：UNDEF NAC C
常量传播框架：单调性、不可分配性
9.4.1：
9.4.2：
冗余：公共子表达式、循环不变表达式、部分冗余表达式
关键边：插入新的基本块
懒惰代码移动：完全冗余、部分冗余
	预期执行表达式：所有的路径都会计算该表达式
	可用表达式：所有路径中都在该点之前被预期执行
	可后延表达式：如果一个程序点，所有路径都有使用该表达式，则可以后延
	被使用的表达式：存在某一条路径使用了该表达式
9.5.1：
9.5.2：
9.5.3：
支配节点(关键节点)
深度优先排序：根-->右-->左 
前进边、后退边、交叉边
回边、可归约性
自然循环：唯一入口点
9.6.1：
9.6.2：
9.6.3：
9.6.4：
9.6.5：
9.6.6：
9.6.7：
9.6.8：
9.6.9：
9.6.10：
9.6.11：
9.6.12：
9.6.13：
基于区域的分析技术：
	循环体区域
	循环区域
不可归约流图：结点分割技术
9.7.1：
9.7.2：
9.7.3：
9.7.4：
9.7.5：
9.7.6：
符号分析：优化、并行化、程序理解的分析
仿射表达式：
	归纳变量：强度消减
	基本归纳变量
	符号化常量
	循环不变变量
9.8.1：
9.8.2：
9.8.3：

指令流水线：分支跳转预测错误，就会出现分支延时  
very long instruction word机器 软件静态调度
superscalar 机器 硬件动态调度

代码调度约束：
	控制依赖：条件跳转
	数据依赖：使用前面指令的结果
		真依赖：写 - 读 
		反依赖：读 - 写
		输出依赖：写 - 写
	资源约束：硬件资源是有限的
寄存器使用和并行性之间折衷：硬件寄存器重命名
	先寄存器分配，再指令调度：寄存器少用，并行化少
	先指令调度，再寄存器分配：并行化多，寄存器多用
投机执行、跳转预测
	指令预取
	poison bit
	带断言的执行
10.2.1：
	(1).真依赖 (2).反依赖 (3).输出依赖 (4).真依赖 (5).反依赖 
10.2.2：
10.2.3：
10.2.4：
10.2.5：
	if (a > t){				LDR R1, a;		LDR R2, t;		LDR R3, b;	LDR R4, c;	LDR R5, d;	
		b = a * a;			SUB R2, R2, R1;	MUL R6, R1, R1;	
	}						CMOVZ R3, R6, R2;
	d = a + c;				ADD R5, R1, R4;
数据依赖图
列表调度方法
带优先级的拓扑排序：
	关键路径：数据依赖图中最长的路径
	关键资源：资源使用/可用资源比值最大的资源
10.3.1:	
10.3.2:	
10.3.3:	
10.3.4:	
全局代码调度：同时考虑多个基本块的调度策略
可以投机执行加载运算，不能投机执行保存运算，可以延迟保存运算
支配、反向支配、控制等价
	基于区域的调度算法
	循环展开
动态调度器、静态调度器
10.4.1：
10.4.2：第一步先加载b，c到寄存器中，然后再考虑条件判断
软件流水线化算法：启发式搜索算法
	循环展开
	序言、稳定状态、尾声
Do-Across循环
模数资源预约表：稳定状态的资源预约表
时间间隔T
强连通分量(Strongly Connected Component)
模数变量扩展：可私有化变量 --> 数组 --> 多寄存器存放 --> 消除依赖关系
硬件支持：带断言的指令
10.5.1：
10.5.2：
10.5.3：
10.5.4：
10.5.5：
10.5.6：
10.5.7：
10.5.8：

并行化：数据应用
处理器间通信开销
线性规划技术求最优解：
	仿射分划：把迭代的多面体分割成多个部分，在不同机器上执行各个部分
	分块：创建一个由迭代组成的层次结构，一块一块的遍历

对称多处理器：共享内存、一致缓存协议
分布式内存的并行机：不一致内存访问机器(共享内存通信)、消息传递机器(消息传递通信)
Amdahl定律：加速比
任务并行性
master - slave (主从服务器)
栅障同步：并行处理器最后阶段
数据局部性：
	时间局部性 
	空间局部性
向量机：一次性对整个向量进行简单算术运算
仿射变换：
	迭代空间
	数据空间
	处理器空间

改变数据结构的布局
分块技术
高速缓存干扰
11.2.1：单独使用循环清零
循环迭代空间：凸多面体
Fourier-Motzkin消除算法
坐标轴变换：控制执行的顺序
11.3.1：
	(1) for (j = 0; j < 5; j++) X[(7j+10), (7j+11)] = 0;
	(2) for (j = 0; j < 6; j++) X[2j-3] = X[2j-2];
	(3) for (j = 0; j <= 40; j++) X[j+10] = 0;
11.3.2：
11.3.3：
11.3.4：
11.3.5：
11.3.6：
11.3.7：
11.3.8：
11.3.9：
11.3.10：
11.3.11：
数组下标使用仿射表达式：仿射访问
11.4.1：
静态访问：访问指令访问数组
动态访问：循环迭代访问数组
数据复用：
	自复用：
	组复用：
	时间复用：相同位置
	空间复用：相同高速缓存
矩阵：秩、线性无关
矩阵零空间：解 --> 循环迭代指向同一个位置
11.5.1：
11.5.2：
11.5.3：
11.5.4：
11.5.5：
11.5.6：
11.5.7：
数据依赖关系问题：整数线性规划：NP问题
丢番图方程：只考虑整数解的方程
	Greatest Common Divisor 测试
	存在整数解的条件：c % gcd(ai) = 0 
整数线性规划的启发式规则：
	独立变量测试
	循环残数测试
	记忆模式
	分支-界定方法
11.6.1：
11.6.2：
11.6.3：
11.6.4：
11.6.5：
11.6.6：
11.6.7：
11.6.8：
11.6.9：
并行性：将计算任务分解成尽可能多的独立单元
仿射空间分划
空间分划约束：具有数据依赖的运算必须分配到同一个处理器上
高斯消除法：根据等式减少变量数目
卫式：增加的测试条件
消除空迭代：收紧循环的界限
消除条件测试：分割循环
基本仿射转换：
	融合
	裂变
	重新索引
	比例变换
	幺模转换：幺模系数矩阵，没有常量向量
		反置
		交换
		倾斜
11.7.1：
11.7.2：
11.7.3：
11.7.4：
11.7.5：
11.7.6：
11.7.7：
11.7.8：
同步运算：同步栅障
程序依赖图(PDG)：发现循环裂变的机会
	环连接的语句不能被分割
	单向的可以分割
11.8.1：
11.8.2：
11.8.3：
流水线化技术：将任务分成数个阶段，各个阶段在不同的处理器上运行
	降低通信量(数据仅在相邻的处理器上共享)
完全可交换循环：时间分划约束具有多个独立解
	多个循环可以任意地排列而不会改变源程序的语义
SOR：连续过松弛法(Successive Over Relaxing)
波阵面：波阵面推进
K个最外层完全可交换循环  --> K-1度的流水线化并行度
Farkas引理：时间分划约束求解
11.9.1：
11.9.2：
11.9.3：
11.9.4：
11.9.5：
局部性优化：
	时间局部性
	数组收缩
	空间局部性(写数据、只读数据)
条状挖掘(stripmining)
11.10.1：
	for(i = 0; i < n; i++){
		T = A[i] + B[i];
		D[i] = T + C[i];
	}
11.10.2：
	for(i = 0; i < n; i++){
		T = A[i] + B[i];
		S = C[i] + D[i];
		E[i] = T + S;
	}
11.10.3：
	for (j = 0; j < n; j += d){
		for (i = n-1; i >= 0; i--){
			for (k = j; k < min(n, j+d); k++){
				S;
			}
		}
	}
仿射转换的应用：
	分布式内存计算机：发送消息通信  --> 给处理器分配大型、独立的计算单元
		数据分配
		通信代码
		优化：权衡同步与通信
	多指令发送处理器：流水线化
		充分利用所有的功能单元
	向量指令、SIMD指令：一条指令可以对很多数据进行处理
	数据预取：将处理器马上要使用的数据提前加载到缓存中。
		不能太晚、不能过早

过程间分析 <--> 过程内分析
	指针别名分析：二分决策图

调用图：
	调用点
	虚方法(virtual method/function)
上下文无关分析
调用串
基于克隆的上下文相关分析
基于摘要的上下文相关分析
12.1.1：
12.1.2：
过程间分析的作用：
	虚方法调用：内联频繁调用的方法
	指针别名分析：
	并行化： 
	软件错误和漏洞检测：
		SQL注入：输入非法，控制数据库
		缓冲区溢出：输入非法，控制操作系统
		
Datalog元素：
	atom：基础原子(参数都是常量的断言)
	断言
	变量或常量项
断言：
	in(B, D)
	equals(X, a)
	edge(X, Y)
	path(X, Y)
规则的子目标：Bi(H)
EDB(外延数据库断言)
IDB(内涵数据库断言)
	def(B, N, X)：基本块B的第N个语句可以对X定值
	succ(B, N, C)：基本块C是基本块B的后继，基本块B有N个语句
	rd(B, N, C, M, X)：基本块C的第M个语句对X定值，到达了B的第N个语句
	assign(B, N, X)
	type(X, T)：X的类型为T
增量式形式
有问题的Datalog规则：
	不安全规则
	不可分层的程序
12.3.1：
12.3.2：
12.3.3：
12.3.4：
12.3.5：
12.3.6：
12.3.7：
指针指向分析
	基于包含的分析技术
	基于等价关系的分析
控制流无关分析：不考虑程序的执行顺序，没有kill的概念
影响指针的语句：
	对象创建：
	复制语句：
	字段保存：
	字段读取：
pts(V, H)：new、=
hpts(H, F, G)：字段保存、字段读取
类型信息：
	vType(V, T)：变量V的类型为T
	hType(H, T)：堆对象H的类型为T
	assignable(T, S)：S对象可以赋值给T对象
12.4.1：
	a --> h 
	b --> g 
	c --> h 
	a.f --> h.f --> g 
	b.f --> g.f --> h 
	d --> c.f --> h.f --> g 
12.4.2：
12.4.3：
调用图：上下文无关和控制流无关的指针指向分析生成(类型声明和语法分析生成调用图)
	actual(S, I, V)：V是调用点S上的第I个实在参数
	formal(S, I, V)：V是方法S中声明的第I个形式参数
	cha(T, N, M)：一个类型为T的接收对象，调用N时，实际调用的方法是M (class hierarchy analysis 类层次结构分析)
	
	invokes(S, M)：调用点S可能调用方法M
反射机制：动态创建对象的类型，方法名等
12.5.1：
12.5.2：
上下文相关性可以提高过程间分析的精确性
上下文环境信息：全局性查询
二分决策图(BDD)
上下文是调用串的表示形式
平凡的SCC、非平凡的SCC
对象相关性
12.6.1：
	p在c1处调用q
	q在c2、c3处递归调用q
	q在c4处调用r
12.6.2：
	q是递归的
	调用r的上下文：
		1.(c1, c4)、(c1, c2, c4)、(c1, c3, c4)...
12.6.3：
BDD(二分决策图)：用图表示布尔函数的方法，把布尔函数表示成一个带根的DAG
	一个根节点、两个叶子节点
	低边：节点对应的变量取值为0
	高边：节点对应的变量取值为1
短路：消除无效的节点
节点合并：合并子节点完全相同的节点
主要的关系运算：
	初始化
	合并
	投影
	连接
12.7.1：
12.7.2：
	2n-1
12.7.3：
	AND逻辑：
	N,M两个节点，N,M都取1则为1，否则为0.
12.7.4：

1.回头看第二遍吧，仔细研究研究编译器！时间就不知道了，唉。
2.使用C++语言，把编译器前端代码写一遍，巩固巩固学习的内容，再理解理解编译原理。

学习编译原理，首先需要学习离散数学，具有一定的数学功底，否则看文法、正则表达式和自动机很迷茫。原本以为离散数学只是一些数学基础，集合、概率等，学过机器学习，知道一些逻辑、谓词逻辑等知识，最近看到Stanford的计算机基础那本书，才知道离散数学非常非常非常重要，是计算机科学的基础，里面就有上下文文法、正则表达式、(非)确定自动机等知识。因此，才明白学习离散数学是学习编译原理的基础。