javascript - 表达语言语法

Question

我想构建一个可以解析此类表达式的解析器:

• A=3
• A<5 或 B>C
• A=null 或(B=3 且 C=false)

然后构建Mongo查询表达式。如果有这样的图书馆，那会对我有很大帮助。与此同时，我开始编写自己的解析器。我发现 Ohm.js 看起来很简单，而且有在线编辑器。我能够到达那里:

Query {
  exp = simpleExp | andExp | orExp
  simpleExp = identifierName operator literal
  andExp = simpleExp "AND" simpleExp
  orExp = simpleExp " OR " simpleExp
  identifierName = identifierStart identifierPart*
  identifierStart = letter
  identifierPart =  letter | digit
  nullLiteral = "null"
  booleanLiteral = ("true" | "false")
  decimalLiteral = digit*
  stringLiteral = "\"" digit* "\""
  literal = stringLiteral | decimalLiteral | booleanLiteral | nullLiteral
  operator = "=" | "<" | ">" | ">=" | "<="  
}

在线编辑器接受简单表达式 (A=3)，但不匹配 AND/OR 组合表达式。我的错误在哪里？顺便说一句，我不坚持这个库，我可以接受其他parsers以及。

Answer 1

有两件事导致您的 exp 规则无法匹配输入 A=2 AND B=3。

为了更好地理解这些，最好阅读 Ohm 的文档，例如；具体来说，syntax reference .

首先，用欧姆的话来说，exp 规则是一个“词法规则”，因为它的名称以小写字母开头。 syntactic and lexical rules 之间只有很小的差异，但它在这里发挥了重要作用:

The difference between lexical and syntactic rules is that syntactic rules implicitly skip whitespace characters.

由于您的规则都不是语法规则，因此不会忽略空格。但它也无法被识别，除了有点奇怪的 "OR " 标记。特别是，语法无法识别 AND 之前的空格，因此解析在此时失败。

因此第一步是将 simpleExp、andExp 和 orExp 重命名为 SimpleExp 来将其更改为语法规则、 AndExp 和 OrExp 分别。如果需要，您可以将 "OR " 更改为 "OR"。

第二个问题就没那么简单了。要解决这个问题，查看 Ohm example arithmetic grammar 中使用的模型会很有用。 。 (请记住，语法只与符号的组织有关；符号的含义在其他地方处理。因此，使用运算符 AND 和 OR 的 bool 表达式语法不同于仅在运算符的拼写方式上使用运算符 * 和 + 的算术语法。算术语言语法确定 * 优先级的方式+ 与 bool 语法指定 AND 优先于 OR 的方式完全相同。但这不是语法的组织方式.

特别是，您违反了 PEG 解析器(如 Ohm)的一个关键方面，Ohm documentation 中也提到了这一点。 。 PEG 形式中的交替(| 运算符)是有序的:(添加强调)

expr1 | expr2

Matches the expression expr1, and if that does not succeed, matches the expression expr2.

换句话说，如果 expr1 匹配，则永远不会尝试 expr2。

考虑到这一点，请考虑以下规则:

exp = simpleExp | andExp | orExp

由于 andExp 和 orExp 均以 simpleExp 开头，因此无法匹配它们中的任何一个。为了使它们匹配，simpleExp 必须匹配，如果 simpleExp 匹配，则替换立即成功，而无需尝试其他替代方案。 (许多 PEG 解析系统使用 / 作为交替运算符的名称，而不是上下文无关语法使用的 |，以避免混淆两个运算符的语义。但欧姆选择不这样做。)

事实上，Ohm 的示例语法并不理想；它遇到了自上而下解析(与 PEG 解析共享)的常见问题，无法处理左递归语法。因此，示例语法描述的语言使乘法和加法具有右结合性。对于乘法和加法来说，这不是问题； (a*b)*c 在数学上与 a*(b*c) 相同。但这会对除法和减法产生很大的影响，因为 (a-b)-c 与 a-(b-c) 不同(em>不)(除非c为0)。

PEG 语法(以及许多自上而下的解析器生成器)通过允许语法规则中的重复运算符来弥补这个问题。因此，编写这两种语法的更好方法很可能是使用重复:

Exp = AndExp ("OR" AndExp)*
AndExp = SimpleExp ("AND" SimpleExp)*
SimpleExp = identifierName operator literal | "(" Exp ")"