词法分析器2(ε-NFA到DFA的转换)

DFA的状态
 
在DFA中，某个状态对应到ε-NFA中的若干状态，应此我们将会得到下面这样的一个结构。
 
 
 
        struct DFA_State
        {
            set<EpsilonNFA_State*> content;
            bool                   bFlag;
#ifdef _DEBUG
            uint                   idx;
#endif
 
            DFA_State(const set<EpsilonNFA_State*>& x) : content(x), bFlag(false)
            {
#ifdef _DEBUG
                idx = inc();
#endif
            }
 
            inline const bool operator==(const DFA_State& x)const
            {
                if (&x == this) return true;
 
                return content == x.content;
            }
 
#ifdef _DEBUG
            inline uint inc()
            {
                static uint i = 0;
                return i++;
            }
#endif
        };
 
 
可以看到，为了调试方便我们在结构中定义了状态的唯一ID以及对应到ε-NFA状态的集合和一个标记位。
 
DFA的边
 
根据上一篇的经验，不难想到DFA的边应该是什么样的，下面直接给出代码，不做说明。
 
 
 
        struct DFA_Edge
        {
            struct
            {
                Char_Type   char_value;
                String_Type string_value;
            }data;
 
            enum Edge_Type
            {
                TUnknown = 0,
                TNot     = 1,
                TChar    = 2,
                TString  = 4
            };
 
            uchar edge_type;
 
            DFA_State* pFrom;
            DFA_State* pTo;
 
            DFA_Edge(const Char_Type& x, bool bNot, DFA_State* pFrom, DFA_State* pTo) : pFrom(pFrom), pTo(pTo)
            {
                data.char_value = x;
                edge_type = bNot ? (TChar | TNot) : TChar;
            }
 
            DFA_Edge(const String_Type& x, bool bNot, DFA_State* pFrom, DFA_State* pTo) : pFrom(pFrom), pTo(pTo)
            {
                data.string_value = x;
                edge_type = bNot ? (TString | TNot) : TString;
            }
 
            inline const bool isNot()const
            {
                return (edge_type & TNot) == TNot;
            }
 
            inline const bool isChar()const
            {
                return (edge_type & TChar) == TChar;
            }
 
            inline const bool isString()const
            {
                return (edge_type & TString) == TString;
            }
 
            const Edge_Type edgeType()const
            {
                if (isChar()) return TChar;
                else if (isString()) return TString;
                else return TUnknown;
            }
 
            const bool operator<(const DFA_Edge& x)const
            {
                return (ulong)pFrom + pTo < (ulong)x.pFrom + x.pTo;
            }
 
            const bool operator==(const DFA_Edge& x)const
            {
                return pFrom == x.pFrom && pTo == x.pTo;
            }
        };
 
 
 
 
由于DFA中不存在ε边，应此DFA将会存在若干个结束状态，但他只有一个开始状态
 
 
 
DFA_State*      pDFAStart;
set<DFA_State*> pDFAEnds;
set<DFA_Edge>   dfa_Edges;
 
 
 
 
为了下一步分析的高效，以后可能会将这里的dfa_Edges同样修改为hashmap。
 
至此DFA所要用到的两个结构迅速的介绍完了。
 
子集构造算法
 
通过各种资料，我们不难发现，从ε-NFA转换到DFA的过程中，最常用就是子集构造算法。子集构造算法的主要思想是让DFA的每个状态对应NFA的一个状态集。这个DFA用它的状态去记住NFA在读输入符号后达到的所有状态。（引自编译原理）其算法如下
 
 
 
输入：一个NFA N。
输出：一个接受同样语言的DFA D。
方法：
1.求取ε-NFA初始状态的ε闭包作为DFA的起始状态，并将这个状态加入集合C中，且它是未标记的。同时记录它的向后字符集。
2.从集合C中取出一个未被标记的子集T和其对应的字符集，标记子集T。
3.使用上一步取出的字

补充：综合编程 , 其他综合 ,