regex - BNF 到正则表达式

Question

我该如何描述语言

A → AA | ( A ) | ε

使用正则表达式生成？

Answer 1

Regular expressions accept strings from regular languages. Regular languages can also be accepted by an FSM.

There's an potentially infinite number of brackets in your language that you have to match up. That means you need an infinite state, obviously impossible in any Finite State Machine. Therefore, your language isn't regular and can't be matched with a regex.

Answer 2

正则表达式不能匹配嵌套括号。

Answer 3

我不确定您如何标记该语言，但该语言不是常规语言，正如使用常规语言的泵引理可以显示的那样（因此，它不能被正则表达式记录）。一个直观的解释是，接受该语言中的单词将要求 FDA “记住”每次开始读取右括号时它刚刚读取的左括号的数量，而这对他们来说是不可能的，因为他们没有“记忆” '。另一方面，下推式自动机...

对于任何 n，该语言可以记为 {( ⁿ ) ⁿ } ^*吗？

Answer 4

你不能——正则表达式只能识别一小部分可能的语言。特别是，非正式地，任何需要无限量内存才能识别的语言都是不可识别的。

在这里，您需要无限量的内存来记住您看到了多少个左括号，以确保右括号的数量相同。

您将需要一些能够解析上下文无关语法的机制，以便能够识别一般由 BNF 描述的语言。现代解析器非常擅长这一点！

Answer 5

正如其他人所说，您不能使用单个正则表达式来执行此操作，但是您可以使用两个“\(”和“\)”对其进行标记。看到您的语言中只能有括号，但我不确定这是否非常有用。

注意：您还需要一名传球手来确保支架正确配对。所以“（（）（）”将标记但不会解析。