用c語言手搓一個(gè)600行的類c語言解釋器: 給編程初學(xué)者的解釋器教程(3)- 詞法分析

用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)記,原因如下:

  1. 字符串轉(zhuǎn)換成標(biāo)記流有時(shí)是有狀態(tài)的解阅,即與代碼的上下文是有關(guān)系的落竹。
  2. 保存所有的標(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è)步驟:

  1. 獲取完整的變量名:
  2. 在符號(hào)表中查找變量:
  3. 如果在符號(hào)表中找到了變量却邓,根據(jù)變量不同的類型硕糊,返回不同的token值;
  4. 如果沒有找到腊徙,在符號(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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末螟蝙,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子民傻,更是在濱河造成了極大的恐慌胰默,老刑警劉巖,帶你破解...
    沈念sama閱讀 219,039評(píng)論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件饰潜,死亡現(xiàn)場(chǎng)離奇詭異初坠,居然都是意外死亡和簸,警方通過查閱死者的電腦和手機(jī)彭雾,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,426評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來锁保,“玉大人薯酝,你說我怎么就攤上這事半沽。” “怎么了吴菠?”我有些...
    開封第一講書人閱讀 165,417評(píng)論 0 356
  • 文/不壞的土叔 我叫張陵者填,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我做葵,道長(zhǎng)占哟,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,868評(píng)論 1 295
  • 正文 為了忘掉前任酿矢,我火速辦了婚禮榨乎,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘瘫筐。我一直安慰自己蜜暑,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,892評(píng)論 6 392
  • 文/花漫 我一把揭開白布策肝。 她就那樣靜靜地躺著肛捍,像睡著了一般。 火紅的嫁衣襯著肌膚如雪之众。 梳的紋絲不亂的頭發(fā)上拙毫,一...
    開封第一講書人閱讀 51,692評(píng)論 1 305
  • 那天,我揣著相機(jī)與錄音酝枢,去河邊找鬼恬偷。 笑死,一個(gè)胖子當(dāng)著我的面吹牛帘睦,可吹牛的內(nèi)容都是我干的袍患。 我是一名探鬼主播,決...
    沈念sama閱讀 40,416評(píng)論 3 419
  • 文/蒼蘭香墨 我猛地睜開眼竣付,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼诡延!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起古胆,我...
    開封第一講書人閱讀 39,326評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤肆良,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后逸绎,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體惹恃,經(jīng)...
    沈念sama閱讀 45,782評(píng)論 1 316
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,957評(píng)論 3 337
  • 正文 我和宋清朗相戀三年棺牧,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了巫糙。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,102評(píng)論 1 350
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡颊乘,死狀恐怖参淹,靈堂內(nèi)的尸體忽然破棺而出醉锄,到底是詐尸還是另有隱情,我是刑警寧澤浙值,帶...
    沈念sama閱讀 35,790評(píng)論 5 346
  • 正文 年R本政府宣布恳不,位于F島的核電站,受9級(jí)特大地震影響开呐,放射性物質(zhì)發(fā)生泄漏烟勋。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,442評(píng)論 3 331
  • 文/蒙蒙 一筐付、第九天 我趴在偏房一處隱蔽的房頂上張望神妹。 院中可真熱鬧,春花似錦家妆、人聲如沸鸵荠。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,996評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽蛹找。三九已至,卻和暖如春哨坪,著一層夾襖步出監(jiān)牢的瞬間庸疾,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,113評(píng)論 1 272
  • 我被黑心中介騙來泰國(guó)打工当编, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留届慈,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,332評(píng)論 3 373
  • 正文 我出身青樓忿偷,卻偏偏與公主長(zhǎng)得像金顿,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子鲤桥,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,044評(píng)論 2 355