上下文
我正在攀登 Nearley 学习曲线,并尝试为搜索查询解析器编写语法。
目标
我想编写能够解析包含布尔运算符的查询字符串的语法(例如AND
、OR
、NOT
(。 让我们将这个问题的AND
作为一个微不足道的案例。
例如,语法应将以下示例字符串识别为有效:
- 裤子
- 裤子和袜子
- 跳千斤顶
尝试
我天真的尝试看起来像这样:
query ->
statement
| statement "AND" statement
statement -> .:+
问题所在
上面的语法尝试是不明确的,因为.:+
实际上可以匹配任何字符串。 我真正想要的是第一个条件匹配任何不包含AND
的字符串。 出现"AND"后,我只想输入第二个条件。
问题
如何在没有歧义语法的情况下检测这两种不同的情况?
我担心我错过了一些基本的东西;我可以想象大量的用例,我们希望由已知的运算符拆分任意文本。
是的,如果你有一个逃生舱口,可以是任何东西,你就会遇到问题。
在某个地方,您将想要定义您的基本代币集是什么,至少类似于S+
,然后如何组成这些代币。
我通常从解析器开始的地方是试图弄清楚递归在解析器中的位置,以及你依赖的解析库的方法。
看起来Nearley是一个Earley解析器,正如他们的维基百科条目所指出的那样,它们对于左递归是有效的。
这只是一个冒险的猜测,但这样的事情至少可能会让你合在一起。
CONJUNCTION -> AND | OR
STATEMENT -> TOKENS | (TOKENS CONJUNCTION STATEMENT)
TOKENS -> [^()]+
像这样的结构应该是明确的,并且禁止在标记中使用括号,除非它们被双引号包围。