6

純粋に自己学習の練習として、Parse::RecDescentモジュールを使用して Perl で Java パーサーを作成しようとしています。Antlr、bisonなどの他のツールを使用して、後でパーサーを再実装する可能性があります。

しかし、Java 言語仕様に従って、パーサーが実際に正しい解析を生成していることを確認するにはどうすればよいでしょうか? elseつまり、ぶら下がっている 、演算子結合性、優先順位などの正しい処理。

1 つの方法は、両方のパーサーに非常に多数のテスト Java プログラムの AST を生成させ、次に 2 つの AST セットを比較することによって、私のパーサーをバグのない既知のパーサーと比較することです。

これが本当に唯一の方法である場合、Java 言語仕様全体を完全にカバーするテスト Java プログラムの大規模なスイートをどこで見つけることができますか?

JavaParserを見てきましたが、完全なテスト データセットがないようです。

もう 1 つの方法は、もちろん、自分で何万ものテスト Java プログラムを手作業で作成することです。これは、時間の観点からだけでなく、網羅性を確保する上でも、私にとって非常に非現実的です。

4

2 に答える 2

6

正しい答えがあるかどうかを判断するには、理想的には何らかの基準と比較する必要があります。これはコンピューター言語にとっては難しいことです。

AST の比較は難しいでしょう。そのような基準がないからです。AST を構築する各パーサーは、パーサーをコーディングした人によって構造が設計された AST を構築します。

つまり、AST を生成するパーサーを構築し、他の誰かの AST を生成するパーサーを入手した場合、選択した AST ノードが他の AST と一致しないことがわかります。次に、AST から別の AST へのマッピングを作成する必要があります (また、マッピングが有効であることをどのように確認しますか?)。パーサーが別のパーサーから AST を生成するように試みることはできますが、生成する AST は使用する解析テクノロジの影響を受けることがわかります。

私の会社が製造するJavaフロントエンドにも同様の問題があります（詳しく知りたい場合は、バイオを参照してください）。私たちが解決したのは、答えが自己一貫性があることをテストすることであり、その後、大きなコードで多くの長期的な経験的テストを行います.

私たちの解決策は次のとおりです。

  • (パーサーを構築し、入手可能な最強の解析テクノロジ (GLR) を使用します。これは、他の解析テクノロジ (LL、LR、...) では容易に認識されない特定の構造を認識できることを意味し、したがって、他のパーサーが生成する AST ノードを生成します。これが重要な例については、以下のコメントを参照してください. それでも、他のほとんどの解析テクノロジで要求されるように、AST ノードの構築を手作業でコーディングする必要を完全に回避する方法で AST ノードを生成します。ハンドコーディングとは異なる AST)。
  • 大量の Java コード (AST を生成する) を解析して、解析エラーがないことを確認します。[JDK はかなり良いサイズの例であり、簡単に入手できます]
  • 私たちのツールは AST を取り、(prettyprint) ソース コードを再生成することができます。コメントを追加しますが、レイアウトは多少異なります。解析後にプリティプリントされたコードも解析されることを確認します。解析されたプリティプリントされたバージョンを再プリティプリントします。常に同じレイアウトを生成するため、これは prettyprinted バージョンと同じである必要があります。このテストは、AST の設計と実装がソース コードに関して何も失われていないことを示しています。
  • シンボル テーブルを作成し、名前の意味を解決し、正当な Java プログラムがフロント エンドに従って型チェックを行うことを確認します。それだけでは、AST の性質については何もわかりませんが、それで十分です (実際、これで十分です!)。型チェック タスクは非常に複雑であるため (ローカルの Java 標準を確認してください)、それもかなりです。壊れやすい。すべてが正しくないと、大量のコードに適用されたときに型チェックが失敗する可能性があります。繰り返しますが、JDK はこれのかなり良いテストです。注: 名前と型の解決を行わない Java パーサーは、実際にはあまり役に立ちません。
  • 上記の結果から、ハイパーリンクされたソース コードを含む JavaDoc のような相互参照を生成します。これは、名前解決 (したがって AST 構築) が適切であることを確認するためにビット コードを手動で簡単にチェックできることを意味します。
  • フロントエンドをさまざまなプログラム分析とコードの変換に適用して、結果を受け入れます。時折発生する問題を見つけて修正します。

これを正しく行うのは困難です。特にJava言語が動き続けているので、近づいてテストの圧力を継続的にかけ続ける必要があります。(私たちは Java 8 にいますが、Java 9 は脅かされています)。要するに、このようなパーサーを構築してその健全性をチェックするのは大変な作業です。

独立した一連のテストを作成したいと考えていますが、実際にテストが行​​われたことはありません。そして、それらのテストが存在する場合 (Oracle と IBM がそれらを持っていると思います) は、解析と名前解決を直接テストするのではなく、コードの一部をコンパイルして実行し、既知の結果を生成することをテストすることを期待します。私たちはコンパイラを構築していないので、そのようなテストがあったとしても実行することはできません。名前解決と型の一貫性チェックを行うことができ、それは役に立ちます。

[私たちは実際に多くの言語フロント エンドに対してこれを行っています。Java は難しいと思います。C++ で試してみてください]

于 2016-09-25T16:36:31.180 に答える
1

@ira-baxter が書いたことに同意します。

つまり、パーサーがすべての有効なソース コードを解析できることを確認するのは簡単です (大量のコードを投入するだけです。これは JavaParser をテストするために行ったものであり、数百メガバイトのソース コードをリポジトリに入れていません)。 .

同じコードを解析し、異なるが同等に有効な AST を構築するさまざまな方法があるため、作成した AST が正しい形状であることを確認することも困難です。いくつかの形状は他の形状よりも扱いやすいですが、固執する「真実」はありません。

ツールが別のパーサーによって生成されたものとは異なる AST を生成する場合、必ずしも 2 つのパーサーのいずれかが間違っていることを意味するわけではなく、単なる設計上の選択である可能性があります。

于 2016-10-28T16:54:45.403 に答える