globals.h

一个大学时候做的编译原理的实验.实验内容是正则表达式到NFA到DFA到最小化DFA最终生成词法分析代码的整个过程的演示.那时由于时间关系,词法分析代码自动生成部分还没完成.

#ifndef _GLOBALS_H_
#define _GLOBALS_H_

#include "stdafx.h"
#include "AutoMakeView1.h"
#include "AutoMakeView2.h"
#include "AutoMakeView3.h"

#include <iostream.h>
#include <math.h>
#include <list>
#include <stack>
#include <queue>
using namespace std;

#pragma comment(lib,"winmm.lib")
#include<mmsystem.h>

typedef int State;//定义状态的类型
typedef char Symbol;//定义元字符类型

typedef struct
{
	State start;
	State end;
}NFA;//定义NFA始态和终态

typedef struct
{
	State state;
	Symbol symbol;
}Node;//NFA邻接表元素类型

/////////////////////////////
typedef struct
{
	int x;//某一状态的x坐标
	int y;//某一状态的y坐标
}CNode;//coordinate node用来表示结点的位置
///////////////////////////////

typedef struct
{
	State start;
	State end;
	Symbol symbol;
}ARC;//边

/*NFA的数据结构*/
typedef list<Node> NODE_LIST;//节点链表
typedef list<NODE_LIST> NFA_LIST;//NFA列表
typedef list<char> LETTER_LIST;//字母表
/*NFA的数据结构*/


//////////////////////////以下是用来处理画图的结构
typedef list<CNode> CNODE_LIST;//坐标节点链表
typedef list<State> STATE_CHAIN;//状态链表，用来保存与运算相关联的状态组
typedef list<STATE_CHAIN> STATE_STACK;//状态链表栈
/////////////////////////////////////////////


/*DFA数据结构*/
typedef list<State> STATE_LIST;//状态集

typedef struct
{
	STATE_LIST statelist;
	Symbol symbol;
}StateListNode;//状态集节点

typedef list<StateListNode> STATELISTNODE_LIST;//状态集节点列表

typedef struct
{
	STATE_LIST dstate;
	STATELISTNODE_LIST slnList;
}TransListNode;//保存一个状态集经过所有元字符所到达的状态集

typedef list<TransListNode> TRANS_LIST;//DFA转换表
/*DFA数据结构*/
extern CString rExp;//正则表达式

extern NODE_LIST* NFA_List;//保存NFA图
extern LETTER_LIST letterlist;//保存NFA字母表
extern NFA objNFA;//保存NFA的初始状态和终止状态
extern int StateSum;//记录NFA的总状态数

extern STATE_LIST* DFAStateArray;//DFA状态集查询表
extern NODE_LIST* DFAtransArray;//DFA状态转换表
extern int DFAStateNum;//DFA状态总数
extern STATE_LIST startlist;//DFA开始状态集
extern STATE_LIST acceptlist;//DFA接受状态集

extern STATE_LIST* MinDFAStateArray;//最小化DFA状态集查询表
extern NODE_LIST* MinDFAtransArray;//最小化DFA状态转换表
extern int MinDFAStateNum;//DFA状态总数

/*对外接口函数*/
extern bool BuildNFA(CString& r);//创建NFA
extern void BuildDFA();//创建DFA
extern void MinDFA();//最小化DFA

extern void ClearNFA();//清空数据结构里保存的东西
extern void ClearDFA();//清空数据结构里保存的东西
extern void ClearMinDFA();//清空数据结构里保存的东西

/*显示函数*/
extern void DrawArrow(CDC* pDC,CPoint& start,CPoint& end);
extern void DrawArc(CDC* pDC,CPoint& start,CPoint& end,int r,CString str);//画曲线箭头
extern void DrawArc(CDC* pDC,CPoint& point,int r,int n,CString str);//重载画曲线箭头，处理只有一个结点的情况
extern void AutoShowNFA(CDC* pDC,CAutoMakeView1*pView);//演示NFA生成过程
extern void PaintNFA(CDC* pDC,list<int>::iterator curiter);//显示NFA
extern void PaintDFA(CDC* pDC,CAutoMakeView2*pView);//显示DFA和转换表
extern void PaintMinDFA(CDC* pDC,CAutoMakeView3*pView);//显示最小化DFA

extern list<int>::iterator CurrentIter;//用于保存当前演示生成的NFA,以便重画NFA

#endif