"早起才能早睡" from <觉主语录>
有一个月没有更新日志了,dave要宣布一个非常不好的消息：系里以没有老师能够指导编译方向为由，拒绝了我的毕业设计选题。dave当时就想说：诺大一个万余人的University，居然还好意思说没有老师能够指导，这也显得学生我太NB了吧，真不好意思在这里继续读下去了。无奈选择了XX管理系统，所以这日志也应该是我今年最后一篇了吧。
这次内容是有穷自动机(finite automata)，在说这个有穷自动机前需要两个辅助的工具。转换图(transition graph)和转换表(transition
table)。
有穷自动机在本质上是与状态转换图(transition diagram)类似，用来匹配一个输入串。但是它的功能仅限于识别一个输入串是否能够被自动机匹配，返回值要么为真要么为假。有穷自动机分为两类：
1、不确定的有穷自动机（Nondeterministic Finite Automata，以后简称NFA）对其边上标记符号没有任何限制，一个符号可以标记离开同一状态的多个边，空串ε也可以作为标记。
NFA由以下几个部分组成：
1）、一个有穷的状态集合S。
2）、一个输入符号集合Σ，即输入字母表（input alphabet）。
3）、一个转换函数（transition function），它为每个状态和Σ∪{ε}中每个符号都给出了相应的后继状态的集合。
4）、S中的一个状态s0 被指定为开始状态。
5）、S的一个子集F指定为接受状态（或者终止状态）集合。
举例，正则语言(a|b)*abb
转换图-1：
转换表-1：
| a |
b |
ε |
|
| 0 |
0,1 |
0 |
φ |
| 1 |
φ |
2 |
φ |
| 2 |
φ |
3 |
φ |
| 3 |
φ |
φ |
φ |
2、确定由有穷自动机（Deterministic Finite Automata，以后简称DFA）中有且仅有一条该符号标记的离开同一状态的边。
DFA是NFA的特例，跟NFA的区别就是：
1）、没有输入ε的转换动作
2）、对于每个状态s和每个输入符号a，有且仅有一条标号为a的边离开s。
举例，还是上面的正则语言(a|b)*abb
转换图-2：
转换表-2：
| a |
b |
|
| 0 |
1 |
0 |
| 1 |
1 |
2 |
| 2 |
1 |
3 |
| 3 |
1 |
0 |
NFA和DFA能识别的语言集合与正则表达式描述的语言集合都是相同的，统称这种语言为正则语言（regular language）。NFA抽象的表示了用来识别某个语言中串的算法，而对应的DFA则是一个简单具体的识别算法。在构造词法分析器的时候，我们真正实现或者模拟的是DFA。每个正则表达式和NFA都是可以转化为DFA的。接下来就是重点NFA–〉DFA的子集构造法。
子集构造法的主要思想是：让DFA的一个状态对应NFA中一个状态集合，这样来解决NFA中接受某符号后状态不确定的问题。
输入：NFA N
输出：DFA D
操作：move(T,a):返回N中从状态集合T任一状态出发通过符号a转换到达的状态集合。
addInSet(T)：把T加入一个集合
isInSet(T):判断T是否属于集合
push(T):将状态集合T入栈
pop():状态集合T出栈
isEmpty();栈是否空
伪码：
s0=N的初始状态集合;
NIA=N的输入符号集，排除ε;
D[][]=D的状态转换表;
T=move(s0,ε);
addInSet(T);
push(T);
while(!isEmpty())
{
T=pop();
for each token in NIA
{
U=move(move(T,token),ε);
if(!isInSet(U))
{
push(U);
addInSet(U);
}
D[T][token]=U;
}
}
数据演示：就用上面(a|b)*abb的例子
第一次while循环后的D：
| a |
b |
|
| 0 |
0,1 |
0 |
第二次：
| a |
b |
|
| 0 |
0,1 |
0 |
| 0,1 |
0,1 |
0,2 |
第三次：
| a |
b |
|
| 0 |
0,1 |
0 |
| 0,1 |
0,1 |
0,2 |
| 0,2 |
0,1 |
0,3 |
第四次：
| a |
b |
|
| 0 |
0,1 |
0 |
| 0,1 |
0,1 |
0,2 |
| 0,2 |
0,1 |
0,3 |
| 0,3 |
0,1 |
0 |
用A代表0 B代表0,1 C代表0,2 D代表0,3，由于D中包含接受状态3，所以D也是接受状态
| a |
b |
|
| A |
B |
A |
| B |
B |
C |
| C |
B |
D |
| D |
B |
A |
这个表格跟转换表2是一致的，检验了该算法的正确性。
PS：即使一度分离，也终会再次相逢。
davelv
于09年12月05日
某次考试结束后去旧书店逛的时候，偶然在一本程序员中看到了RE的DFA和NFA的分析~
Re KC: RE是谁呢?
很NB，异常深奥
估计整个中国对于编译原理的研究的人都不多。市面上编译原理的书少之又少~~
<div class="quote"><span class="q"><b>武科大 黑照(Java学生)</b>: 估计整个中国对于编译原理的研究的人都不多。市面上编译原理的书少之又少~~</span></div>其实情况是,我们学校连个教编译原理的老师都没有…
这样的大学/专业赶紧撤了吧,别再误人子弟了.都改成高职算了
Re
RE是Regular Expression
<div class="quote"><span class="q"><b>CAS davelv(C/C++学生)</b>: 其实情况是,我们学校连个教编译原理的老师都没有…
这样的大学/专业赶紧撤了吧,别再误人子弟了.都改成高职算了</span></div>推荐你看《程序语言设计原理》上面讲得很明白。是机械工业还是电子工业就记不得了
手头有。concepts of programming languages
fifth edition
robert w.sebesta
加油研究以后向你请教，机械工业的
<div class="quote"><span class="q"><b>武科大 黑照(Java学生)</b>: 手头有。concepts of programming languages
fifth edition
robert w.sebesta
加油研究以后向你请教，机械工业的</span></div>我买了<编译原理>（Compilers:Principles,Techniques,& Tools）不过最近毕业设计，没有时间看这个了。
说不上请不请教的，大家都是互相学习
呵呵！还是编程高手呀！
美女,还是帅哥呢哎,不管了,那就hello,你在做C编译器?是计算机的小硕?
<div class="quote"><span class="q"><b>黄贤夏(嵌入式学生)</b>: 美女,还是帅哥呢哎,不管了,那就hello,你在做C编译器?是计算机的小硕?</span></div>Hello~~我是本科学生…原本打算做的,估计今年没时间了,明年继续…
这周正好学了编译原理的这部份，我们系唯一的NB老师，就是这编译原理老师了！唉，我做linux的研究都得自己通过搜索引擎啊