5

新しいプログラミング言語のアイデアが頭の中に浮かんでいたので、それを実装してみようと思いました。Treetop (Ruby gem) を使用してパーサーを作成してみることを友人から勧められました。Treetop のドキュメントはまばらで、私はこれまでこの種のことをしたことがありません。

私のパーサーは、無限ループがあるように動作していますが、スタック トレースはありません。追跡が困難であることが証明されています。初心者レベルの構文解析/AST ガイドの方向性を教えてもらえますか? Treetop のようなツールを使用するための規則、一般的な使用法などを一覧表示するものが本当に必要です。私のパーサー グラマーはGitHubにあります。

class {
  initialize = lambda (name) {
    receiver.name = name
  }

  greet = lambda {
    IO.puts("Hello, #{receiver.name}!")
  }
}.new(:World).greet()
4

2 に答える 2

8

あなたの言語を .rb ファイルにコンパイルするように treetop に依頼しました。それは私に掘り下げる何かを与えました：

$ tt -o /tmp/rip.rb /tmp/rip.treetop

次に、この小さなスタブを使用してループを再作成しました。

require 'treetop'
load '/tmp/rip.rb'
RipParser.new.parse('')

これはハングします。ほら、面白いじゃないですか！空の文字列は、質問の数十行の例と同じように動作を再現します。

ハングしている場所を見つけるために、Emacs キーボード マクロを使用して rip.rb を編集し、各メソッドのエントリにデバッグ ステートメントを追加しました。例えば：

def _nt_root
  p [__LINE__, '_nt_root'] #DEBUG
  start_index = index

これで、ループの範囲を確認できます。

[16, "root"]
[21, "_nt_root"]
[57, "_nt_statement"]
...
[3293, "_nt_eol"]
[3335, "_nt_semicolon"]
[3204, "_nt_comment"]
[57, "_nt_statement"]
[57, "_nt_statement"]
[57, "_nt_statement"]
...

そこからさらにデバッグすると、整数を空の文字列にすることが許可されていることがわかります。

rule integer
   digit*
end

これにより、ステートメントを空の文字列にすることが間接的に許可され、トップレベルのルールstatement*が空のステートメントを永久に消費することができます。に変更*する+とループは修正されますが、別の問題が明らかになります。

/tmp/rip.rb:777:in `_nt_object': stack level too deep (SystemStackError)
        from /tmp/rip.rb:757:in `_nt_compound_object'
        from /tmp/rip.rb:1726:in `_nt_range'
        from /tmp/rip.rb:1671:in `_nt_special_literals'
        from /tmp/rip.rb:825:in `_nt_literal_object'
        from /tmp/rip.rb:787:in `_nt_object'
        from /tmp/rip.rb:757:in `_nt_compound_object'
        from /tmp/rip.rb:1726:in `_nt_range'
        from /tmp/rip.rb:1671:in `_nt_special_literals'
         ... 3283 levels...

範囲は、special_literals、literal_object、object、および Compound_object を介して、間接的に左再帰です。Treetop は、左再帰に直面すると、吐くまでスタックを食べます。その問題を簡単に解決する方法はありませんが、少なくともスタック トレースを取得する必要があります。

また、これは差し迫った問題ではありませんが、 の定義digitは奇妙です: 1 桁または複数のいずれかです。これにより、(おそらく) 不正な integer が発生しdigit*たり、許可されたりします。digit+1________2

于 2011-05-24T10:32:40.387 に答える
1

Parr の Language Implementation Patternsは本当に楽しかったです。Parr はANTLRパーサー ジェネレーターを作成したため、このツールは彼が本全体で使用していますが、それから学ぶには十分に単純でなければなりません。

私が本当に気に入ったのは、各例が前の例に基づいて成長した方法です。彼は巨大な AST 対応のパーサーから始めるのではなく、仕事をするためにますます多くの「バックエンド スマート」を必要とする問題をゆっくりと導入するため、この本は解析が必要な言語に合わせて適切に拡張されます。

もう少し詳しく説明してほしいのは、言語を設計するときに記述して、すべきこととすべきでないことについてアドバイスできる言語の種類です。解析するのが非常に面倒な言語をいくつか見てきましたが、別の方法で行うことができた可能性のある設計上の決定についてもっと知りたいと思っていました.

于 2011-05-24T01:43:33.703 に答える