在開始手寫詞法分析器之前呢，我們得先準(zhǔn)備好一些零件，規(guī)劃好將要使用哪些函數(shù)，如果函數(shù)沒有現(xiàn)成的，那還得自己寫。

輸入

由于我們需要從流中讀出，有時還需要放回流，詞法分析器顯然每次讀入都是按字符讀入，所以使用getchar函數(shù)一般沒有問題，然后對于放回流，C中提供了一個ungetc的后悔函數(shù)，首先先來嘗試一下這個函數(shù)：

int main()
{
    char t;
    t = getchar();
    cout << t;
    ungetc(t, stdin);
    t = 'a';
    t = getchar();
    cout << t;
    // input : 12, output : 11
}

其實(shí)也就是把這個字符放回到標(biāo)準(zhǔn)輸入流的最前面。

判斷

我們需要判斷一個字符它是字符還是數(shù)字，參考實(shí)驗(yàn)指導(dǎo)中的代碼，有一個頭文件ctype.h可以幫上忙 。

isalnum() 判斷一個字符是否是字母或數(shù)字

isalpha() 判斷一個字符是否是字母

isdigit() 判斷一個字符是否是十進(jìn)制數(shù)字

islower() 判斷一個字符是否是小寫字母

isspace() 判斷一個字符是否是空白符(包含\\n等空白效果的控制字符）

返回值：如果滿足，返回非0，不滿足，返回0；

子問題1：識別關(guān)鍵字、標(biāo)識符、數(shù)據(jù)類型

這一步要完成上面這一個分支，計(jì)劃使用Trie樹保存關(guān)鍵字，然后按照以下步驟進(jìn)行，完成一個函數(shù)就可以：

建樹過程：

// 預(yù)設(shè)的keywords和basic
string keyword[] = {"if", "while", "do", "break", "float", "true", "false"};
string basic[] = {"int", "char", "bool", "float"};
// 宏定義，使代碼更可讀
#define KEYWORD 1
#define BASIC 2
#define IDENTITY 3
// 定義全局變量
const int N = 128;
int son[N][N], idx;
int token[N * N]; // 定義這個idx對應(yīng)的token
// insert函數(shù)，詳見Trie樹
void insert(string s, int mode)
{
    int p = 0; // 從根節(jié)點(diǎn)開始
    for(int i = 0; i < s.size(); i ++)
    {
        if(!son[p][s[i]]) son[p][s[i]] = ++ idx;
        p = son[p][s[i]];
    }
    token[idx] = mode;
}
// 查詢函數(shù)，返回token類型
int query(string s)
{
    int p = 0;
    for(int i = 0; i < s.size(); i ++)
    {
        if(!son[p][s[i]]) return IDENTITY;
        p = son[p][s[i]];
    }
    return token[p];
}
// 初始化函數(shù)
void initialize()
{
    for(int i = 0; i < 7; i ++) insert(keyword[i], KEYWORD);
    for(int i = 0; i < 4; i ++) insert(basic[i], BASIC);
}

查詢測試：

已經(jīng)成功的可以使用了。

我們可以發(fā)現(xiàn)，不光是keyword和basic和identity，其他的字符也可以存到Trie樹里面去，比如以下專用符號：

= + - * / < <= > >= == != ; , ( ) [ ] { }

甚至是注釋符號：

/* */

子問題2：識別數(shù)字

首先，為了識別數(shù)字，我們先給出數(shù)字的正則表達(dá)式：

嘗試給出NFA

轉(zhuǎn)化為DFA

分析狀態(tài)轉(zhuǎn)移表：

上標(biāo)轉(zhuǎn)化為代碼表示：

int st[11][5] = {{0, 0, 0, 0, 0},
                 {2, 3, 4, 0, 0},
                 {0, 0, 4, 0, 0},
                 {0, 0, 4, 0, 0},
                 {0, 0, 4, 5, 7},
                 {0, 0, 6, 0, 0},
                 {0, 0, 6, 0, 7},
                 {8, 9, 10, 0, 0},
                 {0, 0, 10, 0, 0},
                 {0, 0, 10, 0, 0},
                 {0, 0, 10, 0, 0}};

根據(jù)狀態(tài)轉(zhuǎn)移表完成編程：

string num() // 輸入一個數(shù)字字符串
{
    string s;
    char t;

    int status = 1;
    int last_status;
    while(1){
        t = getchar();
        switch (t)
        {
        case '+':
            last_status = status;
            status = st[status][0];
            break;
        case '-':
            last_status = status;
            status = st[status][1];
            break;
        case '.':
            last_status = status;
            status = st[status][3];
            break;
        case 'E':
            last_status = status;
            status = st[status][4];
            break;
        case 'e':
            last_status = status;
            status = st[status][4];
            break;

        default:
            if(isdigit(t))
            {
                last_status = status;
                status = st[status][2];
            }
            else {
                last_status = status;
                status = 0;
            }
            break;
        }
        if(!status)
        {
            ungetc(t, stdin);
            break;
        }
        s += t;
    }
    status = last_status;
    if(status != 4 && status != 6 && status != 10) return "";
    return s;
}

結(jié)果測試：

于是乎我們又實(shí)現(xiàn)了一個有限狀態(tài)自動機(jī)，從而實(shí)現(xiàn)了數(shù)字字符串的輸入。

子問題3：將輸入分割為小字符串

要實(shí)現(xiàn)將輸入分割為小字符串，且向前看的步長僅為1步。首先我們需要分析出究竟在什么時候，才應(yīng)該將他們分開。

1） 以下劃線、字母開頭，使用Trie樹搜索；

2） 以+ -開頭，再看一步為數(shù)字，放回加減后使用DFA搜索；

3） 除+ -專用符號開頭，使用Trie樹搜索；

4） 注釋符號開頭，一直接收到遇到注釋尾。

子問題4：處理注釋

此處做一個簡化，不考慮注釋中的轉(zhuǎn)義字符，匹配到 */ 則結(jié)束。

string comments()
{
    string s;
    char last_c, c;

    while(last_c != '*' || c != '/')
    {
        last_c = c;
        c = getchar();
        s += c;
    }


    return s;
}

驗(yàn)證：

可以看到，它自動截取了注釋的前面部分。