1

私はflex/bisonから文法を移植しており、ほとんどすべてが稼働しているように見えます（特に、トークンストリームは問題ないようで、パーサー文法はコンパイルおよび実行されています）が、暴走の問題が発生しているようです私の文法への非常に小さい/中程度のサイズの入力であっても、スタック/メモリの使用量。同じ非末端の制限されていない配列を一緒に連鎖させるための好ましい構築物は何ですか? 私の Bison 文法では、次の形式の生成規則がありました。

statements: statement | statement statements
words: | word words

ANTLR では、同じルール設定を維持すると、小さな入力 (4kB 程度) では見事に機能するように見えますが、より大きな入力 (100kB 程度) ではスタック オーバーフローが発生します。どちらの場合も、生成された自動解析ツリーも見栄えが悪いです。

これらのプロダクション ルールを (再帰的な形式ではなく) 明示的に付加的なものに変更して実験しました。

statements: statement+
words: word*

ただし、これにより、非常に小さな入力でもメモリ使用量が大幅に増加し (1GB 以上)、パーサーは 20 分間実行した後でも解析ツリーを返すことができませんでした。

任意のポインタをいただければ幸いです。

4

2 に答える 2

2

書き換えられたステートメントは、説明した 2 つのルール (最高のパフォーマンスと最小のメモリ使用量) の最適な ANTLR 4 形式です。あなたが説明した問題に関する一般的なフィードバックを次に示します。

  1. 多くの潜在的なパフォーマンスの問題に対して、非常に高度な診断コードを開発しました。このコードの多くは に含まれていますがTestPerformance、エキスパート ユーザー向けであり、結果を解釈するには ANTLR 4 の新しい ALL(*) アルゴリズムをかなり深く理解している必要があります。

  2. Terence と私は、上記をユーザーが利用できるツールに変えることに関心があります。完全な文法と入力例を提供していただければ、その文法と入力のペアを使用して、分析を自動化するツールの有用性をさらに評価することができる場合があります (テストの実行と解釈)。 .

  3. 本の 2 段階の解析戦略を使用していることを確認してください。多くの場合、これにより、正しい入力の解析パフォーマンスが大幅に向上します (正しくない入力は速くなりません)。

  4. 必要以上にメモリを使用することは好みませんが、「過剰」の定義が大きく異なることに注意してください。たとえば、テストに応じて-Xmx4gtoを使用してテスト アプリケーションを実行します。-Xmx12g

于 2013-09-15T18:32:41.093 に答える
1

さて、次の方法で機能するようになりました。私の YACC 文法には次の構造がありました。

lines: lines | line lines;
words: | word words;

ただし、これでは再帰的な解析がうまくいかなかったので、次のように書き直しました。

lines: line+;
words: word*;

これは、@ 280Z28 のフィードバック (および私の最初の推測) と一致しています。これによりパーサーがハングしたため、最初に質問を投稿しましたが、@ 280Z28 の回答に対する私のコメントで概説されているデバッグ手順は、実際にはlines問題を引き起こしているのは解析のみであることが示されました ( words) は問題ありませんでした。気まぐれで、私は次の書き換えを試みました：

lines   : stmt (EOL stmt)+ EOL*;

(line元々は次のように定義されていました。

line : stmt (EOL | EOF);

)

これは、大規模な入力であっても、非常にうまく機能しているようです。しかし、なぜこれが Right Thing To Do(tm) なのか、またはこの質問を引き起こしたリビジョンと比較して違いが生じる理由は、私にはまったくわかりません。この件に関するご意見は引き続きお待ちしております。

于 2013-09-20T17:57:16.810 に答える