文档介绍：词法分析三个核心算法的实现
从正规式到NFA
从NFA到DFA
最小化DFA
1、从正规式到NFA
实验目的:实现由正规式构造NFA的算法,
加深对该算法的理解。
实验要求:
输入:任意一个正规式r;
输出:接受L(r)的NFA N。
注:NFA的表现形式不限。
算法回顾
首先构造识别和字母表中一个符号的NFA
i
开始
识别正规式的NFA
a
f
i
f
开始
识别正规式a的NFA
构造识别主算符为选择的正规式的NFA
f
i
开始
识别正规式s | t的NFA
N (s)
N (t)
构造识别主算符为连接的正规式的NFA
i
N (s)
f
开始
识别正规式st 的NFA
N (t)
构造识别主算符为闭包的正规式的NFA
N (s)
f
开始
识别正规式s* 的NFA
i
对于加括号的正规式(s),使用N(s)本身作为它的NFA。
所用数据结构提示
用字符串存储正规式;
用结构体数组或链表存放状态转换图
struct NFA
{ int from;
int to;
char *varch;
}表示经过字符串varch,from到to状态。
中间过程可借助栈完成。
算法提示
利用算符优先的思想来处理正规式中所涉及的各种算符(*,|,(,),·)所对应的操作。
根据各运算符间的优先关系,构造相应的算符优先关系表。如右表。
用字符串存储输入的正规式,利用算符优先分析过程,来分析输入的字符串。
·
|
(
)
*
#
·
>
>
<
>
<
>
|
<
>
<
>
<
>
(
<
<
<
=
<
E
)
>
>
E
>
>
>
*
>
>
E
>
>
>
#
<
<
<
E
<
=
程序流程
‘#’入符号栈;
输入串+‘#’(将输入串中的连接用‘·’代替);
While(输入字符!=‘#’||符号栈顶元素!=‘#’)
{
if(输入字符是小写字母或数字)
{构造识别正规式a的NFA; NFA的弧入队列;起始节点入状态栈;读取下一个字符。}
else
{比较符号栈顶元素和输入字符的优先关系(查表)
{
case ’<’:
{当前输入符号进符号栈;读取下一个字符;}
case ‘=’:
{符号栈栈顶元素出栈;读取下一个字符;}
程序流程
case ‘>’:
{符号栈栈顶元素出栈;
if(符号栈顶元素==‘|’)
{状态栈2个栈顶元素出栈,分别为s,t;构造识别正规式s|t 的NFA; NFA的弧入队列;起始节点入状态栈;}
else if (符号栈顶元素==‘·’)
{状态栈2个栈顶元素出栈,分别为s,t;构造识别正规式s·t的NFA; NFA的弧入队列;起始节点入状态栈;}
else if(输入字符==‘*’)
{状态栈1栈顶元素s出栈;构造识别正规式s*的NFA; NFA的弧入队列;起始节点入状态栈;读取下一个字符。}
else error! }
} } }
把状态栈顶元素出栈,该元素的弧的起始节点为整个NFA的起始节点,该弧的终止节点为整个NFA的终止节点。