菜鸟请教正则表达式问题

C:\Users\Delectate>python
Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) [MSC v.1914 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> tmpStr="Situated about 150 miles (240 km) north of Las Vegas, the remote start hamlet of just 50 year-round start residents lacks a grocery store end or even a gasoline station."
>>> re.findall(r'start.*end', tmpStr)
['start hamlet of just 50 year-round start residents lacks a grocery store end']
>>>

\bstart((?!start).)*end\b

用理论帮助思考，考虑一个 NFA，它的状态是
x/s/st/sta/star/start/starts/startst/startsta/startstar/startstart/starte/starten/startend
你希望这个机器接受 start 开头 end 结尾且中间没有 start 或者 end 的字符串，初始状态是 x。

用 q+r = q' 表示 q 之后看到 r 就进入 q'，只有 startend 是接受状态

读入最开始的 start：
x+s = s
s+t = st
st+a = sta
sta+r = star
star+t = start

中间可能出现 start：
start/starts/startst/startsta/startstar/starte/starten+s = starts
starts+t = startst
startst+a = startsta
startsta+r = startstar
startstar+t = startstart

中间可能出现 end：
start/starts/startst/startsta/startstar/starte/starten+e = starte
starte+n=starten
starten+d=startend

任何其他字符：
start+[^se] = start
starts+[^set] = start
startst+[^sea] = start
startsta+[^ser] = start
startstar+[^set] = start
starte+[^sen] = start
starten+[^sed] = start

通过 NFA 转换为正则表达式的算法得出一个写法是这样的

start((e(ne|e)*(ns|s)|s)(t(a(r(t(e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)*(t(a(r(te(ne|e)*(n[^sed]|[^sen])|e(ne|e)*(n[^sed]|[^sen])|[^set])|e(ne|e)*(n[^sed]|[^sen])|[^ser])|e(ne|e)*(n[^sed]|[^sen])|[^sea])|e(ne|e)*(n[^sed]|[^sen])|[^set])|e(ne|e)*(n[^sed]|[^sen])|[^se])*((e(ne|e)*(ns|s)|s)(t(a(r(t(e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)*(t(a(r(te(ne|e)*nd|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)((.(e(ne|e)*(ns|s)|s)(t(a(r(t(e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)*(t(a(r(te(ne|e)*(n[^sed]|[^sen])|e(ne|e)*(n[^sed]|[^sen])|[^set])|e(ne|e)*(n[^sed]|[^sen])|[^ser])|e(ne|e)*(n[^sed]|[^sen])|[^sea])|e(ne|e)*(n[^sed]|[^sen])|[^set])|.e(ne|e)*(n[^sed]|[^sen]))((e(ne|e)*(ns|s)|s)(t(a(r(t(e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)*(t(a(r(te(ne|e)*(n[^sed]|[^sen])|e(ne|e)*(n[^sed]|[^sen])|[^set])|e(ne|e)*(n[^sed]|[^sen])|[^ser])|e(ne|e)*(n[^sed]|[^sen])|[^sea])|e(ne|e)*(n[^sed]|[^sen])|[^set])|e(ne|e)*(n[^sed]|[^sen])|[^se])*((e(ne|e)*(ns|s)|s)(t(a(r(t(e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)*(t(a(r(te(ne|e)*nd|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)|.(e(ne|e)*(ns|s)|s)(t(a(r(t(e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)*(t(a(r(te(ne|e)*nd|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)|.e(ne|e)*nd)*

呃，上面那个似乎有错误，正确的结果应该是：

start((e(ne|e)*(ns|s)|s)(t(a(r(e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)*(t(a(r(e(ne|e)*(n[^sed]|[^sen])|[^set])|e(ne|e)*(n[^sed]|[^sen])|[^ser])|e(ne|e)*(n[^sed]|[^sen])|[^sea])|e(ne|e)*(n[^sed]|[^sen])|[^set])|e(ne|e)*(n[^sed]|[^sen])|[^se])*((e(ne|e)*(ns|s)|s)(t(a(r(e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)|e(ne|e)*(ns|s)|s)*(t(a(re(ne|e)*nd|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)|e(ne|e)*nd)

本来感觉还会写的，看完楼上大佬解答，我怂了

想到一个比较笨的方法，如果只有一个 end，可以考虑字符串逆序然后用懒惰模式

@delectate 这个还是会包含第一个"start"

@Nasei 简洁明了, 多谢! 明白了(?!abc)的用法

@geelaw 理论功底深厚, 谢谢!

@xml123 逆序怎么操作? 我查查资料

@IvanLi127 膜拜各位大佬

@noming #7 字符串逆序之后，dne.*?trats

或者直接 re.search("(start.*)?(stat.*end)", s).group(2)

零款断言能解决的事情，3L 搞这么复杂，无语了。

http://ideone.com/G6SzMw

@noqwerty 每次客户端我总是把回复错误点击成感谢。

anyway，你这个不行啊。它要有更多 start 呢?

@ipwx #12 多个也没问题啊，第一组是 greedy 的会把所有前面的 start 都匹配到： https://regex101.com/r/2jv8x3/1

\bstart(?!.*start).*\bend\b

WoW。。。。 我现在觉得 3L 是对的。

@Nasei @injector 我们用的零宽断言没法把所有这样的 start-end 对给搞出来。 @noqwerty 当然你那个也不行。

但是 3L 老哥的 NFA 却可以。

https://regex101.com/r/cDExSo/1

错了 https://regex101.com/r/cDExSo/2

@ipwx 我试了下我的，可以啊

@Nasei 哦刚刚看错了。你这个确实可以。棒！

不过 NFA/DFA 转 Regex 好像确实有点那么意思。

@xml123 #9 startendend 会拿到太长的结果。

@ipwx #11 对于我来说零宽断言不够“纯粹”。

而且重点是方法很简单（结果确实很复杂），所谓“理论帮助思考”，是指思考的很大一部分负担由理论内部所消化类似于使用方程比算术方法简单，“条件表达为方程”（建立一个 (G)NFA ）以及“解方程”（把 (G)NFA 转换为正则表达式）中，前者是比直接想出反向的算式简单的，后者是机械的。

至于为什么直接写一个正则表达式更加困难，是因为正则表达式中对补集、交集的表达力比较弱（纯粹的正则表达式根本没有这些功能，比如计算一个正则表达式识别的语言补的正则表达式，是没有什么很直接的办法的），而 (G)NFA 表达这些很容易。

#18 见 https://gist.github.com/GeeLaw/be3aec94a6ba7c3817ef2e16d261f616

@noqwerty #10 startendstartend 会只能拿到第二个匹配。

@geelaw 哦哦，我理解错他的意思了，是要匹配到所有 start...end 对，不是只有一个 end

要是我的话，把 start 和 end 替换成 html tag，丢给浏览器解析，然后 CSS Selectors，XPath 随便玩

每次你用正则解析序列化的结构数据，就是重新写了一遍这种数据结构的解析器 -- 鲁迅

@geelaw 嘛嘛，理论辅助思考这点我同意。

但是我觉得作为工程问题，可维护性也是很重要的。显然在这个例子里面，零宽断言（ @Nasei 版本）容易看懂，比较容易维护，就可以了。你那个版本的正则，只能作为智力游戏的结果，不能作为工程实践。

如果有什么是正则零宽都不能解决的，我认为应该上文法解析器。当然不能是 LL/LR 这类笨重的不好维护的解析器，我觉得以 PyParsing 为代表的那种解析器更适合工程。

@geelaw 对，PyParsing 为代表的是 PEG 解析器。

https://en.wikipedia.org/wiki/Parsing_expression_grammar

这类我觉得更适合工程，更容易维护。因为你可以把一个一个子规则拆开来写单元测试，而不是写一长串 CFG 规则，然后用外部工具转换成根本没法调试的一坨代码。

start （.*?） end 这样就行，非贪婪模式，基本正则就可以，写一大串是搞什么

(start(:?[a-z\s]+)?end)