[原创]RegExp DEMO version -- [2]最核心函数代码（上） -- int dealState(SymbolT
===============================================新版本所有链接如下：
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]最核心数据类型
===============================================
这个函数是状态机的执行部分，
他根据getSymbol()函数返回的一个词，来决定正则状态机的行为。
下面我来对这其中的一些细节做一下解释：
======================================
[1] 在这个DEMO版本中，输入被看作是字节流，像一个汉字会被解析成两个INPUT_ELE，
例如："王"会被解析为 "\xCD\xF5"。
[2] 我的一个比较重要的概念是“子状态机”，被“()”和“[]”包围的都是“子状态机”，
将括号以这种方式独立出来处理，可以很方便的进行各种运算（重复，或，连接）
[3] 在[regexp.h]中定义的Machine结构中，记录着一个子状态机的很多属性，如下：
开始状态，结束状态 --- 将这个子状态机看成一端口网络，
这样在进行运算时可以采用和INPUT_ELE相同的处理方式；
开始位置，结束位置 --- 这个保留，目前还没有使用；
连接模式，否定模式 --- 这个目前只是用到了“否定模式”，
这些都是为以后更加强大的功能做铺垫的；
[4] 字节流的输入元素范围是[0-255]，输入元素[256]代表“空”，在编译原理中叫“epsilon”；
[5] 在字母表的处理方法：char g_ele_ary[256]; /*用来做字母表有效置1,否则置0*/
大家都是程序员，用代码来说明最直接不过了；
[abc] --- 将g_ele_ary['a']，g_ele_ary['b']，g_ele_ary['c'] 置 1，其余置 0；
[^abc] --- 将g_ele_ary['a']，g_ele_ary['b']，g_ele_ary['c'] 置 0，其余置 1；
在OR_MACHINE_END状态时，遍历字母表，如果是否定模式就将g_ele_ary[]中为 0 的加入NFA表格；
否则，将g_ele_ary[]中为 1 的加入NFA状态表格；
[6] 重复运算的实现方法：* + ?比较好办，在两个状态之间加上合适的epsilon弧线就可以了；
{m} {m, } {m,n}这个不好办，目前的方法是模仿宏扩展，克隆m或n个被重复对象；
m被称为repeat_needed，n被称为repeat_optional，对于INPUT_ELE和MACHINE分别编写了函数；
[7] 先说这么多吧，有什么问题，可以先看代码，实在看不懂的可以问我。
例如："王"会被解析为 "\xCD\xF5"。
[2] 我的一个比较重要的概念是“子状态机”，被“()”和“[]”包围的都是“子状态机”，
将括号以这种方式独立出来处理，可以很方便的进行各种运算（重复，或，连接）
[3] 在[regexp.h]中定义的Machine结构中，记录着一个子状态机的很多属性，如下：
开始状态，结束状态 --- 将这个子状态机看成一端口网络，
这样在进行运算时可以采用和INPUT_ELE相同的处理方式；
开始位置，结束位置 --- 这个保留，目前还没有使用；
连接模式，否定模式 --- 这个目前只是用到了“否定模式”，
这些都是为以后更加强大的功能做铺垫的；
[4] 字节流的输入元素范围是[0-255]，输入元素[256]代表“空”，在编译原理中叫“epsilon”；
[5] 在字母表的处理方法：char g_ele_ary[256]; /*用来做字母表有效置1,否则置0*/
大家都是程序员，用代码来说明最直接不过了；
[abc] --- 将g_ele_ary['a']，g_ele_ary['b']，g_ele_ary['c'] 置 1，其余置 0；
[^abc] --- 将g_ele_ary['a']，g_ele_ary['b']，g_ele_ary['c'] 置 0，其余置 1；
在OR_MACHINE_END状态时，遍历字母表，如果是否定模式就将g_ele_ary[]中为 0 的加入NFA表格；
否则，将g_ele_ary[]中为 1 的加入NFA状态表格；
[6] 重复运算的实现方法：* + ?比较好办，在两个状态之间加上合适的epsilon弧线就可以了；
{m} {m, } {m,n}这个不好办，目前的方法是模仿宏扩展，克隆m或n个被重复对象；
m被称为repeat_needed，n被称为repeat_optional，对于INPUT_ELE和MACHINE分别编写了函数；
[7] 先说这么多吧，有什么问题，可以先看代码，实在看不懂的可以问我。
===============================================
/*状态机输入响应部分,定义了各个状态的具体行为*/
int dealState(SymbolType symboltype) {
int OR_MACHINE_i;
switch (symboltype) {
case DOT:
case NUMBER:
case NOT_NUMBER:
case AZaz09_:
case NOT_AZaz09_:
case ALL_SPACE:
case NOT_ALL_SPACE:
/*模拟输入字母表中的每个元素*/
pmnew = newMachine(NULL, NULL, g_scan_pos, -1, '|', NULL);
pmnew->state_start = newState(); /*状态机开始状态*/
pmnew->state_end = newState(); /*状态机开始状态*/
/*将开始状态与当前状态连接*/
appendStateTable(g_st, pmnew->state_start); /*添加到状态表格*/
setdestState(g_st->curState, g_st->eleCount, pmnew->state_start);
g_st->curState = pmnew->state_start; /*移动到新的状态*/
/*调用这一个状态机,将它的断点,运算模式压入堆栈*/
pushMachine(g_mstk, pmnew);
/*将这些分支加入到这个子状态机*/
if (symboltype == DOT) {
for (OR_MACHINE_i=0; OR_MACHINE_i<(int)'\n'; OR_MACHINE_i++) {
g_ele_ary[OR_MACHINE_i] = 1;
}
for (OR_MACHINE_i=(int)'\n' + 1; OR_MACHINE_i<=sizeof(g_ele_ary); OR_MACHINE_i++) {
g_ele_ary[OR_MACHINE_i] = 1;
}
}
if (symboltype == NUMBER) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if (OR_MACHINE_i < '0' || OR_MACHINE_i > '9') {
g_ele_ary[OR_MACHINE_i] = 0;
} else {
g_ele_ary[OR_MACHINE_i] = 1;
}
}
}
if (symboltype == NOT_NUMBER) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if (OR_MACHINE_i < '0' || OR_MACHINE_i > '9') {
g_ele_ary[OR_MACHINE_i] = 1;
} else {
g_ele_ary[OR_MACHINE_i] = 0;
}
}
}
if (symboltype == AZaz09_) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if ((OR_MACHINE_i>='0' && OR_MACHINE_i<='9')
|| (OR_MACHINE_i>='A' && OR_MACHINE_i<='Z')
|| (OR_MACHINE_i>='a' && OR_MACHINE_i<='z')) {
g_ele_ary[OR_MACHINE_i] = 1;
} else {
g_ele_ary[OR_MACHINE_i] = 0;
}
}
}
if (symboltype == NOT_AZaz09_) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if ((OR_MACHINE_i>='0' && OR_MACHINE_i<='9')
|| (OR_MACHINE_i>='A' && OR_MACHINE_i<='Z')
|| (OR_MACHINE_i>='a' && OR_MACHINE_i<='z')) {
g_ele_ary[OR_MACHINE_i] = 0;
} else {
g_ele_ary[OR_MACHINE_i] = 1;
}
}
}
if (symboltype == ALL_SPACE) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if (OR_MACHINE_i==' ' || OR_MACHINE_i=='\n'
|| OR_MACHINE_i=='\r' || OR_MACHINE_i=='\t'
|| OR_MACHINE_i=='\f' || OR_MACHINE_i=='\v') {
g_ele_ary[OR_MACHINE_i] = 1;
} else {
g_ele_ary[OR_MACHINE_i] = 0;
}
}
}
if (symboltype == NOT_ALL_SPACE) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if (OR_MACHINE_i==' ' || OR_MACHINE_i=='\n'
|| OR_MACHINE_i=='\r' || OR_MACHINE_i=='\t'
|| OR_MACHINE_i=='\f' || OR_MACHINE_i=='\v') {
g_ele_ary[OR_MACHINE_i] = 0;
} else {
g_ele_ary[OR_MACHINE_i] = 1;
}
}
}
return dealState(OR_MACHINE_END);
break;
case BACKTRACE:
/*将当前状态与子状态机的结束状态连接*/
setdestState(g_st->curState, (int)g_st->eleCount, g_mstk->topM->state_end);
/*将当前状态回退到子状态机的头部,开始一个新的分支*/
g_st->curState = g_mstk->topM->state_start;
break;
case INPUT_ELE:
/*是一个终结符,连上一条弧*/
g_lastchar = g_symbol_charvalue;
psnew = newState();
appendStateTable(g_st, psnew); /*添加到状态表*/
setdestState(g_st->curState, (int)g_symbol_charvalue, psnew);
/*重复运算符*/
getSymbol();
switch (g_symbol_type) {
case REPEAT_ZERO_MORE:
/*(a*)*/
setdestState(g_st->curState, g_st->eleCount, psnew);
setdestState(psnew, g_st->eleCount, g_st->curState);
/*移动到新的状态*/
g_st->curState = psnew;
printf("debug: ZEOR_MORE\n");
break;
case REPEAT_ZERO_ONCE:
/*(a?)*/
setdestState(g_st->curState, g_st->eleCount, psnew);
/*移动到新的状态*/
g_st->curState = psnew;
printf("debug: ZEOR_ONCE\n");
break;
case REPEAT_ONCE_MORE:
/*(a+)*/
setdestState(psnew, g_st->eleCount, g_st->curState);
/*移动到新的状态*/
g_st->curState = psnew;
printf("debug: ONCE_MORE\n");
break;
case REPEAT_RANGE_MN:
/*(a{m,n})*/
if (g_repeat_m <= 0) {
/*处理{0,n}的情况,把刚刚的a变成(a?)*/
setdestState(g_st->curState, g_st->eleCount, psnew);
/*移动到新的状态*/
g_st->curState = psnew;
/*重复n-1次(a?)*/
repeat_optional(g_repeat_n-1, g_lastchar);
} else {
/*移动到新的状态*/
g_st->curState = psnew;
repeat_needed(g_repeat_m-1 , g_lastchar);
repeat_optional(g_repeat_n-g_repeat_m, g_lastchar);
}
printf("debug: type -> %d\t| m -> %d | n -> %d\n", symboltype, g_repeat_m, g_repeat_n);
break;
case REPEAT_RANGE_M_MORE:
/*(a{m,})*/
/*移动到新的状态*/
g_st->curState = psnew;
repeat_needed(g_repeat_m-1, g_lastchar);
/*做一个（a*）*/
psnew = newState();
appendStateTable(g_st, psnew);
setdestState(g_st->curState, g_lastchar, psnew);
setdestState(g_st->curState, g_st->eleCount, psnew);
setdestState(psnew, g_st->eleCount, g_st->curState);
/*移动新的状态*/
g_st->curState = psnew;
printf("debug: type -> %d\t| m -> %d | n -> max_int\n", symboltype, g_repeat_m);
break;
case REPEAT_RANGE_M:
/*(a{m})*/
/*移动到新的状态*/
g_st->curState = psnew;
repeat_needed(g_repeat_m-1, g_lastchar);
printf("debug: type -> %d\t| m -> %d\n", symboltype, g_repeat_m);
break;
default:
/*不是重复运算符,移动到新的状态,然后重新循环*/
g_st->curState = psnew;
return 0;
}/*重复运算符 -- 结束*/
break;/*INPUT_ELE -- 结束*/
int dealState(SymbolType symboltype) {
int OR_MACHINE_i;
switch (symboltype) {
case DOT:
case NUMBER:
case NOT_NUMBER:
case AZaz09_:
case NOT_AZaz09_:
case ALL_SPACE:
case NOT_ALL_SPACE:
/*模拟输入字母表中的每个元素*/
pmnew = newMachine(NULL, NULL, g_scan_pos, -1, '|', NULL);
pmnew->state_start = newState(); /*状态机开始状态*/
pmnew->state_end = newState(); /*状态机开始状态*/
/*将开始状态与当前状态连接*/
appendStateTable(g_st, pmnew->state_start); /*添加到状态表格*/
setdestState(g_st->curState, g_st->eleCount, pmnew->state_start);
g_st->curState = pmnew->state_start; /*移动到新的状态*/
/*调用这一个状态机,将它的断点,运算模式压入堆栈*/
pushMachine(g_mstk, pmnew);
/*将这些分支加入到这个子状态机*/
if (symboltype == DOT) {
for (OR_MACHINE_i=0; OR_MACHINE_i<(int)'\n'; OR_MACHINE_i++) {
g_ele_ary[OR_MACHINE_i] = 1;
}
for (OR_MACHINE_i=(int)'\n' + 1; OR_MACHINE_i<=sizeof(g_ele_ary); OR_MACHINE_i++) {
g_ele_ary[OR_MACHINE_i] = 1;
}
}
if (symboltype == NUMBER) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if (OR_MACHINE_i < '0' || OR_MACHINE_i > '9') {
g_ele_ary[OR_MACHINE_i] = 0;
} else {
g_ele_ary[OR_MACHINE_i] = 1;
}
}
}
if (symboltype == NOT_NUMBER) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if (OR_MACHINE_i < '0' || OR_MACHINE_i > '9') {
g_ele_ary[OR_MACHINE_i] = 1;
} else {
g_ele_ary[OR_MACHINE_i] = 0;
}
}
}
if (symboltype == AZaz09_) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if ((OR_MACHINE_i>='0' && OR_MACHINE_i<='9')
|| (OR_MACHINE_i>='A' && OR_MACHINE_i<='Z')
|| (OR_MACHINE_i>='a' && OR_MACHINE_i<='z')) {
g_ele_ary[OR_MACHINE_i] = 1;
} else {
g_ele_ary[OR_MACHINE_i] = 0;
}
}
}
if (symboltype == NOT_AZaz09_) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if ((OR_MACHINE_i>='0' && OR_MACHINE_i<='9')
|| (OR_MACHINE_i>='A' && OR_MACHINE_i<='Z')
|| (OR_MACHINE_i>='a' && OR_MACHINE_i<='z')) {
g_ele_ary[OR_MACHINE_i] = 0;
} else {
g_ele_ary[OR_MACHINE_i] = 1;
}
}
}
if (symboltype == ALL_SPACE) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if (OR_MACHINE_i==' ' || OR_MACHINE_i=='\n'
|| OR_MACHINE_i=='\r' || OR_MACHINE_i=='\t'
|| OR_MACHINE_i=='\f' || OR_MACHINE_i=='\v') {
g_ele_ary[OR_MACHINE_i] = 1;
} else {
g_ele_ary[OR_MACHINE_i] = 0;
}
}
}
if (symboltype == NOT_ALL_SPACE) {
for (OR_MACHINE_i=0; OR_MACHINE_i<sizeof(g_ele_ary); OR_MACHINE_i++) {
if (OR_MACHINE_i==' ' || OR_MACHINE_i=='\n'
|| OR_MACHINE_i=='\r' || OR_MACHINE_i=='\t'
|| OR_MACHINE_i=='\f' || OR_MACHINE_i=='\v') {
g_ele_ary[OR_MACHINE_i] = 0;
} else {
g_ele_ary[OR_MACHINE_i] = 1;
}
}
}
return dealState(OR_MACHINE_END);
break;
case BACKTRACE:
/*将当前状态与子状态机的结束状态连接*/
setdestState(g_st->curState, (int)g_st->eleCount, g_mstk->topM->state_end);
/*将当前状态回退到子状态机的头部,开始一个新的分支*/
g_st->curState = g_mstk->topM->state_start;
break;
case INPUT_ELE:
/*是一个终结符,连上一条弧*/
g_lastchar = g_symbol_charvalue;
psnew = newState();
appendStateTable(g_st, psnew); /*添加到状态表*/
setdestState(g_st->curState, (int)g_symbol_charvalue, psnew);
/*重复运算符*/
getSymbol();
switch (g_symbol_type) {
case REPEAT_ZERO_MORE:
/*(a*)*/
setdestState(g_st->curState, g_st->eleCount, psnew);
setdestState(psnew, g_st->eleCount, g_st->curState);
/*移动到新的状态*/
g_st->curState = psnew;
printf("debug: ZEOR_MORE\n");
break;
case REPEAT_ZERO_ONCE:
/*(a?)*/
setdestState(g_st->curState, g_st->eleCount, psnew);
/*移动到新的状态*/
g_st->curState = psnew;
printf("debug: ZEOR_ONCE\n");
break;
case REPEAT_ONCE_MORE:
/*(a+)*/
setdestState(psnew, g_st->eleCount, g_st->curState);
/*移动到新的状态*/
g_st->curState = psnew;
printf("debug: ONCE_MORE\n");
break;
case REPEAT_RANGE_MN:
/*(a{m,n})*/
if (g_repeat_m <= 0) {
/*处理{0,n}的情况,把刚刚的a变成(a?)*/
setdestState(g_st->curState, g_st->eleCount, psnew);
/*移动到新的状态*/
g_st->curState = psnew;
/*重复n-1次(a?)*/
repeat_optional(g_repeat_n-1, g_lastchar);
} else {
/*移动到新的状态*/
g_st->curState = psnew;
repeat_needed(g_repeat_m-1 , g_lastchar);
repeat_optional(g_repeat_n-g_repeat_m, g_lastchar);
}
printf("debug: type -> %d\t| m -> %d | n -> %d\n", symboltype, g_repeat_m, g_repeat_n);
break;
case REPEAT_RANGE_M_MORE:
/*(a{m,})*/
/*移动到新的状态*/
g_st->curState = psnew;
repeat_needed(g_repeat_m-1, g_lastchar);
/*做一个（a*）*/
psnew = newState();
appendStateTable(g_st, psnew);
setdestState(g_st->curState, g_lastchar, psnew);
setdestState(g_st->curState, g_st->eleCount, psnew);
setdestState(psnew, g_st->eleCount, g_st->curState);
/*移动新的状态*/
g_st->curState = psnew;
printf("debug: type -> %d\t| m -> %d | n -> max_int\n", symboltype, g_repeat_m);
break;
case REPEAT_RANGE_M:
/*(a{m})*/
/*移动到新的状态*/
g_st->curState = psnew;
repeat_needed(g_repeat_m-1, g_lastchar);
printf("debug: type -> %d\t| m -> %d\n", symboltype, g_repeat_m);
break;
default:
/*不是重复运算符,移动到新的状态,然后重新循环*/
g_st->curState = psnew;
return 0;
}/*重复运算符 -- 结束*/
break;/*INPUT_ELE -- 结束*/
[此贴子已经被作者于2007-6-3 0:13:38编辑过]
