正規表現パーサーを実装するときにドット（。）記号を実装する方法は？

Question

私は、ドラゴンブックのアルゴリズムを使用して正規表現パーサを実装しています。今私はDTranテーブルを生成して、(a|b)*abbのようないくつかの基本正規表現を解析することができます。

しかし、どの文字にも一致する.シンボルを実装する際に問題が発生しました。ドラゴンブックにそれに関するテキストはありません、それを実装するいくつかの例や記事がありますか？

Answer 1

あなた自身で解決してください、それはそれの楽しさです。以下はあまり答えはありませんが、それにもかかわらずです。

1. n個の "。"の一致の状態/条件を追跡します。そう。[n]そしてパターンマッチングを続ける。
2. チートと先を見て、本当に良い考えではありません。それ以来、[n]は大きくなる可能性がありますが、おそらくそうではありません。

実際には、*のような他のパターンマッチングに似ていますが、同じテキストで複数のマッチが発生する可能性があります。それがなぜ残っているのかもしれないのでしょうか（文法が豊富であると、Dtranや状態マシンは難しくなります）。それは本当に似ていますが、charを受け入れます。あなたはNFA（非決定論的有限オートマトン）に切り替える必要があるかもしれません。

明らかに私はドラゴンの本を研究していませんでしたが、大学では "計算の理論"を取り上げました。私は多くの状態マシンを描きました。