什么是算法解析EX pressions中缀表示法？ [英] What is the algorithm for parsing expressions in infix notation?

问题描述

我想解析布尔EX pressions在PHP。如下所示：

I would like to parse boolean expressions in PHP. As in:

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

该条款可以被认为是简单的标识符。他们将有一个小的结构，但是解析器并不需要担心。它应该只是识别关键字键，否（）。一切是一个词。

我记得我们在学校里写了简单的算术EX pression评估，但我不记得是怎么回事了完成的。我也不知道是什么关键字来查找在谷歌/左右。

I remember we wrote simple arithmetic expression evaluators at school, but I don't remember how it was done anymore. Nor do I know what keywords to look for in Google/SO.

有一个现成的库将是很好，但我记得算法是pretty的简单，所以它可能是有趣和教育，以重新实现它自己。

A ready made library would be nice, but as I remember the algorithm was pretty simple so it might be fun and educational to re-implement it myself.

推荐答案

递归下降解析器的乐趣写和轻松阅读。第一步是写你的语法了。

Recursive descent parsers are fun to write and easy to read. The first step is to write your grammar out.

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

Maybe this is the grammar you want.

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

打开这个成一个递归下降解析器是超级容易。只要写每个非终结一个函数。

Turning this into a recursive descent parser is super easy. Just write one function per nonterminal.

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 (")

这是不完整的。你必须提供多一点code：

This isn't complete. You have to provide a little more code:

• 输入功能。 消耗，偷看和 is_term 你提供的功能。他们会很容易实现使用常规EX pressions。 消费（S）读取输入的下一个标记，并抛出一个错误，如果它不匹配取值。 PEEK（）只返回一个偷看的下一个标记而不消费它。 is_term（S）返回true，如果取值是一个词。

• Input functions. consume, peek, and is_term are functions you provide. They'll be easy to implement using regular expressions. consume(s) reads the next token of input and throws an error if it doesn't match s. peek() simply returns a peek at the next token without consuming it. is_term(s) returns true if s is a term.

输出功能。 或，和，不是和 TERM 每次一张的前pression被成功解析被调用。他们可以做任何你想要的。

Output functions. OR, AND, NOT, and TERM are called each time a piece of the expression is successfully parsed. They can do whatever you want.

包装函数。而不是只调用了 EXPR 直接，你会想要写一个小包装函数初始化变量使用消耗和偷看，然后调用 EXPR ，和最后检查，以确保没有任何剩余的输入未得到消耗。

Wrapper function. Instead of just calling expr directly, you'll want to write a little wrapper function that initializes the variables used by consume and peek, then calls expr, and finally checks to make sure there's no leftover input that didn't get consumed.

即使这一切，它仍然是code一个很小的量。 在Python，完整的程序是84线的，这包括一些测试。

Even with all this, it's still a tiny amount of code. In Python, the complete program is 84 lines, and that includes a few tests.

这篇关于什么是算法解析EX pressions中缀表示法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！