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

Question

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

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

术语可以被视为简单的标识符。它们将具有一些结构，但解析器不需要担心这个问题。它应该只识别关键字and or not ( )。其他所有内容都是术语。 我记得我们在学校写过简单的算术表达式评估器，但我不记得它是如何完成的。我也不知道在Google / SO中要查找哪些关键字。 一个现成的库会很好，但是我记得算法非常简单，所以重新实现它可能会很有趣且具有教育意义。

- Vilx-

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行，其中还包括一些测试。

- Jason Orendorff

---

+1 是一种有趣的方式！我一直认为这是实现良好编程的最佳启发式方法。 - Edmund

嗯...它确实简单易读！:D 我想我得再深入研究一下。据我理解（但我并不是很懂），这只会向前查找一个符号，所以在某些语法上可能会失败...但那可能不是我的情况，也许我错了。:P - Vilx-

这个特定的函数只向前查看一个符号，但如果你需要更多的前瞻，你可以添加一个 peek_ahead(n) 函数并进行扩展。这实际上是递归下降的优势之一：将其修改以执行一些特定任务（因为你要解析的语言有点混乱）通常非常简单。 - Jason Orendorff

Python程序的链接已损坏。 - CarenRose

@CarenRose 现在应该已经修复了。谢谢。 - Jason Orendorff

Answer 2

为什么不直接使用PHP解析器呢？

 $terms=array('and','or','not','A','B','C','D'...);
 $values=array('*','+','!',1,1,0,0,1....);

 $expression="A and B or C and (D or F or not G)";
 $expression=preg_replace($terms, $values,$expression);
 $expression=preg_replace('^(+|-|!|1|0)','',$expression);
 $result=eval($expression);

实际上，第二个正则表达式是错误的（只有在需要防止任何代码注入时才需要）- 但您已经了解了这个想法。 C.

- symcbean

---

嗯...我猜这是有可能的...虽然会更加棘手，因为术语也会有特殊格式 - 比如 #23@45。 - Vilx-

Answer 3

我已经按照Plinth的建议实现了逆波兰表达式转换算法。然而，这个算法只会给你后缀表达式，也就是逆波兰表达式（RNP）。你仍然需要对它进行求值，但是一旦你有了RNP形式的表达式，这就非常容易了（例如在这里中有描述）。 下面的代码可能不符合良好的PHP编程风格，我的PHP知识有些有限。但是它应该足以让你理解思路。

$operators = array("and", "or", "not");
$num_operands = array("and" => 2, "or" => 2, "not" => 1);
$parenthesis  = array("(", ")");

function is_operator($token) {
    global $operators;
    return in_array($token, $operators);
}

function is_right_parenthesis($token) {
    global $parenthesis;
    return $token == $parenthesis[1];
}

function is_left_parenthesis($token) {
    global $parenthesis;
    return $token == $parenthesis[0];
}

function is_parenthesis($token) {
    return is_right_parenthesis($token) || is_left_parenthesis($token);
}

// check whether the precedence if $a is less than or equal to that of $b
function is_precedence_less_or_equal($a, $b) {
    // "not" always comes first
    if ($b == "not")
        return true;

    if ($a == "not")
        return false;

    if ($a == "or" and $b == "and")
        return true;

    if ($a == "and" and $b == "or")
        return false;

    // otherwise they're equal
    return true;
}


function shunting_yard($input_tokens) {
    $stack = array();
    $output_queue = array();

    foreach ($input_tokens as $token) {
        if (is_operator($token)) {
            while (is_operator($stack[count($stack)-1]) && is_precedence_less_or_equal($token, $stack[count($stack)-1])) {
                    $o2 = array_pop($stack);
                    array_push($output_queue, $o2);
            }
            array_push($stack, $token);

        } else if (is_parenthesis($token)) {
            if (is_left_parenthesis($token)) {
                array_push($stack, $token);
            } else {
                while (!is_left_parenthesis($stack[count($stack)-1]) && count($stack) > 0) {
                    array_push($output_queue, array_pop($stack));
                }
                if (count($stack) == 0) {
                    echo ("parse error");
                    die();
                }
                $lp = array_pop($stack);
            }
        } else {
            array_push($output_queue, $token);  
        }
    }

    while (count($stack) > 0) {
        $op = array_pop($stack);
        if (is_parenthesis($op))
            die("mismatched parenthesis");
        array_push($output_queue, $op);
    }

    return $output_queue;
}

