我正在尝试通过从头开始构建抽象语法树来构建正则表达式的解析器(没有任何项目依赖项或工具，例如Java中的cup解析器等)。我不想保存正则表达式中包含的所有信息，但我想尽可能地简化它。
例如，x::=y|z 应生成与字符类 x::=[yz] 相同的 AST。然而，由于正则表达式可能(并且确实)变得非常复杂，所以我无法决定要实现哪些等价物。例如，我不知道如何保存否定选择x::=[^b]，这相当于x::=a|c|d|e|。 ..
你会做出什么抽象？其中一些抽象稍后会导致错误的 AST 吗？
最佳答案
AST 表示所解析的特定程序的语法(在 OP 的情况下为“正则表达式”)。通常AST源自实际的解析树，它记录了输入程序的具体分解。
OP 建议他想要一个代表与字符类相同的字符交替的 AST。他似乎将“等效”或“规范”形式与特定解析混淆了。
一般来说，如果分解标准化，可能会有不同的输入字符串，具有明显不同的解析树和相同的 AST。这并不总是那么容易做到。人们可能会发现简单的情况(OP 的示例就是其中之一)，其中可以为部分语言定义规范形式，并强制将等效结构强制转换为该规范形式。一般来说，并不总是保证您可以从任意等效的规范中生成规范。
或者您可能会遇到这样的情况，正如 OP 所建议的，您在尝试选择一个时感到困惑:将 [^x] 表示为 127 个 ASCII 替代项的显式集合是否更好？您应该为 [^<63characters>] 选择什么？ [^<64 个字符>]？ [^<65 个字符]？ Unicode 中的 [^x] 表示怎么样，可以说它有 2^24 个字符？
作为一个实际问题，我建议 OP 生成解析树和/或与该解析树对应的任何 AST。然后，如果有意义的话，他可以尝试将 AST 标准化为规范形式，但最好将其作为单独的步骤进行。
关于java - 如何构建正则表达式的最佳 AST？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37878198/