如何解析语言语法中的点运算符？

Question

假设我正在编写解析以下语法的解析器：

foo.bar().baz = 5;

语法规则看起来像这样：

program: one or more statement
statement: expression followed by ";"
expression: one of:
  - identifier (\w+)
  - number (\d+)
  - func call: expression "(" ")"
  - dot operator: expression "." identifier

两个表达式有问题，func 调用和点运算符。这是因为表达式是递归的并且在开始时寻找另一个表达式，导致堆栈溢出。这个问题我将重点关注点运算符。

我们在加号运算符方面遇到了类似的问题。但是，与其使用表达式，不如使用这样的方法来解决它（改为查找“术语”）：

add operation: term "+" term
term: one of:
  - number (\d+)
  - "(" expression ")"

然后 term 包括除添加操作本身之外的所有内容。为了确保多个加运算符可以在不使用括号的情况下链接在一起，人们宁愿这样做：

add operation: term, one or more of ("+" followed by term)

我在想类似的解决方案可以用于点运算符或函数调用。

但是，点运算符的工作方式略有不同。我们总是从左到右进行评估，并且需要允许完整的表达式，以便您可以在中间进行函数调用等。带括号的示例可能是：

(foo.bar()).baz = 5;

不幸的是，我不想要求括号。如果遵循用于加号运算符的方法，最终会出现这种情况。

我该如何着手实施它？

目前我的解析器从不向前看，但即使我向前看，完成起来似乎仍然很棘手。

Answer 1

一种方法可能是点运算符解析 non-dot 表达式，即与表达式相同但没有点运算符的规则。这可以防止递归。

然后，当 non-dot 表达式被解析后，检查后面是否有点和标识符。如果不是这种情况，我们就完成了。如果是这种情况，请将当前节点包裹在一个点操作节点中。然后，跟踪到目前为止已为此操作解析的整个字符串文本。然后将所有内容恢复到解析操作之前，现在 re-parse 一个“自定义表达式”，其中第一个 directly-nested 表达式实际上会尝试匹配之前解析的确切字符串而不是真实的表达。重复直到不再有 dot-identifier 对（这应该由新的“自定义表达式”自动发生）。

这很混乱、复杂，而且可能很慢，我不确定它是否可行，但我会尝试一下。我会很感激其他解决方案。

Answer 2

简单的解决方案是使用 bottom-up 解析器，它不会在左递归时掉入无底洞，但我想您已经拒绝了该解决方案。

不过，我不明白您反对使用循环结构。字段查找和函数调用等后缀修饰符与加法等二元运算符并没有真正的不同（当然，除了它们不需要声明最终正确的操作数这一事实）。加号和减号自由混合，您可以通过重复解析，如：

additive: term ( '+' term | '-' term )*

同样，后缀修饰符可以很容易地解析为：

postfixed: atom ( '.' ID | '(' opt-expr-list `)` )*

我正在使用一种扩展 BNF 形式：括号组； | 将备选方案分开，并且比连接更严格地绑定； * 表示其左侧原子的“零次或多次重复”。

属于同一类别的另一个后缀运算符是 array/map 下标 ('[' expr ']')，尽管您可能还有其他后缀运算符。

请注意，与上面的附加语法一样，选择适当的替代项不需要查看下一个标记。如果不能窥视未来的一个标记，就很难解析。幸运的是，开销很小。

如何解析语言语法中的点运算符？

How to parse dot operator in language syntax?

parsing