1

現在、「ドラゴン ブック」(コンパイラ: 原則、手法、およびツール) を読み進めており、DFA (決定論的有限オートマトン) を使用する字句解析の章で行き詰っています。

DFA は 2 次元配列で、最初の次元には状態が含まれ、2 番目の次元には遷移シンボルが含まれます。これは、すべての DFA 状態に言語のすべての記号が含まれていることを意味します。この本の例では小さな言語 (通常は 2 つの記号) を使用し、章の最後に次の注記を付けています。 、配列は1メガバイト未満しか消費しません。」

ただし、文字列を一致させるには、すべての文字、つまり文字セット全体を一致させたいと考えており、多くの入力ファイルは UTF-8 エンコーディングを使用しています。これにより、アルファベットが大きくなり、DFA のサイズが非常に大きくなります。

これが私が立ち往生しているポイントです。字句解析器や正規表現シミュレーターは一般的にこれをどのように処理していますか?

ありがとう！

4

2 に答える 2

1

私はこの問題についてひらめきました。字句解析では、ASCII 範囲を超える文字を照合する必要があるのは、文字列やコメントなどでワイルドカード マッチングを行うときだけです。これらはワイルドカードでのみ使用され、個別には使用されないため、値が 128 以上のすべての文字は、単一の「その他」の値として表すことができます。このように、アルファベットと DFA は小さいままですが、遷移テーブルを使用して Unicode 文字セット全体に一致させることができます。

于 2013-09-19T20:34:41.883 に答える