拖了快半年了，终于把《硬件/软件接口》过完了，第一遍看的比较粗略，也深深地意识到深入学CPU的难度之大T_T，回来先把编译原理的坑给填了吧Q_Q。

课后答案：http://dragon-book.jcf94.com/
官方主页：http://dragonbook.stanford.edu/

看了几章，感觉《龙书》里面废话很多啊，很多东西都重复讲了好多遍，而且感觉第二章很多余。

不知道是不是我太肤浅了。

1. Introduction

引论

1.1 language processors

语言处理器

区别一下编译器（Compiler）和解释器（Interpreter）：

高级语言的源程序经过编译器编译后产生目标程序，然后将数据输入目标程序得到输出结果；解释器则是同时将数据和源程序输入，利用输入的数据来执行源程序中指定的操作，得到输出。

通常，一个完整的语言处理系统（高级语言编译器）由以下几部分组成：

高级语言通过一系列步骤，最终生成能够在机器上执行的机器码。

1.2 the structure of a compiler

编译器的结构

编译器整体上可以分为两个部分：分析部分（前端）和综合（后端）。

分析是将源程序分解成多个组成要素，收集有关的信息放在一个符号表（Symbol Table）里，并产生一个中间表示形式。

综合则是根据上一步得到的符号表和中间表示形式进一步生成机器码。

常把编译的过程分成5个阶段：

Lexical Analysis 词法分析
Parsing 语法分析
Semantic Analysis 语义分析
Optimization 中间代码生成和优化
Code Generation 代码生成

1.3 the evolution of programming languages

程序设计语言的发展历程

1.4 the science of building a compiler

构建编译器的科学

1.5 applications of compiler technology

编译技术的应用

1.6 programming language basics

程序设计语言基础

1.7 summary of chapter 1

1.8 references for chapter 1

2. A Simple Syntax-directed Translator

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

2.1 introduction

引言

2.2 syntax definition

语法定义

本节定义了一种上下文无关文法（Context-free Grammar），其由四个元素组成：

一个终结符号集合：文法中语言基本符号的集合
一个非终结符号集合：每个非终结符号表示一个终结符号串的集合
一个产生式集合：
箭头左边称为产生式头，右边称为产生式体。用于表示某个构造的某种书写形式。意为：产生式头 可以具有 产生式体 的形式
指定一个非终结符号为开始符号

有了明确的定义之后，文法推导就是：
从开始符号出发，不断将某个非终结符号替换为该非终结符号的某个产生式的体。
则可以从开始符号推导出来的所有终结符号串的集合，即称为该文法定义的语言。

语法分析（Parsing）的任务是：接受一个终结符号串作为输入，找出从文法开始符号推导出这个串的方法。

如果不能推导出来，则报告该符号串中包含语法错误。

2.3 syntax-directed translation

语法制导翻译

2.4 parsing

语法分析

2.5 a translator for simple expressions

简单表达式的翻译器

本章是以一个简单的文法制导翻译器为例，介绍编译的过程。

前几节是对中缀转后缀表达式翻译器文法、语法方面的分析。

书中在这里给出了一个极其简单的中缀转后缀的表达式翻译器：

/* ***********************************************
MYID	: Chen Fan
LANG	: JAVA
PROG	: postfix
************************************************ */

import java.io.*;

class Parser
{
	static int lookahead;

	public Parser() throws IOException
	{
		lookahead = System.in.read();
	}

	void expr() throws IOException
	{
		term();
		while(true)
		{
			if (lookahead == '+')
			{
				match('+');
				term();
				System.out.write('+');
			} else
			if (lookahead == '-')
			{
				match('-');
				term();
				System.out.write('-');
			} else return ;
		}
	}

	void term() throws IOException
	{
		if (Character.isDigit((char)lookahead))
		{
			System.out.write((char)lookahead);
			match(lookahead);
		} else throw new Error("Syntax error");
	}

	void match(int t) throws IOException
	{
		if (lookahead == t) lookahead = System.in.read();
		else throw new Error("Syntax error");
	}
}

public class Postfix
{
    public static void main(String[] args) throws IOException 
    {
    	Parser parse = new Parser();
    	parse.expr();
    	System.out.write('\n');
    }
}

平时JAVA用的比较少，正好这时候多熟悉下

