#prog #article
Можно ли подсчитать производную от регулярного выражения? Можно и нужно!
Статья рассказывает о изученной и эффективной, но почему-то мало известной на практике технике построения распознающих конечных автоматов непосредственно из регулярных выражений. К сожалению, в статье рассматривается лишь задача о соответствии регулярного тексту, в ней ничего не говорится о, скажем, захвате соответствующих частей текста.
"In this paper, we have presented RE derivatives, which are an old, but largely forgotten, technique for constructing DFAs directly from REs. Our experience has been that RE derivatives are a superior technique for generating scanners from REs and they should be in the toolkit of any programmer. Specifically, RE derivatives have the following advantages:
• They provide a direct RE to DFA translation that is well suited to implementation in functional languages.
• They support extended REs almost for free.
• The generated scanners are often optimal in the number of states and are uniformly better than those produced by previous tools.
In addition to presenting the basic RE to DFA algorithm, we have also discussed a number of practical issues related to implementing a scanner generator that is based on RE derivatives, including supporting large character sets"
www.ccs.neu.edu/home/turon/re-deriv.pdf
