3

在我正在研究的这个简单的表达式解析器中，我无法避免左递归。本质上，我想将方程“fx y”解析为两个表达式“fx”和“(fx)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
      [\s\n\t\r]
   end
end
4

1 回答 1

1

您没有提供有关所需结果的足够信息。特别是，您是否希望“f(ab) y”解析为“(f(a(b))) y”？我假设您这样做...这意味着没有后跟左括号的函数具有元数。

所以你想说：

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

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

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

您也可以在http://groups.google.com/group/treetop-dev中提出此类问题

于 2012-08-31T00:07:41.357 回答