布尔查询/表达式到Concrete语法树
我正在创建一个允许布尔表达式的搜索表单,例如:“foo AND bar”或“foo AND NOT bar”。
是否有PHP,Ruby或Java库可以将布尔表达式转换为具体的语法树?
(我可以编写自己的词法分析器/解析器,但我宁愿使用经过试验和测试的东西)
编辑:澄清一下,我不解析心律失常的表达。 它将用于解析允许布尔运算符的全文查询。
我推荐Treetop 。 这是一种为您的PEG( 解析表达式语法 )生成解析器的小语言 。 它比LALR语法更容易使用,并且比递归下降解析器更强大(即它可以做一些前瞻性多个符号)。
虽然Treetop并不复杂,但开始时有一些简单的例子是有帮助的。 你可以在threedaymonk的树梢上找到它们的例子 。
对于大多数解析器框架,标准入门语法之一通常是数学表达式解析器。 它会分析3+4*5-(6/-7)
等等。有些教程会更进一步,并向您展示如何构建语法树并评估表达式。
典型的boolean
表达式语法通常与此中缀表示法中的数学表达式语法直接类似。
-
AND
和OR
是二元运算符(即它们需要2个操作数),就像+
和*
-
NOT
是一元运算符(它需要1个操作数),就像一元一样-
- 有些运营商的优先级高于其他运营商
- 您可以使用
(…)
对子表达式进行分组
因此,您应该能够通过大多数解析器包的计算器教程并根据您的问题进行调整。 实际上,在许多方面, boolean
表达式解析更简单,因为例如:
- 在数学表达式中,
-
运算符被重载(可能是二元或一元) - 某些运算符(例如取幂)是右关联的
在boolean
表达式语法中,通常运算符不会重载,并且所有内容都是左关联的。
链接
- antlr.org – 计算器教程
我知道这个问题现在差不多有三年了,但我最近把Java中的一个库专门用来操作布尔表达式: jbool_expressions 。
它包含一个工具,也解析了字符串输入中的表达式:
Expression expr = ExprParser.parse("( ( (! C) | C) & A & B)")
您还可以进行一些相当简单的简化:
Expression simplified = RuleSet.simplify(expr); System.out.println(expr);
给
(A & B)
希望这可以帮助。
在寻找一个坐着的解算器时偶然发现了这个…… http://jboolexpr.sourceforge.net/可能就是你所需要的。
$patterns=array( '/\band\b/i', '/\bor\b/i', '/\bfoo\b/i', '/\bbar\b/i', '/\bnot\b/i'); $replace=array( '*', // value for 'and' '+', // value for 'or' '1', // value for 'foo' '0', // value for 'bar' '!'); // value for 'not' $expression="foo AND NOT bar"; $result=eval(preg_replace($pattern, $replace, $expression));
您可以轻松添加自己的事实,它将自动处理括号和优先级。 考虑如何处理$ expression中的意外输入可能是一个好主意(提示替换版本应该只包含1,0,+,*,(,)和!)
C。