[Lisp-cn] [OT]正则表达式的字符集合功能应该如何实现？

[宋为]

最近拿Common Lisp写了个小的正则表达式引擎。
按龙书上给的方法实现的。

地址：（还没有按照asdf打包）
https://github.com/leosongwei/ll-regex

但是在实现高级功能的时候遇到了问题。我想实现集合功能（就是[a-z]这种），
于是就把构建出来的集合作为一种匹配类型放在nfa中，然后构建dfa。然后发现存
在这样的问题：

表达式是a\e（我暂时用\e表示所有小写英文字母），不能匹配aa。

构建出来的DFA是这样的：
（最前面是编号，states是构造DFA用的中间变量，outs 是 (cons 如果匹配 应该
去的地方)，sym指出如果停在某处，应该返回的值，若是最后一次跳转到3，就返
回 'MATCH）

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实不是一个DFA，是个NFA，接收到“aa”时，每个字母既和LOWCASE这
个集合匹配，又和"a"匹配，从理论上讲，此时不应该知道要跳往哪一个状态。如
此看来这肯定不是正确的姿势。

求指点正确的实现方法。谢谢啦。

[Liutos]

然而我并䞍懂NFA/DFA【逃

最近拿Common Lisp写了䞪小的正则衚蟟匏匕擎。
按韙乊䞊给的方法实现的。
地址还没有按照asdf打包
https://github.com/leosongwei/ll-regex
䜆是圚实现高级功胜的时候遇到了问题。我想实现集合功胜就是[a-z]这种
于是就把构建出来的集合䜜䞺䞀种匹配类型攟圚nfa䞭然后构建dfa。然后发现存
圚这样的问题
衚蟟匏是a\e我暂时甚\e衚瀺所有小写英文字母䞍胜匹配aa。
构建出来的DFA是这样的
最前面是猖号states是构造DFA甚的䞭闎变量outs 是 (cons 劂果匹配 应该
去的地方)sym指出劂果停圚某倄应该返回的倌若是最后䞀次跳蜬到3就返
回 'MATCH

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实䞍是䞀䞪DFA是䞪NFA接收到“aa”时每䞪字母既和LOWCASE这
䞪集合匹配又和"a"匹配从理论䞊讲歀时䞍应该知道芁跳埀哪䞀䞪状态。劂
歀看来这肯定䞍是正确的姿势。
求指点正确的实现方法。谢谢啊。
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了 Google 眑䞊论坛的“Lisp-cn(Lisp䞭文甚户组)”矀组。
芁查看曎倚选项请访问 https://groups.google.com/d/optout。

--
Liutos Love Linux LaTeX Lisp Ling

我的GitHub䞻页https://github.com/Liutos

[Nala Ginrut]

没有时闎细看劂果䜠是想知道NFA劂䜕蜬DFA的话最奜读Hopcraft的《自劚机理论、语蚀和计算富论》

Post by Liutos
然而我并䞍懂NFA/DFA【逃

最近拿Common Lisp写了䞪小的正则衚蟟匏匕擎。
按韙乊䞊给的方法实现的。
地址还没有按照asdf打包
https://github.com/leosongwei/ll-regex
䜆是圚实现高级功胜的时候遇到了问题。我想实现集合功胜就是[a-z]这种
于是就把构建出来的集合䜜䞺䞀种匹配类型攟圚nfa䞭然后构建dfa。然后发现存
圚这样的问题
衚蟟匏是a\e我暂时甚\e衚瀺所有小写英文字母䞍胜匹配aa。
构建出来的DFA是这样的
最前面是猖号states是构造DFA甚的䞭闎变量outs 是 (cons 劂果匹配 应该
去的地方)sym指出劂果停圚某倄应该返回的倌若是最后䞀次跳蜬到3就返
回 'MATCH

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实䞍是䞀䞪DFA是䞪NFA接收到“aa”时每䞪字母既和LOWCASE这
䞪集合匹配又和"a"匹配从理论䞊讲歀时䞍应该知道芁跳埀哪䞀䞪状态。劂
歀看来这肯定䞍是正确的姿势。
求指点正确的实现方法。谢谢啊。
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了 Google 眑䞊论坛的“Lisp-cn(Lisp䞭文甚户组)”矀组。
芁查看曎倚选项请访问 https://groups.google.com/d/optout。

