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

Question

我想在 PHP 中解析 bool 表达式。如:

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

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

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

现成的库会很好，但我记得算法非常简单，所以自己重新实现它可能会很有趣并且很有教育意义。

Answer 1

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

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

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 和 is_term 是您提供的函数。使用正则表达式可以很容易地实现它们。 consume(s) 读取输入的下一个标记，如果不匹配 s 则抛出错误。 peek() 只是返回对下一个标记的窥视而不使用它。 is_term(s) 如果 s 是一个术语，则返回 true。

• 输出函数。 OR、AND、NOT 和 TERM 每次成功解析一段表达式时都会调用。他们可以为所欲为。

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

即使有了所有这些，代码量仍然很小。 In Python, the complete program is 84 lines ，其中包括一些测试。