阅读Chomsky hierarchy ... ...我知道 regexp 无法解析 type-2 语法(上下文无关语法)，也无法解析 type-1 和 type-0。 正则表达式可以解析/捕获所有类型 3 语法( regular grammars )吗？
最佳答案
是的，只要它们支持交替、串联和 Kleene 星。 PCRE (Perl/Java/JavaScript/PHP/...) 类型的正则表达式就是这种情况:交替是通过 ((...)|(...)) 实现的，串联由 (...)(...) 表示，Kleene 星由 (...)* 表示。 (还有一些其他细节 - 在大多数这些语言中，您需要使用诸如 \A 和 \z 之类的内容来指示“字符串开始”和“结束” -of-string”，这在常规语法中被认为是理所当然的 - 但这就是想法。)
但并非编程上下文中称为“正则表达式”的所有内容都必须具有上述所有内容；例如，POSIX Basic Regular Expressions仅支持非常有限的交替形式，其中交替的所有“分支”都由单个字符组成(例如，而 PCRE 既有 (a|b|c) 也有特殊情况等效的[abc]，POSIX BRE只有[abc]，因此无法表达(ab|c)之类的东西。
关于正则表达式解析类型 3 语法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9261972/