あいさつ！
ドラゴンブックの第 3 章 (字句解析) を読んでいるうちに、彼らが有限オートマトンについて話し始めるまで、ほとんどすべて (正規表現でトークンを指定する方法) を理解できました。そして、それは字句解析器を説明する上で大きな部分を占めるように思われました。
これで、有限オートマトンの概念は理解できましたが、字句解析器での役割と使用法がわかりません。正規表現でトークンを指定しないのはなぜですか?
前もって感謝します。
質問する
1549 次
1 に答える
0
正規表現は、有限オートマトンで、より正確には決定論的オートマトンで表すことができます。
Regex を記述すると、lexer はそれを DFA に変換して、テキスト内の一致を見つけます。もちろん、有限オートマトンは字句解析器でその役割を果たします。
Thompson の構築アルゴリズム ( http://en.wikipedia.org/wiki/Thompson 's_construction_algorithm ) のような正規表現を FA に変換する非常に単純なアルゴリズムがありますが、最適化されたアルゴリズムを見つけることができます。
于 2014-03-04T10:01:31.273 に答える