526互联

从0开始自制解释器——重构代码

发布时间 2023-04-08 18:50:24作者: masimaro

在上一篇文章中，完成了对括号的支持，这样整个程序就可以解析普通的算术表达式了。但是在解析两个括号的过程中发现有大量的地方需要进行索引的回退操作，索引的操作应该保证能得到争取的token，这个步骤应该放在词法分析的阶段，如果在语法分析阶段还要考虑下层词法分析的过程，就显得有些复杂了。而且随着后续支持的符号越来越多，可能又得在大量的地方进行这种索引变更的操作，代码将难以理解和维护。因此这里先停下来进行一次代码的重构。

基本架构

这里的代码我按照教程里面的结构进行组织。将按照程序的逻辑分为3层，最底层负责操作字符串的索引保证下次获取token的时候索引能在正确的位置。第二层是词法分析部分，负责给字符串的每个部分都打上对应的token。第三个部分是语法分析的部分，它负责解析之前设计的BNF范式，并计算对应的结果。

详细的代码

上面给出模块划分的概要可能没怎么说清楚，下面将通过代码来进行详细的说明。

Token 模块

为了支持这个设计，首先变更一下全局变量的定义，现在定义的全局变量如下所示

extern Token g_currentToken; //当前token
extern int g_nPosition; //当前字符索引的位置
extern char g_currentChar; //当前字符串

之前通过 get_next_char() 来返回当前指向的token并变更索引的时候发现我们在任何时候想获取当前指向的字符时永远要变更索引，这样就不得不考虑在某些时候要进行索引的回退。比如在解析整数退出的时候，此时当前字符已经指向下一个字符了，但是我们在接下来解析其他符号的时候调用 get_next_char() 导致索引多增加了一个。这种情况经常出现，因此这里使用全局变量保存当前字符，只在需要进行索引增加的时候进行增加。另外我们不希望上层来直接操作这个索引，因此在最底层的Token模块提供一个名为 advance() 的函数用于将索引加一，并获取之后的字符。它的定义如下

void advance()
{
    g_nPosition++;
    // 如果到达字符串尾部，索引不再增加
    if (g_nPosition >= strlen(g_pszUserBuf))
    {
        g_currentChar = '\0';
    }
    else
    {
        g_currentChar = g_pszUserBuf[g_nPosition];
    }
}

这样在对应需要用到当前字符的位置就不再使用 get_next_char() , 而是改用全局变量 g_currentChar。例如现在的 skip_whitespace 函数现在的定义如下

void skip_whitespace()
{
    while (is_space(g_currentChar))
    {
        advance();
    }
}

这样我们在获取下一个token的时候只在必要的时候进行索引的递增。

lex 模块

由于打标签的工作交个底层的Token模块了，该模块主要用来实现词法分析的功能，也就是给各个部分打上标签，根据之前Token部分提供的接口，需要对 get_next_token 函数进行修改。

bool get_next_token()
{
    dyncstring_reset(&g_currentToken.value);
    while (g_currentChar != '\0')
    {
        if (is_digit(g_currentChar))
        {
            g_currentToken.type = CINT;
            parser_number(&g_currentToken.value);
            return true;
        }
        else if (is_space(g_currentChar))
        {
            skip_whitespace();
        }
        else
        {
            switch (g_currentChar)
            {
                case '+':
                    g_currentToken.type = PLUS;
                    dyncstring_catch(&g_currentToken.value, '+');
                    advance();
                    break;
                case '-':
                    g_currentToken.type = MINUS;
                    dyncstring_catch(&g_currentToken.value, '-');
                    advance();
                    break;
                case '*':
                    g_currentToken.type = DIV;
                    dyncstring_catch(&g_currentToken.value, '*');
                    advance();
                    break;
                case '/':
                    g_currentToken.type = MUL;
                    dyncstring_catch(&g_currentToken.value, '/');
                    advance();
                    break;
                case '(':
                    g_currentToken.type = LPAREN;
                    dyncstring_catch(&g_currentToken.value, '(');
                    advance();
                    break;
                case ')':
                    g_currentToken.type = RPAREN;
                    dyncstring_catch(&g_currentToken.value, ')');
                    advance();
                    break;
                case '\0':
                    g_currentToken.type = END_OF_FILE;
                    break;
                default:
                    return false;
            }

            return true;
        }
    }

    return true;
}

在这个函数中，将不再通过输出参数来返回当前的token，而是直接修改全局变量。同时也不再使用get_next_char 函数来获取当前指向的字符，而是直接使用全局变量。并且在适当的时机调用advance 来实现递增。

另外在上层我们直接使用 g_currentToken 拿到当前的token，而在适当的时机调用新增的eat() 函数来实现更新token的操作。

bool eat(LPTOKEN pToken, ETokenType eType)
{
    if (pToken->type == eType)
    {
        get_next_token();
        return true;
    }

    return false;
}

该函数接受两个参数，第一个是当前token的值，第二个是我们期望当前token是何种类型。如果当前token的类型与期望的不符则报错，否则更新token。

interpreter 模块

该模块主要负责解析根据前面的BNF范式来完成计算并解析内容。这个模块提供三个函数get_factor、get_term、expr。这三个函数的功能没有变化，只是在实现上依靠lex 模块提供的功能。主要思路是直接使用 g_currentToken 这个全局变量来获得当前的token，使用 eat() 来更新并获得下一个token的值。这里我们以get_factor() 函数为例

int get_factor(bool* pRet)
{
    int value = 0;
    if (g_currentToken.type == CINT)
    {
        value = atoi(g_currentToken.value.pszBuf);
        *pRet = eat(&g_currentToken, CINT);
    }
    else
    {
        if (g_currentToken.type == LPAREN)
        {
            bool bValid = true;
            bValid = eat(&g_currentToken, LPAREN);
            value = expr(&bValid);
            bValid = eat(&g_currentToken, RPAREN);
            *pRet = bValid;
        }
    }

    return value;
}

与前面分析的相同，该函数主要负责获取整数和计算括号中子表达式的值。在解析完整数和括号中的子表达式之后，需要调用eat分别跳过对应的值。只是在识别到括号之后需要跳过左右两个括号。

这样就完成了对应的分层，每层只负责自己该做的事。不用在上层考虑修改索引的问题，结构也更加清晰，未来在添加功能的时候也更加方便。剩下几个函数就不再贴出代码了，感兴趣的小伙伴可以去对应的GitHub仓库上查阅相关代码。
从0开始自制解释器——重构代码