如何为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，arg +arg= call #展开call = func (“arg”)“展开func=arg+”(“arg”)

因此，字母标识符可以解析为arg或call的func。结果解析器显然选择将g简化为另一个arg，而不是func的第一部分。

我不熟悉PegJS，所以我不能建议如何强迫解析器提交。您确实需要一个1令牌的前瞻性来解决这个问题。

然而，我确实知道解析器在一般情况下。许多正则表达式引擎都是“贪婪的”：它们将获取最长的匹配字符串。如果你有其中一个，关键的问题是

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

将在返回到任何其他处理之前使用span "4，g“，从而排除了将"g()”作为第二个参数的可能性。在这种情况下，您需要的是找到单个参数的语法，并且对每个参数都很贪婪。使用逗号作为分隔符，并将它们放在一个arg_list (一个新的非令牌)中：

arg_list = arg \
           arg "," arg_list

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

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