5

ANTLRWorks1.4には次の文法があります。私は、テキストアドベンチャーゲームクリエーターでパーサーを実装するためのアイデアをいじっています。ユーザーは、ゲームで許可されるさまざまなコマンドを指定します。

grammar test;

parse       :   cmd EOF;


cmd         :   putSyn1 gameObject inSyn1 gameObject;

putSyn1     :   Put | Place | Drop ;

inSyn1      :   In | Into | Within;


gameObject  :   det obj;

det         :   The | A | An | ;

obj          :  Word obj | Word;


Space       :       (' ' | '\t' | '\r' | '\n'){$channel=HIDDEN;};
Put         :   'put';
Place       :   'place';
Drop        :   'drop';
In          :   'in';
Into        :   'into';
Within      :   'within';
The         :   'the';
A           :   'a';
An          :   'an';

Word        :   ('a'..'z' | 'A'..'Z')+;

関係するさまざまな微妙な点を感じているところです（ここで行ったように）。

今回は、ANTLRを使用して、次のような入力を解析できるかどうか疑問に思っています。

put wood in fire place

つまり、「木」と「暖炉」は上記のgameObjectsです。ただし、「場所」は「置く」の同義語でもあります。したがって、これも同様に有効です。

place wood in fire place

ANTLRは、最後の「場所」トークンを解析しようとすると、NoViableAltExceptionを返します。「暖炉」をgameObjectとして認識したい。

それで、この種のことはANTLRで可能ですか？文法で可能ですか？

一方で、私はNFAや辞書などのビットを含む奇妙なカスタムデータ構造を使用する手動実装に取り​​組んでいます。しかし、私はまだもっと時間が必要であり、必要な検索と挿入のアルゴリズムを設計するためにいくつかの脳細胞を犠牲にしなければなりません。

しかし、これがANTLRで可能であれば、生成されたC＃ファイルを使用できますね。

4

2 に答える 2

4

もちろん。PL/1 は、予約語がないことで有名です。たとえば、キーワードとして必要ない場所ならどこでも変数名としてキーワード (たとえばIF ) を使用できます。

 IF  IF = 1  THEN  ELSE=3;  ELSE END=4;

これを行うパーサーを構築するのはより困難です。識別子がキーワードであるかどうかのコンテキストがわからないため、レクサーでこれを「単純に」行うことはできません。

いくつかの方法があります。エンティティのような識別子が見つかった場合:

1) lexer にパーサーに " do you want a keyword now? " と尋ねさせます。その場合、キーワードを生成します。ここでパーサーを連携させるのは難しいかもしれません。決定するためにさらに多くの入力を確認する必要があるため、パーサーが知らない可能性もあります。Fortran の有名なフォーマット ステートメントを考えてみましょう。

     FORMAT ( A1, I2, ... ) X

「FORMAT」という単語が表示されたときに、それがキーワードなのか識別子なのかはわかりません。X を検査するには、任意に先にスキャンする必要があります。X がステートメントの末尾以外の場合、FORMAT ワードは配列識別子の名前です。X がステートメントの終わりである場合、それは FORMAT キーワードおよびステートメントです。

2) キーワード (識別子が一致する場合) と識別子の両方を発行し、パーサーに両方を試行させます。ほとんどのパーサーはこれをうまく処理できませんが、適切に設計されていれば、 GLR パーサーはこれをうまく処理できます。これは、パーサーの先読み機能をプッシュすることで、FORMAT 問題を自明に処理します。(ANTLR は GLR ではありません。DMS Software Reengineering Toolkitにはまさにそのような GLR パーサーがあり、このトリックをよく使用します)。

3) すべての識別子のようなものをハッシュ テーブルに配置します。再帰降下パーサーを使用します (ANTLR はその 1 つです)。そのパーサーがキーワードを必要とする場合、取得した識別子を調べて、それが必要なキーワードであることを確認します。キーワードが必要ない場合は、単に識別子を識別子として使用します。ANTLR を使用していないため、ANTLR でこのトリックを実装する方法がわかりません。これでは、「先読みなしでは判断できない」場合はうまく処理できません。

于 2010-10-02T18:18:24.513 に答える
1

私はパーサーの代わりに字句解析器でこのようなものを処理します-字句解析器に「最大限のマンチ」をさせて、「暖炉」を単一のトークンとして認識し、「場所」を別のトークンとしてのみ認識します「火」の直前ではありません。

これにより、パーサーは、入力内の同じ文字シーケンスがたまたま 2 つの完全に別個のトークンのすべてまたは一部を形成していることに気付く必要がありません。

于 2010-10-02T14:30:06.190 に答える