如何为 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))

错误：Line 1, column 4: Expected ")" or [0-9a-z,A-Z] but "(" found.

我知道左递归与右递归的概念，但我不知道如何让它无限递归调用规则。

Answer 1

我认为问题出在你的语法歧义上。向 GNF（前导终端）扩展一点，我们得到一个字母符号的两个规则链：

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

因此，字母标识符可以解析为 arg 或 call[=34] 的 func =].您生成的解析器显然选择将 g 缩减为另一个 arg，而不是 func 的第一部分].

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

但是，我确实了解一般的解析器。许多正则表达式引擎都是 "greedy"：它们会抓取最长的匹配字符串。如果你有其中之一，关键问题是

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

将在 returns 之前消耗跨度 "4, g" 进行任何其他处理，从而消除了找到 "g()" 作为第二个参数的可能性。在这种情况下，您需要的是一种语法，它可以找到单独的参数，并且对每个贪婪。使用逗号作为分隔符，并将它们组合成一个arg_list（一个新的non-token）：

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

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

如何为 pegJS 定义递归规则

How to define recursive rule for pegJS

javascript

recursion

parsing

pegjs