c++ - 解释器的良好优化

Question

关闭。这个问题需要更多 focused .它目前不接受答案。












想改进这个问题？更新问题，使其仅关注一个问题 editing this post .

7年前关闭。




Improve this question




我正在为我自己的编程语言构建一个解释器作为一种爱好，使用 C++11。到目前为止，我的解释器可以理解变量、表达式和打印语句。

我的解释器只是一个简单的解释器，它将源文件转换为标记列表，解析器只需执行标记，因为它在存储标记的 C++ vector 中找到它们。

变量查找

我查找变量的方式是，我获取变量名的长度，然后循环遍历变量 vector ，只获取变量名长度的第一个字符。当我找到变量名时，我会抓取变量的其余部分，变量名和值的存储方式如下:

variable_name:variable_value

如果变量值是字符串，则变量值周围有引号。

表达式评估

在评估表达式时，我首先一次循环遍历表达式 1 个字符，并确定该字符是数字、运算符还是括号。然后，如果有一个超过 1 个字符的数字，则将完整的数字字符组合在一起。

当我这样做时，我会将所有内容添加到 vector 中。我计算前置减号的数量是否是偶数，以便我知道是用加号还是减号替换它们。

例子:

------------10  ->  becomes +10
because there are 12 minuses before the 10

然后我循环遍历 vector 并计算左括号的数量，当我看到左括号时，我将迭代器的值存储在一个变量中。然后我从那个迭代器开始，抓取括号内部的内容。

然后我循环遍历括号的内部，首先进行除法，然后再次循环并进行乘法，然后进行减法，最后进行加法。然后，当评估完成时，我删除表达式的那部分周围的括号，并将值存储在 vector 中的左​​括号位置。

例子:

(10 + -(2 * 4))
(10 + -(8))
(10 + - 8)
(10 - 8)
(2)

我写了一个手写的词法分析器和解析器。词法分析器只是按照您的预期进行，它将源代码作为字符串循环，一次 1 个字符，并将这些字符组合在一起以识别每个标记。

解析器只是将标记 vector 中的项目与字符串进行比较，没有正则表达式。

解析器示例

token vector 如下所示:

[0] print
[1] string:"Hello World"
[2] sc

解析器使用字符串 print string sc识别标记顺序背后的含义。

我可以对我做事的方式进行任何好的优化吗？我从来没有学过计算机科学或任何编译器类(class)，所以我很感激任何改进我的解释器的提示。如果你愿意，我可以给你看代码，虽然它很长。

Answer 1

您可以获得的最大加速可能是(假设是动态类型语言):

创建一个可以存储数字、字符串、 bool 值和其他值类型的通用值对象，您将使用您的语言

将表达式解析为 AST

例如

struct Value {
    int type;
    enum {
       NUMBER = 1,
       STRING = 2
    };
    double doubleValue;         // Value in case it's a number
    std::string stringValue;    // Value in case it's a string

    Value(double x) : type(NUMBER), doubleValue(x) { }
    Value(const std::string& x) : type(STRING), stringValue(x) { }
};

那么一个 AST 节点可以是一个常量、一个变量查找、一元运算或二元运算:

struct ASTNode {
    virtual Value compute() = 0;
    virtual ~ASTNode() {}
};

struct ConstantNode : ASTNode {
    Value x;
    ConstantNode(Value x) : x(x) {}
    virtual Value compute() { return x; }
};

struct VariableNode : ASTNode {
    std::string name;
    VariableNode(const std::string& name) : name(name) {}
    virtual value compute() { return lookup(name); }
};

struct AdditionNode : ASTNode {
    ASTNode *a, *b;
    AdditionNode(ASTNode *a, ASTNode *b) : a(a), b(b) {}
    virtual Value compute() {
        Value av = a->compute();
        Value bv = b->compute();
        if (av.type == Value::NUMBER && bv.type == Value::NUMBER) {
            return av.doubleValue + bv.doubleValue;
        } else if (av.type == Value::STRING && bv.type == Value::STRING) {
            return av.stringValue + bv.stringValue;
        } else {
            throw std::runtime_error("Type mismatch");
        }
    }
};

您要使用哪种类型的指针取决于您计划如何管理内存(在自定义池中分配节点的裸指针对于垃圾收集方法可能是可以的，否则一些引用计数的智能指针会更好地工作)。

使用这种方法计算表达式时，您只需执行所需的操作(无需在运行时重做解析)。