11

私は教育目的で IMAP プロトコル用のレクサーを作成していますが、レクサーとパーサーの境界線をどこに引くべきか悩んでいます。IMAP サーバーの応答の例を次に示します。

* FLAGS (\Answered \Deleted)

この応答は、次のような正式な構文で定義されます。

mailbox-data   = "FLAGS" SP flag-list
flag-list      = "(" [flag *(SP flag)] ")"
flag           = "\Answered" / "\Deleted"

これらは文字列リテラル (別名「端末」トークン) として指定されているため、次のように、レクサーがそれぞれに対して一意のトークンを発行する方が正しいでしょう。

(TknAnsweredFlag)
(TknSpace)
(TknDeletedFlag)

または、次のようなものを発行するのも同じくらい正しいでしょうか:

(TknBackSlash)
(TknString "Answered")
(TknSpace)
(TknBackSlash)
(TknString "Deleted")

私の混乱は、前者の方法がレクサーを過度に複雑にする可能性があること\Answeredです.2つの異なるコンテキストで2つの意味がある場合、レクサーは正しいトークンを発行しません。不自然な例として (電子メール アドレスが引用符で囲まれているため、このような状況は発生しません)、レクサーは \Answered@googlemail.com のような電子メール アドレスをどのように処理しますか? それとも、そのようなあいまいさが生じないように設計された正式な構文ですか?

4

3 に答える 3

7

原則として、字句構文が文法に反映されることは望ましくありません。たとえば、C のようなコンピューター プログラミング言語の字句解析器は確かに数字を認識しますが、通常、HEXNUMBER および DECIMALNUMBER トークンを生成することは不適切です。これは文法にとって重要ではないためです。

あなたが望むのは、文法が目的に関連して関心のあるケースを区別できるようにする最も抽象的なトークンだと思います。文法の一部で引き起こされる混乱や、他の部分で行う可能性のある選択によって、これを調整することができます。

単にフラグ値を読み飛ばすだけの場合は、実際にはそれらを区別する必要はなく、コンテンツが関連付けられていない TknFlag で十分です。

フラグの値を個別に処理することが目標の場合は、ANSWERED および/または DELETED の指示があったかどうかを知る必要があります。それらが語彙的にどのように綴られているかは関係ありません。だから私はあなたの TknAnsweredFlag ソリューションを使います。TknSpace をダンプします。これは、フラグの任意のシーケンスで、介在するスペースが必要になるためです (あなたの仕様はそう言っています)。

時折、そのような旗のようなものが数十個ある状況に出くわします。次に、それぞれにトークンがあると、文法が乱雑になり始めます。文法が特定のフラグを知る必要がない場合は、関連付けられた文字列値を持つ TknFlag が必要です。文法で区別するためにフラグの小さなサブセットが必要であるが、それらのほとんどは必要ない場合は、妥協する必要があります。文法にとって重要なフラグには個別のトークンを用意し、残りのフラグには関連付けられた文字列をすべてキャッチする TknFlag を使用します。 .

2 つの異なる解釈を持つことの難しさについて: これはトレードオフの 1 つです。その問題がある場合、トークンは、区別できるように、文法で必要な両方の場所で十分に詳細である必要があります。「\」が文法のどこかでトークンとして関連している場合、TknBackSlash と TknAnswered の両方を作成できます。ただし、文法のある部分での処理方法が別の部分と異なる場合は、多くの場合、モード駆動型レクサーを使用してこれを回避できます。モードは、それぞれに (サブ) レクサーが関連付けられた有限状態マシンであると考えてください。モード間の移行は、キューであるトークンによってトリガーされます (FLAGS トークンが必要です。フラグ値を取得しようとしているのはまさにそのようなキューです)。モードでは、他のモードでは生成されないトークンを生成できます。したがって、あるモードでは "\" トークンを生成するかもしれませんが、フラグ モードではその必要はありません。モードのサポートは、レクサーではかなり一般的です。これは、この問題が予想よりも一般的であるためです。例については、Flex のドキュメントを参照してください。

あなたが質問をしているという事実は、あなたが正しい選択をするための正しい道を歩んでいることを示しています. トークンを最小限に抑えるという保守性の目標 (技術的には、トークンを使用してすべての ASCII 文字を解析できます) と、必要に応じて十分に区別するための基本的な要件とのバランスを取る必要があります。十数個の文法を作成した後では、このトレードオフは簡単に思えますが、私が提供した経験則はかなり優れていると思います。

于 2011-03-19T17:21:53.590 に答える
1

私は最初にCFGを思いつき、その仕事をするために必要な端末はすべて、レクサーが認識すべきものです。それ以外の場合は、文字列をトークン化する適切な方法を推測しているだけです。

于 2011-03-19T13:28:19.477 に答える
0

lexer と parser を分離しないことをお勧めします。最新の解析アプローチ ( PEGsなど) では、lexing と parsing を混在させることができます。この方法では、トークンはまったく必要ありません。

于 2011-03-19T13:20:49.007 に答える