1 #include <stdio.h> 2 #include <string.h> 3 #include <malloc.h> 4 typedef struct _array_description 5 { 6 int array_size;//代表当前层的最高索引,即上界 7 struct _array_description* next;//代表下一级 8 }array_description,*parray_description; 9 //注意我们把最低层的放在最前面，这样有利于下标的处理 10 11 typedef struct _basic_type_pattern 12 { 13 char* faction_name;//代表类型名字 14 int pointer_layer;//代表指针的级数，我们限制为8级，即只占一个字节，其他三个字节以后再使用，先留着 15 parray_description array_layer;//这里是数组描述，以链表串起多级数组 16 char* pattern_name;//代表分量的类型 17 }basic_type_pattern,*pbasic_type_pattern; 18 typedef struct _composition_list//这个是复合结构的产生式，包括联合、结构、函数 19 { 20 pbasic_type_pattern current;//当前的分量 21 struct _composition_list* next;//下一个分量的指针 22 }composition_list,*pcomposition_list; 23 typedef struct _type_description 24 { 25 pcomposition_list current_gen_list;//代表当前的产生式的体,也是函数参数的列表 26 int type_type;//1为函数，2为结构，3为联合，4为基础类型 27 char* name;//当前类型的名字 28 void* function_zone;//这个代表了函数相关的域，其中有三个域，类型链表，变量链表，动作链表 29 //这三个域都是需要后面定义的类型，所以我们目前把他作为一个void类型的指针来处理 30 int return_pointer ;//代表返回值的指针层数 31 char* return_name;//代表返回值的类型 32 }type_description,*ptype_description;//类型声明的体 33 typedef struct _type_avl_tree 34 { 35 struct _type_description* current_type_body;//产生体链表的头节点 36 //因为有交叉引用。。。 37 int tree_depth;//当前树的高度，这个域是用来计算平衡因子的 38 struct _type_avl_tree* left;//左子树 39 struct _type_avl_tree* right;//右子树 40 }type_avl_tree,*ptype_avl_tree;//这里是整个的类型avl树 41 42 ptype_avl_tree type_tree_head=NULL;//先初始化为空 43 ptype_avl_tree tree_node_stack[100];//这个栈是为了插入和删除用的，以及用来平衡树高 44 //前面的结构都是对应于类型符号表的，采取的是avl 45 //下面开始介绍变量符号表，采取的是hash 46 //对于变量符号表，我们首先需要考虑一个变量所包括的域，其实这些域在定义类型符号表的时候都使用过了 47 //即basic_type_pattern这个结构体，已经有我们所需要的所有的东西,对于hash值一样的变量，我们通过一个链表串接起来 48 //而这个链表结构我们现在都有了 49 //现在我们唯一需要的就是hash表的空间以及hash的方法,这里我们分配400个表项，因为397刚好是质数 50 //hash函数我们直接采用累加法，最简单的 51 typedef struct _var_hash_node 52 { 53 char* var_name; 54 int pointer_layer;//代表指针的级数，我们限制为8级，即只占一个字节，其他三个字节以后再使用，先留着 55 parray_description array_layer;//这里是数组描述，以链表串起多级数组 56 struct _type_description* var_type;//代表变量的类型 57 }var_hash_node,*pvar_hash_node; 58 typedef struct _var_hash_chain 59 { 60 pvar_hash_node current_var; 61 struct _var_hash_node next_var; 62 }var_hash_chain,*pvar_hash_chain; 63 pvar_hash_chain var_hash_table[400];//注意我们要在后面把这个全都初始化为空 64 void generation_free(void* generation_body)//释放生成体链表所占的空间 65 { 66 pcomposition_list temp_com_list_before,temp_com_list_after; 67 pbasic_type_pattern temp_basic_pattern; 68 parray_description temp_array_layer_before,temp_array_layer_after; 69 temp_com_list_before=(pcomposition_list)generation_list;//转换一下指针 70 while(temp_com_list_before!=NULL) 71 { 72 temp_com_list_after=temp_com_list_before->next; 73 temp_basic_pattern=temp_com_list_before->current; 74 free(temp_basic_pattern->faction_name); 75 temp_array_layer_before=temp_basic_pattern->array_layer; 76 while(temp_array_layer_before!=NULL) 77 { 78 temp_array_layer_after=temp_array_layer_before->next; 79 free(temp_array_layer_before); 80 temp_array_layer_before=temp_array_layer_after; 81 }//释放所有的数组空间 82 free(temp_com_list_before); 83 temp_com_list_before=temp_com_list_after; 84 }//释放所有的分量 85 }//现在所有的都释放完成了 86 87 88 89 void insert_var_hash(pvar_hash_node new_var)//在hash表中插入一个表项 90 { 91 int string_hash; 92 int for_i; 93 char* current_name; 94 pvar_hash_chain temp_link;//用来串接链表 95 current_name=new_var->var_name; 96 for_i=0; 97 string_hash=0; 98 while(current_name[for_i]!=' ') 99 { 100 string_hash+=current_name[for_i]; 101 } 102 string_hash=string_hash%397;//取模 103 temp_link=malloc(sizeof(struct _var_hash_chain)); 104 temp_link->next_var=var_hash_table[string_hash]; 105 temp_link->current_var=new_var; 106 var_hash_table[string_hash]=temp_link; 107 } 108 void delete_var_hash(char* current_name)//这里其实我们不管具体的name，因为，删除的时候我们是一起删除的 109 { 110 int string_hash; 111 int for_i; 112 pvar_hash_chain temp_link;//用来串接链表 113 for_i=0; 114 string_hash=0; 115 while(current_name[for_i]!=' ') 116 { 117 string_hash+=current_name[for_i]; 118 } 119 string_hash=string_hash%397;//取模 120 temp_link=var_hash_table[string_hash]->next_var; 121 free(var_hash_table[string_hash]); 122 var_hash_table[string_hash]=temp_link; 123 } 124 125 pvar_hash_node search_var_hash(char* current_name)//通过名字来查找变量符号表 126 { 127 int string_hash; 128 int for_i; 129 pbasic_type_pattern result; 130 pvar_hash_node temp_link;//用来串接链表 131 for_i=0; 132 string_hash=0; 133 while(current_name[for_i]!=' ') 134 { 135 string_hash+=current_name[for_i]; 136 } 137 string_hash=string_hash%397;//取模 138 temp_link=var_hash_table[string_hash]; 139 while(temp_link!=NULL) 140 { 141 result=temp_link->current_var; 142 if(strcmp(result,current_name)==0) 143 { 144 return result; 145 } 146 else 147 { 148 temp_link=temp_link->next_var; 149 } 150 } 151 return NULL; 152 } 153 154 void modify_node_depth(ptype_avl_tree current)//修改节点的高度 155 //由于这个操作需要做很多判断，不修改成函数的话，其他函数将会很长，所以做成一个函数 156 { 157 if(current->left!=NULL) 158 { 159 if(current->right!=NULL) 160 { 161 current->tree_depth=1+(current->left->tree_depth+current->right->tree_depth+1)/2; 162 } 163 else 164 { 165 current->tree_depth=1+current->left->tree_depth; 166 } 167 } 168 else 169 { 170 if(current->right!=NULL) 171 { 172 current->tree_depth=1+current->right->tree_depth; 173 } 174 else 175 { 176 current->tree_depth=1; 177 } 178 } 179 } 180 void avl_rotate_left( ptype_avl_tree father, ptype_avl_tree current)//将avl树左旋 181 { 182 ptype_avl_tree temp_node_one,temp_node_two,temp_node_three;//这命名碉堡了有木有 183 if(father==NULL)//如果旋转的是头节点 184 { 185 temp_node_one=current->right; 186 type_tree_head=current->right;//修改头节点 187 temp_node_two=temp_node_one->left; 188 current->right=temp_node_two; 189 type_tree_head->left=current; 190 //至此节点之间的关系修改完毕 191 //现在开始修改两个节点的高度 192 modify_node_depth(current);//修改高度有先后顺序的，先修改下面的，后修改上面的 193 modify_node_depth(temp_node_one) 194 } 195 else 196 { 197 temp_node_one=current->right; 198 current->right=temp_node_one->left; 199 temp_node_one->left=current; 200 if(father->left==current) 201 { 202 father->left=temp_node_one; 203 } 204 else 205 { 206 father->right=temp_node_one; 207 } 208 modify_node_depth(current); 209 modify_node_depth(temp_node_one); 210 mpdify_node_depth(father); 211 //这里需要修改三个节点 212 } 213 } 214 void avl_rotate_right(ptype_avl_tree father, ptype_avl_tree current)//右旋节点 215 { 216 ptype_avl_tree temp_node_one,temp_node_two,temp_node_three;//这命名碉堡了有木有 217 if(father==NULL)//如果旋转的是头节点 218 { 219 temp_node_one=current->left; 220 type_tree_head=current->left;//修改头节点 221 temp_node_two=temp_node_one->right; 222 current->left=temp_node_two; 223 type_tree_head->right=current; 224 //至此节点之间的关系修改完毕 225 //现在开始修改两个节点的高度 226 modify_node_depth(current);//修改高度有先后顺序的，先修改下面的，后修改上面的 227 modify_node_depth(temp_node_one) 228 } 229 else 230 { 231 temp_node_one=current->left; 232 current->left=temp_node_one->right; 233 temp_node_one->right=current; 234 if(father->right==current) 235 { 236 father->right=temp_node_one; 237 } 238 else 239 { 240 father->left=temp_node_one; 241 } 242 modify_node_depth(current); 243 modify_node_depth(temp_node_one); 244 mpdify_node_depth(father); 245 //这里需要修改三个节点 246 } 247 } 248 249 void insert_avl_node(ptype_description new_type_node)//插入一个新的节点 250 { 251 ptype_avl_tree temp_node_one,temp_node_two,temp_node_three,new_node; 252 ptype_description temp_type_description; 253 int stack_pointer=0; 254 int compare_result=0;//这个变量会被复用，在插入时作为字符串比较的结果，在平衡时作为高度差。 255 int original_depth;//这个用来记录节点原来的高度 256 tree_node_stack[0]=NULL;//哨兵节点，在旋转的时候有用 257 new_node=malloc(sizeof(struct _type_avl_tree)); 258 new_node->current_gen_list=new_type_node; 259 new_node->left=NULL; 260 new_node->right=NULL; 261 new_node->tree_depth=1; 262 if(type_tree_head==NULL) 263 { 264 type_tree_head=new_node; 265 return 0; 266 } 267 else 268 { 269 temp_node_one=type_tree_head; 270 while(temp_node_one!=NULL) 271 { 272 stack_pointer++; 273 tree_node_stack[stack_pointer]=temp_node_one; 274 temp_type_description=(ptype_description)temp_node_one->current_type_body; 275 compare_result=strcmp(new_type_node->name,temp_type_description->name); 276 if(compare_result<0) 277 { 278 temp_node_one=temp_node_one->left; 279 } 280 else 281 { 282 temp_node_one=temp_node_one->right; 283 } 284 }//这个栈记录了插入所经过的路径 285 temp_node_one=tree_node_stack[stack_pointer]; 286 if(compare_result<0) 287 { 288 temp_node_one->left=new_node; 289 } 290 else 291 { 292 temp_node_one->right=new_node; 293 } 294 //现在节点关系已经建立了,开始平衡树高度了 295 while(stack_pointer>0)//遍历整个栈，来寻找需要平衡的节点 296 //注意，这里跳出循环的条件是，某个节点在修改后高度没有改变，这样就没有必要再去修改了 297 //或者启用了平衡操作，启用平衡操作之后可以确保高度没有改变，因此可以退出 298 { 299 temp_node_one=tree_node_stack[stack_pointer]; 300 original_depth=temp_node_one->tree_depth; 301 modify_tree_depth(temp_node_one); 302 if(original_depth==temp_node_one->tree_depth) 303 { 304 return 0; 305 } 306 else 307 { 308 compare_result=temp_node_one->left->tree_depth-temp_node_one->right->tree_depth; 309 if(compare_result==2)//如果左边比右边高2 310 { 311 //这个时候需要考虑是要进行两次旋转还是一次旋转 312 if(tree_node_stack[stack_pointer+1]->right==tree_node_stack[stack_pointer+2]) 313 //这种情况我们需要做两次旋转 314 { 315 avl_rotate_left(tree_node_stack[stack_pointer],tree_node_stack[stack_pointer+1]); 316 } 317 avl_rotate_right(tree_node_stack[stack_pointer-1],tree_node_stack[stack_pointer]); 318 //第二次旋转 319 return 0; 320 } 321 else 322 { 323 if(compare_result==-2) 324 { 325 if(tree_node_stack[stack_pointer+1]->left==tree_node_stack[stack_pointer+2]) 326 { 327 avl_rotate_right(tree_node_stack[stack_pointer],tree_node_stack[stack_pointer+1]); 328 } 329 avl_rotate_left(tree_node_stack[stack_pointer-1],tree_node_stack[stack_pointer]); 330 return 0; 331 } 332 else 333 { 334 //这里继续向上传递 335 stack_pointer--; 336 } 337 } 338 } 339 } 340 //至此所有的插入及平衡都做完了 341 } 342 } 343 344 void delete_avl_node(char* avl_node_name)//这里我们要求已经做过参数检查了，挂了自己撞墙去 345 { 346 ptype_avl_tree temp_node_one,temp_node_two,temp_node_three;//神一样的命名方法 347 ptype_description temp_type_description; 348 int stack_pointer=0; 349 int compare_result=0; 350 int original_depth=0; 351 temp_node_one=type_tree_head; 352 tree_node_stack[0]=NULL;//哨兵 353 temp_type_description=(ptype_description)temp_node_one->current_type_body; 354 compare_result=strcmp(avl_node_name,temp_type_description->name); 355 while(compare_result!=0) 356 { 357 stack_pointer++; 358 tree_node_stack[stack_pointer]=temp_node_one; 359 if(compare_result>0) 360 { 361 temp_node_one=temp_node_one->right; 362 } 363 else 364 { 365 temp_node_one=temp_node_one->left; 366 } 367 temp_type_description=(ptype_description)temp_node_one->current_type_body; 368 compare_result=strcmp(avl_node_name,temp_type_description->name); 369 }//找到对应的节点 370 if(temp_node_one->left==NULL||temp_node_one->right==NULL)//如果有删除的节点只有一个或零个子节点 371 { 372 if(stack_pointer==0)//如果是头节点，且只有不多于1个的子节点 373 { 374 type_tree_head=temp_node_one->left|temp_node_one->right;//这里就不需要考虑空节点了，这里已经考虑过了 375 free(temp_node_one); 376 return 0;//直接返回 377 }//这里就不需要平衡了 378 else//如果不是头节点 379 { 380 temp_node_two=tree_node_stack[stack_pointer]; 381 if(temp_node_two->left==temp_node_one) 382 { 383 temp_node_two->left=temp_node_one->left|temp_node_one->right; 384 } 385 else 386 { 387 temp_node_two->right=temp_node_one->left|temp_node_one->right; 388 }//修正好所有的节点关系 389 } 390 } 391 else//有两个子节点，选择后继来处理 392 { 393 temp_node_two=temp_node_one->right; 394 while(temp_node_two!=NULL) 395 { 396 stack_pointer++; 397 tree_node_stack[stack_pointer]=temp_node_two; 398 temp_node_two=temp_node_two->left; 399 } 400 temp_node_two=tree_node_stack[stack_pointer]; 401 temp_node_one->current_generate_body=temp_node_two->current_generate_body; 402 //这样就把这个节点复制过去了 403 //现在我们要删除这个新的节点 404 stack_pointer--;//最后一个点抛弃，因为我们要删除这个点 405 //现在我们开始修改好节点关系，修改完之后再去平衡 406 if(temp_node_one->right==temp_node_two)//这个是特殊情况 407 { 408 temp_node_one->right=temp_node_two->right; 409 } 410 else 411 { 412 tree_node_stack[stack_pointer]->left=temp_node_two->right; 413 }//这里修正好所有的节点关系，然后再开始平衡 414 415 416 417 418 419 420 } 421 //现在开始进行平衡 422 while(stack_pointer>0) 423 { 424 //这里跳出循环的条件是某个节点的高度没有变化，调用平衡处理之后，还是有可能影响上面的节点 425 //所以还是需要处理其他的点，因此平衡处理不是跳出循环的条件 426 temp_node_three=tree_node_stack[stack_pointer]; 427 original_depth=temp_node_three->tree_depth; 428 modify_node_depth(temp_node_three); 429 if(temp_node_three->tree_depth==original_depth) 430 { 431 //如果子树的高度不变，则不需要继续处理了 432 return 0; 433 } 434 else//这里平衡操作不需要做第二次旋转，一次旋转就足够了 435 { 436 compare_result=temp_node_three->left->tree_depth-temp_node_three->right->tree_depth; 437 if(compare_result==2) 438 { 439 rotate_avl_right(tree_node_stack[stack_pointer-1],tree_node_stack[stack_pointer]); 440 stack_pointer--; 441 } 442 else 443 { 444 if(compare_result==-2) 445 { 446 rotate_avl_left(tree_node_stack[stack_pointer-1],tree_node_stack[stack_pointer]); 447 stack_pointer--; 448 } 449 else 450 { 451 stack_pointer--; 452 } 453 } 454 } 455 } 456 return 0; 457 } 458 ptype_description search_avl_tree(char* target_name)//在当前avl树中寻找是否有相应的名字的节点 459 { 460 ptype_avl_tree result;//作为遍历树的指针 461 ptype_description return_result;//作为返回的节点 462 int compare_result;//比较的时候的返回结果 463 result=type_tree_head; 464 while(result!=NULL) 465 { 466 return_result=(ptype_description)result->current_type_body; 467 compare_result=strcmp(target_name,return_result->name); 468 if(compare_result==0) 469 { 470 break;//不需要继续找了 471 } 472 else 473 { 474 if(compare_result<0) 475 { 476 result=result->left; 477 } 478 else 479 { 480 result=result->right; 481 } 482 } 483 } 484 return return_result; 485 } 486 487 488 489