===============================================
这个是老版本，一会儿我发个最新的DEMO版本
新版本链接如下：
RegExp DEMO version -- [1]正则表达式 TO NFA表格 -- 词法分析代码
RegExp DEMO version -- [2]最核心函数代码（上） -- int dealState(SymbolType symboltype)
RegExp DEMO version -- [2]最核心函数代码（中） -- int dealState(SymbolType symboltype)
RegExp DEMO version -- [2]最核心函数代码（下） -- int dealState(SymbolType symboltype)
RegExp DEMO version -- [3][regexp.h]最核心数据类型
===============================================
我博客中的一篇文章，最近要完成的一个项目：做一个正则表达式的解析工具。
Blog: http://rabbit5455.bc-cn.net
=========================================
最近一直努力的学习编译原理，对于里面提到的“自动机”好好理解了一下，
还感受了一下lex和yacc的强大功能，真是厉害啊 。。。
我的兄弟伦子小朋友想写一个8086的编译解释工具（类似一个虚拟机）。
我对于CPU的理解很简单，它首先可以看成一个数字电路，可以用数字逻辑的方式
来理解，而数字逻辑便是状态机了，状态机会动了，也就是“自动机”了，
“确定的有穷自动机（DFA）”模型与真实的CPU应该是一码子事情了，
而（DFA）对应了一条“正规文法”，
“正规文法”对应了一个“正则表达式”，
“正则表达式”可以转化为一个“不确定的有穷自动机（NFA）”，
（NFA）可以转化为（DFA），呵呵 。。。
累了，想去睡觉去了 。。。
怎么看来看去，就是个圈啊 。。。
呵呵：“正则表达式” == （DFA）
这几天一直都在分析正则表达式的词法，语法 。。。
把正则表达式的词法分析图画了出来，代码在后面
（图片比较大，点击查看大图，那样清楚 
）
代码也写好了，如下：
/*词法分析,取得一个符号*/
SymbolType getSymbol() {
char *cc = &g_symbol_charvalue;
char tmp; /*临时变量*/
*cc = g_strRegExp[++g_scan_pos];
if ((*cc>='0' && *cc<='9') || (*cc>='a' && *cc<='z') || (*cc>='A' && *cc<='Z')) {
return g_symbol_type=INPUT_ELE;
}
/*正则表达式结尾*/
if (*cc == NULL) {return g_symbol_type=END_REGEXP;}
if (*cc == '(') {return g_symbol_type=AND_MACHINE_BEGIN;}
if (*cc == ')') {return g_symbol_type=AND_MACHINE_END;}
if (*cc == '[') {return g_symbol_type=OR_MACHINE_BEGIN;}
if (*cc == ']') {return g_symbol_type=OR_MACHINE_END;}
if (*cc == '|') {return g_symbol_type=BACKTRACE;}
if (*cc == '^') {return g_symbol_type=NOT_OP;}
if (*cc == '.') {return g_symbol_type=DOT;}
/*转义字符*/
if (*cc == '\\') {
*cc = g_strRegExp[++g_scan_pos];
if (*cc == 'd') {return g_symbol_type=NUMBER;}
if (*cc == 'D') {return g_symbol_type=NOT_NUMBER;}
if (*cc == 'f') {*cc = '\f'; return g_symbol_type=INPUT_ELE;}
if (*cc == 'n') {*cc = '\n'; return g_symbol_type=INPUT_ELE;}
if (*cc == 'r') {*cc = '\r'; return g_symbol_type=INPUT_ELE;}
if (*cc == 't') {*cc = '\t'; return g_symbol_type=INPUT_ELE;}
if (*cc == 'v') {*cc = '\v'; return g_symbol_type=INPUT_ELE;}
if (*cc == 's') {return g_symbol_type=ALL_SPACE;}
if (*cc == 'S') {return g_symbol_type=NOT_ALL_SPACE;}
if (*cc == 'w') {return g_symbol_type=AZaz09_;}
if (*cc == 'W') {return g_symbol_type=NOT_AZaz09_;}
/*16进制*/
if (*cc == 'x') {
tmp = g_strRegExp[++g_scan_pos];
if (tmp>='0' && tmp<='9') {
*cc = tmp - '0';
} else if (tmp>='a' && tmp<='f') {
*cc = tmp - 'a' + 10;
} else if (tmp>='A' && tmp<='F') {
*cc = tmp - 'A' + 10;
} else {
/*不是16进制数字,返回原字符'x'*/
g_scan_pos--;
return g_symbol_type=INPUT_ELE;
}
tmp = g_strRegExp[++g_scan_pos];
if (tmp>='0' && tmp<='9') {
*cc *= 16;
*cc += tmp - '0';
} else if (*cc>='a' && *cc<='f') {
*cc *= 16;
*cc += tmp - 'a' + 10;
} else if (*cc>='A' && *cc<='F') {
*cc *= 16;
*cc += tmp - 'A' + 10;
} else {
/*这个不是16进制数字,只有一位:\xF*/
g_scan_pos--;
return g_symbol_type=INPUT_ELE;
}
return g_symbol_type=INPUT_ELE;
}
/*8进制*/
if (*cc>='0' && *cc<='3') {
*cc -= '0';
tmp = g_strRegExp[++g_scan_pos];
if (tmp>='0' && tmp<='7') {
*cc *= 8;
*cc += tmp - '0';
} else {
/*只有一位8进制数字:\7*/
g_scan_pos--;
return g_symbol_type=INPUT_ELE;
}
tmp = g_strRegExp[++g_scan_pos];
if (tmp>='0' && tmp<='7') {
*cc *= 8;
*cc += tmp - '0';
} else {
/*只有两位8进制数字:\77*/
g_scan_pos--;
return g_symbol_type=INPUT_ELE;
}
return g_symbol_type=INPUT_ELE;
}
if (*cc>='4' && *cc<='7') {
*cc -= '0';
tmp = g_strRegExp[++g_scan_pos];
if (tmp>='0' && tmp<='7') {
*cc *= 8;
*cc += tmp - '0';
} else {
/*只有一位8进制数字:\7*/
g_scan_pos--;
return g_symbol_type=INPUT_ELE;
}
return g_symbol_type=INPUT_ELE;
} else {
/*[^x0-7dDfnrtvsSwW]*/
return g_symbol_type=INPUT_ELE;
}
}
/*重复运算*/
if (*cc == '*') {return g_symbol_type=REPEAT_ZERO_MORE;}
if (*cc == '+') {return g_symbol_type=REPEAT_ONCE_MORE;}
if (*cc == '?') {return g_symbol_type=REPEAT_ZERO_ONCE;}
if (*cc == '{') {
*cc = g_strRegExp[++g_scan_pos];
if (*cc>'9' || *cc<'0') {return g_symbol_type=UNKNOWN;}
g_repeat_m = 0; /*取{m,n}的m*/
while (*cc>='0' && *cc<='9') {
g_repeat_m *= 10;
g_repeat_m += *cc-'0';
*cc = g_strRegExp[++g_scan_pos];
}
/*{m}*/
if (*cc == '}') {return g_symbol_type=REPEAT_RANGE_M;}
if (*cc != ',') {return g_symbol_type=UNKNOWN;}
*cc = g_strRegExp[++g_scan_pos];
/*{m,}*/
if (*cc == '}') {return g_symbol_type=REPEAT_RANGE_M_MORE;}
/*{m,n}*/
if (*cc>'9' || *cc<'0') {return g_symbol_type=UNKNOWN;}
g_repeat_n = 0; /*取{m,n}的n*/
while (*cc>='0' && *cc<='9') {
g_repeat_n *= 10;
g_repeat_n += *cc-'0';
*cc = g_strRegExp[++g_scan_pos];
}
if (*cc == '}') {
return g_symbol_type=REPEAT_RANGE_MN;
} else {
return g_symbol_type=UNKNOWN;
}
}
return g_symbol_type=UNKNOWN;
}
[此贴子已经被作者于2007-6-2 23:14:18编辑过]
