5

（注意：我读过其他类似的问题，但我无法弄清楚）。

我写了这个语法：

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 演示中进行测试

4

3 回答 3

8

好问题。首先将您的第一个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)"两个脚本。

于 2012-11-23T03:26:05.407 回答
5

如果我理解正确，您的问题不是左递归，而是解析树的结构。

您已经正确地消除了左递归，但不幸的是，摆脱左递归的唯一方法是在原始分析树中消除左递归。这些东西的大部分理论只是匹配正确的字符串集。您仍然匹配同一组字符串，因此理论上很满意，但您需要一个左递归解析树。更多关于 wikipedia上的问题。

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 进行左递归的注释。

那是假设您想要数据结构。如果您只想要括号，请将操作替换为：

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}
于 2013-11-13T07:42:29.837 回答
0

您可以使用+运算符重新构造呼叫非终端并将其重复部分放在单独的规则中，这样：

start = call

ident = i:[a-z]+ { return i.join(''); }
spaces = [ ]+

call = f:ident g:args+ {
    return f + g.join('');
}

args = spaces a:ident { return "(" + a + ")"; }
于 2016-09-01T11:30:59.350 回答