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

Question

我想在PHP中解析布尔表达式.如:

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每一块的表达的被成功地分析时间被调用.他们可以做任何你想做的事.

• 包装功能.而不是只打电话expr直接,你要编写初始化所使用的变量,一个小包装函数consume和peek,然后调用expr,最后检查,以确保有是没有得到消耗没有剩余输入.

即便如此,它仍然是一小部分代码.在Python中,完整的程序是84行,包括一些测试.

Answer 2

我会选择 Pratt 解析器。这几乎就像递归下降，但更聪明:) Douglas Crockford（JSLint 成名）在这里给出了一个不错的解释。