V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
noming
V2EX  ›  问与答

菜鸟请教正则表达式问题

  •  
  •   noming · 2019-09-21 06:15:55 +08:00 · 2177 次点击
    这是一个创建于 1898 天前的主题,其中的信息可能已经有所发展或是发生改变。

    想匹配一段文字中"start"到"end"之间的内容, 文中除了"start"和"end"其他的可能是任意字符, 该段文字中可能存在多个"start", 怎样写正则表达式只匹配从"end"之前最近的那个"start"到"end"之间的内容.

    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.

    如上段文字, 只匹配"start residents lacks a grocery store end". 写了好久没弄出来, 也不知道如何搜索该问题. 谢了!

    25 条回复    2019-09-21 17:26:06 +08:00
    delectate
        1
    delectate  
       2019-09-21 06:46:55 +08:00   ❤️ 1
    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']
    >>>
    Nasei
        2
    Nasei  
       2019-09-21 07:14:06 +08:00   ❤️ 2
    \bstart((?!start).)*end\b
    geelaw
        3
    geelaw  
       2019-09-21 07:30:27 +08:00   ❤️ 3
    用理论帮助思考,考虑一个 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)*
    geelaw
        4
    geelaw  
       2019-09-21 07:34:02 +08:00
    呃,上面那个似乎有错误,正确的结果应该是:

    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)
    IvanLi127
        5
    IvanLi127  
       2019-09-21 08:49:30 +08:00 via Android   ❤️ 1
    本来感觉还会写的,看完楼上大佬解答,我怂了
    xml123
        6
    xml123  
       2019-09-21 09:04:29 +08:00
    想到一个比较笨的方法,如果只有一个 end,可以考虑字符串逆序然后用懒惰模式
    noming
        7
    noming  
    OP
       2019-09-21 09:09:37 +08:00
    @delectate 这个还是会包含第一个"start"

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

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

    @xml123 逆序怎么操作? 我查查资料
    noming
        8
    noming  
    OP
       2019-09-21 09:11:10 +08:00
    @IvanLi127 膜拜各位大佬
    xml123
        9
    xml123  
       2019-09-21 09:13:25 +08:00
    @noming #7 字符串逆序之后,dne.*?trats
    noqwerty
        10
    noqwerty  
       2019-09-21 09:22:58 +08:00   ❤️ 1
    或者直接 re.search("(start.*)?(start.*end)", s).group(2)
    ipwx
        11
    ipwx  
       2019-09-21 09:25:12 +08:00
    零款断言能解决的事情,3L 搞这么复杂,无语了。

    http://ideone.com/G6SzMw
    ipwx
        12
    ipwx  
       2019-09-21 09:27:55 +08:00 via Android
    @noqwerty 每次客户端我总是把回复错误点击成感谢。

    anyway,你这个不行啊。它要有更多 start 呢?
    noqwerty
        13
    noqwerty  
       2019-09-21 09:34:14 +08:00
    @ipwx #12 多个也没问题啊,第一组是 greedy 的会把所有前面的 start 都匹配到: https://regex101.com/r/2jv8x3/1
    injector
        14
    injector  
       2019-09-21 10:11:12 +08:00
    \bstart(?!.*start).*\bend\b
    ipwx
        15
    ipwx  
       2019-09-21 11:38:10 +08:00
    WoW。。。。 我现在觉得 3L 是对的。

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

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

    https://regex101.com/r/cDExSo/1
    ipwx
        16
    ipwx  
       2019-09-21 11:38:37 +08:00
    Nasei
        17
    Nasei  
       2019-09-21 11:49:57 +08:00
    @ipwx 我试了下我的,可以啊
    ipwx
        18
    ipwx  
       2019-09-21 11:52:25 +08:00
    @Nasei 哦刚刚看错了。你这个确实可以。棒!

    不过 NFA/DFA 转 Regex 好像确实有点那么意思。
    geelaw
        19
    geelaw  
       2019-09-21 12:08:11 +08:00
    @xml123 #9 startendend 会拿到太长的结果。

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

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

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

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

    @noqwerty #10 startendstartend 会只能拿到第二个匹配。
    noqwerty
        20
    noqwerty  
       2019-09-21 12:28:17 +08:00 via Android
    @geelaw 哦哦,我理解错他的意思了,是要匹配到所有 start...end 对,不是只有一个 end
    autoxbc
        21
    autoxbc  
       2019-09-21 14:02:31 +08:00
    要是我的话,把 start 和 end 替换成 html tag,丢给浏览器解析,然后 CSS Selectors,XPath 随便玩

    每次你用正则解析序列化的结构数据,就是重新写了一遍这种数据结构的解析器 -- 鲁迅
    ipwx
        22
    ipwx  
       2019-09-21 14:06:41 +08:00
    @geelaw 嘛嘛,理论辅助思考这点我同意。

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

    如果有什么是正则零宽都不能解决的,我认为应该上文法解析器。当然不能是 LL/LR 这类笨重的不好维护的解析器,我觉得以 PyParsing 为代表的那种解析器更适合工程。
    ipwx
        23
    ipwx  
       2019-09-21 14:08:24 +08:00
    @geelaw 对,PyParsing 为代表的是 PEG 解析器。

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

    这类我觉得更适合工程,更容易维护。因为你可以把一个一个子规则拆开来写单元测试,而不是写一长串 CFG 规则,然后用外部工具转换成根本没法调试的一坨代码。
    flynaj
        24
    flynaj  
       2019-09-21 17:17:13 +08:00 via Android
    start (.*?) end 这样就行,非贪婪模式,基本正则就可以,写一大串是搞什么
    imdong
        25
    imdong  
       2019-09-21 17:26:06 +08:00
    (start(:?[a-z\s]+)?end)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   980 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 19:19 · PVG 03:19 · LAX 11:19 · JFK 14:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.