编译原理 × Haskell

Talk is Cheap

这周上编译系统课，讲词法分析，讲到了很多归纳 / 递归 / 树形结构 / … 相关的内容，这也太——适合放在 Haskell 里写了，加上这些函数这么纯，多适合用函数式的语言实现. 于是开始着手做这件事情，我们小组讨论的选题是 NFA （Nondeterministic Finite Automaton）转 DFA （Deterministic Finite Automaton），于是先从这里开始.

Show Me the Code

项目的 GitHub 地址：Compiler in HS

希望后续可以多写点代码，不要让 NFA2DFA 成为留守模块.

数据抽象

首先对 NFA, DFA 做数据抽象，根据两者的形式化定义，如下：

type Symbol = Char 

type State = Int
type StatesCollection = Set.Set State

type NfaTransition = Map.Map (State, Maybe Symbol) (Set.Set State) 
type DfarTransition = Map.Map (State, Maybe Symbol) State 
type DfaTransition = Map.Map (StatesCollection, Maybe Symbol) StatesCollection 

data NFA = NFA {
    startState :: State,
    stateSet   :: Set.Set State,
    acceptSet  :: Set.Set State,
    alphabet   :: Set.Set Symbol,
    transition :: NfaTransition
} deriving Show 

data DFA = DFA {
    startStates     :: StatesCollection,
    alphabt         :: Set.Set Symbol,
    collectionSet   :: Set.Set StatesCollection,
    transitionRules :: DfaTransition
    -- acCollectionSet :: Set.Set StatesCollection
} deriving Show

data DFAr = DFAr {                  -- simplified DFA
    startNode    :: State,
    nodeSet      :: Set.Set State,
    acceptNodes  :: Set.Set State,
    alphabat     :: Set.Set Symbol,
    rules        :: DfarTransition
} deriving Show

NFA 就是 NFA 了，DFAr 是简化的 DFA，这样的设计和代码的结构有关系（A.K.A. 想一出是一出，我对代码的结构并没有预先的宏观的设计:）.

[TODO]