1

好的，所以，我有一个练习来构建一种 java 编译器。细节我就不多说了。基本上，我想知道是否可以使用可以识别右括号的正则表达式。例如，这将是一个合法的输入

void foo(){
   asd
}

这不会是

void foo(){
   asd
   if (){
      asd
   }

如您所见，2 个开瓶器 ({) 只有 1 个关闭器 (})，因此输入无效。有什么方法可以使用正则表达式并确定出现次数是否匹配？

4

4 回答 4

5

无法使用正则表达式检查括号是否正确，因为要检查是否需要跟踪已打开的括号数量等，但正则表达式无法做到这一点。

我建议你，特别是如果你想构建一个编译器，熟悉形式语言理论。例如，这篇维基百科文章对形式语言理论上下文中的正则表达式提供了一些见解：http ://en.wikipedia.org/wiki/Regular_expression#Formal_language_theory

于 2013-05-26T16:14:38.013 回答
1

最简单（简化？）的答案：

如果您解析语法，您通常会维护某种堆栈（直接或间接）。对于每个左括号，您将一个元素推入堆栈。看到右括号后，您可以通过检查堆栈知道它是否与最后一个左括号匹配。

另请注意，打开括号的方法有很多种，“{”只是其中一种。 因此堆栈不仅会告诉您有多少个左括号，还会告诉您在给定的解析状态下哪种类型的右括号是合法的。

于 2013-05-26T16:19:09.847 回答
1

标准正则表达式只能表达正则语言的语法，这正是确定性有限自动机所接受的语言类别。DFA只有有限个状态，而括号可以无限嵌套；可能具有无限嵌套级别的语言不是正则语言，不能仅通过正则表达式进行解析。

虽然大多数语言中的正则表达式库不是“只是”标准正则表达式并且能够解析一些非正则语言，但它们通常需要过于复杂的表达式才能做到这一点。

通常，要检查括号语言的格式良好的嵌套，您将需要上下文无关语法(CFG) 解析器。CFG 比正则表达式严格更强（即如果一个语法可以用 RE 表达，那么它可以用 CFG 表达，反之不一定）。

于 2013-05-26T16:36:46.630 回答
0

好的工具是用于 Tokens 的 Flex 和用于语法的 Bison，如果您使用 C

JFlex 和 Cup，如果你想用 Java 来做，也可以使用 Visitor paddern 以获得更好的程序结构

于 2013-05-26T16:20:51.697 回答