编译原理实验二 XLEX

# XLEX 软件文档

# 关于

SCNU-CS 编译原理实验二，本来想好好写一写的，但是时间紧迫，先水一水吧，以后有时间再改一改。（还有 bug 没改）

# 作者

@dzcgood

# 开发环境

Qt Creator 4.11.1(Community)

# 顶层程序流程图

# 实现思路

# this | nfa 选择

设 this 和 nfa 都代表一个 nfa 图，则执行‘|’操作只需要新建 startNode 和 endNode 和四条边，将二者连接即可。

# thisnfa 连接

直接把 this->endNode 和 nfa -> startNode 之间加一条 NFAEdge 连起来

# a* 闭包

需要新建 startNode 和 endNode，和 nfa 前后连起来，然后把 nfa 的 startNode 和 endNode 连起来。总结一下，就是新建两个结点和四条边。

# 生成 NFA

获取 NFA 图，由输入的正则表达式产生 NFA

正则表达式转 NFA 递归方法思路： 首先把 (…) 看成一个单元素 NFA, 和 a 等价，把单个 NFA 看成一个或数个元素的 Union，即 NFA = a [|b|c…]。扫描正则表达式，首先扫描 | 进行拆分递归，逐项建立 NFA 后，用 ‘|’ 连接，对于括号要进行进行递归处理

# 生成 DFA

分为两个步骤：

• 给 NFA 的结点编号并建立初始 DFA 结点
• 确定结点与结点之间的关系，建立 DFA 的边

# NFA 结点编号，建立 DFA 结点

# 建立 DFA 的边

# 最小化 DFA

分为两个步骤：

• 求初态集合、终态集合并对这些集合进行划分，建立最后的 DFANode
• 建立 DFANode 之间的边，形成最小 DFA 图

# 集合划分，建立 DFANode

# 建立 DFANode 的边

# 生成 c 语言代码

对于从个某结点出发的每一条边，分为两类，指向自己的，以及指向下一个结点的。对于指向自己的边，生成 while 语句；对于指向下一个结点的边，生成 if 语句，并且需要递归进入下一个结点，直到当前结点的状态为 END 时，结束递归，并回调。

# 枚举、结构体、类设计

# 枚举

定义了一个枚举 State，用于标记每个结点的状态，包括 START（开始节点）, END（结束结点）, NORMAL（其他结点）

/**
    定义各个结点的状态：开始，结束，普通
*/
enum State{
    START,END,NORMAL
};

# 结构体

共四个结构体，NFANode，NFAEdge，DFANode，DFAEdge，分别代表一个 NFA 图的结点、一条 NFA 图的边、一个 DFA 图的结点、一个 DFA 图的边。接下来详细说明四个结构体的具体定义。

# NFANode

DFANode 用来描述一个 NFA 图的结点，其属性包括编号（id），状态 (state)，入边 (inEdges)，出边 (outEdges)

/**
    NFA的结点
*/
struct NFANode{
    //唯一标记结点
    int id;
    //标实该结点是否为开始结点或结束结点
    State state;
    //入边
    vector<NFAEdge> inEdges;
    //出边
    vector<NFAEdge> outEdges;
    //构造函数
    NFANode(int i, State s) : id(i), state(s){}
    //空参构造函数
    NFANode(): id(DEFAULT_ID), state(NORMAL){}
};

# NFAEdge

NFAEdge 用于描述一条 NFA 图中的边，其属性包括开始结点 (startNode)，结束结点 (endNode)，处理的字符 (word)

/**
    NFA的边
*/
struct NFAEdge{
    //该边由startNode指向endNode
    NFANode * startNode;
    NFANode * endNode;
    //该边处理字符word
    char word;
    //构造函数
    NFAEdge(NFANode * s, NFANode * e, char c): startNode(s), endNode(e), word(c){}
    //空参构造函数
    NFAEdge(): startNode(NULL), endNode(NULL), word('\0'){}
};

# DFANode

DFANode 用于描述一个 DFA 图的结点，其属性包括该结点的 EPSILION 闭包 (nodes)，由该结点出发的边 (edges)，结点名 (minName)，状态 (state)，还有一系列的操作，如插入边，插入结点，输出结点信息等

//DFA结点
struct DFANode
{
    //该结点的EPSILION闭包
    set<int> nodes;
    //由该结点出发的边
    vector<DFAEdge> edges;
    //给这个结点取个名字，A, B, C, D
    string minName;
    //该结点在DFA图中的状态
    State state = NORMAL;
    //判断结点id是否在该结点中
    bool contains(int id);
    //在该结点插入id
    void insert(int id);
    //在该结点插入边
    void insert(DFAEdge edge);
    //将两个结点合成一个结点
    void unionNode(DFANode * node);
    //该结点处理字符c后转变为的结点
    DFANode * process(char c);
    //输出该结点信息 如： {1，2，4，6}
    string toString();
};

# DFAEdge

