对编译原理的一点总结(Beta)

编译原理本人学的很差，虽然这是比较专业的课程。像大多数很多课程一样，考试的话虽然我都拿不到优秀，但是我对这些课程的内容都有浓厚兴趣（估计没 人信，有兴趣还学的差？谁信啊？！）。所以，我时常会看一看，总结一下思路（只总结一部分，其他以后看到再补充），记下来，下次看的时候进入状态快一点， 有错误欢迎指正，这个写的东西类似于学习笔记。

1. 概念、基础

首先编程语言分为编译型语言（或者静态（static）、半静态，半动态语言，如c/c++）和解释型语言（或动态（dynamic）语言，如 c#/java/大多数脚本语言），对这两种语言来说”编译”所做的工作是有所不同的。高层次的语言解释执行是一种趋势，现代的面向对象语言一般都是或者 将会设计成解释型语言，因为动态性虽然带来的性能的损失，但是随着计算机性能的提高我们通常会愿意用性能会换取动态语言的灵活性。下面我将会尝试说明两种 语言的编译过程，并在必要的时候指出某个过程是针对哪种语言的。

说一件趣事，会对你立即编译有帮助，编译在英文里面是compile，这个单词不仅用在计算机方面，还用在书籍出版方面，编译汇总一本书籍然后出 版，所以compile基本上是把分散的东西（你自己的多个程序源码文件、程序语言库等）汇总起来（一个目标代码程序）使之有秩序并能为之所用。

编译的流程一般分为以下几个过程。预处理（preprocess，有时候包括在词法分析中）；词法分析（lexical analysis or scanner)；语法分析（syntax analysis）；语义分析（semantic analysis）；代码优化（code optimatization）；目标代码生产（code generation）。通常有两个数据结构与所有这些过程交互，符号表（symbol table）和出错管理器。这些过程一般都以相应模块出现在编译器中。与编译有关的过程还有链接（linking）和加载（loading）。但是对于解 释型语言上面的过程可以归于编译阶段最多到语法分析，其他的过程都是在解释执行时完成的，包括链接、加载、和符号表和出错管理器的交互。

编译器的架构一般采用管道模式（pipe line design pattern），可以想想bash命令行的使用中的管道模式，但是区别是编译器里面有”遍（pass）”的概念。

编译技术为了重用和方便建造，把编译阶段分为前端和后端，有一套理论（如自展）来指导如何用一种语言来生成另一种语言的编译程序，例如如何用同一种语言来生成自身语言的编译程序。

2. 预处理、词法分析

对于编译型语言和解释型语言来说，这两个过程大体相似。

预处理完成的基本上是清洁、整理源代码的作用，包括删除注释，替换宏（或者等价的inline结构）等等。现代的程序语言有一种趋势，把越来越多的 工作尽可能提到编译的前阶段来处理（只要是理论上允许，不对整个编译架构产生影响），如预处理程序能检查保留字的拼写，简单的语法错误等等。

对于注释，现代的程序语言越来越倾向于采取可识别语义的注释，如Java中的javadoc格式和annotation。这些注释本身就是另一种语言，并有可能（如annotation）对它注释的语义有补充、限制的作用。

词法分析完成的工作主要是把程序源代码中出现关键字、标识符、常量等用一种中间表示替代，在这一过程中主要涉及到符号表和出错管理器就会被建立。

3. 语法分析

4. 语义分析

5. 代码优化

6. 目标代码生成

7. 加载

8. 解释型语言的编译、加载、执行过程

下面大体以Java为代表说一下解释型语言的编译过程。

调用Javac把程序源代码java文件处理成二进制的class文件，这就是Java全部的所谓的编译过程，class文件可以理解为一种中间表示，JVM规范中定义了其格式，在class文件里面会建立常量表。

当用Java命令运行java程序（class 文件）时，JVM会接管从class文件到能够使你的程序运行起来、接受用户输入的全部过程。

JVM首先会用内建的bootstrap class loader加载一些必须的核心类（如rt.jar, i18n.jar等），这个加载过程对于运行任何java程序都是一样的。接着会使用Extension loader（不确定是属于bootstrap class loader范畴还是属于System class loader范畴）加载JAVA_HOME\LIB\EXT目录下的类，最后按照一定顺序和需要加载位于CLASSPATH上的类。可以在运行java程 序时使用下面的参数看详细的加载过程。

Setting the parameter -verbose:class on the java command line prints a trace of the class loading process.

关于加载器的整个层次架构可以看资源里面的相应的文章。加载后的每一个类会用一个Class类的实例表示，这些Class实例就是JVM内部可以识 别的关于类的所有信息。一个类加载器加载的类对这个加载器和他所有的子加载器可见，对其他的类加载器不可见，也就是说如果这些不可见的类加载器也加载了同 样的类，那么这两个类实例在JVM内部会被识别成两个类。

