java - 根据 Java 中的语法验证字符串

Question

我正在做一个业余项目(尝试学习正则表达式并更好地进行一般解析)并尝试编写一个函数来验证字符串在特定语法下是否有效。语法如下:

statement -> delimeter token
delimeter -> / or -
token -> name ([check])* (delimeter token)?
check -> token
         @id="..."

我已经为上面的每个( token 除外)写出了正则表达式，它们写在下面。但是，当我尝试写出 token 正则表达式时，我意识到它取决于自身(递归)。我不太确定如何编写这个正则表达式，或者这是否是正确的方法，因为检查可能会非常深入。有没有更好的方法来验证字符串是否可以用语法表示？如果没有，我该如何使用正则表达式执行此操作？

String delimeter = "/|-";
String name = "((?i)\\A[a-z][_a-z\\d\\-\\.]*){1}";
String checkToken = would just be equal to token;
String checkID = "(?i)\\A\\s*@id\\s*=\\s*\".*\"\\s*\\Z";

我正在使用 String.matches 调用来查看字符串是否与正则表达式匹配，现在只是检查较小的内容，例如名称是否正确。

Answer 1

您正在寻找对 Chomsky hierarchy 的更好理解.

层次结构的简单形式有以下几种:

1. 递归可枚举被图灵机匹配
2. Context-sensitive匹配Linear-bounded non-deterministic Turing machine
3. Context-free 匹配Non-deterministic pushdown automaton
4. 正则匹配有限状态自动机

正则表达式是对可以匹配正则语言的有限状态自动机的描述。如果语言不规则，您将面临 summoning Tony the Pony 的风险当尝试将非常规语言与正则表达式匹配时(这不是一件好事)。

给定的匹配工具可以匹配其级别或更高级别的任何语言。因此，非确定性下推自动机可以匹配上下文无关语言和常规语言。但是有限状态自动机只能匹配常规语言。

通常，在编译器设计等方面，词法分析器(使用常规语言)与使用上下文无关语言的解析器生成器配对。这可以从 lex 的配对中看出。和 yacc ，或 flex 和 bison。

Lex 有一个匹配标记并将它们传递给 yacc 的语法。在现代 Java 世界中，您可能希望查看 antlr。 - 另一个语言识别工具，可帮助您编写解析器。 JavaCC还推荐了(另一种有些人更喜欢的工具，如果你打算走这条路，你应该研究这两个)。 Lex & Yacc、Antlr 和 JavaCC 是称为 parser generators 的工具域的一部分。如果您想比较它们。

我建议给 Lex & Yacc Tutorial一读。虽然，是的，它是针对您未使用的 lex 和 yacc 的，但有一节介绍其背后的理论(词法分析和解析)。理解该理论将帮助您理解为什么您当前的方法不起作用。