编译的学习和实践日志七[有穷自动机]

  "早起才能早睡" 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)中有且仅有一条该符号标记的离开同一状态的边。
DFANFA的特例,跟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
 

NFADFA能识别的语言集合与正则表达式描述的语言集合都是相同的,统称这种语言为正则语言(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

091205日


相关博文

This entry was posted in 程序设计, 编译与语言 and tagged , . Bookmark the permalink.

13 Responses to 编译的学习和实践日志七[有穷自动机]

  1. kingsamchen says:

    某次考试结束后去旧书店逛的时候,偶然在一本程序员中看到了RE的DFA和NFA的分析~

  2. davelv says:

    Re KC: RE是谁呢?

  3. fujianfafu says:

    很NB,异常深奥

  4. heizhao says:

    估计整个中国对于编译原理的研究的人都不多。市面上编译原理的书少之又少~~

  5. davelv says:

    <div class="quote"><span class="q"><b>武科大 黑照(Java学生)</b>: 估计整个中国对于编译原理的研究的人都不多。市面上编译原理的书少之又少~~</span></div>其实情况是,我们学校连个教编译原理的老师都没有…

    这样的大学/专业赶紧撤了吧,别再误人子弟了.都改成高职算了

  6. kingsamchen says:

    Re
    RE是Regular Expression

  7. heizhao says:

    <div class="quote"><span class="q"><b>CAS davelv(C/C++学生)</b>: 其实情况是,我们学校连个教编译原理的老师都没有…

    这样的大学/专业赶紧撤了吧,别再误人子弟了.都改成高职算了</span></div>推荐你看《程序语言设计原理》上面讲得很明白。是机械工业还是电子工业就记不得了

  8. heizhao says:

    手头有。concepts of programming languages

    fifth edition

    robert w.sebesta

    加油研究以后向你请教,机械工业的

  9. davelv says:

    <div class="quote"><span class="q"><b>武科大 黑照(Java学生)</b>: 手头有。concepts of programming languages

    fifth edition

    robert w.sebesta

    加油研究以后向你请教,机械工业的</span></div>我买了<编译原理>(Compilers:Principles,Techniques,& Tools)不过最近毕业设计,没有时间看这个了。

    说不上请不请教的,大家都是互相学习

  10. lovethinkpad says:

    呵呵!还是编程高手呀!

  11. hxx_study says:

    美女,还是帅哥呢哎,不管了,那就hello,你在做C编译器?是计算机的小硕?

  12. davelv says:

    <div class="quote"><span class="q"><b>黄贤夏(嵌入式学生)</b>: 美女,还是帅哥呢哎,不管了,那就hello,你在做C编译器?是计算机的小硕?</span></div>Hello~~我是本科学生…原本打算做的,估计今年没时间了,明年继续…

  13. 梦之翼 says:

    这周正好学了编译原理的这部份,我们系唯一的NB老师,就是这编译原理老师了!唉,我做linux的研究都得自己通过搜索引擎啊

发表评论

电子邮件地址不会被公开。 必填项已用*标注