0

所以，我正在尝试使用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.

我得到了左右递归的想法，但我不知道如何让它无限地递归调用规则。

4

1 回答 1

2

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

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

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

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

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

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

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

arg_list = arg \
           arg "," arg_list

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

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

于 2017-02-10T17:48:16.390 回答