DFAEdge 用于描述一条 DFA 图的边，其属性包括指向的结点（next）和处理的字符（word）

//DFA边
struct DFAEdge
{
    //边指向的结点
    DFANode * next;
    //处理的字符
    char word;
    //构造函数
    DFAEdge(DFANode *n, char c): next(n), word(c){}
};

# 类

一共定义了三个类，分别是 NFA, DFA, Proxy，其中 NFA 和 DFA 类分别代表一个 NFA 图和 DFA 图，Proxy 是代理类，用于代理有关 NFA 和 DFA 类的操作，具体包括生成 NFA 图、给 NFA 图编号并生成 DFA 图、最小化 DFA 图、生成 c 语言代码等操作。

# NFA

主要涉及到选择（a | b）闭包（a*），连接（ab）操作

/**
    NFA类，集成构建NFA图的操作
*/
class NFA{
public:
    //NFA图的开始结点
    NFANode * startNode;
    //NFA图的结束结点
    NFANode * endNode;
    //结点个数
    int nodeNumber;
    //空参构造函数
    NFA():startNode(NULL), endNode(NULL), nodeNumber(2){}
    //初始化一个处理字符c的NFA图
    //这里原作者id的类型是char ？？？ 暂时没看懂，，先改成 int
    NFA(char c, int id1, int id2);
    //初始化一个识别c的标号未定的NFA图
    NFA(char c);
    //已知开始结点和结束结点
    NFA(NFANode * s, NFANode * e): startNode(s), endNode(e){}
    //浅复制
    void operator=(const NFA &nfa);
    // a | b 选择
    void Or(const NFA &nfa);
    // ab 连接
    void And(const NFA &nfa);
    // a* 闭包
    void Star();
    //当前NFA图是否为空
    bool isEmpty() const;
    //id对应的结点是不是endNode
    bool isEnd(int id) const;
    //获取endNode的id
    int getEndId() const;
    //获取startNode的id
    int getStartId() const;
};

# DFA

用于描述一个 DFA 图，其主要操作涉及到由该结点生成该结点对应的 c 语言代码

//DFA类

class DFA
{
public:
    //DFA图的结点
    vector<DFANode*> graph;
    //通过id返回图的结点
    vector<DFANode*> getNodes(int id);
    //DFA图最小开始结点
    DFANode *minStartNode;
    //DFA图最小结束结点
    vector<DFANode*> minEndNodes;
    //能处理的字符
    set<char> wordList;
    //建一个新结点
    DFANode* crateNewNode(int id);
    //判断两个结点的转化是否等价，若转化后是同一个结点，则等价
    static bool equals(DFANode *node1, DFANode *node2, set<char> words);
    //判断该结点是否为结束结点
    bool isEndNode(DFANode *node) const;
    //从当前DFA中删除某个结点
    void delNode(DFANode *node);
    //获取该结点的c语言代码，n是结点指针，lines是生成的代码，tabNumber是缩进数
    void getCode(DFANode *n, vector<string> &lines, int tabNumber);
private:
    //获取缩进的空格
    string getTabs(int tabNumber);
};

# Proxy

代理 NFA 和 DFA 的操作，包括产生 NFA，产生 DFA，最小化 DFA

class Proxy
{
public:
    //正则表达式
    string regularExpression;
    //NFA图
    NFA nfa;
    //最初始的DFA图
    DFA dfa;
    /*
        经过处理后的DFA图
        因为有好几个结点最后会合成一个结点，所以minDFA其实是有好多个vector组成的，
        每个vector元素又包含了好几个结点，这写结点最后会被合成一个结点
        例子： minDFA = {{1}， {3，5，7}, {2,4}, {6,8}}
     */
    vector<vector<DFANode *>> minDFA;
    //最终的DFA
    DFA finalDFA;
    //DFA最小化生成的表格
    char chart[MAX_NODE_NUMBER][MAX_NODE_NUMBER];
    //最后生成的代码
    string code;
    //能处理的字符集
    set<char> wordList;
    //构造函数，用正则表达式来初始化Proxy代理类
    Proxy(const string regExp);
    //给NFA的结点编号并建立初始DFA结点
    void serializeNFA();
    //初始DFA图后处理
    void processDFA();
    //最小化DFA
    void minimizeDFA();
    //最小DFA图后处理
    void processMinDFA();
    //生成c语言代码
    void generateCode();
private:
    //获取NFA图，由输入的正则表达式产生NFA
    NFA getNFA(const string regExp);
    //把正则表达式看成 a | b | c的形式，以'|'为分隔符号，所以要先获取'|' 的索引
    vector<int> getOrOperatorIndex(const string regExp);
    //判断ch是不是字符（字母或数字）
    bool isLetter(char ch);
    //获取索引为index的左括号对应的右括号的索引，在初始化NFA的时候会用到
    int getRightBracketIndex(const string regExp, const int leftIndex);
    //用于得知id号结点可以有哪些转化
    vector<int> getConnections(int id);
};