转换为状态机的正则表达式的简短示例？

在Stack Overflow播客#36(http://blog.stackoverflow.com/2009/01/podcast-36/)中,有人表达了这样的观点:一旦你理解了设置状态机是多么容易,你就会知道永远不要试图不恰当地使用正则表达式.

我做了很多搜索.我发现了一些学术论文和其他复杂的例子,但我想找一个简单的例子来帮助我理解这个过程.我使用了很多正则表达式,我想确保我永远不再使用"不恰当".

当然,虽然你需要更复杂的例子来真正理解RE的工作原理.考虑以下RE:

^[A-Za-z][A-Za-z0-9_]*$

这是一个典型的标识符(必须以alpha开头,后面可以包含任意数量的字母数字和非字符字符,包括无字符).以下伪代码显示了如何使用有限状态机完成此操作:

state = FIRSTCHAR
for char in all_chars_in(string):
    if state == FIRSTCHAR:
            if char is not in the set "A-Z" or "a-z":
                error "Invalid first character"
            state = SUBSEQUENTCHARS
            next char
    if state == SUBSEQUENTCHARS:
            if char is not in the set "A-Z" or "a-z" or "0-9" or "_":
                error "Invalid subsequent character"
            state = SUBSEQUENTCHARS
            next char

现在,正如我所说,这是一个非常简单的例子.它没有说明如何进行贪婪/不一致的匹配,回溯,一行(而不是整行)的匹配以及RE语法容易处理的状态机的其他更深奥的功能.

这就是REs如此强大的原因.执行单线程RE可以执行的实际有限状态机代码通常非常长且复杂.

你可以做的最好的事情是获取一些特定简单语言的lex/yacc(或等效)代码的副本,并查看它生成的代码.它并不漂亮(它不一定是因为它不应该由人类阅读,它们应该是在查看lex/yacc代码),但它可以让你更好地了解它们是如何工作的.

一个相当方便的方法来帮助查看这个在任何模式上使用python的鲜为人知的re.DEBUG标志:

>>> re.compile(r'<([A-Z][A-Z0-9]*)\b[^>]*>(.*?)', re.DEBUG)
literal 60
subpattern 1
  in
    range (65, 90)
  max_repeat 0 65535
    in
      range (65, 90)
      range (48, 57)
at at_boundary
max_repeat 0 65535
  not_literal 62
literal 62
subpattern 2
  min_repeat 0 65535
    any None
literal 60
literal 47
groupref 1
literal 62

'literal'和'range'之后的数字是指它们应该匹配的ascii字符的整数值.

动起来做自己的!

HTTP://osteele.com/tools/reanimator/ ???

这是一个非常好的拼凑工具,可以将正则表达式可视化为FSM.它不支持您在现实世界正则表达式引擎中找到的某些语法,但肯定足以准确理解正在发生的事情.