擴充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 | char
21 ＜有返回值函數定義＞ ::= ＜聲明頭部＞‘(’＜參數＞‘)’ ‘{’＜復合語句＞‘}’
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開始
擴充C0文法
二、符號表(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 else
13 {
14 ;//如果該符號表項沒有引出的子表，DONOTHING
15 }
16 }
push(string name)
（2）出棧算法：符號表退棧操作，將當前符號表更新為次棧頂符號表
![]()
1 void TableManager::pop()
2 {
3 // 如果當前符號表是由某個符號表項引出的，則更新當前符號表為該符號表項所在的符號表
4 if(pCurrentTable->pParentItem != NULL)
5 {
6 pCurrentTable = pCurrentTable->pParentItem->pParentTable;
7 }
8 else
9 {
10 ;// 如果為頂層符號表，DONOTING
11 }
12 }
pop()
（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 else
17 {
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 else
35 {
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 else
49 {
50 itemExist = 1;
51 return mid;
52 }
53 }
find(string name, int left, int right, int isCaseSensitive)
（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 else
11 {
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 else
25 {
26 int index = find(newItem->name, 0, itemNumber-1, 0);
27 if(itemExist == 1)
28 {
29 //ERROR
30 return -1;
31 }
32 else
33 {
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 }
insert(string name, int kind, int type, string value, int dimension)
