词法分析程序思路
(一)正则规则和正则表达式
1] 数据结构:正则规则使用 RegularRule 类来存储,正则表达式为一个 string。
2] RegularRule:
i. alphabet:map<char, set<char>>,存储主字符表,key 为某类字符的代表符号,
value 是这个代表符号代表的所有字符的集合。这个属性提供给用户自定义的
方法,用户可以随意更改正则规则。
ii. assistAlpha:set<char>,存储辅助字符,实际上只有‘*’,‘|’,‘(’,‘)’四个符
号。这个属性用户无法修改,因为所有的正则文法都可以用这四个辅助字符
来表示。
3] bool check(string ):用于检查一个字符串是否是符合这种正则文法的正则表达式。
大体算法如下:首先判断表达式中的各个辅助符号是否符合限制要求,然后遍历
各字符是否是设定好的集合中的字符,一条不满足就返回 false,全部满足返回
true。
(二)NFA 的存储结构设计
1] 原则:使用节点序号来唯一标识一个节点,使用类似邻接表但做了一定修改的形
式来存储。(详见 UML 静态类图)
2] Node 类:在主表中存储 NFA 的各个节点,包含节点序号和邻接表地址两个属性。
3] AdjoinNode 类:邻接表节点类,含有该节点的序号,由主节点转换为该节点的条
件,以及下一个邻接节点的地址三个属性组成。
4] nodeMap:map<int,Node*>,NFA 节点主表,使用哈希表来无序存储各个节点,key
为节点序号,value 为该节点对应的 Node 对象。
5] sIndex:int,存储初态节点序号,初始化为 0。
6] zIndex:int,存储终态节点序号,初始化为 1。
7] regularRule:RegularRule,存储该 NFA 遵守的自定义的正则规则。
8] regularExpr:string,存储该 NFA 对应的正则表达式。
(三)正规式转化 NFA
1] 核心:把正则表达式分成一个一个的子模块,然后依据各个辅助符号进行模块间