ruby - Treetop の左再帰の扱い方

Question

構築しようとしている新しい汎用プログラミング言語用の文法ファイルがあります。私はこの言語を堅牢で自然に使えるようにしようとしています (Ruby などから大きな影響を受けています)。そのために、いくつかの左再帰規則を導入しました。

次の左再帰ルールを示していると思われる例をいくつか見てきました。

rule l_recurse
  l_recurse / 'something else'
end

次のように変更することで、非左再帰にすることができます。

rule r_recurse
  'something else' / r_recurse
end

私には、これには別の問題があり、それでも失敗するように見えます。私は正しいですか、それともこれは「うまくいく」でしょうか？

私が (見つけて) 排除しようとしている特定の左再帰は、この文法ファイルにあります。どのルールが影響を受けるかはわかりませんが、少なくともいくつかは左再帰があると指摘されました。(ちなみに、範囲のルールを強化することで、彼が言及した特定の範囲の問題を排除しようとしました。)

score 4 · Accepted Answer

特定のケース

rule l_recurse
  l_recurse / 'something else'
end

に単純化します

rule l_recurse
   'something_else'
end

（そして正しい再帰規則もそうです）あなたが知りたいことを見つけるためにあなたの具体的な例を見る必要があります. この質問に対する答えは、左再帰の除去の一般的なルールを示します。

典型的な簡単に削除できる左再帰のケースの 1 つはリストです。

rule l_list
    item | l_list ',' item
end

これは右再帰に変更できます

rule r_list
    item r_tail?
end

rule r_tail
    ',' r_list
end

(これは一般的な再帰消去の特殊なケースです)。

1 に答える 1