bnf - 如何为 bool 搜索运算符编写明确的 nearley 语法

Question

背景

我正在攀登 Nearley学习曲线并尝试为搜索查询解析器编写语法。

目标

我想编写能够解析包含 bool 运算符(例如 AND、OR、NOT)的查询字符串的语法。让我们对这个问题使用 AND 作为一个简单的案例。

例如，语法应该将这些示例字符串识别为有效:

• 裤子
• 裤子和 socks
• 开合跳

尝试

我天真的尝试看起来像这样:

query -> 
    statement
  | statement "AND" statement

statement -> .:+

问题

上面的语法尝试是有歧义的，因为 .:+ 将匹配任何字符串。我真正想要的是第一个条件匹配任何不包含 AND 的字符串。一旦出现“AND”，我只想输入第二个条件。

问题

如何在没有歧义语法的情况下检测这两种不同的情况？

我担心我遗漏了一些基本的东西；我可以想象大量的用例，我们希望通过已知运算符拆分任意文本。

Answer 1

是的，如果您有一个实际上可以是任何东西的逃生舱口，您就会遇到问题。

在某个地方你会想要定义你的基本标记集是什么，至少是像 \S+ 这样的东西，然后是这些标记是如何组成的。

对于解析器，我通常开始的地方是试图弄清楚递归在解析器中的位置，以及解析您所依赖的库的方法。

看起来 Nearley 是一个 Earley 解析器，并且 the wikipedia entry for them notes, they're efficient for left-recursion .

这只是一个冒险的猜测，但这样的事情至少可以让你合取。

CONJUNCTION -> AND | OR
STATEMENT -> TOKENS | (TOKENS CONJUNCTION STATEMENT)
TOKENS -> [^()]+

像这样的结构应该是明确的并且禁止在标记中使用括号，除非它们被双引号括起来。