6

Lexer DFA で「コードが大きすぎます」というエラーが発生する

ANTLR 3 を使用して Java Server Pages を解析しようとしています。

Java には、1 つのメソッドのバイト コードに対して 64k の制限があり、ANTLR によって生成された Java ソースをコンパイルするときに、「コードが大きすぎます」というエラーが発生し続けます。

場合によっては、レクサーを妥協することで修正できました。たとえば、JSP は XML の「名前」トークンを使用しますが、これにはさまざまな文字を含めることができます。「名前」トークンでは ASCII 文字のみを受け入れることにしました。これにより、一部のテストが大幅に簡素化され、レクサーでコンパイルできるようになりました。

しかし、これ以上手を抜くことはできないところまで来ましたが、DFA はまだ複雑すぎます。

私はそれについて何をすべきですか？

複雑な DFA の原因となるよくある間違いはありますか?

おそらく予測に役立つセマンティック述語または固定先読みに依存して、DFAの生成を禁止する方法はありますか?

この字句解析器を手で書くのは簡単ですが、ANTLR をあきらめる前に、明らかなことを見落としていないことを確認したいと思います。

バックグラウンド

ANTLR 3 レクサーは、DFA を使用して、入力をトークン化する方法を決定します。生成された DFA には、 というメソッドがありspecialStateTransition()ます。このメソッドにはswitch、DFA の各状態のケースを含むステートメントが含まれています。各ケース内にはif、状態からの遷移ごとに 1 つの一連のステートメントがあります。各ifステートメントの条件は、入力文字をテストして、遷移に一致するかどうかを確認します。

これらの文字テスト条件は非常に複雑になる場合があります。通常、次の形式をとります。

int ch = … ; /* "ch" is the next character in the input stream. */
switch(s) { /* "s" is the current state. */
  …
  case 13 :
    if ((('a' <= ch) && (ch <= 'z')) || (('A' <= ch) && (ch <= 'Z')) || … )
      s = 24; /* If the character matches, move to the next state. */
    else if …

lexer に小さな変更を加えたように見えるだけで、1 つの遷移に対して数十回の比較が行われ、各状態に対して複数の遷移が行われ、多数の状態が発生する可能性があります。考慮されている状態のいくつかは、私のセマンティック述語のために到達できないと思いますが、セマンティック述語は DFA によって無視されているようです。(ただし、読み間違えている可能性があります。このコードは、私が手で書くことができるものではありません!)

Jsp2x ツールで ANTLR 2 の文法を見つけましたが、その構文木に満足できず、ANTLR のスキルをリフレッシュしたいので、自分で書いてみようと思いました。私は ANTLRWorks を使用しており、DFA のグラフを生成しようとしましたが、ANTLRWorks にはそれを妨げるバグがあるようです。

4

2 に答える 2

4

残念ながら、非常に大きな (多くの異なるトークン) 文法にはその問題があります (SQL 文法もこれに悩まされます)。

これは、トークンを生成する「完全な」レクサー ルールとは対照的な特定のレクサー ルールを作成したり、ルール内で文字を一致させる方法を再配置したりすることで修正できる場合がありますfragmentsが、すでに自分で試した方法を見ると、できるとは思えません。あなたのケースで多くを得ました。ただし、レクサーの文法を SO に投稿する意思がある場合は、私または他の誰かが変更できるものを目にする可能性があります。

一般に、この問題は、レクサー文法を 2 つ以上の個別のレクサー文法に分割し、それらを 1 つの「マスター」文法にインポートすることによって修正されます。ANTLR 用語では、これらは複合文法と呼ばれます。それらについては、この ANTLR Wiki ページを参照してください: http://www.antlr.org/wiki/display/ANTLR3/Composite+Grammars

編集

@Gunther が OP の下のコメントで正当に言及したように、Q&A を参照してください: Why my antlr lexer Java class is "code too large"? 小さな変更 (特定の述語の削除) により、この「コードが大きすぎます」というエラーが表示されなくなりました。

于 2011-09-22T17:44:00.040 に答える
3

実際、複合文法を作成することは必ずしも容易ではありません。多くの場合、この AntTaskはこの問題を解決するのに役立ちます (文法を再コンパイルした後に毎回実行する必要がありますが、このプロセスはそれほど退屈ではありません)。

残念ながら、この魔法のスクリプトでさえ、いくつかの複雑なケースでは役に立ちません。コンパイラは、 DFA トランジション (静的 String[] フィールド)のブロックが大きすぎると不平を言い始めることがあります。

そのようなフィールドを(IDE リファクタリング機能を使用して)任意に生成された名前を持つ別のクラスに移動することで、簡単に解決する方法を見つけました。このような方法で 1 つまたは複数のフィールドだけを移動する場合は、常に役立ちます。

于 2012-09-18T18:22:13.793 に答える