parsing - 消除此 PEG.js 语法上的左递归

Question

(注意:我读过其他问题，例如 this ，但我无法弄清楚)。

我写了这个语法:

start = call

ident = [a-z]+
spaces = [ ]+

call = f:ident spaces g:(call / ident) {
    return f + "(" + g + ")";
}

使用此输入

a b c d

返回

"a(b(c(d)))"

我想要

"a(b)(c)(d)"

我认为这个左递归规则可以给我类似的东西，但是 PEG.js 不支持左递归。

call = f:(call / ident) spaces g:ident {
    return f + "(" + g + ")";
}

这种情况下如何消除左递归？

PS:你可以在 online PEG.js demo 上测试一下

Answer 1

好问题。首先将您的第一个 ident 与其他所有内容分开，因为它会得到特殊处理(没有括号)。接下来，遵循规则来处理spaces ident递归，该递归将收集括号内的值。该循环包装 ident 文本并附加递归收集的任何新文本。

这是规则的简写版本(请注意，tail 是一个单独的规则):

head: ident tail?;        //the "head" ident is separated
tail: spaces ident tail?; //each "tail" ident is looped over

这是 PEG 脚本:

start = head

ident = [a-z]+
spaces = [ ]+

head = head:ident tail:tail? {
    return head + tail;
}

tail = spaces next:ident tail:tail? {
    return "(" + next + ")" + tail
}

<小时/>

编辑:这是一种替代方案，可以在一个规则中完成工作，并且与您的规则更相似。

start = head

ident = [a-z]+
spaces = [ ]+

head = head:ident tail:(spaces next:ident{return "(" + next + ")" })* {
    return head + tail.join("")
}

<小时/>

两个脚本的 a b c d 输出均为 “a(b)(c)(d)”。