Python 的 re 可否表示类似 a^nba^n 这样的字符串？

2019-06-04 23:15:05 +08:00
 persistz

该公式指的是，在 b 的前后有相同个数的 n。 n 不是具体值，所以关键点在于相同个数而非指定个数。 已知 Perl 是可以的，好奇 python 的 re 库可否实现？

2021 次点击
所在节点    Python
11 条回复
persistz
2019-06-04 23:18:25 +08:00
更正一下，有个 typo...相同个数的 a。
xml123
2019-06-04 23:26:27 +08:00
(a+)b\1 不就行了吗，不过前后需要指定边界
junkun
2019-06-04 23:27:17 +08:00
按照计算理论来说，正则语法是 3 型语法，而 a^nba^n 是典型的 2 型语法。而且 2 型语法是 3 型语法的超集。所以理论上来说是匹配不了的。
persistz
2019-06-04 23:30:21 +08:00
@xml123 这里\1 指的是第一个括号对吧？我试一下，因为之前找到 re 里对这种写法的定义…
persistz
2019-06-04 23:31:20 +08:00
@junkun 嗯，这是没错的，但编程语言里的 re 不是真正的正则语言，所以概念上不能直接和 CFL 比较
junkun
2019-06-04 23:32:09 +08:00
但是 Python 的 re 是可以的。用\1 表示第一个捕获组。
persistz
2019-06-04 23:34:35 +08:00
@junkun 感谢感谢！结帖！
persistz
2019-06-04 23:34:45 +08:00
@xml123 感谢感谢！
lance6716
2019-06-05 01:16:15 +08:00
@junkun 哇，这怎么实现
Death
2019-06-05 11:17:20 +08:00
@persistz @junkun
所以 regex 这个名字还是挺有误导性的 hhh
印象中 regex 是能够匹配到 CSL 的，但是等价不等价就不知道了……
persistz
2019-06-05 19:50:20 +08:00
@Death regex 是属于 CSL 的，因为即使有 back-reference，也可以拿 LBA 表示，正好看到了一篇论文讲这个

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/570927

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX