編譯器實作之旅——第四章實作詞法分析器-有解無憂

在上一章的旅程中，我們討論了詞法分析器的實作思路，我們也為詞法分析器的實作做了許多準備作業，現在，就讓我們來實作詞法分析器吧，

1. 詞法分析器的類定義

詞法分析器的類定義如下：

class Lexer
{
public:

    // Constructor
    explicit Lexer(const string &inputFilePath);


    // NextToken
    Token NextToken();


    // Destructor
    ~Lexer();


private:

    // Attribute
    FILE *__filePtr;
    int __lineNo;


    // NextToken START Stage Dispatch
    void __nextTokenStartStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken IN_ID Stage Dispatch
    void __nextTokenInIDStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken IN_NUMBER Stage Dispatch
    void __nextTokenInNumberStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken IN_DIVIDE Stage Dispatch
    void __nextTokenInDivideStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken IN_COMMENT Stage Dispatch
    void __nextTokenInCommentStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken END_COMMENT Stage Dispatch
    void __nextTokenEndCommentStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken IN_LESS Stage Dispatch
    void __nextTokenInLessStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken IN_GREATER Stage Dispatch
    void __nextTokenInGreaterStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken IN_ASSIGN Stage Dispatch
    void __nextTokenInAssignStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);


    // NextToken IN_NOT Stage Dispatch
    void __nextTokenInNotStage(int nowChar, bool &saveBool, LEXER_STAGE &lexerStage,
        TOKEN_TYPE &tokenType, string &tokenStr);
};

可見，詞法分析器的核心函式是NextToken，每次呼叫這個函式，詞法分析器都會回傳下一個決議到的Token；為了實作詞法分析器的各個狀態的不同行為，我們定義了多個分派函式；此外，我們還定義了一個__lineNo變數，以記錄當前的行數，用于報錯資訊中，

2. 建構式和解構式的實作

接下來，我們來看看詞法分析器的建構式和解構式的實作：

Lexer::Lexer(const string &inputFilePath):
    __filePtr(fopen(inputFilePath.c_str(), "r")) {}


Lexer::~Lexer()
{
    fclose(__filePtr);
}

建構式和解構式的實作很簡單，這里就不討論了，

3. NextToken函式的實作

接下來，我們來看看詞法分析器最重要的NextToken函式的實作：

Token Lexer::NextToken()
{
    LEXER_STAGE lexerStage = LEXER_STAGE::START;
    TOKEN_TYPE tokenType;
    string tokenStr;

    while (lexerStage != LEXER_STAGE::DONE)
    {
        int nowChar = fgetc(__filePtr);
        bool saveBool = true;

        switch (lexerStage)
        {
            case LEXER_STAGE::START:
                __nextTokenStartStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::IN_ID:
                __nextTokenInIDStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::IN_NUMBER:
                __nextTokenInNumberStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::IN_DIVIDE:
                __nextTokenInDivideStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::IN_COMMENT:
                __nextTokenInCommentStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::END_COMMENT:
                __nextTokenEndCommentStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::IN_LESS:
                __nextTokenInLessStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::IN_GREATER:
                __nextTokenInGreaterStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::IN_ASSIGN:
                __nextTokenInAssignStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;

            case LEXER_STAGE::IN_NOT:
                __nextTokenInNotStage(nowChar, saveBool, lexerStage, tokenType, tokenStr);
                break;
        }

        if (saveBool)
        {
            tokenStr += nowChar;
        }
    }

    return {tokenType, tokenStr, __lineNo};
}

在決議開始前，我們首先將詞法分析器的狀態置為“開始”狀態，然后不斷回圈，直至詞法分析器的狀態變為“完成”狀態，在回圈體中，詞法分析器不斷讀入下一個字符，并利用一個saveBool布林值保存當前讀入的這個字符是否需要被保存，接下來，根據詞法分析器的不同狀態，分別呼叫各個分派函式，這些分派函式均具有修改saveBool，lexerStage，tokenType，tokenStr這些變數的能力，當分派函式執行完畢后，如果saveBool還是true，則將當前讀取到的字符加入記號字串中，最終，我們構造并回傳一個Token，

接下來，我們來看看各個分派函式的實作，首先從“開始”狀態的分派函式開始，

4. “開始”狀態的分派函式的實作

__nextTokenStartStage函式用于在詞法分析器處于“開始”狀態時被呼叫，其實作如下：

