7

識別子がキーワードで始まる言語があるとします。たとえば、「case」がキーワードであるが、「caser」が有効な識別子であるとします。また、レクサー ルールが正規表現のみを処理できるとします。次に、レクサーの識別子ルールの前にキーワードルールを配置できないようです。これは、「caser」を「case」の後に「r」が続くものとして解析するためです。また、識別子ルールがキーワードに一致し、キーワード ルールがトリガーされないため、識別子ルールの後にキーワード字句解析ルールを配置することもできません。

したがって、代わりに、lexer で keyword_or_identifier ルールを作成し、パーサーに keyword_or_identifier がキーワードか識別子かを判断させることができます。これは通常行われていることですか？

「先読み機能を備えた別のレクサーを使用する」ことが（一種の）答えであることは理解していますが、現在のレクサーはそのように機能しているように見えるため、従来のDFAベースのレクサーでこれがどのように行われるかにも興味があります。

4

1 に答える 1

8

元の から始まるほとんどのレクサーは、lex次のように代替と一致します。

  1. 最長一致を使用します。

  2. 最長一致に一致する代替が 2 つ以上ある場合は、レクサー定義で最初の代替を使用します。

これにより、次のスタイルが可能になります。

"case"                  { return CASE; }
[[:alpha:]][[:alnum:]]* { return ID; }

入力パターンがcaserの場合、2 番目の選択肢が使用されます。これが最長の一致であるためです。入力パターンが の場合、case r両方が に一致するため、最初の選択肢が使用され、case上記のルール (2) により、最初の選択肢が勝ちます。

これは少し恣意的に思えるかもしれませんが、ほとんどの場合、DFA のアプローチと一致しています。まず第一に、DFA は最初に受け入れ状態に達したときに停止しません。もしそうなら[[:alpha:]][[:alnum:]]*、最初の文字で受け入れ状態に入る (アルファベットだと仮定して) ようなパターンは役に立たないでしょう。代わりに、DFA ベースのレクサーは、現在の状態から可能な遷移がなくなるまで続行し、その後、最後の受け入れ状態までバックアップします。（下記参照。）

特定の DFA 状態が 2 つの異なるルールのために受け入れられる場合がありますが、それも問題ではありません。最初の承認ルールのみが記録されます。

公平を期すために、これは DFA の数学的モデルとは少し異なります。DFA は、すべての状態のすべてのシンボルに遷移があり (ただし、それらの多くは「シンク」状態への遷移である可能性があります)、状況に応じて完全な入力に一致します。入力の最後のシンボルが読み取られたときに、オートマトンが受け入れ状態にあるかどうか。lexer モデルは少し異なりますが、同様に簡単に形式化できます。

理論モデルの唯一の難点は、「最後の受容状態に戻ること」です。実際には、これは通常、受け入れ状態に到達するたびに状態と入力位置を記憶することによって行われます。これは、おそらく任意の量だけ、入力ストリームを巻き戻す必要があることを意味します。

ほとんどの言語はバックアップを頻繁に必要とするわけではなく、無期限のバックアップを必要とする言語はほとんどありません。一部のレクサー ジェネレーターは、バックアップ状態がない場合、より高速なコードを生成できます。(またはflexを使用すると、これが行われます。)-Cf-CF

無期限のバックアップにつながる一般的なケースの 1 つは、文字列リテラルに対して適切なエラーを返さないことです。

["][^"\n]*["]    { return STRING; }
 /* ... */
.                { return INVALID; }

ここで、同じ行に"一致するものがあれば、最初のパターンは で始まる文字列リテラルと一致します。"(\簡単にするために -escapes を省略しました。) 文字列リテラルが終了していない場合、最後のパターンは一致しますが、入力を . に巻き戻す必要があります"。ほとんどの場合、一致しない を無視して字句解析を続けようとしても無意味"です。行の残りの部分をすべて無視する方が理にかなっています。そのため、バックアップは非効率的であるだけでなく、誤ったエラー メッセージが急増する可能性もあります。より良い解決策は次のとおりです。

["][^"\n]*["]    { return STRING; } 
["][^"\n]*       { return INVALID_STRING; }

ここで、2 番目の選択肢は、文字列が終了していない場合にのみ成功します。これは、文字列が終了している場合、最初の選択肢がもう 1 文字一致するためです。したがって、これらの選択肢がどの順序で表示されるかは問題ではありません。

于 2013-05-05T23:04:54.570 に答える