regex - 正则表达式解析 type-3 语法

Question

阅读Chomsky 层次结构……我知道 regexp 无法解析 type-2 语法（无上下文语法），也无法解析 type-1 和 type-0。正则表达式可以解析/捕获所有类型 3 语法（正则语法）吗？

Answer 1

是的，只要它们支持交替、串联和 Kleene 星号。PCRE (Perl/Java/JavaScript/PHP/...) 类型的正则表达式就是这种情况：交替由 实现((...)|(...))，连接由实现(...)(...)，Kleene 星由实现(...)*。（还有一些其他的细节——在大多数这些语言中，你需要使用类似\Aand\z来表示“字符串开头”和“字符串结尾”，这在常规语法中被认为是理所当然的——但那是这个想法。）

但并非在编程上下文中称为“正则表达式”的所有内容都必须具有上述所有内容；例如，POSIX 基本正则表达式仅支持非常有限的交替形式，其中交替的所有“分支”都由单个字符组成（例如，虽然 PCRE 具有两者(a|b|c)和特殊情况等效项[abc]，但 POSIX BRE 仅具有[abc]，所以不能表达类似的东西(ab|c)）。