void Lexer::__nextTokenStartStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    if (isalpha(nowChar))
    {
        lexerStage = LEXER_STAGE::IN_ID;
    }
    else if (isdigit(nowChar))
    {
        lexerStage = LEXER_STAGE::IN_NUMBER;
    }
    else if (isspace(nowChar))
    {
        saveBool = false;

        if (nowChar == '\n')
        {
            __lineNo++;
        }
    }
    else
    {
        switch (nowChar)
        {
            case '+':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::PLUS;
                break;

            case '-':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::MINUS;
                break;

            case '*':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::MULTIPLY;
                break;

            case '/':
                saveBool = false;
                lexerStage = LEXER_STAGE::IN_DIVIDE;
                break;

            case '<':
                lexerStage = LEXER_STAGE::IN_LESS;
                break;

            case '>':
                lexerStage = LEXER_STAGE::IN_GREATER;
                break;

            case '=':
                lexerStage = LEXER_STAGE::IN_ASSIGN;
                break;

            case '!':
                lexerStage = LEXER_STAGE::IN_NOT;
                break;

            case ';':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::SEMICOLON;
                break;

            case ',':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::COMMA;
                break;

            case '(':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::LEFT_ROUND_BRACKET;
                break;

            case ')':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::RIGHT_ROUND_BRACKET;
                break;

            case '[':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::LEFT_SQUARE_BRACKET;
                break;

            case ']':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::RIGHT_SQUARE_BRACKET;
                break;

            case '{':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::LEFT_CURLY_BRACKET;
                break;

            case '}':
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::RIGHT_CURLY_BRACKET;
                break;

            case EOF:
                lexerStage = LEXER_STAGE::DONE;
                tokenType = TOKEN_TYPE::END_OF_FILE;
                break;

            default:
                InvalidChar(nowChar, __lineNo);
                break;
        }
    }
}

“開始”狀態是整個詞法分析器中最復雜的狀態，在這個狀態下，詞法分析器可能會遇到并處理很多種情況，列舉如下：

如果當前讀取到的字符是一個字母，則詞法分析器應進入“正在讀取單詞”狀態
同理，如果當前讀取到的字符是一個數字，則詞法分析器應進入“正在讀取數字”狀態
如果當前讀取到的字符是一個空白符，則詞法分析器應停留在“開始”狀態，并丟掉當前讀取到的字符，特別的，如果當前讀取到的字符是一個換行符，則當前行數需要加1
如果當前讀取到的字符是“+”、“-”、“*”、“;”、“,”、“(”、“)”、“[”、“]”、“{”、“}”或EOF這些僅由一個字符構成的記號，則我們可以立即確定當前記號的類別，并令詞法分析器立即進入“完成”狀態
如果當前讀取到的字符是“/”、“<”、“>”、“=”或“!”，則詞法分析器應進入各中間狀態
如果當前讀取到的字符不滿足上述各種情況之一，則報錯退出

這里需要額外說明的是，如果當前讀取到的字符是一個“/”，則我們此時并不知道這個“/”需不需要被保存下來，我們必須等到確定這個“/”是一個除號時，再保存這個“/”，故此時，我們需要將saveBool置為false，

5. “正在讀取單詞/數字”狀態的分派函式的實作

__nextTokenInIDStage與__nextTokenInNumberStage函式分別用于在詞法分析器處于“正在讀取單詞”和“正在讀取數字”狀態時被呼叫，其實作如下：

void Lexer::__nextTokenInIDStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    if (!isalpha(nowChar))
    {
        saveBool = false;
        ungetc(nowChar, __filePtr);
        lexerStage = LEXER_STAGE::DONE;
        tokenType = KEYWORD_MAP.count(tokenStr) ? KEYWORD_MAP.at(tokenStr) : TOKEN_TYPE::ID;
    }
}


void Lexer::__nextTokenInNumberStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    if (!isdigit(nowChar))
    {
        saveBool = false;
        ungetc(nowChar, __filePtr);
        lexerStage = LEXER_STAGE::DONE;
        tokenType = TOKEN_TYPE::NUMBER;
    }
}

當詞法分析器處于“正在讀取單詞”狀態時，如果當前讀取到的字符還是一個字母，那么此時什么都不需要做（詞法分析器的狀態不變，saveBool也不變）；如果不是，則我們知道：此時單詞已經讀完了，且很重要的一點是：當前讀取到的字符并不算在這個單詞內，所以，我們需要將saveBool置為false，并退回當前讀取到的字符至檔案句柄；同時，我們將詞法分析器的狀態置為“完成”狀態；此外，我們需要查閱關鍵詞表，以確定當前讀取到的單詞是否是一個關鍵詞，

當詞法分析器處于“正在讀取數字”狀態時，情況與“正在讀取單詞”狀態是幾乎一致的，唯獨不同的是，讀取數字時不需要進行關鍵詞判定，

6. “正在讀取除號”狀態的分派函式的實作

__nextTokenInDivideStage函式用于在詞法分析器處于“正在讀取除號”狀態時被呼叫，其實作如下：

void Lexer::__nextTokenInDivideStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    if (nowChar == '*')
    {
        saveBool = false;
        lexerStage = LEXER_STAGE::IN_COMMENT;
    }
    else
    {
        saveBool = false;
        ungetc(nowChar, __filePtr);
        lexerStage = LEXER_STAGE::DONE;
        tokenType = TOKEN_TYPE::DIVIDE;
        tokenStr = "/";
    }
}

