(コンパイラの書き方を学んでいるところなので、間違った主張があれば訂正してください)
単純に正規表現を使用できるのに、コード (goto ステートメント、テーブル駆動型の実装) で DFA を実装する人がいるでしょうか? 私が理解している限り、字句解析器は文字列を取り込み、言語の文法定義では端末であるトークンのリストを大量に生成し、それらを正規表現で記述できるようにします。正規表現の束をループして、一致が見つかった場合にループから抜け出す方が簡単ではないでしょうか?
質問する
811 次
1 に答える
7
多くの場合、DFA よりも正規表現を書く方が簡単だというあなたの言う通りです。しかし、考えるべき良い質問は
これらの正規表現マッチャーはどのように機能しますか?
正規表現マッチャーの非常に高速な実装のほとんどは、内部である種のオートマトン (NFA または最小状態 DFA) にコンパイルすることによって機能します。正規表現を使用して一致するトークンを記述し、それらすべてをループすることによって機能するスキャナーを構築したい場合は、絶対にそうすることができますが、内部的にはおそらく DFA にコンパイルされます。
非常に複雑なため、スキャンや解析を行うために DFA を実際にコード化する人を目にすることは非常にまれです。lexやのようなツールがあるのはこのためです。これらのツールを使用flexすると、一致する正規表現を指定して、バックグラウンドで DFA に自動的にコンパイルできます。そうすれば、両方の長所を活かすことができます。より適切な正規表現のフレームワークを使用して何を照合するかを記述しますが、舞台裏で DFA の速度と効率を得ることができます。
巨大な DFA の構築に関するもう 1 つの重要な点は、複数の異なる正規表現の照合を並行して試行する単一の DFA を構築できることです。これにより、可能なすべての正規表現一致を同時に検索する方法で文字列に対して一致する DFA を実行できるため、効率が向上します。
お役に立てれば！
于 2013-01-19T23:14:25.510 に答える