菜鸟请教正则表达式问题

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.*)?(start.*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)