function str2bool($s) {
    if ($s == "true")
        return true;
    if ($s == "false")
        return false;
    die('$s doesn\'t contain valid boolean string: '.$s.'\n');
}

function apply_operator($operator, $a, $b) {
    if (is_string($a))
        $a = str2bool($a);
    if (!is_null($b) and is_string($b))
        $b = str2bool($b);

    if ($operator == "and")
        return $a and $b;
    else if ($operator == "or")
        return $a or $b;
    else if ($operator == "not")
        return ! $a;
    else die("unknown operator `$function'");
}

function get_num_operands($operator) {
    global $num_operands;
    return $num_operands[$operator];
}

function is_unary($operator) {
    return get_num_operands($operator) == 1;
}

function is_binary($operator) {
    return get_num_operands($operator) == 2;
}

function eval_rpn($tokens) {
    $stack = array();
    foreach ($tokens as $t) {
        if (is_operator($t)) {
            if (is_unary($t)) {
                $o1 = array_pop($stack);
                $r = apply_operator($t, $o1, null);
                array_push($stack, $r);
            } else { // binary
                $o1 = array_pop($stack);
                $o2 = array_pop($stack);
                $r = apply_operator($t, $o1, $o2);
                array_push($stack, $r);
            }
        } else { // operand
            array_push($stack, $t);
        }
    }

    if (count($stack) != 1)
        die("invalid token array");

    return $stack[0];
}

// $input = array("A", "and", "B", "or", "C", "and", "(", "D", "or", "F", "or", "not", "G", ")");
$input = array("false", "and", "true", "or", "true", "and", "(", "false", "or", "false", "or", "not", "true", ")");
$tokens = shunting_yard($input);
$result = eval_rpn($tokens);
foreach($input as $t)
    echo $t." ";
echo "==> ".($result ? "true" : "false")."\n";

- ahans

---

太好了。完美无缺。谢谢。 - Kunal Dethe

Answer 4

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

- Rafał Dowgird

---

这么简单的表达式，这样做是否有点过度呢？ - Vilx-

Answer 5

Dijkstra's shunting yard algorithm 是将中缀表达式转换为后缀表达式的传统算法，常用于图形计算。

- plinth

---

啊，这是我们在学校里用的那个！不过我刚意识到 - 它如何与一元 NOT 运算符配合工作？ - Vilx-

与二进制没什么不同。您正在转换为RPN，因此A OR NOT B应变为A B NOT OR在rpn中。 - plinth

Answer 6

你可以使用LR解析器来构建解析树，然后评估该树以获取结果。其中包括例子的详细描述可以在Wikipedia中找到。如果你还没有编写过相关代码，我今晚可以写一个小例子给你。

- ahans

---

仅针对这样的逻辑表达式进行操作并不会过度杀伤。您将需要使用某种解析方式。但是我必须纠正解析树的问题：您不必显式地构建它，而可以在运行时评估结果。等待我的示例，您将看到它非常容易。;-) 然而，也许只是通过eval()使用PHP的解析器是您最实际的解决方案。 - ahans

今天不会实现LR解析器，但我现在很感兴趣，想知道与Shunting Yard相比，这个解决方案会是什么样子。 - ahans

Answer 7

最简单的方法是使用正则表达式将您的表达式转换为 PHP 语法中的表达式，然后使用 eval，正如 symcbean 建议的那样。但我不确定您是否想在生产代码中使用它。

另一种方法是编写自己的简单 递归下降解析器。它并不像听起来那么难。对于像您这样的简单语法（布尔表达式），您可以轻松从头开始编写一个解析器。您还可以使用类似于 ANTLR 的解析器生成器为 php，可能会找到一些 php 解析器生成器。

- MAK