表达语言的语法

Question

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

A=3
A<5 或 B>C
A=null 或 (B=3 AND 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.

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

因此，第一步是将 simpleExp、andExp 和 orExp 重命名为 SimpleExp、AndExp 和 [=22]，从而将它们更改为句法规则=]，分别。然后，如果需要，您可以将 " OR " 更改为 "OR"。

第二个问题就没那么简单了。要解决它，查看 Ohm example arithmetic grammar 中使用的模型会很有用。（请记住，语法只与符号的组织有关；符号的含义在别处处理。因此，使用运算符 AND 和 OR 的布尔表达式语法不同于使用运算符 * 和 + 仅在运算符的拼写方式上。算术语言语法确定 * 优先于 + 的方式与布尔语法的方式完全相同会指定 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 解析系统使用 / 作为交替运算符的名称，而不是上下文无关文法使用的 |，以避免混淆这两个运算符的语义。但是欧姆选择不这样做那个。)

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

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

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

表达语言的语法

Grammar for expression language

javascript

grammar

expression