关于正则的语法方面，就做到这吧。下一步是生成nfa，进而dfa，以及dfa的最简化。等下一个版本出来的话，估计要好久了。
1 #include <stdio.h> 2 #include <malloc.h> 3 #include <string.h> 4 //这个版本在上一个版本的基础上，添加了?+这两个操作符，这两个操作符都是单目操作符，跟*操作符同一级别 5 //因此碰到这两个操作符的时候，跟*操作符一样的处理 6 //除了新加的操作符外，还添加了字符集，模式为a-z这种，但是字符集只能通过假名来引用 7 //因此如果想使用字符集，则必须先通过假名来定义这个字符集，然后在后续的正则表达式中通过假名 8 //来使用这个字符集 9 //因此这里需要修改reg_opera_type，以及输入处理函数。 10 //注意这里的字符集定义的识别是通过判断正则的第二个字符是否是-来作用的，所以如果在其他类型的正则 11 //表达式中想使用-符号的话，千万不要把它放在第二个字符里面，因为这样会产生错误 12 //虽然可以去判断正则的长度来消除这种错误，不过我就懒得管了 13 //想改的话，读者自己去改吧 14 int token[100]; 15 int token_pointer; 16 char reg_operator[100]; 17 int reg_operator_pointer=0; 18 int name_number=0; 19 //注意这里name_number是全局的，而其他的几个栈及变量都是每个子表达式都复用的 20 //其实那些变量及栈可以每次申请一个，为了节省空间，我就懒得管了，直接复用。 21 int input_pointer=0; 22 char reg_input[40];//由于命名表达式的存在，考虑加长字符，其实随便多大都可以处理。 23 enum reg_opera_type 24 { 25 parenthesis=1,//对应括号 26 closure,//对应闭包运算符 27 one_or_more,//对应+运算符 28 maybe_exist,//对应？运算符 29 cat,//对应连接运算符 30 or,//对应选择运算符 31 alias,//对应命名子表达式 32 set_of_char,//对应字符集 33 literal_char//单字符 34 };//正则节点类型 35 typedef struct _reg_pattern 36 { 37 enum reg_opera_type type; 38 union 39 { 40 struct//对应二元操作符 41 { 42 int left; 43 int right; 44 }; 45 struct//对应假名 46 { 47 int origin_number; 48 int hash_table_number; 49 }; 50 struct//对应字符集 51 { 52 char begin; 53 char end; 54 }; 55 char value;//对应字符值 56 int sub;//对应闭包运算符和括号运算符以及问号运算符及+运算符 57 }; 58 }reg_pattern;//差不多当作抽象语法树吧 59 reg_pattern reg_pattern_table[100]; 60 //当前的hash只使用加法hash加上一个模97，因为考虑到97是质数 61 typedef struct _hash_table//hash表类型 62 { 63 enum _state 64 { 65 empty=0, 66 in_use, 67 deleted 68 }state; 69 char* name_of_alias; 70 int reg_pattern_number; 71 }hash_table; 72 hash_table simple_hash_table[100]; 73 int look_up_hash_table(char* source)//查询一个名字是否在hash表中 74 { 75 int string_length; 76 int counter; 77 int index; 78 int result; 79 string_length=strlen(source); 80 result=0; 81 for(index=0;index<string_length;index++) 82 { 83 result+=*(source+index); 84 } 85 result=result%97; 86 counter=0; 87 while(counter<97)//顶多查询97次，如果查询达到了97次，则说明当前hash表中不存在这个字符串 88 { 89 if(simple_hash_table[result].state==empty)//如果当前位置为空，说明不存在这个节点，直接返回-1 90 { 91 return -1; 92 } 93 else 94 { 95 if(simple_hash_table[result].state==deleted)//如果为删除状态，则继续向下寻找，注意索引溢出的处理 96 { 97 result=(result+1)%97; 98 counter++; 99 } 100 else 101 { 102 if(strcmp(source,simple_hash_table[result].name_of_alias)==0)//如果出于使用状态，则开始比较 103 { 104 return result;//名字相同则返回索引 105 } 106 else//不同则继续向下寻找 107 { 108 result+=(result+1)%97; 109 counter++; 110 } 111 } 112 } 113 } 114 return -1;//如果找了达到了97次，则返回-1 115 } 116 117 118 119 120 int insert_hash_table(char* source,int index_of_reg_pattern) 121 { 122 int string_length; 123 int counter; 124 int index; 125 int result; 126 string_length=strlen(source); 127 result=0; 128 for(index=0;index<string_length;index++) 129 { 130 result+=*(source+index); 131 } 132 result=result%97; 133 counter=0; 134 while(counter<97) 135 { 136 if(simple_hash_table[result].state==in_use)//如果在使用中，则继续下次寻找 137 { 138 result=(result+1)%97; 139 counter++; 140 } 141 else//如果可用，则使用 142 { 143 simple_hash_table[result].state=in_use; 144 simple_hash_table[result].name_of_alias=source; 145 simple_hash_table[result].reg_pattern_number=index_of_reg_pattern; 146 return result; 147 } 148 } 149 return -1;//已经满了 ，插入失败 150 } 151 152 int is_begin_of_token() 153 //判断输入字符是否可以当作一个token的开始符号，这样是为了处理非显示的连接符 154 //由于转义字符也是可以当作token的开始字符，所以也是返回1 155 { 156 switch(reg_input[input_pointer]) 157 { 158 case '*': 159 case '?': 160 case '+': 161 case '|': 162 case '.': 163 case ']': 164 case ')': 165 case ' ': 166 return 0; 167 default: 168 return 1; 169 } 170 //这里两个闭括号的存在都是为了处理非显示的连接符 171 //而把开括号移动到外部的switch之中 172 //主要是为了防止括号嵌套引起的错误 173 } 174 tackle_invisible_cat()//如果后面跟的是开括号（包括普通括号和假名括号）或者字符，则这时候要去处理隐式连接符 175 { 176 if(is_begin_of_token()) 177 { 178 tackle_cat(); 179 } 180 181 } 182 183 void tackle_or()//处理并操作符,这个处理完之后，输入指针也会后移 184 { 185 if(reg_operator_pointer!=0)//如果操作符栈中已经有操作符了 186 { 187 if(reg_operator[reg_operator_pointer-1]!='(')//括号另外说 188 { 189 name_number++; 190 if(reg_operator[reg_operator_pointer-1]=='.') 191 //如果前面的优先级比当前的高，则处理前面的优先级 192 { 193 printf("name%d is concat of name%d and name%d ",name_number,token[token_pointer-2],token[token_pointer-1]); 194 } 195 else 196 //这里处理的是相同优先级的情况，其实这里可以与前面的合并的，只不过打印信息不同 197 { 198 printf("name%d is name%d or name%d ",name_number,token[token_pointer-2],token[token_pointer-1]); 199 } 200 token[token_pointer-2]=name_number; 201 token_pointer--; 202 reg_operator[reg_operator_pointer-1]='|'; 203 input_pointer++; 204 } 205 else//对于括号，则直接入栈 206 { 207 reg_operator[reg_operator_pointer++]='|'; 208 input_pointer++; 209 } 210 } 211 else//对于空操作符栈，也是直接入栈 212 { 213 reg_operator[reg_operator_pointer++]='|'; 214 input_pointer++; 215 } 216 } 217 int tackle_cat()//处理连接符，处理完之后输入指针不会移动，因为指针本来就指向了后面的字符 218 { 219 if(reg_operator_pointer!=0)//如果操作符栈不为空 220 { 221 if(reg_operator[reg_operator_pointer-1]=='(')//如果前面有括号，则直接入栈 222 { 223 reg_operator[reg_operator_pointer++]='.'; 224 } 225 else//对于前面不是括号的情况下 226 { 227 if(reg_operator[reg_operator_pointer-1]=='.')//优先级相同则输出前面的那个 228 { 229 name_number++; 230 printf("name%d is the concat of name%d and name%d ",name_number,token[token_pointer-2],token[token_pointer-1]); 231 reg_pattern_table[name_number].type=cat; 232 reg_pattern_table[name_number].left=token[token_pointer-2]; 233 reg_pattern_table[name_number].right=token[token_pointer-1]; 234 token[token_pointer-1]=0; 235 token[token_pointer-2]=name_number; 236 token_pointer--; 237 } 238 else//否则的话，前面的优先级比当前优先级低，操作符入栈 239 { 240 reg_operator[reg_operator_pointer++]='.'; 241 } 242 } 243 } 244 else//如果操作符栈为空，则入栈 245 { 246 reg_operator[reg_operator_pointer++]='.'; 247 } 248 } 249 void tackle_parenthesis(void)//处理闭括号模式，这里有点复杂,这里匹配完之后，指针会向后移一位 250 { 251 if(reg_operator[reg_operator_pointer-1]=='(')//如果前面那个操作符为开括号，则匹配输出,并把输入指针向后移 252 { 253 name_number++; 254 printf("name%d is (name%d) ",name_number,token[token_pointer-1]); 255 reg_pattern_table[name_number].type=parenthesis; 256 reg_pattern_table[name_number].sub=token[token_pointer-1]; 257 token[token_pointer-1]=name_number; 258 input_pointer++; 259 reg_operator[--reg_operator_pointer]=' '; 260 //这时候需要考虑后面的是否少了显示的连接符，如果判断缺少连接符，则需要加上去 261 tackle_invisible_cat(); 262 } 263 else//如果闭括号前面还有运算符，那么根据他们的优先级输出，这个时候输入指针是不变的，注意 264 { 265 name_number++; 266 if(reg_operator[reg_operator_pointer-1]=='.') 267 { 268 printf("name%d is the concat of name%d and name%d ",name_number,token[token_pointer-2],token[token_pointer-1]); 269 reg_pattern_table[name_number].type=cat; 270 reg_pattern_table[name_number].left=token[token_pointer-2]; 271 reg_pattern_table[name_number].right=token[token_pointer-1]; 272 } 273 else 274 { 275 printf("name%d is name%d or name%d ",name_number,token[token_pointer-2],token[token_pointer-1]); 276 reg_pattern_table[name_number].type=or; 277 reg_pattern_table[name_number].left=token[token_pointer-2]; 278 reg_pattern_table[name_number].right=token[token_pointer-1]; 279 } 280 token[token_pointer-1]=0; 281 token[token_pointer-2]=name_number; 282 token_pointer--; 283 reg_operator_pointer--; 284 } 285 } 286 int tackle_alias(void)//注意这里处理完中括号匹配之后，还需要处理可能存在的非显示连接符 287 { 288 int length,index; 289 char* new_alias; 290 index=length=0; 291 while(reg_input[input_pointer+length]!=']') 292 { 293 length++; 294 } 295 new_alias=malloc(sizeof(char)*(length));//总的长度为length-1,另外加上一个 。 296 for(index=0;index<length-1;index++) 297 { 298 new_alias[index]=reg_input[input_pointer+index+1]; 299 } 300 new_alias[index]=' '; 301 input_pointer+=length+1; 302 index=look_up_hash_table(new_alias);//寻找hash表 303 if(index!=-1) 304 { 305 length=simple_hash_table[index].reg_pattern_number;//找到别名所代表的正则模式 306 token[token_pointer++]=length;//别名的正则模式的名字入栈 307 printf("match a alias,%s is the alias of name%d ",new_alias,length); 308 tackle_invisible_cat(); 309 return 1; 310 } 311 else//否则，返回错误信息 312 { 313 printf("the alias can't be matched "); 314 return -1; 315 } 316 } 317 318 int tackle_inter_reg(void) 319 { 320 token_pointer=0; 321 while(reg_input[input_pointer]!=' ')//还没处理到输入的末尾 322 { 323 switch(reg_input[input_pointer]) 324 { 325 case '\'://注意这里因为在c语言中这个字符也是转义字符，所以要双斜杠才能写出来 326 input_pointer++; 327 name_number++; 328 printf("transition literal is encounted "); 329 printf("the literal is %c ",reg_input[input_pointer]); 330 printf("the literal's token name is name%d ",name_number); 331 token[token_pointer++]=name_number; 332 reg_pattern_table[name_number].type=literal_char; 333 reg_pattern_table[name_number].value=reg_input[input_pointer]; 334 input_pointer++; 335 tackle_invisible_cat(); 336 break; 337 case '('://对于括号，直接入栈 338 reg_operator[reg_operator_pointer++]='('; 339 input_pointer++; 340 break; 341 case ')': 342 tackle_parenthesis(); 343 break; 344 case '*'://由于这个运算符优先级很高，不需要入栈了，直接拿顶上的token输出就行 345 name_number++; 346 printf("name%d is multiple of name%d ",name_number,token[token_pointer-1]); 347 reg_pattern_table[name_number].type=closure; 348 reg_pattern_table[name_number].sub=token[token_pointer-1]; 349 token[token_pointer-1]=name_number; 350 input_pointer++; 351 tackle_invisible_cat(); 352 break; 353 case '+'://同上 354 name_number++; 355 printf("name%d is one or more instance of name%d ",name_number,token[token_pointer-1]); 356 reg_pattern_table[name_number].type=one_or_more; 357 reg_pattern_table[name_number].sub=token[token_pointer-1]; 358 token[token_pointer-1]=name_number; 359 input_pointer++; 360 tackle_invisible_cat(); 361 break; 362 case '?'://同上 363 name_number++; 364 printf("name%d is one or zero instance of name%d ",name_number,token[token_pointer-1]); 365 reg_pattern_table[name_number].type=maybe_exist; 366 reg_pattern_table[name_number].sub=token[token_pointer-1]; 367 token[token_pointer-1]=name_number; 368 input_pointer++; 369 tackle_invisible_cat(); 370 break; 371 case '['://对于开的中括号，因为中括号中只能允许假名存在，所以直接调用函数处理， 372 //处理完之后指针位于闭中括号的后面一个字符，所以switch中不需要考虑闭中括号了 373 //注意处理时后面可能接上一个非显示的连接符 374 //这个时候需要特殊处理 375 tackle_alias(); 376 break; 377 case '|'://对于这个符号， 378 tackle_or(); 379 break; 380 default: 381 name_number++; 382 printf("name%d is %c ",name_number,reg_input[input_pointer]); 383 token[token_pointer++]=name_number; 384 reg_pattern_table[name_number].type=literal_char; 385 reg_pattern_table[name_number].value=reg_input[input_pointer]; 386 input_pointer++; 387 tackle_invisible_cat(); 388 break; 389 } 390 } 391 //处理完了输入，这个时候可能还有剩余的内容在栈中 392 while(reg_operator_pointer>=1)//如果全部的输入都弄完了，可是 操作符栈中还有数据，则输出 393 { 394 name_number++; 395 if(reg_operator[reg_operator_pointer-1]=='.') 396 { 397 printf("name%d is concat of name%d and name%d ",name_number,token[token_pointer-2],token[token_pointer-1]); 398 reg_pattern_table[name_number].type=cat; 399 reg_pattern_table[name_number].left=token[token_pointer-2]; 400 reg_pattern_table[name_number].right=token[token_pointer-1]; 401 402 } 403 else 404 { 405 printf("name%d is name%d or name%d ",name_number,token[token_pointer-2],token[token_pointer-1]); 406 reg_pattern_table[name_number].type=or; 407 reg_pattern_table[name_number].left=token[token_pointer-2]; 408 reg_pattern_table[name_number].right=token[token_pointer-1]; 409 410 } 411 token[token_pointer-2]=name_number; 412 token_pointer--; 413 reg_operator_pointer--; 414 } 415 return name_number;//返回最后一个生成的token，作为假名的正则代号 416 } 417 int tackle_particle()//这里处理一个正则表达式名字的定义，每次处理完之后复用输入数组 418 { 419 //首先处理假名部分 420 int index; 421 char* name; 422 input_pointer=0; 423 while(reg_input[input_pointer++]!=':')//注意这里在停止迭代之后，指针指的是冒号后面的那个字符， 424 { 425 //一直向后找，直到找到冒号分隔符 426 } 427 //字符串长度比指针的值小1 428 name=malloc(sizeof(char)*(input_pointer));//考虑到字符串的结尾 ，于是不需要减1了 429 for(index=0;index<input_pointer-1;index++)//把名字复制过去 430 { 431 name[index]=reg_input[index]; 432 } 433 name[index]=' '; 434 if(reg_input[input_pointer+1]=='-')//如果后面接的是字符集模式，则直接处理，因为这个比较简单 435 { 436 name_number++;//新建一个字符集的名字 437 printf("new set of literal is created "); 438 printf("the set's name is name%d ",name_number); 439 printf("the set begins from %c, and end with %c ",reg_input[input_pointer],reg_input[input_pointer+2]); 440 index=name_number; 441 } 442 else 443 { 444 index=tackle_inter_reg();//处理当前的小正则表达式,并得到这个表达式所生成的名字 445 } 446 insert_hash_table(name,index); 447 printf("creat a alias: %s is name%d ",name,index);//输出，建立了一个新的假名 448 } 449 450 int main(void) 451 { 452 int index; 453 printf("please type in your short regex definition "); 454 printf("if there is no more definition, just enter a newline "); 455 scanf("%s",reg_input); 456 while(strlen(reg_input)>=3)//当输入的字符数小于三个的时候，认为结束 457 { 458 tackle_particle(); 459 printf("please type in your short regex definition "); 460 printf("if there is no more definition, just enter a newline "); 461 scanf("%s",reg_input); 462 } 463 for(index=0;index<97;index++)//这里将所有的假名输出，并释放空间，其实无所谓，反正系统会回收 464 { 465 if(simple_hash_table[index].state==in_use) 466 { 467 printf("there is a alias whose name is %s ",simple_hash_table[index].name_of_alias); 468 free(simple_hash_table[index].name_of_alias); 469 } 470 } 471 }