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

Question

(注:我读过像其他的问题这个,但我一直没能想出解决办法).

我写了这个语法:

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:你可以在在线PEG.js演示中测试这个

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)"两个脚本.

Answer 2

如果我理解正确,你的问题不是递归,而是解析树的结构.

你已经正确地消除了左递归,但不幸的是,摆脱左递归的唯一方法是消除原始分析树中的左递归.这个东西的大多数理论只是匹配正确的字符串集.你仍然匹配同一组字符串,所以理论很高兴,但你想要一个左递归解析树.更多关于维基百科上的问题.

AFAIK,你不能让PEG解析器的原始输出是左递归的.但是,您可以使用输出执行任何操作.因此将其解析为一个数组,然后进行后处理以使其具有良好的左结构.

使用简化(无空格,无多字符标识符)语法来执行此操作:

 start = call

 id = [a-z]

 call
     = arr:id+ {
         var acc = arr[0]
         for (i = 1; i < arr.length; i++) {
            acc = [acc, arr[i]]
         }
         return acc;
     }

它分析abcd到[ [ [ 'a', 'b' ], 'c' ], 'd' ].我只是使用+而不是递归,然后遍历生成我们想要的结构的结果数组.维基百科有关于使用PEG进行左递归的一些注释.

这是假设你想要数据结构.如果您只想要parens,请将此操作替换为:

var acc = arr[0]
for (i = 1; i < arr.length; i++) {
    acc = acc + '(' + arr[i] + ')'
}
return acc;

这给了a(b)(c)(d).

要将空格和多字符ID放回,您可以这样做:

 start = call

 id = [a-z]+

 _ = [ ]+

 call
      = a:id as:arg* {
          arr = [a].concat(as)
          var acc = arr[0]
          for (i = 1; i < arr.length; i++) {
              acc = acc + '(' + arr[i] + ')'
          }
          return acc;
      }

 arg = _ a:id {return a}