如何使用纯函数式编程在ocaml中创建非上下文解析器？

Question

我试图在OCaml中使用纯函数式编程创建一个非上下文解析器。该函数将采用字符串列表，如果它遵循格式（a ^ xb ^ yc ^ zd ^ k）则返回true，这意味着该列表需要包含任何数字（大于0）的“a”，“b” ，“c”和“d”。

有人建议我尝试创建一组相互递归的函数，但我一直在努力想办法成功地做到这一点。

以下是该函数的一些示例输入和输出：

# string(["a";"b";"c";"d"]);;
- : bool = true

# string(["a";"a";"b";"c";"c";"c";"d"]);;
- : bool = true

# string(["a";"c";"d";"d"]);;
- : bool = false

任何帮助将不胜感激！

Answer 1

制作纯粹功能的关键是所有状态都必须作为函数参数传递并返回值。在您的情况下，状态是输入流;即尚未解析的列表。

一种方法是让每个解析函数返回一个布尔值，说明它是否看到了预期的内容，并返回列表的未解析的剩余部分。

这意味着你将使用类似这样的类型的解析函数：

aplus : string list -> bool * string list
bplus : string list -> bool * string list

如果你只是在寻找一个跟随b的，你可以像这样编码：

let parse strings =
    let (good, rest) = aplus strings in
    if not good then false
    else let (good, rest) = bplus rest in
    good && rest = []

这是非常麻烦的代码。如果你有一个类似“&&”的函数，它可能会更整洁，除了它将未解析的列表传递给下一个函数。当你开始编写纯粹的功能代码时，会经常出现这种情况。

还有许多其他方法可以构建解析，有些方法可能比上面更好。但关键（恕我直言）是你的解析函数需要返回输入流的其余部分以及成功/失败指示。

（注意，这里没有递归，但是当你编写单独的解析函数时会出现这种情况。）