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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 1983 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

个数

Python

可否

perl

11 条回复

persistz

2019-06-04 23:18:25 +08:00 via Android

更正一下，有个 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 via Android

@xml123 这里\1 指的是第一个括号对吧？我试一下，因为之前找到 re 里对这种写法的定义…

persistz

2019-06-04 23:31:20 +08:00 via Android

@junkun 嗯，这是没错的，但编程语言里的 re 不是真正的正则语言，所以概念上不能直接和 CFL 比较

junkun

2019-06-04 23:32:09 +08:00

但是 Python 的 re 是可以的。用\1 表示第一个捕获组。

persistz

2019-06-04 23:34:35 +08:00 via Android

@junkun 感谢感谢！结帖！

persistz

2019-06-04 23:34:45 +08:00 via Android

@xml123 感谢感谢！

lance6716

2019-06-05 01:16:15 +08:00 via Android

@junkun 哇，这怎么实现

Death

2019-06-05 11:17:20 +08:00 via Android

@persistz @junkun
所以 regex 这个名字还是挺有误导性的 hhh
印象中 regex 是能够匹配到 CSL 的，但是等价不等价就不知道了……

persistz

2019-06-05 19:50:20 +08:00

@Death regex 是属于 CSL 的，因为即使有 back-reference，也可以拿 LBA 表示，正好看到了一篇论文讲这个