3

作業中のこの単純な式パーサーで左再帰を回避するのに問題があります。基本的に、方程式'fxy'を2つの式'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」として解析されると思いますか？私はあなたがそうすると思います...これは、開き括弧が続かない関数がアリティ1を持っていることを意味します。

だからあなたは言いたい：

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

一方、fのアリティに関する外部（文法の）知識があり、たとえばTeXの構文解析で発生するように、「式」を正確に何度も繰り返したい場合は、セマンティック述語を使用する必要があります。 ＆{| s | ...}反復式リスト内）。sempredのブロックに渡される引数は、SyntaxNode（このシーケンスサブルールがまだ成功していないため、まだ構築できません）ではなく、シーケンス内のこれまでに蓄積されたノードの配列であることに注意してください。ブロックの戻り値の真実性が解析結果を決定し、反復を停止する可能性があります。

使用を検討する可能性のあるもう1つのツールは、先読み（！stuff_I_dont_expect_to_followまたは＆stuff_that_must_follow）です。

http://groups.google.com/group/treetop-devでそのような質問をすることもできます

于 2012-08-31T00:07:41.357 に答える