如何在不回溯的情况下避免树顶中的左递归

Question

在我正在开发的这个简单表达式解析器中，我很难避免左递归。本质上，我想将等式"f x y"解析为两个表达式"f x"one_answers"（f x）y"（带隐式括号）。如何在避免左递归和回溯的同时做到这一点？是否必须有一个中间步骤？

#!/usr/bin/env ruby
require 'rubygems'
require 'treetop'
Treetop.load_from_string DATA.read
parser = ExpressionParser.new
p parser.parse('f x y').value
__END__
grammar Expression
   rule equation
      expression (w+ expression)*
   end
   rule expression
      expression w+ atom
   end
   rule atom
      var / '(' w* expression w* ')'
   end
   rule var
      [a-z]
   end
   rule w
      [sntr]
   end
end

Answer 1

您没有提供足够的关于所需结果的信息。特别是，你希望"f（a b）y"解析为"（f（a（b））y"吗？我想你是这样做的…这意味着一个没有括号的函数有arity 1。

所以你想说：

rule equation
  expression w* var / expression w* parenthesised_list
end
rule parenthesised_list
  '(' w* ( expression w* )+ ')'
end

另一方面，如果你对f的arity有外部（语法）知识，并且你想准确地迭代"expression"那么多次——例如在解析TeX时发生的那样——那么你将需要使用语义谓词&迭代表达式列表中的｛|s|…｝）。请注意，传递给sempred块的参数不是SyntaxNode（由于该序列子规则尚未成功，因此无法构建），而是序列中迄今为止累积的节点数组。块返回值的真实性决定了解析结果，并可以停止迭代。

您可能考虑使用的另一个工具是前瞻性（！stuff_I_dont_expect_to_follow或&stuff_that_must_follow）。

您也可以在http://groups.google.com/group/treetop-dev