當詞法分析器已經讀取到了一個“/”后，其進入“正在讀取除號”狀態（請注意，此時的saveBool是false），此時，如果又讀取到了一個“”，則詞法分析器應進入“正在讀取注釋”狀態；反之，如果讀取到的字符不是“”，我們就可以確定：之前讀取到的“/”真的是一個除號，那么我們就需要退回當前讀取到的這個字符，然后將詞法分析器的狀態置為“完成”狀態，并設定記號的類別和記號字串，

7. “正在讀取/逃離注釋”狀態的分派函式的實作

__nextTokenInCommentStage和__nextTokenEndCommentStage函式分別用于在詞法分析器處于“正在讀取注釋”和“正在逃離注釋”狀態時被呼叫，其實作如下：

void Lexer::__nextTokenInCommentStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    saveBool = false;

    if (nowChar == '*')
    {
        lexerStage = LEXER_STAGE::END_COMMENT;
    }
}


void Lexer::__nextTokenEndCommentStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    saveBool = false;

    if (nowChar == '/')
    {
        lexerStage = LEXER_STAGE::START;
    }
    else if (nowChar != '*')
    {
        lexerStage = LEXER_STAGE::IN_COMMENT;
    }
}

首先，不管是哪個函式，只要和注釋搭邊了，saveBool都應置false，

正如上一章所說，當詞法分析器處于“正在讀取注釋”狀態時，其只希望看到“*”，如果看到了，則詞法分析器的狀態就應轉入“正在逃離注釋”狀態，否則，什么都沒有變，詞法分析器將仍然處于“正在讀取注釋”狀態，

同理，當詞法分析器處于“正在逃離注釋”狀態時，如果其看到的是“/”，則詞法分析器就成功逃離了注釋，其狀態就回到了“開始狀態”；而如果其看到的還是“*”，則詞法分析器將繼續停留在“正在逃離注釋”狀態；否則，很可惜，詞法分析器應退回到“正在讀取注釋”狀態，

8. “正在讀取小于號/大于號/等號/不等號”狀態的分派函式的實作

__nextTokenInLessStage、__nextTokenInGreaterStage、__nextTokenInAssignStage、__nextTokenInNotStage函式分別用于在詞法分析器處于“正在讀取小于號”、“正在讀取大于號”、“正在讀取等號”和“正在讀取不等號”狀態時被呼叫，其實作如下：

void Lexer::__nextTokenInLessStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    lexerStage = LEXER_STAGE::DONE;

    if (nowChar == '=')
    {
        tokenType = TOKEN_TYPE::LESS_EQUAL;
    }
    else
    {
        saveBool = false;
        ungetc(nowChar, __filePtr);
        tokenType = TOKEN_TYPE::LESS;
    }
}


void Lexer::__nextTokenInGreaterStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    lexerStage = LEXER_STAGE::DONE;

    if (nowChar == '=')
    {
        tokenType = TOKEN_TYPE::GREATER_EQUAL;
    }
    else
    {
        saveBool = false;
        ungetc(nowChar, __filePtr);
        tokenType = TOKEN_TYPE::GREATER;
    }
}


void Lexer::__nextTokenInAssignStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    lexerStage = LEXER_STAGE::DONE;

    if (nowChar == '=')
    {
        tokenType = TOKEN_TYPE::EQUAL;
    }
    else
    {
        saveBool = false;
        ungetc(nowChar, __filePtr);
        tokenType = TOKEN_TYPE::ASSIGN;
    }
}


void Lexer::__nextTokenInNotStage(int nowChar, bool &saveBool,
    LEXER_STAGE &lexerStage, TOKEN_TYPE &tokenType, string &tokenStr)
{
    if (nowChar == '=')
    {
        lexerStage = LEXER_STAGE::DONE;
        tokenType = TOKEN_TYPE::NOT_EQUAL;
    }
    else
    {
        InvalidChar(nowChar, __lineNo);
    }
}

這幾個函式的實作思路都是一致的，其均用于處理類似于：當前記號是一個“<”還是一個“<=”的矛盾，我們不妨以“正在讀取小于號”為例，來看看這幾個函式的實作，

當詞法分析器已經讀取到了一個“<”后，其進入“正在讀取小于號”狀態，在此狀態下，無論當前讀取到的字符是什么，詞法分析器都一定會進入“完成”狀態，我們只需要看看當前讀取到的字符是不是一個“=”，如果是，則我們就讀取到了一個“<=”；如果不是，則我們就只是讀取到了一個“<”，和前面一樣，此時我們需要置saveBool為false，并退回當前讀取到的字符，

略有不同的是，當詞法分析器讀取到一個“!”，然后進入“正在讀取不等號”狀態后，其必須繼續讀取到一個“=”，以構成“!=”；而如果此時讀取到的字符并不是“=”，則將被認為是一個語法錯誤，

至此，“前端中的前端”——詞法分析器，就已經全部實作完成了，接下來，我們需要為實作編譯器前端的第二個組件——語法分析器做準備，請看下一章：《實作語法分析器前的準備》，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261292.html

標籤：其他

上一篇：無重復字符的最長子串

下一篇：最大連續1的個數

編譯器實作之旅——第四章 實作詞法分析器