美文网首页
从0开始自制解释器——添加对括号的支持

从0开始自制解释器——添加对括号的支持

作者: 一叶障目 | 来源:发表于2023-03-23 17:42 被阅读0次

    在上一篇我们添加了对乘除法的支持,也介绍了BNF范式,并且针对当前的算术表达式写出了对应的范式,同时根据范式给出相应的代码实现。这篇我们将继续为算数表达式添加对括号的支持。

    对应的BNF 范式

    在上一篇我们给出了乘除法对应的范式

    <expr>::=<term>{(PLUS|MINUS)<term>}
    <term>::=<factor>{(DIV|MUL)<factor>}
    <factor>::={(0|1|2|3|4|5|6|7|8|9)}
    

    针对乘除法的优先级比加减法高,我们的做法是将乘除法单独作为一个部分,然后在最外层表达式中只处理加减法。基于这种思路,我们来看如何处理括号的问题。例如下面的算数表达式

    ((1+2)*3+4) - (5 - 6 / 3)
    

    这里我们直接给出对应的文法,然后再来分析一下该如何由这个文法得到对应的表达式

    <expr>::=<term>{(PLUS|MINUS)<term>}
    <term>::=<factor>{(DIV|MUL)<factor>}
    <factor>::=({(0|1|2|3|4|5|6|7|8|9|)})|LPAREN<expr>RPAREN
    
    1. 首先根据表达式,它应该由两个term来组成 expr = term - term
    2. 接着看看两个term,它们并不是单纯的加法运算,所以两个term应该只有单纯的一个factor,也就是 expr = factor - factor
    3. 因为最外层都有括号,所以再次展开 expr = (expr1) - (expr2)
    4. 这时就又到了分析expr的过程了,左侧的expr最外层是一个加法,所以这里可以得到 expr1 = term + term
    5. 右侧的expr 最外层是一个减法,也就是 expr2 = term - term
    6. 结合最外层的表达式可以得到 expr = (term1 + term2) - (term3 - term4)
    7. term1 部分有一个乘法,所以它可以解析为 term1 = factor * factor
    8. term2 部分就是单独的数字所以可以得到 term2 = factor,并且进一步得到 term2=4
    9. term3 部分就是单纯的数字,可以得到 term3 = factor,并且进一步得到 term3=5
    10. term4 部分有一个除法,所以它可以解析为 term3 = factor / factor
    11. 此时整个表达式可以表示为 expr = (factor1 * factor2 + 4) - (5 - factor3 / factor4)
    12. factor1 本身也是一个括号,加表达式,所以它可以表示为 factor1 = (expr)
    13. factor2 是一个数字,所以它表示为 factor2 = 3
    14. factor3 是一个数字,所以它表示为 factor3 = 6
    15. factor4 是一个数字,所以它表示为 factor4 = 3
    16. 此时表达式可以是 expr = ((expr1) * 3 + 4) - (5 - 6 / 3)
    17. 此时再次分析这个 expr1 可以得到 expr1 = 1+2
    18. 这个时候,整个表达式就出来了 expr = ((1+2) * 3 + 4) - (5 - 6 / 3)

    用图来表示大概可以表示如下

    代码实现

    有了范式,我们就可以按照范式来组织代码实现。

    首先我们先在 ETokenType 中添加针对括号的标签

    typedef enum e_TokenType
    {
        CINT = 0, //整数
        PLUS, //加法
        MINUS, //减法
        DIV, //乘法
        MUL, //除法
        LPAREN, //左括号
        RPAREN, //右括号
        END_OF_FILE // 字符串末尾结束符号
    }ETokenType;
    

    然后在 get_next_token 函数中添加对括号进行词法分析并打标签的功能

    bool get_next_token(LPTOKEN pToken)
    {
        char c = get_next_char();
    
        dyncstring_reset(&pToken->value);
        if (is_digit(c))
        {
            dyncstring_catch(&pToken->value, c);
            pToken->type = CINT;
            parser_number(&pToken->value);
        }
        else if(is_space(c))
        {
            skip_whitespace();
            return get_next_token(pToken);
        }
        else
        {
            switch (c) {
            case '+':
                pToken->type = PLUS;
                break;
            case '-':
                pToken->type = MINUS;
                break;
            case '*':
                pToken->type = DIV;
                break;
            case '/':
                pToken->type = MUL;
                break;
            case '(':
                pToken->type = LPAREN;
                break;
            case ')':
                pToken->type = RPAREN;
                break;
            case '\0':
                pToken->type = END_OF_FILE;
                break;
            default:
                return false;
            }
        }
    
        return true;
    }
    

    这里我对这个函数进行了一些改写,针对依靠单个字符就能打上标签的采用switc来进行处理,像空白字符、数字这种有多种字符类型的就采用普通的if处理。

    然后在get_oper 中添加对括号的识别

        if (get_next_token(&token) && (token.type == PLUS || token.type == MINUS || token.type == DIV || token.type == MUL || token.type == LPAREN || token.type == RPAREN))
        {
            oper = token.type;
            if (pRet)
                *pRet = true;
        }
    

    然后根据文法,get_factor 需要能够返回一个 expr的结果,所以这里需要添加以下代码

        if (token.type == LPAREN)
        {
            bool bValid = true;
            value = expr(&bValid);
            if (!bValid)
                *pRet = false;
    
            if (get_next_token(&token) && token.type == RPAREN)
                *pRet = true;
            else
                *pRet = false;
        }
    

    如果我们得到的标签不为括号则按照原来的处理方式来处理,如果是括号,则将括号中的内容作为表达式并计算表达式的值,作为整数来返回。之前的expr 函数我们仅仅将结果打印并返回是否解析成功,这里需要做一些改进。我们使用一个传出参数来返回解析是否成功,而将计算结果作为值进行返回。

    另外需要特别注意的是,我们将反括号的判断放到了 get_factor 函数中,所以在 get_termexpr 中,遇到反括号应该考虑对位置索引进行递减,并且遇到反括号应该认为到达末尾并推出。这里的代码就不贴出来了。有兴趣的小伙伴可以看github上上传的代码。地址

    相关文章

      网友评论

          本文标题:从0开始自制解释器——添加对括号的支持

          本文链接:https://www.haomeiwen.com/subject/wtwirdtx.html