为什么递归正则表达式不是正则表达式? [英] Why is recursive regex not regex?

问题描述

我正在阅读 这个问题，看到有几个人说递归正则表达式严格来说不是正则表达式.

I was reading through some of the responses in this question and saw that a few people said that recursive regular expressions were not strictly speaking regular expressions.

这是为什么?

推荐答案

严格"正则表达式描述了正则语言.但是许多特性，例如在表达式本身中使用反向引用或递归，都可以用来编写接受非正则语言的正则表达式.

"Strictly" regular expressions describe regular languages. But many features, such as the usage of backreferences in the expression itself or recursion for example, can be used to write regular expressions that accept non-regular languages.

例如描述的语言

(a+)b+\1

不是常规的，因为您不能强制 a 在 b 之前和之后出现相同的次数.至少不是常规语言.对于上下文无关甚至上下文敏感的语言，情况就完全不同了.

isn't regular, as you can't force that a appears the same number of times before and after the bs. At least not in a regular language. With context-free or even context-sensitive languages, that's a completely different matter.

但是，仅使用基本事物(例如各种量词、字符类等)的正则表达式通常仍然描述正则语言.

However, regular expressions that only use elementary things such as the various quantifiers, character classes, etc. usually still describe regular languages.

这篇关于为什么递归正则表达式不是正则表达式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！