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

Question

我正在做一个副项目（尝试学习正则表达式并在一般解析方面做得更好）并尝试编写一个函数来验证字符串在特定语法下是否有效。语法如下：

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

我已经为上面的每一个（除了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

trying to write a function that will validate if a string is valid under a particular grammar

呃，parser 是执行此操作的函数。如果它解析，它是有效的。如果出现语法错误，则不会。这是验证 字符串， 而不是根据您的标题验证语法本身。

I've written out regular expressions for each of the above (except token), they are written below. However, when I tried to write out the token regex, I realized that it depends on itself (recursive). I'm not too sure how to write this regex or if this is even the correct way to go about it anymore, since check can go very deep potentially. Is there a better way to validate if the string can be represented by the grammar or no? If not, how do I do this with regex?

你不知道。

您不能使用正则表达式解析递归语法。正则表达式用于表征 词法分析器。 语法将是 context-free 语法，LL(1) 或 LR( 1).如果您不知道这些术语的含义，您需要大量阅读。

Answer 2

您正在寻求更好地了解 Chomsky hierarchy。

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

递归可枚举与图灵机匹配
上下文敏感与线性有界非确定性图灵机匹配
无上下文与非确定性下推自动机匹配
正则与有限状态自动机匹配

正则表达式是对可以匹配正则语言的有限状态自动机的描述。如果语言不规则，则在尝试将非规则语言与正则表达式匹配时会冒 summoning Tony the Pony 的风险（这不是一件好事）。

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

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

Lex 具有匹配标记并将它们传递给 yacc 的语法。在现代 Java 世界中，如果您想比较它们，您可能希望查看 antlr - Another Tool for Language Recognition to help you with writing the parser. JavaCC also comes recommended (another tool that some like better, you should look into both of these if you intend to go down this path). Lex & Yacc, Antlr, and JavaCC are part of a domain of tools known as parser generators。

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

Answer 3

具有递归定义的语法通常不是正则的，因此不能用正则表达式来解析。

然而，在您的情况下，您似乎可以将语法转换为常规形式：

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

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

Validating a string against a grammar in Java

java

regex

validation

parsing