2.6 lexical analysis

词法分析

前一节中的翻译器功能比较弱，为了在不改变语法的情况下扩充其功能，在词法分析这一步加入更多内容。

2.7 symbol tables

符号表

词法分析的目的是按照文法从源程序中提取出各种词素，存在符号表中，然后将分析完的词素信息交给语法分析器。

在这里还有个作用域的问题，因此符号表的整体结构是一个栈的形态，每进到一个新的代码块中，就应该多建立一个符号表，查找变量定义时，则是从内层向外层逐层查询。

2.8 intermediate code generation

生成中间代码

2.9 summary of chapter 2

3. Lexical Analysis

词法分析

3.1 the role of the lexical analyzer

词法分析器的作用

3.2 input buffering

输入缓冲

3.3 specification of tokens

词法单元的规约

介绍了正则表达式的相关规则。

3.4 recognition of tokens

词法单元的识别

介绍了使用状态转换图来分析词法单元的方法。

3.5 the lexical-analyzer generator lex

词法分析器生成工具Lex

3.6 finite automata

有限自动机

有限自动机是一种识别器，它们只能对每个可能的输入串回答是或者否。

有限自动机可以分为两类：

不确定的有限自动机（Nondeterministic Finite Automata）
对边上的标号没有限制，同一个标号可能有多条离开一个状态的边
确定的有限自动机（Deterministic Finite Automata）
每个状态下对于每个独立的符号，只有一条边

正则表达式 $(a|b)^*abb$ 的NFA和DFA示例：

NFA抽象地表示了用来识别某个语言串的算法，DFA则是一个具体可以实现该语言串的算法。

3.7 from regular expressions to automata

从正则表达式到自动机

通常有了正则表达式就很容易得到它的NFA，而模拟NFA对于软件来说肯定是没有模拟DFA来的方便。因此常要将NFA转化为DFA，再交给软件去模拟。（当然，有时候从NFA到DFA的转化代价可能要大于直接模拟NFA，这时候就不会考虑再转化了）

书中介绍了一种广搜算法来完成NFA到DFA的转化。

子集构造法

initially, t-closure(so) is the only state in Dstates, and it is unmarked;
while ( there is an unmarked state T in Dstates )
{
	mark T;
	for ( each input symbol a )
	{
		U = t-closure( move(T, a) );
		if ( U is not in Dstates )
			add U as an unmarked state to Dstates;
		Dtran[T, a] = U;
	}
}

计算t-closure(T)