--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub䞻页https://github.com/Liutos
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了Google眑䞊论坛䞊的“Lisp-cn(Lisp䞭文甚户组)”矀组。
芁查看曎倚选项请访问https://groups.google.com/d/optout。

[宋为]

现在在学编译原理，看来还要提高知识水平啊

没有时间细看，如果你是想知道NFA如何转DFA的话，最好读Hopcraft的《自动机理
论、语言和计算导论》
然而我并不懂NFA/DFA【逃
最近拿Common Lisp写了个小的正则表达式引擎。
按龙书上给的方法实现的。
地址：（还没有按照asdf打包）
https://github.com/leosongwei/ll-regex
但是在实现高级功能的时候遇到了问题。我想实现集合功能（就是[a-z]
这种），
于是就把构建出来的集合作为一种匹配类型放在nfa中，然后构建dfa。然
后发现存
在这样的问题：
表达式是a\e（我暂时用\e表示所有小写英文字母），不能匹配aa。
构建出来的DFA是这样的：
（最前面是编号，states是构造DFA用的中间变量，outs 是 (cons 如果
匹配 应该
去的地方)，sym指出如果停在某处，应该返回的值，若是最后一次跳转到
3，就返
回 'MATCH）

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实不是一个DFA，是个NFA，接收到“aa”时，每个字母既和
LOWCASE这
个集合匹配，又和"a"匹配，从理论上讲，此时不应该知道要跳往哪一个
状态。如
此看来这肯定不是正确的姿势。
求指点正确的实现方法。谢谢啦。
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Lisp-cn(Lisp中文用
户组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问 https://groups.google.com/d/optout。
--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub主页：https://github.com/Liutos
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了Google网上论坛上的“Lisp-cn(Lisp中文用户
组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问https://groups.google.com/d/optout。
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了Google网上论坛上的“Lisp-cn(Lisp中文用户组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问https://groups.google.com/d/optout。

--
此致

---------------------------------------------------------
乱码部分为GPG数字签名，用于验证传输完整性。请当面向我验证公钥。

[Nala Ginrut]

话说自动机不是应该在编译原理之前学么

Post by 宋为
现在在学编译原理，看来还要提高知识水平啊

没有时间细看，如果你是想知道NFA如何转DFA的话，最好读Hopcraft的《自动机理
论、语言和计算导论》
然而我并不懂NFA/DFA【逃
最近拿Common Lisp写了个小的正则表达式引擎。
按龙书上给的方法实现的。
地址：（还没有按照asdf打包）
https://github.com/leosongwei/ll-regex
但是在实现高级功能的时候遇到了问题。我想实现集合功能（就是[a-z]
这种），
于是就把构建出来的集合作为一种匹配类型放在nfa中，然后构建dfa。然
后发现存
在这样的问题：
表达式是a\e（我暂时用\e表示所有小写英文字母），不能匹配aa。
构建出来的DFA是这样的：
（最前面是编号，states是构造DFA用的中间变量，outs 是 (cons 如果
匹配 应该
去的地方)，sym指出如果停在某处，应该返回的值，若是最后一次跳转到
3，就返
回 'MATCH）

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实不是一个DFA，是个NFA，接收到“aa”时，每个字母既和
LOWCASE这
个集合匹配，又和"a"匹配，从理论上讲，此时不应该知道要跳往哪一个
状态。如
此看来这肯定不是正确的姿势。
求指点正确的实现方法。谢谢啦。
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Lisp-cn(Lisp中文用
户组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问 https://groups.google.com/d/optout。
--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub主页：https://github.com/Liutos
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了Google网上论坛上的“Lisp-cn(Lisp中文用户
组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问https://groups.google.com/d/optout。
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了Google网上论坛上的“Lisp-cn(Lisp中文用户组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问https://groups.google.com/d/optout。

--
此致
---------------------------------------------------------
乱码部分为GPG数字签名，用于验证传输完整性。请当面向我验证公钥。
--

[宋为]

学校比较水，没有这门课 =。=

Post by Nala Ginrut
话说自动机不是应该在编译原理之前学么

Post by 宋为
现在在学编译原理，看来还要提高知识水平啊

没有时间细看，如果你是想知道NFA如何转DFA的话，最好读Hopcraft的《自动机理
论、语言和计算导论》
然而我并不懂NFA/DFA【逃
最近拿Common Lisp写了个小的正则表达式引擎。
按龙书上给的方法实现的。
地址：（还没有按照asdf打包）
https://github.com/leosongwei/ll-regex
但是在实现高级功能的时候遇到了问题。我想实现集合功能（就是[a-z]
这种），
于是就把构建出来的集合作为一种匹配类型放在nfa中，然后构建dfa。然
后发现存
在这样的问题：
表达式是a\e（我暂时用\e表示所有小写英文字母），不能匹配aa。
构建出来的DFA是这样的：
（最前面是编号，states是构造DFA用的中间变量，outs 是 (cons 如果
匹配 应该
去的地方)，sym指出如果停在某处，应该返回的值，若是最后一次跳转到
3，就返
回 'MATCH）

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实不是一个DFA，是个NFA，接收到“aa”时，每个字母既和
LOWCASE这
个集合匹配，又和"a"匹配，从理论上讲，此时不应该知道要跳往哪一个
状态。如
此看来这肯定不是正确的姿势。
求指点正确的实现方法。谢谢啦。
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Lisp-cn(Lisp中文用
户组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问 https://groups.google.com/d/optout。
--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub主页：https://github.com/Liutos
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了Google网上论坛上的“Lisp-cn(Lisp中文用户
组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问https://groups.google.com/d/optout。
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了Google网上论坛上的“Lisp-cn(Lisp中文用户组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问https://groups.google.com/d/optout。

--
此致
---------------------------------------------------------
乱码部分为GPG数字签名，用于验证传输完整性。请当面向我验证公钥。
--

--
此致

---------------------------------------------------------
乱码部分为GPG数字签名，用于验证传输完整性。请当面向我验证公钥。

[Liutos]

然而我们圓时连猖译原理郜没有

孊校比蟃氎没有这闚诟 =。=

话诎自劚机䞍是应该圚猖译原理之前孊么

现圚圚孊猖译原理看来还芁提高知识氎平啊

Post by Nala Ginrut
没有时闎细看劂果䜠是想知道NFA劂䜕蜬DFA的话最奜读Hopcraft的《自劚机理
论、语蚀和计算富论》
然而我并䞍懂NFA/DFA【逃
最近拿Common Lisp写了䞪小的正则衚蟟匏匕擎。
按韙乊䞊给的方法实现的。
地址还没有按照asdf打包
https://github.com/leosongwei/ll-regex
䜆是圚实现高级功胜的时候遇到了问题。我想实现集合功胜就是[a-z]
这种
于是就把构建出来的集合䜜䞺䞀种匹配类型攟圚nfa䞭然后构建dfa。然
后发现存
圚这样的问题
衚蟟匏是a\e我暂时甚\e衚瀺所有小写英文字母䞍胜匹配aa。
构建出来的DFA是这样的
最前面是猖号states是构造DFA甚的䞭闎变量outs 是 (cons 劂果
匹配 应该
去的地方)sym指出劂果停圚某倄应该返回的倌若是最后䞀次跳蜬到
3就返
回 'MATCH

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实䞍是䞀䞪DFA是䞪NFA接收到“aa”时每䞪字母既和
LOWCASE这
䞪集合匹配又和"a"匹配从理论䞊讲歀时䞍应该知道芁跳埀哪䞀䞪
状态。劂
歀看来这肯定䞍是正确的姿势。
求指点正确的实现方法。谢谢啊。
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了 Google 眑䞊论坛的“Lisp-cn(Lisp䞭文甚
户组)”矀组。
芁退订歀矀组并停止接收歀矀组的电子邮件请发送电子邮件到lisp-
芁查看曎倚选项请访问 https://groups.google.com/d/optout。
--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub䞻页https://github.com/Liutos
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了Google眑䞊论坛䞊的“Lisp-cn(Lisp䞭文甚户
组)”矀组。
芁退订歀矀组并停止接收歀矀组的电子邮件请发送电子邮件到lisp-
芁查看曎倚选项请访问https://groups.google.com/d/optout。
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了Google眑䞊论坛䞊的“Lisp-cn(Lisp䞭文甚户组)”矀组。
芁退订歀矀组并停止接收歀矀组的电子邮件请发送电子邮件到lisp-
芁查看曎倚选项请访问https://groups.google.com/d/optout。

--
歀臎
---------------------------------------------------------
乱码郚分䞺GPG数字筟名甚于验证䌠蟓完敎性。请圓面向我验证公钥。
--

--
歀臎
---------------------------------------------------------
乱码郚分䞺GPG数字筟名甚于验证䌠蟓完敎性。请圓面向我验证公钥。
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了 Google 眑䞊论坛的“Lisp-cn(Lisp䞭文甚户组)”矀组。
芁查看曎倚选项请访问 https://groups.google.com/d/optout。

--
Liutos Love Linux LaTeX Lisp Ling

我的GitHub䞻页https://github.com/Liutos

[Nala Ginrut]

别泄气有了也没什么卵甚

Post by Liutos
然而我们圓时连猖译原理郜没有

孊校比蟃氎没有这闚诟 =。=

话诎自劚机䞍是应该圚猖译原理之前孊么

现圚圚孊猖译原理看来还芁提高知识氎平啊

Post by Nala Ginrut
没有时闎细看劂果䜠是想知道NFA劂䜕蜬DFA的话最奜读Hopcraft的《自劚机理
论、语蚀和计算富论》
然而我并䞍懂NFA/DFA【逃
最近拿Common Lisp写了䞪小的正则衚蟟匏匕擎。
按韙乊䞊给的方法实现的。
地址还没有按照asdf打包
https://github.com/leosongwei/ll-regex
䜆是圚实现高级功胜的时候遇到了问题。我想实现集合功胜就是[a-z]
这种
于是就把构建出来的集合䜜䞺䞀种匹配类型攟圚nfa䞭然后构建dfa。然
后发现存
圚这样的问题
衚蟟匏是a\e我暂时甚\e衚瀺所有小写英文字母䞍胜匹配aa。
构建出来的DFA是这样的
最前面是猖号states是构造DFA甚的䞭闎变量outs 是 (cons 劂果
匹配 应该
去的地方)sym指出劂果停圚某倄应该返回的倌若是最后䞀次跳蜬到
3就返
回 'MATCH

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实䞍是䞀䞪DFA是䞪NFA接收到“aa”时每䞪字母既和
LOWCASE这
䞪集合匹配又和"a"匹配从理论䞊讲歀时䞍应该知道芁跳埀哪䞀䞪
状态。劂
歀看来这肯定䞍是正确的姿势。
求指点正确的实现方法。谢谢啊。
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了 Google 眑䞊论坛的“Lisp-cn(Lisp䞭文甚
户组)”矀组。
芁退订歀矀组并停止接收歀矀组的电子邮件请发送电子邮件到lisp-
芁查看曎倚选项请访问 https://groups.google.com/d/optout。
--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub䞻页https://github.com/Liutos
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了Google眑䞊论坛䞊的“Lisp-cn(Lisp䞭文甚户
组)”矀组。
芁退订歀矀组并停止接收歀矀组的电子邮件请发送电子邮件到lisp-
芁查看曎倚选项请访问https://groups.google.com/d/optout。
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了Google眑䞊论坛䞊的“Lisp-cn(Lisp䞭文甚户组)”矀组。
芁退订歀矀组并停止接收歀矀组的电子邮件请发送电子邮件到lisp-
芁查看曎倚选项请访问https://groups.google.com/d/optout。

--
歀臎
---------------------------------------------------------
乱码郚分䞺GPG数字筟名甚于验证䌠蟓完敎性。请圓面向我验证公钥。
--

--
歀臎
---------------------------------------------------------
乱码郚分䞺GPG数字筟名甚于验证䌠蟓完敎性。请圓面向我验证公钥。
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了 Google 眑䞊论坛的“Lisp-cn(Lisp䞭文甚户组)”矀组。
芁查看曎倚选项请访问 https://groups.google.com/d/optout。

--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub䞻页https://github.com/Liutos
--
--
Lisp-cn(Lisp䞭文甚户组)
CLUG http://lisp.org.cn
---
悚收到歀邮件是因䞺悚订阅了Google眑䞊论坛䞊的“Lisp-cn(Lisp䞭文甚户组)”矀组。
芁查看曎倚选项请访问https://groups.google.com/d/optout。

[宋为]

如果没有更好的办法我就只有在parser这里搞定了：
[0-9]

(0|1|2|3|4|5|6|7|8|9)

=_=

然而我并不懂NFA/DFA【逃
最近拿Common Lisp写了个小的正则表达式引擎。
按龙书上给的方法实现的。
地址：（还没有按照asdf打包）
https://github.com/leosongwei/ll-regex
但是在实现高级功能的时候遇到了问题。我想实现集合功能（就是[a-z]这种），
于是就把构建出来的集合作为一种匹配类型放在nfa中，然后构建dfa。然后发现存
在这样的问题：
表达式是a\e（我暂时用\e表示所有小写英文字母），不能匹配aa。
构建出来的DFA是这样的：
（最前面是编号，states是构造DFA用的中间变量，outs 是 (cons 如果匹配 应该
去的地方)，sym指出如果停在某处，应该返回的值，若是最后一次跳转到3，就返
回 'MATCH）

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实不是一个DFA，是个NFA，接收到“aa”时，每个字母既和LOWCASE这
个集合匹配，又和"a"匹配，从理论上讲，此时不应该知道要跳往哪一个状态。如
此看来这肯定不是正确的姿势。
求指点正确的实现方法。谢谢啦。
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Lisp-cn(Lisp中文用户
组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问 https://groups.google.com/d/optout。
--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub主页：https://github.com/Liutos
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了Google网上论坛上的“Lisp-cn(Lisp中文用户组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问https://groups.google.com/d/optout。

--
此致

---------------------------------------------------------
乱码部分为GPG数字签名，用于验证传输完整性。请当面向我验证公钥。

[宋为]

现在就是不知道这种搞法是不是正确的姿势：
[0-9] > (0|1|2|3|4|5|6|7|8|9)
[a-d] > (a|b|c|d)

Post by 宋为
如果没有更好的办法我就只有在parser这里搞定了：
[0-9]

(0|1|2|3|4|5|6|7|8|9)

=_=

然而我并不懂NFA/DFA【逃
最近拿Common Lisp写了个小的正则表达式引擎。
按龙书上给的方法实现的。
地址：（还没有按照asdf打包）
https://github.com/leosongwei/ll-regex
但是在实现高级功能的时候遇到了问题。我想实现集合功能（就是[a-z]这种），
于是就把构建出来的集合作为一种匹配类型放在nfa中，然后构建dfa。然后发现存
在这样的问题：
表达式是a\e（我暂时用\e表示所有小写英文字母），不能匹配aa。
构建出来的DFA是这样的：
（最前面是编号，states是构造DFA用的中间变量，outs 是 (cons 如果匹配 应该
去的地方)，sym指出如果停在某处，应该返回的值，若是最后一次跳转到3，就返
回 'MATCH）

0: #<D states:(0) outs:((LOWCASE . 1) (a . 2)) sym:NIL>
1: #<D states:NIL outs:((LOWCASE . 1) (a . 1)) sym:NIL>
2: #<D states:(1) outs:((LOWCASE . 3) (a . 1)) sym:NIL>
3: #<D states:(2) outs:((LOWCASE . 1) (a . 1)) sym:MATCH>

我意识到这其实不是一个DFA，是个NFA，接收到“aa”时，每个字母既和LOWCASE这
个集合匹配，又和"a"匹配，从理论上讲，此时不应该知道要跳往哪一个状态。如
此看来这肯定不是正确的姿势。
求指点正确的实现方法。谢谢啦。
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Lisp-cn(Lisp中文用户
组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问 https://groups.google.com/d/optout。
--
Liutos Love Linux LaTeX Lisp Ling
我的GitHub主页：https://github.com/Liutos
--
--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn
---
您收到此邮件是因为您订阅了Google网上论坛上的“Lisp-cn(Lisp中文用户组)”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到lisp-
要查看更多选项，请访问https://groups.google.com/d/optout。

--
此致

---------------------------------------------------------
乱码部分为GPG数字签名，用于验证传输完整性。请当面向我验证公钥。