解析中缀表示法的表达式的算法是什么？

我想在 PHP 中解析布尔表达式。如：

A and B or C and (D or F or not G)

这些术语可以被视为简单的标识符。它们会有一些结构，但解析器不需要担心这一点。它应该只识别关键字and or not ( )。其他一切都是一个术语。

我记得我们在学校写过简单的算术表达式求值器，但我不记得它是如何完成的了。我也不知道要在 Google/SO 中查找哪些关键字。

一个现成的库会很好，但据我记得该算法非常简单，因此自己重新实现它可能会很有趣且有教育意义。

递归下降解析器是写起来很有趣 and 易于阅读。第一步是写出你的语法。

也许这就是您想要的语法。

expr        = and_expr ('or' and_expr)*
and_expr    = not_expr ('and' not_expr)*
not_expr    = simple_expr | 'not' not_expr
simple_expr = term | '(' expr ')'

将其转变为递归下降解析器非常容易。只需为每个非终结符编写一个函数即可。

def expr():
    x = and_expr()
    while peek() == 'or':
        consume('or')
        y = and_expr()
        x = OR(x, y)
    return x

def and_expr():
    x = not_expr()
    while peek() == 'and':
        consume('and')
        y = not_expr()
        x = AND(x, y)
    return x

def not_expr():
    if peek() == 'not':
        consume('not')
        x = not_expr()
        return NOT(x)
    else:
        return simple_expr()

def simple_expr():
    t = peek()
    if t == '(':
        consume('(')
        result = expr()
        consume(')')
        return result
    elif is_term(t):
        consume(t)
        return TERM(t)
    else:
        raise SyntaxError("expected term or (")

这并不完整。您必须提供更多代码：

• 输入功能。 consume, peek, and is_term是您提供的功能。使用正则表达式很容易实现它们。consume(s)读取输入的下一个标记，如果不匹配则抛出错误s. peek()只是返回对下一个令牌的查看而不消耗它。is_term(s)返回 true 如果s是一个术语。

• 输出功能。 OR, AND, NOT, and TERM每次成功解析表达式的一部分时都会调用。他们可以做任何你想做的事。

• 包装函数。而不是仅仅打电话expr直接，您需要编写一个小包装函数来初始化使用的变量consume and peek，然后调用expr，最后检查以确保没有未消耗的剩余输入。

即使如此，代码量仍然很小。在Python中，完整的程序有84行，其中包括一些测试。