加载后进行的一个过程是链接（linking），包括验证（verification，验证加载的class是否是well-formed），准备 （preparation，为静态存储和JVM中内部使用的数据结构如method talbe（类比C++中的VTABLE）分配空间），解析（Resolution，解析一个类中引用到的所有类，这可能又包括一个递归的加载、链接过 程）。

之后进行的是一个初始化过程，包括静态变量的初始器（initializer）和静态结构（如static {}）的初始器。接下来进行新的类实例的创建并进入程序的运行状态。

下面把这个过程和编译型语言的编译过程进行一个非常不严格的类比，以方便理解。

类加载创建Class实例和分配空间的初始化过程可能有点像编译型语言的代码生成过程，生成可以运行的二进制程序，但是生成的二进制程序不会进行固 化存储。链接过程中的验证执行的是一部分的语法分析和全部的语义分析，这可能和编译型语言的编译过程倒过来了。最后的类实例的创建过程可能和编译型语言的 加载二进制程序文件（类比Class的实例）并运行的过程有点类似，包括JVM也会类似于活动记录（Activation Record）的Method Frame结构，包括动态链、静态链，这些结构JVM也都会创建。

（临时发布草稿，还会不断更新补充）

Resources:

1. 侯文永，张冬茉，《编译原理》，电子工业出版社
2. The JavaTM Virtual Machine Specification Second Edition
3. The Java Language Specification, Third Edition
4. 金山词霸
5. Java programming dynamics, Part 1: Classes and class loading
6. Understanding Extension Class Loading
7. Bootstrap class loader
   

Technorati : compiler, compiler construction, compiler theory, java, programming language
Del.icio.us : compiler, compiler construction, compiler theory, java, programming language
Zooomr : compiler, compiler construction, compiler theory, java, programming language

关于正则表达式

说明：作者放弃本文的所有权力，本文摘录自其他资料，仅作自己学习之用，请尊重摘录源的作者的版权。

1. 基本概念

正则表达式最早是由数学家Stephen Kleene于1956年提出，正则表达式并非一门专用语言，但它可用于在一个文件或字符里查找和替代文本的一种标准。正则表达式经过几个时期的发展，现在的标准已经被ISO(国际标准组织)批准和被Open Group组织认定。

2. 正则表达式基础

正则表达式由一些普通字符和一些元字符（metacharacters）组成。普通字符包括大小写的字母和数字，而元字符则具有特殊的含义。

元字符		描述
.		匹配任何单个字符。例如正则表达式r.t匹配这些字符串：rat、rut、r t，但是不匹配root。
$		匹配行结束符。例如正则表达式weasel$ 能够匹配字符串"He's a weasel"的末尾，但是不能匹配字符串"They are a bunch of weasels."。
^		匹配一行的开始。例如正则表达式^When in能够匹配字符串"When in the course of human events"的开始，但是不能匹配"What and When in the"。
*		匹配0或多个正好在它之前的那个字符。例如正则表达式.*意味着能够匹配任意数量的任何字符。
\		这是引用府，用来将这里列出的这些元字符当作普通的字符来进行匹配。例如正则表达式\$被用来匹配美元符号，而不是行尾，类似的，正则表达式\.用来匹配点字符，而不是任何字符的通配符。
[ ] [c1-c2] [^c1-c2]		匹配括号中的任何一个字符。例如正则表达式r[aou]t匹配rat、rot和rut，但是不匹配ret。可以在括号中使用连字符-来指定字符的区间，例如正则表达式 [0-9]可以匹配任何数字字符；还可以制定多个区间，例如正则表达式[A-Za-z]可以匹配任何大小写字母。另一个重要的用法是"排除"，要想匹配 除了指定区间之外的字符--也就是所谓的补集--在左边的括号和第一个字符之间使用^字符，例如正则表达式[^269A-Z] 将匹配除了2、6、9和所有大写字母之外的任何字符。
\< \>		匹配词（word）的开始（\<）和结束（\>）。例如正则表达式\能够匹配字符串"for the wise"中的"the"，但是不能匹配字符串"otherwise"中的"the"。注意：这个元字符不是所有的软件都支持的。
\( \)		将 \( 和 \) 之间的表达式定义为"组"（group），并且将匹配这个表达式的字符保存到一个临时区域（一个正则表达式中最多可以保存9个），它们可以用 \1 到\9 的符号来引用。
|		将两个匹配条件进行逻辑"或"（Or）运算。例如正则表达式(him|her) 匹配"it belongs to him"和"it belongs to her"，但是不能匹配"it belongs to them."。注意：这个元字符不是所有的软件都支持的。

---

3. 程序语言或环境的支持

4. 实例

临时发布，待续

Resources：

1. 揭开正则表达式语法的神秘面纱


2. 正则表达式之道

Technorati : re, regular expression, 字符匹配, 正则表达式
Del.icio.us : re, regular expression, 字符匹配, 正则表达式