我想在 PHP 中解析布尔表达式。例如:
A and B or C and (D or F or not G)
术语可以被视为简单的标识符。它们将具有一些结构,但解析器不需要担心这个问题。它应该只识别关键字and or not ( )
。其他所有内容都是术语。
我记得我们在学校写过简单的算术表达式评估器,但我不记得它是如何完成的。我也不知道在Google / SO中要查找哪些关键字。
一个现成的库会很好,但是我记得算法非常简单,所以重新实现它可能会很有趣且具有教育意义。我想在 PHP 中解析布尔表达式。例如:
A and B or C and (D or F or not G)
术语可以被视为简单的标识符。它们将具有一些结构,但解析器不需要担心这个问题。它应该只识别关键字and or not ( )
。其他所有内容都是术语。
我记得我们在学校写过简单的算术表达式评估器,但我不记得它是如何完成的。我也不知道在Google / SO中要查找哪些关键字。
一个现成的库会很好,但是我记得算法非常简单,所以重新实现它可能会很有趣且具有教育意义。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行,其中还包括一些测试。
$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.
$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";
我会选择Pratt解析器。它几乎像递归下降但更聪明 :) Douglas Crockford(JSLint的作者)在这里给出了一个不错的解释(链接)。
Dijkstra's shunting yard algorithm 是将中缀表达式转换为后缀表达式的传统算法,常用于图形计算。
你可以使用LR解析器来构建解析树,然后评估该树以获取结果。其中包括例子的详细描述可以在Wikipedia中找到。如果你还没有编写过相关代码,我今晚可以写一个小例子给你。
最简单的方法是使用正则表达式将您的表达式转换为 PHP 语法中的表达式,然后使用 eval,正如 symcbean 建议的那样。但我不确定您是否想在生产代码中使用它。
另一种方法是编写自己的简单 递归下降解析器。它并不像听起来那么难。对于像您这样的简单语法(布尔表达式),您可以轻松从头开始编写一个解析器。您还可以使用类似于 ANTLR 的解析器生成器为 php,可能会找到一些 php 解析器生成器。
peek_ahead(n)
函数并进行扩展。这实际上是递归下降的优势之一:将其修改以执行一些特定任务(因为你要解析的语言有点混乱)通常非常简单。 - Jason Orendorff