如何使用解析器组合器解析 Java 数组类型签名？

Question

为了自己的乐趣，我正在 Haskell 中构建一个小型的单文件解析器组合器库。我为这个库给自己带来的一个挑战是构建工具，以便我可以为 Java 函数签名创建一个解析器，例如将

boolean isPrime(int n)

解析为与语言无关的表示形式，例如

Function { returnType = Type { typeName = "boolean", subTypes = [] }, functionName = "isPrime", args = ... }

。然而，当涉及到解析 Java 类型时，我遇到了一个问题。像

Tuple<Integer, List<Integer>>

这样的类型可以很好地解析，因为它的语法可以在没有左递归的情况下表示：

javatype := identifier, subtypes
identifier := regex("[a-zA-Z_][a-zA-Z0-9_]*")
subtypes := ('<', javatype, (',', javatype) zero or more times, '>') | NOTHING

（为我糟糕的语法写作技巧和简化Java标识符规则道歉）

然而，数组类型引入了左递归，这是众所周知的解析器组合器难以处理的。对于数组类型，我们将

javatype

规则更改为：

javatype := (javatype, "[]") | (identifier, subtypes)

。这给了我们左递归。我们可以尝试将规则重写为

javatype := (identifier, subtypes) | (javatype, "[]")

，但这意味着对于像

int[]

这样的类型，解析器只会解析

"int"

而不是

"[]"

。

如何重写类型语法规则以避免左递归，同时允许数组类型？

Answer 1

您可以消除此规则中的左递归：

javatype := (javatype, "[]") | (identifier, subtypes)

像这样：

javatype := (identifier, subtypes) javatype2
javatype2 := "[]" javatype2 | e

（其中 e 是空字符串）