首页 > 代码库 > 扩充C0文法编译器开发笔记（一）符号表
扩充C0文法编译器开发笔记（一）符号表
零、简介
这是一个编译大作业。
一、扩充C0文法
文法包括 常量说明和定义、变量说明和定义、无返回值函数定义和调用、有返回值函数定义和调用、条件语句、while循环语句、情况语句、赋值语句、返回语句、读语句、写语句，支持加减乘除四则运算、整数比较运算。包含一维数组、不包含实型、不包含for循环语句。程序由main方法进入。具体文法见下：
1 ＜加法运算符＞ ::= +｜- 2 ＜乘法运算符＞ ::= *｜/ 3 ＜关系运算符＞ ::= <｜<=｜>｜>=｜!=｜== 4 ＜字母＞ ::= ＿｜a｜．．．｜z｜A｜．．．｜Z 5 ＜数字＞ ::= ０｜＜非零数字＞ 6 ＜非零数字＞ ::= １｜．．．｜９ 7 ＜字符＞ ::= ‘＜加法运算符＞‘｜‘＜乘法运算符＞‘｜‘＜字母＞‘｜‘＜数字＞‘ 8 ＜字符串＞ ::= "｛十进制编码为32,33,35-126的ASCII字符｝" 9 ＜程序＞ ::= ［＜常量说明＞］［＜变量说明＞］{＜有返回值函数定义＞|＜无返回值函数定义＞}＜主函数＞10 ＜常量说明＞ ::= const＜常量定义＞;{ const＜常量定义＞;}11 ＜常量定义＞ ::= int＜标识符＞＝＜整数＞{,＜标识符＞＝＜整数＞}12 | char＜标识符＞＝＜字符＞{,＜标识符＞＝＜字符＞}13 ＜无符号整数＞ ::= ＜非零数字＞｛＜数字＞｝14 ＜整数＞ ::= ［＋｜－］＜无符号整数＞｜０15 ＜标识符＞ ::= ＜字母＞｛＜字母＞｜＜数字＞｝16 ＜声明头部＞ ::= int＜标识符＞ | char＜标识符＞17 ＜变量说明＞ ::= ＜变量定义＞;{＜变量定义＞;}18 ＜变量定义＞ ::= ＜类型标识符＞(＜标识符＞|＜标识符＞‘[’＜无符号整数＞‘]’){,(＜标识符＞|＜标识符＞‘[’＜无符号整数＞‘]’ )}19 ＜常量＞ ::= ＜整数＞| ＜字符＞20 ＜类型标识符＞ ::= int | char21 ＜有返回值函数定义＞ ::= ＜声明头部＞‘(’＜参数＞‘)’ ‘{’＜复合语句＞‘}’22 ＜无返回值函数定义＞ ::= void＜标识符＞‘(’＜参数＞‘)’‘{’＜复合语句＞‘}’23 ＜复合语句＞ ::= ［＜常量说明＞］［＜变量说明＞］＜语句列＞24 ＜参数＞ ::= ＜参数表＞25 ＜参数表＞ ::= ＜类型标识符＞＜标识符＞{,＜类型标识符＞＜标识符＞}| ＜空＞26 ＜主函数＞ ::= void main‘(’‘)’ ‘{’＜复合语句＞‘}’27 ＜表达式＞ ::= ［＋｜－］＜项＞{＜加法运算符＞＜项＞}28 ＜项＞ ::= ＜因子＞{＜乘法运算符＞＜因子＞}29 ＜因子＞ ::= ＜标识符＞｜＜标识符＞‘[’＜表达式＞‘]’｜＜整数＞|＜字符＞｜＜有返回值函数调用语句＞|‘(’＜表达式＞‘)’ 30 ＜语句＞ ::= ＜条件语句＞｜＜循环语句＞| ‘{’＜语句列＞‘}’｜＜有返回值函数调用语句＞; 31 |＜无返回值函数调用语句＞;｜＜赋值语句＞;｜＜读语句＞;｜＜写语句＞;｜＜空＞; |＜情况语句＞｜＜返回语句＞;32 ＜赋值语句＞ ::= ＜标识符＞＝＜表达式＞|＜标识符＞‘[’＜表达式＞‘]’=＜表达式＞33 ＜条件语句＞ ::= if ‘(’＜条件＞‘)’＜语句＞［else＜语句＞］34 ＜条件＞ ::= ＜表达式＞＜关系运算符＞＜表达式＞｜＜表达式＞ //表达式为0条件为假，否则为真35 ＜循环语句＞ ::= while ‘(’＜条件＞‘)’＜语句＞36 ＜情况语句＞ ::= switch ‘(’＜表达式＞‘)’ ‘{’＜情况表＞ ‘}’37 ＜情况表＞ ::= ＜情况子语句＞{＜情况子语句＞}38 ＜情况子语句＞ ::= case＜常量＞：＜语句＞39 ＜有返回值函数调用语句＞ ::= ＜标识符＞‘(’＜值参数表＞‘)’40 ＜无返回值函数调用语句＞ ::= ＜标识符＞‘(’＜值参数表＞‘)’41 ＜值参数表＞ ::= ＜表达式＞{,＜表达式＞}｜＜空＞42 ＜语句列＞ ::= ｛＜语句＞｝43 ＜读语句＞ ::= scanf ‘(’＜标识符＞{,＜标识符＞}‘)’44 ＜写语句＞ ::= printf ‘(’ ＜字符串＞,＜表达式＞ ‘)’| printf ‘(’＜字符串＞ ‘)’| printf ‘(’＜表达式＞‘)’45 ＜返回语句＞ ::= return[‘(’＜表达式＞‘)’] 46 47 48 附加说明：49 50 （1）char类型的表达式，用字符的ASCII码对应的整数参加运算，在写语句中输出字符51 52 （2）标识符不区分大小写字母53 54 （3）写语句中的字符串原样输出 55 56 （4）情况语句中，switch后面的表达式和case后面的常量只允许出现int和char类型；每个情况子语句执行完毕后，不继续执行后面的情况子语句 57 58 （5）数组的下标从0开始
二、符号表(Table)
符号表是在编译过程中编译程序用来记录源程序中的各种名字（即标识符）的特性信息的表格。符号表的每一个符号表项将填入名字标识符以及与该名字相关联的信息，这些信息将全面地反映各个符号的属性及他们在编译过程中的特征，比如名字的种类（数组、变量、常量等）、类型（整形、字符型等）、值等与该名字的语义有关的其他信息等。
1、符号表结构
符号表由符号表项(TableItem)构成，每个符号表项结构见下：
1 class Table; 2 class TableItem 3 { 4 public: 5 string name; // 符号表项名，如函数名、变量名等 6 int kind; // 标识符种类，如VAR、CONST、ARRAY、FUNCTION等 7 int type; // 标识符类型，如INT、CHAR等 8 string value; // 值或地址（例如常量的值、变量的地址） 9 int dimension; // 数组的上界、函数的参数个数10 Table* pChildTable; // 指向由该项引出的子表11 Table* pParentTable; // 指向该项所在的表12 13 TableItem(string name, int kind, int type, string value, int dimension, Table* parentTable);14 ~TableItem();15 };
2、符号表管理
符号表由符号表管理类(TableManager)管理，如下：
1 class Table; 2 class TableItem; 3 class TableManager 4 { 5 public: 6 Table* pCurrentTable; // 指向当前符号表 7 Table* pTopTable; // 指向最顶层符号表 8 TableItem* pCurrentItem; // 指向当前符号表项 9 10 TableManager();11 virtual ~TableManager();12 13 // 检查当前符号表，是否存在名称为name的符号表项14 int checkCurrent(string name, int isCaseSensitive);15 // 检查所有的符号表，是否存在名称为name的符号表项16 int checkAll(string name, int isCaseSensitive);17 // 根据名称name返回对应的符号表项18 TableItem* find(string name, int isCaseSensitive);19 // 插入符号表项20 void insert(string name, int kind, int type, string value, int dimension);21 // 当前符号表项出栈22 void pop();23 // 将name对应的符号表项压栈24 void push(string name);25 };
3、符号表管理算法
（1）压栈算法：符号表压栈操作，若当前符号表的最后一项为函数头部或过程头部，则为该项建立子符号表，并将当前符号表指针更新为此符号表
1 void TableManager::push(string name) 2 { 3 if(pCurrentTable->itemNumber == 0) 4 { 5 ;// 如果当前没有符号表项，DONOTHING 6 } 7 // 如果名称叫name的符号表项有引出的表，则将该表压入栈顶 8 else if(find(name, 1)->pChildTable != NULL) 9 {10 pCurrentTable = find(name, 1)->pChildTable;11 }12 else13 {14 ;//如果该符号表项没有引出的子表，DONOTHING15 }16 }
（2）出栈算法：符号表退栈操作，将当前符号表更新为次栈顶符号表
1 void TableManager::pop() 2 { 3 // 如果当前符号表是由某个符号表项引出的，则更新当前符号表为该符号表项所在的符号表 4 if(pCurrentTable->pParentItem != NULL) 5 { 6 pCurrentTable = pCurrentTable->pParentItem->pParentTable; 7 } 8 else 9 {10 ;// 如果为顶层符号表，DONOTING11 }12 }
（3）查询算法：修改自二分查找（符号表项按其名称的字母顺序，将其索引值存入一个数组，在该数组中二分查找），如果存在该符号表项，则返回索引值，否则返回该符号表项应该插入的位置
1 int Table::find(string name, int left, int right, int isCaseSensitive) 2 { 3 int mid = (left+right)/2; 4 if(left == right) 5 { 6 if(compare(name, itemList[itemIndex[left]]->name, isCaseSensitive) == 0) 7 { 8 itemExist = 1; 9 return left;10 }11 else if(compare(name, itemList[itemIndex[left]]->name, isCaseSensitive) == 1)12 {13 itemExist = 0;14 return left+1;15 }16 else17 {18 itemExist = 0;19 return left;20 }21 }22 else if(left+1 == right)23 {24 if(compare(name, itemList[itemIndex[left]]->name, isCaseSensitive) == 0)25 {26 itemExist = 1;27 return left;28 }29 else if(compare(name, itemList[itemIndex[right]]->name, isCaseSensitive) == 0)30 {31 itemExist = 1;32 return right;33 }34 else35 {36 itemExist = 0; // newItem位置在left和right中间37 return right;38 }39 }40 else if(compare(name, itemList[itemIndex[mid]]->name, isCaseSensitive) == -1)41 {42 return find(name, left, mid, isCaseSensitive);43 }44 else if(compare(name, itemList[itemIndex[mid]]->name, isCaseSensitive) == 1)45 {46 return find(name, mid, right, isCaseSensitive);47 }48 else49 {50 itemExist = 1;51 return mid;52 }53 }
（4）插入算法：将新的符号表项插入符号表中，并根据其名称的字母序建立索引，存入有序数组中，方便二分查找
1 int Table::insert(string name, int kind, int type, string value, int dimension) 2 { 3 newItem = new TableItem(name, kind, type, value, dimension, this); 4 if(itemNumber == 0) 5 { 6 itemIndex[0] = 0; 7 itemList[itemNumber++] = newItem; 8 return 0; 9 }10 else11 {12 if(name < itemList[itemIndex[0]]->name)13 {14 for(int i = itemNumber - 1; i >= 0; i--)15 itemIndex[i+1] = itemIndex[i];16 itemIndex[0] = itemNumber;17 itemList[itemNumber++] = newItem;18 }19 else if(name > itemList[itemIndex[itemNumber-1]]->name)20 {21 itemIndex[itemNumber] = itemNumber;22 itemList[itemNumber++] = newItem;23 }24 else25 {26 int index = find(newItem->name, 0, itemNumber-1, 0);27 if(itemExist == 1)28 {29 //ERROR30 return -1;31 }32 else33 {34 for(int i = itemNumber - 1; i >= index; i--)35 itemIndex[i+1] = itemIndex[i];36 itemIndex[index] = itemNumber;37 itemList[itemNumber++] = newItem;38 }39 }40 return 0;41 }42 }
扩充C0文法编译器开发笔记（一）符号表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。