函數定義
由於語法分析本身比較複雜,所以我們將它拆分成 3 個部分進行講解,分別是:變量定義、函數定義、表達式。本章講解函數定義相關的內容。
EBNF 表示
這是上一章的 EBNF 方法中與函數定義相關的內容。
variable_decl ::= type {'*'} id { ',' {'*'} id } ';'
function_decl ::= type {'*'} id '(' parameter_decl ')' '{' body_decl '}'
parameter_decl ::= type {'*'} id {',' type {'*'} id}
body_decl ::= {variable_decl}, {statement}
statement ::= non_empty_statement | empty_statement
non_empty_statement ::= if_statement | while_statement | '{' statement '}'
| 'return' expression | expression ';'
if_statement ::= 'if' '(' expression ')' statement ['else' non_empty_statement]
while_statement ::= 'while' '(' expression ')' non_empty_statement
解析函數的定義
上一章的代碼中,我們已經知道了什麼時候開始解析函數的定義,相關的代碼如下:
...
if (token == '(') {
current_id[Class] = Fun;
current_id[Value] = (int)(text + 1); // the memory address of function
function_declaration();
} else {
...
即在這斷代碼之前,我們已經為當前的標識符(identifier)設置了正確的類型,上面這斷代碼為當前的標識符設置了正確的類別(Fun),以及該函數在代碼段(text segment)中的位置。接下來開始解析函數定義相關的內容:parameter_decl 及 body_decl。
函數參數與彙編代碼
現在我們要回憶如何將“函數”轉換成對應的彙編代碼,因為這決定了在解析時我們需要哪些相關的信息。考慮下列函數:
int demo(int param_a, int *param_b) {
int local_1;
char local_2;
...
}
那麼它應該被轉換成什麼樣的彙編代碼呢?在思考這個問題之前,我們需要了解當 demo函數被調用時,計算機的棧的狀態,如下(參照第三章講解的虛擬機):
| .... | high address
+---------------+
| arg: param_a | new_bp + 3
+---------------+
| arg: param_b | new_bp + 2
+---------------+
|return address | new_bp + 1
+---------------+
| old BP | <- new BP
+---------------+
| local_1 | new_bp - 1
+---------------+
| local_2 | new_bp - 2
+---------------+
| .... | low address
這裡最為重要的一點是,無論是函數的參數(如 param_a)還是函數的局部變量(如 local_1)都是存放在計算機的 棧 上的。因此,與存放在 數據段 中的全局變量不同,在函數內訪問它們是通過 new_bp 指針和對應的位移量進行的。因此,在解析的過程中,我們需要知道參數的個數,各個參數的位移量。
函數定義的解析
這相當於是整個函數定義的語法解析的框架,代碼如下:
void function_declaration() {
// type func_name (...) {...}
// | this part
match('(');
function_parameter();
match(')');
match('{');
function_body();
//match('}'); // ①
// ②
// unwind local variable declarations for all local variables.
current_id = symbols;
while (current_id[Token]) {
if (current_id[Class] == Loc) {
current_id[Class] = current_id[BClass];
current_id[Type] = current_id[BType];
current_id[Value] = current_id[BValue];
}
current_id = current_id + IdSize;
}
}
其中①中我們沒有消耗最後的}字符。這麼做的原因是:variable_decl 與 function_decl 是放在一起解析的,而 variable_decl 是以字符 ; 結束的。而 function_decl 是以字符 } 結束的,若在此通過 match 消耗了 ‘;’ 字符,那麼外層的 while 循環就沒法準確地知道函數定義已經結束。所以我們將結束符的解析放在了外層的 while 循環中。
而②中的代碼是用於將符號表中的信息恢復成全局的信息。這是因為,局部變量是可以和全局變量同名的,一旦同名,在函數體內局部變量就會覆蓋全局變量,出了函數體,全局變量就恢復了原先的作用。這段代碼線性地遍歷所有標識符,並將保存在 BXXX 中的信息還原。
解析參數
parameter_decl ::= type {'*'} id {',' type {'*'} id}
解析函數的參數就是解析以逗號分隔的一個個標識符,同時記錄它們的位置與類型。
int index_of_bp; // index of bp pointer on stack
void function_parameter() {
int type;
int params;
params = 0;
while (token != ')') {
// ①
// int name, ...
type = INT;
if (token == Int) {
match(Int);
} else if (token == Char) {
type = CHAR;
match(Char);
}
// pointer type
while (token == Mul) {
match(Mul);
type = type + PTR;
}
// parameter name
if (token != Id) {
printf("%d: bad parameter declaration\n", line);
exit(-1);
}
if (current_id[Class] == Loc) {
printf("%d: duplicate parameter declaration\n", line);
exit(-1);
}
match(Id);
//②
// store the local variable
current_id[BClass] = current_id[Class]; current_id[Class] = Loc;
current_id[BType] = current_id[Type]; current_id[Type] = type;
current_id[BValue] = current_id[Value]; current_id[Value] = params++; // index of current parameter
if (token == ',') {
match(',');
}
}
// ③
index_of_bp = params+1;
}
其中①與全局變量定義的解析十分一樣,用於解析該參數的類型。
而②則與上節中提到的“局部變量覆蓋全局變量”相關,先將全局變量的信息保存(無論是是否真的在全局中用到了這個變量)在 BXXX 中,再賦上局部變量相關的信息,如 Value 中存放的是參數的位置(是第幾個參數)。
③則與彙編代碼的生成有關,index_of_bp 就是前文提到的 new_bp 的位置。
函數體的解析
我們實現的 C 語言與現代的 C 語言不太一致,我們需要所有的變量定義出現在所有的語句之前。函數體的代碼如下:
void function_body() {
// type func_name (...) {...}
// -->| |<--
// ... {
// 1. local declarations
// 2. statements
// }
int pos_local; // position of local variables on the stack.
int type;
pos_local = index_of_bp;
// ①
while (token == Int || token == Char) {
// local variable declaration, just like global ones.
basetype = (token == Int) ? INT : CHAR;
match(token);
while (token != ';') {
type = basetype;
while (token == Mul) {
match(Mul);
type = type + PTR;
}
if (token != Id) {
// invalid declaration
printf("%d: bad local declaration\n", line);
exit(-1);
}
if (current_id[Class] == Loc) {
// identifier exists
printf("%d: duplicate local declaration\n", line);
exit(-1);
}
match(Id);
// store the local variable
current_id[BClass] = current_id[Class]; current_id[Class] = Loc;
current_id[BType] = current_id[Type]; current_id[Type] = type;
current_id[BValue] = current_id[Value]; current_id[Value] = ++pos_local; // index of current parameter
if (token == ',') {
match(',');
}
}
match(';');
}
// ②
// save the stack size for local variables
*++text = ENT;
*++text = pos_local - index_of_bp;
// statements
while (token != '}') {
statement();
}
// emit code for leaving the sub function
*++text = LEV;
}
其中①用於解析函數體內的局部變量的定義,代碼與全局的變量定義幾乎一樣。
而②則用於生成彙編代碼,我們在第三章的虛擬機中提到過,我們需要在棧上為局部變量預留空間,這兩行代碼起的就是這個作用。
代碼
本章的代碼可以在 Github 上下載,也可以直接 clone
git clone -b step-4 https://github.com/lotabout/write-a-C-interpreter
本章的代碼依舊無法運行,還有兩個重要函數沒有完成:statement 及 expression,感興趣的話可以嘗試自己實現它們。
小結
本章中我們用了不多的代碼完成了函數定義的解析。大部分的代碼依舊是用於解析變量:參數和局部變量,而它們的邏輯和全局變量的解析幾乎一致,最大的區別就是保存的信息不同。
當然,要理解函數定義的解析過程,最重要的是理解我們會為函數生成怎樣的彙編代碼,因為這決定了我們需要從解析中獲取什麼樣的信息(例如參數的位置,個數等),而這些可能需要你重新回顧一下“虛擬機”這一章,或是重新學習學習彙編相關的知識。