javascript - 如何为pegJS定义递归规则

Question

所以，我尝试使用 PegJS为简单语言定义解析器。

该语言纯粹由无限深度的函数调用组成，这些函数调用之间用逗号分隔，例如:

f(4, g()) => [f, [4, g, []]]

g()
f(5) => [g, [], f, [5]]

这是我的语法:

call = 
  func"("arg")"

func =
  [a-zA-Z]+

arg =
  [0-9a-z,A-Z]+ / call


_ "whitespace"
  = [ \t\n\r]*

但它不是递归的:

输入:b(r(6))

错误:第 1 行第 4 列:应为“)”或 [0-9a-z,A-Z]，但找到了“(”。

我了解左递归与右递归的想法，但我不知道如何使其无限递归调用规则。

Answer 1

我认为问题出在你的语法歧义上。稍微向 GNF(前导终端)扩展，我们得到字母符号的两个规则链:

arg = [0-9a-z,A-Z]+ arg = call # 展开调用 = func"("arg")"# 展开函数 = [a-zA-Z]+"("arg")"

因此，字母标识符可以解析为调用的arg或func。您生成的解析器显然选择将 g 减少为另一个 arg，而不是 func 的第一部分。

我不熟悉 PegJS，所以我无法建议如何强制你的解析器提交。您确实需要1个 token 的前瞻来解决这个问题。

但是，我总体上了解解析器。许多正则表达式引擎都是“贪婪的”:它们会获取最长的匹配字符串。如果您有其中之一，那么关键问题是

arg = [0-9a-z,A-Z]+

将在返回到任何其他处理之前消耗范围“4, g”，从而消除了查找“g()”作为第二个参数的可能性。在这种情况下，您需要的是一种能够找到单个参数的语法，并且对每个参数都贪婪。使用逗号作为分隔符，并将它们一起放入一个arg_list(一个新的非token)中:

arg_list = arg \
           arg "," arg_list

call = func "(" arg_list ")" \
       func "()"

这是解析函数调用的一种规范方法。