编译器实现之旅——第四章实现词法分析器

小仙女本仙人 2022-08-12 发布于北京

展开全文

在上一章的旅程中，我们讨论了词法分析器的实现思路，我们也为词法分析器的实现做了许多准备工作。现在，就让我们来实现词法分析器吧。

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，并退回当前读取到的字符。

略有不同的是，当词法分析器读取到一个“!”，然后进入“正在读取不等号”状态后，其必须继续读取到一个“=”，以构成“!=”；而如果此时读取到的字符并不是“=”，则将被认为是一个语法错误。

至此，“前端中的前端”——词法分析器，就已经全部实现完成了。接下来，我们需要为实现编译器前端的第二个组件——语法分析器做准备。请看下一章：《实现语法分析器前的准备》。