编译原理实验报告
实验名称：正规式转换成自动机的图形表示
学号：
姓名：
XX 大学 XX 学院
2021 年 12 月 7 日
一．实验目的
通过正规式转换成DFA图形，掌握这一过程中涉及的正规式、有穷自动机的概
念、相互转换原理及算法实现技术，培养分析问题和解决问题的能力。
二．实验内容
编制和调试一个程序，它将用户输入的正规式转换为以状态图和矩阵形式表示的确定有
穷自动机。要求：
（1）把正规式转换为NFA。
（2）将NFA 确定化为DFA
输入：正规式
输出：最简 DFA 各边的状态和转换条件
三．实验步骤
1．实验设计：（基于实验的内容，构造程序所需的模块）
○
1
输入正规式。
○
2
将正规式中缺少的连接符补全
○
3
将补全连接符之后的正规式转化为后缀式。
○
4
根据得到的后缀式，将正规式转化为 NFA。
○
5
将上一步得到的 NFA 转化为 DFA。
○
6
将得到的 DFA 进一步化简。
2.数据结构：
正规式转为 NFA:
Trans 类:（存放转换条件和转换到的状态）
char incept(转换条件 )
NFA_Node* des(转换状态)
NFA_Noda 类:（存放 NFA 的一个状态）
int stateID(状态名 )
vector<Trans*> t(转换条件和转换状态集合)
bool visit(是否被遍历)
void AddTrans(Trans* tt) （为 stateID 状态添加新的转换条件和转
换状态）
NFA 类：（存放 NFA）
NFA_Node* start(开始状态)
NFA_Node* end(结束状态)
Converter()类（将正规式转为 NFA）
int S_ID
stack<NFA> stNFA(转 NFA 时暂时存放当前已求出的各个 NFA)
stack<char> Operator_Stack（正规式转为后缀式时存放操作符的栈）
string lamb(正规式转为的后缀表达式)
bool isOperator(char c)（判断 c 是否是操作符）
int getOperatorNumber(char t1)（得到 t1 的优先级）
bool Operator_Less_Than(char t1, char t2)（判断 t1 和 t2 的优先
级）
void pretreat(string str)（将正规式连接符补全）
void Houzhui(string lamb)（转为后缀表达式）
NFA& Connect(NFA G1, NFA G2)（G1G2,把 NFA G1 连在 NFA G2 后面）
NFA& Union(NFA G1, NFA G2) (G1|G2)
NFA& Closure(NFA G2) (G2*,求 G2 闭包)
NFA ToNFA()（将正规式转为 NFA）
NFA 转为 DFA:
DFA_Edge 类:（存放转换条件和转换到的状态）
char incept(转换条件)
DFA_Node* des(转换状态 )
bool visit
DFA_Node 类：（存放一个 DFA 状态）
int stateID（状态名）
vector<DFA_Edge*> t（转换条件和转换状态）
vector<int> ori（存放同一状态的 nfa 状态）
bool flag（是否为终态）
NFA_To_DFA 类：（将 NFA 转化为 DFA）
int MaxStatus
int T[MAX][MAX](T[0][0],dfa 状态数，T[I][0]dfa 第 i 个状态的状态
数,T[i][j]dfa 第 i 个状态中的第 j 个 nfa 状态，若
为 0 则代表第 j 个 nfa 状态不在第 i 个 dfa 状态里
)
int visit[MAX]( 求 每 一 次 的 dfa 状 态 时 的 nfa 的 状 态 )
vector<NFA_Node*> tmp( 求 每 个 dfa 状 态 时 暂 时 每 个 存 放
dfa 状态包含的 nfa)
set<char> Alpha(转换条件)
vector<NFA_Node*> nfa(存放要转换的 NFA)
NFA_Node* start(开始结点)
vector<DFA_Node*> dfa（存放转换完的 DFA）
int cando(存 NFA 的终态)
void Init()（将 tmp 清空）
NFA_Node*& find(int st)（返回 nfa 状态 st 的 NFA 结点）
DFA_Node*& finddfa(int st)（返回 dfa 状态 st 的 DFA 结点）
void findclosure(NFA_Node* p)（求与 nfa 状态 p 同一 dfa 状态的
nfa 的状态数）
void closure()（求目前一个 dfa 包含的 nfa 状态数）
int AddStatus()(判断是否产生新状态，若是在 DFA 里添加新状态，返
回-1，若没有产生新状态，返回该状态位置)
void moveto(int st,char c)（找到 dfa 状态 st 通过条件 c 到达的
nfa 状态）
void Convert()（将 NFA 转为 DFA）
void Display()（输出 DFA）
DFA 最小化:
struct edge{
string first;//边的初始结点
string condition;//边上的条件
string last;//边的终点
};
string move(string collection,char ch,edge *b) //状态集合 I
评论10