2

小さなクエリ言語用のANTLRパーサーを構築しています。クエリ言語は定義上あいまいであり、クエリを処理するにはすべての可能な解釈（AST）が必要です。

Example:

    query   : CLASSIFIED_TOKEN UNCLASSIFIED_TOKEN 
            | ANY_TOKEN UNCLASSIFIED_TOKEN 
            ;

この場合、入力が両方のルールに一致する場合、両方の解釈で2つのASTを取得する必要があります。ANTLRは最初に一致したASTを返します。

同じ文法で可能なすべてのASTを取得する簡単な方法を知っていますか？パーサーを複数回実行することを考えています。反復間ですでに一致しているルールを「オフ」にします。これは汚いようです。より良いアイデアはありますか？たぶん、これを行うことができるJavaサポートを備えた他のlex / parserツールですか？

ありがとう

4

2 に答える 2

2

私があなたなら、あいまいさを取り除きます。多くの場合、コンテキスト情報を使用して、どの文法規則が実際にトリガーされるかを判断することで、これを行うことができます。たとえば、

C* X;

C（あなたの言語ではありませんが、これはポイントを作るためのものです）では、これが単なる無意味な乗算（Cで書くことは合法です）なのか、それとも「Cへのポインタ」型の変数Xの宣言なのかわかりません。 "。したがって、2 つの有効な (あいまいな) 解析があります。しかし、C が型宣言であることがわかっている場合 (何らかのコンテキスト、おそらく以前のコード宣言から)、パーサーをハックして不適切な選択を削除し、あいまいさのない「正しい」解析を 1 つだけ行うことができます。

本当にコンテキストがない場合は、GLR パーサーが必要になる可能性があります。これは、最終的なツリーで両方の解析を喜んで生成します。Javaで利用できるものは知りません。

私たちのDMS Software Reengineering Toolkit [Java ベースの製品ではない] は GLR 解析をサポートしており、あいまいな難しい言語を解析するために常にそれを使用しています。上記の C の例を処理する方法は、両方の解析を生成することです。これは、GLR パーサーがこれを喜んで行うためです。その後、追加情報 (シンボル テーブル テーブルなど) がある場合は、ツリーを後処理して不適切な解析を削除します。

DMS は、クエリ言語などの任意の言語のカスタマイズされた分析と変換をサポートするように設計されており、文法の定義を容易にします。文脈自由文法 (あいまいさの有無にかかわらず) があれば、DMS はコードを解析でき、後で何をすべきかを決定できます。

于 2012-07-26T20:23:07.520 に答える
1

I doubt you're going to get ANTLR to return multiple parse trees without wholesale rewriting of the code.

I believe you're going to have to partition the ambiguities, each into its own unambiguous grammar and run the parse multiple times. If the total number of ambiguous productions is large you could have an unmanageable set of distinct grammars. For example, for three binary ambiguities (two choices) you'll end up with 8 distinct grammars, though there might be slightly fewer if one ambiguous branch eliminates one or more of the other ambiguities.

Good luck

于 2012-07-26T19:16:43.217 に答える