push all states of T onto stack;
initialize t-closure(T) to T;
while ( stack is not empty )
{
	pop t, the top element, off stack;
	for ( each state u 'with an edge from t to u labeled 空集)
	if ( u is not in t-closure(T) )
	{
		add u to t-closure(T);
		push u onto stack;
	}
}

3.8 design of a lexical-analyzer generator

词法分析器生成工具的设计

3.9 optimization of dfa-based pattern matchers

基于DFA模式匹配器的优化

3.10 summary of chapter 3

3.11 references for chapter 3

4. Syntax Analysis

语法分析

4.1 introduction

引论

4.2 context-free grammars

上下文无关文法

4.3 writing a grammar

设计文法

4.4 top-down parsing

自顶向下的语法分析

4.5 bottom-up parsing

自底向上的语法分析

4.6 introduction to lr parsing: simple lr

LR语法分析技术介绍：简单LR

4.7 more powerful lr parsers

更强大的LR语法分析器

4.8 using ambiguous grammars

使用二义性文法

4.9 parser generators

语法分析器生成工具

4.10 summary of chapter 4

4.11 references for chapter 4

5. Syntax-directed Translation

语法制导的翻译

5.1 syntax-directed definitions

语法制导定义

5.2 evaluation orders for sdd’s

SDD的求值顺序

5.3 applications of syntax-directed translation

语法制导翻译的应用

5.4 syntax-directed translation schemes

语法制导的翻译方案

5.5 hnplementing l-attributed sdd’s

实现L属性的SDD

5.6 summary of chapter 5

5.7 references for chapter 5

6. Intermediate-code Generation

中间代码生成

6.1 variants of syntax trees

语法树的变体

6.2 three-address code

三地址代码

6.3 types and declarations

类型和声明

6.4 translation of expressions

表达式的翻译

6.5 type checking

类型检查

6.6 control flow

控制流

6.7 backpatching

回填

6.8 switch-statements

switch语句

6.9 intermediate code for procedures

过程的中间代码

6.10 summary of chapter 6

6.11 references for chapter 6

7. Run-time Environments

运行时环境

7.1 storage organization

存储组织

7.2 stack allocation of space

空间的栈式分配

7.3 access to nonlocal data on the stack

栈中非局部数据的访问

7.4 heap management

堆管理

7.5 introduction to garbage collection

垃圾回收概述

7.6 introduction to trace-based collection

基于跟踪的回收概述

7.7 short-pause garbage collection

短停顿垃圾回收

7.8 advanced topics in garbage collection

垃圾回收中的高级论题

7.9 summary of chapter 7

7.10 references for chapter 7

8. Code Generation

代码生成

8.1 issues m the design of a code generator

代码生成器设计中的问题

8.2 the target language

目标语言

8.3 addresses in the target code

目标代码中的地址

8.4 basic blocks and flow graphs

基本块和流图

8.5 optimization of basic blocks

基本块的优化

8.6 a simple code generator

一个简单的代码生成器

8.7 peephole optimization

窥孔优化

8.8 register allocation and assignment

寄存器分配和指派

8.9 instruction selection by tree rewriting

通过树重写来选择指令

8.10 optimal code generation for expressions

表达式的优化代码的生成

8.11 dynamic programming code-generation

动态规划代码生成

8.12 summary of chapter 8

8.13 references for chapter 8

9. Machine-independent Optimizations

机器无关优化

9.1 the principal sources of optimization

优化的主要来源

9.2 introduction to data-flow analysis

数据流分析简介

9.3 foundations of data-flow analysis

数据流分析基础

9.4 constant propagation

常量传播

9.5 partial-redundancy elimination

部分冗余的消除

9.6 loops in flow graphs

流图中的循环

9.7 region-based analysis

基于区域的分析

9.8 symbolic analysis

符号分析

9.9 summary of chapter 9

9.10 references for chapter 9

10. Instruction-level Parallelism

指令级并行

10.1 processor architectures

处理器体系结构

10.2 code-scheduling constraints

代码调度约束

10.3 basic-block scheduling

基本块调度

10.4 global code scheduling

全局代码调度

10.5 software pipelining

软件流水线化

10.6 summary of chapter 10

10.7 references for chapter 10

11. Optimizing for Parallelism and Locality

并行性和局部性优化

11.1 basic concepts

基本概念

11.2 matrix multiply: an in-depth example

矩阵乘法：一个深入的例子

11.3 iteration spaces

迭代空间

11.4 aftlne array indexes

仿射的数组下标

11.5 data reuse

数据复用

11.6 array data-dependence analysis

数组数据依赖关系分析

11.7 finding synchronization-free parallelism

寻找无同步的并行性

11.8 synchronization between parallel loops

并行循环之间的同步

11.9 pipelining

流水线

11.10 locality optimizations

局部性优化

11.11 other uses of affine transforms

仿射转换的其他用途

11.12 summarv of chapter 11

11.13 references for chapter 11

12. Interprocedural Analysis

过程间分析

12.1 basic concepts

基本概念

12.2 why interprocedural analysis?

为什么需要过程间分析

12.3 a logical representation of data flow

数据流的一种逻辑表示方式

12.4 a simple pointer-analysis algorithm

一个简单的指针分析算法

12.5 context-insensitive interprocedural analysis

上下文无关的过程间分析

12.6 context-sensitive pointer analysis

上下文相关指针分析

12.7 datalog implementation by bdd’s

使用BDD的Datalog实现

12.8 summary of chapter 12

12.9 references for chapter 12

a. A Complete Front End

一个完整的编译器前端

a.1 the source language

源语言

a.2 main

Main

a.3 lexical analyzer

词法分析器

a.4 symbol tables and types

符号表和类型

a.5 intermediate code for expressions

表达式的中间代码

a.6 jumping code for boolean expressions

布尔表达式的跳转代码

a.7 intermediate code for statements

语句的中间代码

a.8 parser

语法分析器

a.9 creating the front end

创建前端

b. Finding Linearly Independent Solutions

Index
寻找线性独立解

待续…