用c語言手搓一個(gè)600行的類c語言解釋器: 給編程初學(xué)者的解釋器教程(3)- 詞法分析
項(xiàng)目github地址及源碼:
https://github.com/yunwei37/tryC
這一篇講講在tryC中詞法分析器是怎樣構(gòu)建的
詞法分析器是什么玩意
回想一下上一篇我們說的詞法分析階段寓落,編譯器做了這樣一件事:
對(duì)源程序進(jìn)行閱讀,并將字符序列瞪浸,也就是源代碼中一個(gè)個(gè)符號(hào)收集到稱作記號(hào)(token)的單元中
幫編譯器執(zhí)行詞法分析階段的模塊拉岁,就叫詞法分析器啦许饿。詞法分析器能夠?qū)υ创a字符串做預(yù)處理,以減少語法分析器的復(fù)雜程度。
詞法分析器以源碼字符串為輸入讲岁,輸出為標(biāo)記流(token stream)蔗崎,即一連串的標(biāo)記酵幕,比如對(duì)于源代碼中間:
num = 123.4;
這樣一個(gè)賦值語句中,變量num算是一個(gè)token缓苛,“=”符號(hào)算是一個(gè)token芳撒,“123.4”算是一個(gè)token;每個(gè)token有自己的類別和屬性,比如“123.4”的類別是數(shù)字笔刹,屬性(值)是123.4芥备;每個(gè)token可以用這一對(duì)兒表示:{token, token value},就像“123.4”可以表示為{Num, 123.4}
詞法分析器輸入上面那句話舌菜,就得到這樣一個(gè)標(biāo)記流:
{Sym, num}, {'=', assign}, {Num, 123.4}
詞法分析器的具體實(shí)現(xiàn)
由于詞法分析器對(duì)于各個(gè)語言基本都是大同小異萌壳,在其他地方也有很多用途,并且手工構(gòu)造的話實(shí)際上是一個(gè)很枯燥又容易出錯(cuò)的活計(jì)日月,因此其實(shí)已經(jīng)有了不少現(xiàn)成的實(shí)現(xiàn)袱瓮,比如 lex/flex 。
通常詞法分析器的實(shí)現(xiàn)會(huì)涉及到正則表達(dá)式爱咬、狀態(tài)機(jī)的一些相關(guān)知識(shí)尺借,或者通過正則表達(dá)式用上面那些工具來生成。但對(duì)于我們這樣一個(gè)簡(jiǎn)單的解釋器來說台颠,手工構(gòu)造詞法分析器褐望,并且完全不涉及到正則表達(dá)式的知識(shí),理解起來也并不是很困難啦串前。
先來看看token是怎樣寫的
token的數(shù)據(jù)結(jié)構(gòu)如下:
int token; // current token type
union tokenValue { // token value
symbol* ptr;
double val;
} token_val;
- 用一個(gè)整型變量 token 來表示當(dāng)前的 token 是什么類型的瘫里;
- 用一個(gè)聯(lián)合體來表示附加的token屬性,ptr可以附加指針類型的值荡碾,val可以附加數(shù)值谨读。
token 的類型采用枚舉表示定義:
/* tokens and classes (operators last and in precedence order) */
enum {
Num = 128, Char, Str, Array, Func,
Else, If, Return, While, Print, Puts, Read,
Assign, OR, AND, Equal, Sym, FuncSym, ArraySym, Void,
Nequal, LessEqual, GreatEqual, Inc, Dec
};
比如我們會(huì)將“==”標(biāo)記為Equal,將Num標(biāo)記為Sym等等坛吁。從這里也可以看出劳殖,一個(gè)標(biāo)記(token)可能包含多個(gè)字符;而詞法分析器能減小語法分析復(fù)雜度的原因拨脉,正是因?yàn)樗喈?dāng)于通過一定的編碼(采用標(biāo)記來表示一定的字符串)來壓縮和規(guī)范化了源碼哆姻。
另外,一些單個(gè)字符我們直接作為token返回玫膀,比如:
'}' '{' '(' ')' ';' '[' ']' .....
詞法分析器真正干活的函數(shù)們
首先需要說明一下矛缨,源碼字符串為輸入,輸出為標(biāo)記流(token stream)帖旨,這里的標(biāo)記流并不是一次性將所有的源代碼翻譯成長(zhǎng)長(zhǎng)的一串標(biāo)記串箕昭,而是需要一個(gè)標(biāo)記的時(shí)候再轉(zhuǎn)換一個(gè)標(biāo)記,原因如下:
- 字符串轉(zhuǎn)換成標(biāo)記流有時(shí)是有狀態(tài)的解阅,即與代碼的上下文是有關(guān)系的落竹。
- 保存所有的標(biāo)記流沒有意義且浪費(fèi)空間。
所以通常的實(shí)現(xiàn)是提供一個(gè)函數(shù)货抄,每次調(diào)用該函數(shù)則返回下一個(gè)標(biāo)記述召。這里說的函數(shù)就是 next() 朱转。
這是next()的基本框架:其中“AAA”"BBB"是token類型;
void next() {
while (token = *src) {
++src;
if(token == AAA ){
.....
}else if(token == BBB ){
.....
}
}
}
用while循環(huán)的原因有以下幾個(gè):
處理錯(cuò)誤:
如果碰到了一個(gè)我們不認(rèn)識(shí)的字符桨武,可以指出錯(cuò)誤發(fā)生的位置肋拔,然后用while循環(huán)跳過當(dāng)前錯(cuò)誤,獲取下一個(gè)token并繼續(xù)編譯呀酸;跳過空白字符凉蜂;
在我們實(shí)現(xiàn)的tryC語言中,空格是用來作為分隔用的性誉,并不作為語法的一部分窿吩。因此在實(shí)現(xiàn)中我們將它作為“不識(shí)別”的字符進(jìn)行跳過。
現(xiàn)在來看看AAA错览、BBB具體是怎樣判斷的:
換行符和空白符
...
if (token == '\n') {
old_src = src; // 記錄當(dāng)前行纫雁,并跳過;
}
else if (token == ' ' || token == '\t') { }
...
注釋
...
else if (token == '#') { // skip comments
while (*src != 0 && *src != '\n') {
src++;
}
}
...
單個(gè)字符
...
else if ( token == '*' || token == '/' || token == ';' || token == ',' ||
token == '(' || token == ')' || token == '{' || token == '}' || token == '[' || token == ']') {
return;
}
...
數(shù)字
token 為Num倾哺;
token_val.val為值轧邪;
...
else if (token >= '0' && token <= '9') { // process numbers
token_val.val = (double)token - '0';
while (*src >= '0' && *src <= '9') {
token_val.val = token_val.val * 10.0 + *src++ - '0';
}
if (*src == '.') {
src++;
int countDig = 1;
while (*src >= '0' && *src <= '9') {
token_val.val = token_val.val + ((double)(*src++) - '0')/(10.0 * countDig++);
}
}
token = Num;
return;
}
...
字符串
token 為Str;
token_val.ptr保存字符串指針羞海;
...
else if (token == '"' ) { // parse string
last_pos = src;
char tval;
int numCount = 0;
while (*src != 0 && *src != token) {
src++;
numCount++;
}
if (*src) {
*src = 0;
token_val.ptr = malloc(sizeof(char) * numCount + 8);
strcpy(token_val.ptr, last_pos);
*src = token;
src++;
}
token = Str;
return;
}
...
字符
token 為Char忌愚;
token_val.val為值;
...
else if (token == '\'') { // parse char
token_val.val = *src++;
token = Char;
src++;
return;
}
...
變量:這是最復(fù)雜的一部分
對(duì)變量的處理需要以下幾個(gè)步驟:
- 獲取完整的變量名:
- 在符號(hào)表中查找變量:
- 如果在符號(hào)表中找到了變量却邓,根據(jù)變量不同的類型硕糊,返回不同的token值;
- 如果沒有找到腊徙,在符號(hào)表中間插入新的變量
關(guān)于符號(hào)表具體的內(nèi)容简十,會(huì)獨(dú)立出一篇文章來解釋。
...
else if ((token >= 'a' && token <= 'z') || (token >= 'A' && token <= 'Z') || (token == '_')) {
last_pos = src - 1; // process symbols
char nameBuffer[MAXNAMESIZE];
nameBuffer[0] = token;
while ((*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z') || (*src >= '0' && *src <= '9') || (*src == '_')) {
nameBuffer[src - last_pos] = *src;
src++;
}
nameBuffer[src - last_pos] = 0; // get symbol name
int i;
for (i = symPointer-1; i >= 0; --i) { // search symbol in symbol table
if (strcmp(nameBuffer, symtab[i].name) == 0) { // if find symbol: return the token according to symbol type
if (symtab[i].type == Num || symtab[i].type == Char) {
token_val.ptr = &symtab[i];
token = Sym;
}
else if (symtab[i].type == FuncSym) {
token_val.ptr = &symtab[i];
token = symtab[i].type;
}
else if (symtab[i].type == ArraySym) {
token_val.ptr = &symtab[i];
token = symtab[i].type;
}
else {
if (symtab[i].type == Void) {
token = Sym;
token_val.ptr = &symtab[i];
}
else token = symtab[i].type;
}
return;
}
}
strcpy(symtab[symPointer].name, nameBuffer); // if symbol not found, create a new one
symtab[symPointer].levelNum = currentlevel;
symtab[symPointer].type = Void;
token_val.ptr = &symtab[symPointer];
symPointer++;
token = Sym;
return;
}
...
其他的一些符號(hào)撬腾,可能需要再多讀取一個(gè)字符才能確定具體token
...
else if (token == '=') { // parse '==' and '='
if (*src == '=') {
src++;
token = Equal;
}
return;
}
else if (token == '+') { // parse '+' and '++'
if (*src == '+') {
src++;
token = Inc;
}
return;
}
else if (token == '-') { // parse '-' and '--'
if (*src == '-') {
src++;
token = Dec;
}
return;
}
else if (token == '!') { // parse '!='
if (*src == '=') {
src++;
token = Nequal;
}
return;
}
else if (token == '<') { // parse '<=', or '<'
if (*src == '=') {
src++;
token = LessEqual;
}
return;
}
else if (token == '>') { // parse '>=', or '>'
if (*src == '=') {
src++;
token = GreatEqual;
}
return;
}
else if (token == '|') { // parse '||'
if (*src == '|') {
src++;
token = OR;
}
return;
}
else if (token == '&') { // parse '&&'
if (*src == '&') {
src++;
token = AND;
}
return;
}
...
錯(cuò)誤處理
...
else {
printf("unexpected token: %d\n", token);
}
...
可對(duì)照源碼查看
https://github.com/yunwei37/tryC