黄金解析系统-它可以在编程中用于什么?

简单的例子,lex将转换为:

如果(a+b>2),则

关于:

IF_TOKEN LEFT_PAREN IDENTIFIER(a) PLUS_SIGN IDENTIFIER(b) GREATER_THAN NUMBER(2) RIGHT_PAREN THEN_TOKEN

解析获取该令牌流,并尝试从中获得更多意义。在本例中,它将尝试将这些标记与IF_语句相匹配。对于解析,IF_语句可能如下所示:

 IF ( BOOLEAN_EXPRESSION ) THEN 

因此,解析器可以将上述内容转换为:

    if_statement
        |
        v
    boolean_expression.operator = GREATER_THAN
       |          |
       |          v
       V       numeric_constant.string="2" 
    expression.operator = PLUS_SIGN
     |     |
     |     v
     v   identifier.string = "b"
   identifier.string = "a"

这里有一个IF_语句。IF_语句只有一个参数,它是布尔_表达式。以某种方式向解析器解释了这一点。当解析器转换令牌流时,它“知道”IF是什么样的,并且知道BOOLEAN_表达式是什么样的,因此它可以在看到代码时进行适当的赋值。

例如,如果您刚刚:

如果(a+b)那么

接下来,我们将看到布尔_表达式有3个组件,运算符(大于)和两侧,左侧和右侧。

在左侧,它指向另一个表达式“a+b”,而在右侧,它指向一个数值_常量,在本例中是字符串“2”。同样,解析器“知道”这是一个数值常量,因为我们告诉它关于数字字符串。如果不是数字,它将是一个标识符(如“a”和“b”是)。

请注意,如果我们有如下内容:

如果(a+b>“XYZ”),则

如果我们这样做了:

如果[a>b)那么

解析器可以很容易地将该语法错误视为一个问题,并将抛出一个错误。这串代币看起来和它所知道的都不一样。

所以,关键是当你得到一个完整的解析树时,你有一些保证,在第一次剪切“代码看起来不错”。现在在执行过程中,很可能会出现其他错误。

要计算解析树,只需遍历树。在编译或求值部分,您将有一些代码与解析树的主要节点相关联。假设我们有一个翻译。

public void execute_if_statment(ParseTreeNode node) {
    // We already know we have a IF_STATEMENT node
    Value value = evaluate_expression(node.getBooleanExpression());
    if (value.getBooleanResult() == true) {
        // we do the "then" part of the code
    }
}

public Value evaluate_expression(ParseTreeNode node) {
    Value result = null;
    if (node.isConstant()) {
        result = evaluate_constant(node);
        return result;
    }
    if (node.isIdentifier()) {
        result = lookupIdentifier(node);
        return result;
    }
    Value leftSide = evaluate_expression(node.getLeftSide());
    Value rightSide = evaluate_expression(node.getRightSide());
    if (node.getOperator() == '+') {
        if (!leftSide.isNumber() || !rightSide.isNumber()) {
            throw new RuntimeError("Must have numbers for adding");
        }
        int l = leftSide.getIntValue();
        int r = rightSide.getIntValue();
        int sum = l + r;
        return new Value(sum);
    }
    if (node.getOperator() == '>') {
        if (leftSide.getType() != rightSide.getType()) {
            throw new RuntimeError("You can only compare values of the same type");
        }
        if (leftSide.isNumber()) {
            int l = leftSide.getIntValue();
            int r = rightSide.getIntValue();
            boolean greater = l > r;
            return new Value(greater);
        } else {
            // do string compare instead
        }
    }
}

你可以看到这里有一个递归计算器。您可以看到我们是如何检查运行时类型并执行基本计算的。

在我们的系统中,所有表达式都有一个运算符和左右两侧。表达式的每一面也是一个表达式,因此您可以看到我们如何立即尝试并计算它们,以获得它们的实际值。需要注意的是,如果表达式由一个常量组成,那么我们只需返回常量值,如果它是一个标识符,我们将它作为一个变量查找(这将是一个抛出“我找不到变量‘a’”消息的好地方),否则我们将返回到左侧/右侧。

我希望您能够看到,一旦您从解析器获得了令牌流,简单的计算器将如何工作。请注意,在评估过程中,语言的主要元素是如何到位的,否则我们将出现语法错误,永远无法进入此阶段。我们可以简单地期望“知道”当我们有一个,例如,加号操作符时,我们将有两个表达式,左边和右边。或者当我们执行IF语句时,我们已经有一个布尔表达式要计算。解析对我们来说是什么样的沉重负担。

开始使用一种新的语言可能是一个挑战,但你会发现一旦你开始使用,其余的都变得非常简单,并且它几乎是“神奇的”,最终一切都能正常工作。

请注意,请原谅格式错误,但下划线会把事情搞砸——我希望还是很清楚。

我推荐antlr.org作为参考,并推荐我在任何解析器使用中使用的“免费”工具。

GOLD可用于任何类型的应用程序,其中必须将上下文无关语法应用于输入。