Pushie

Swift 中创建下推自动机。简单的方法。

Pushie 允许您快速轻松地创建下推自动机，用于快速简单地解析自己定义的语言。设计用于易于阅读和理解

使用方法

首先安装 Pod

pod 'Pushie'

创建您的自动机

要创建自动机，您需要进行以下操作：1. 创建机器中的不同状态。2. 指定状态之间的转换。3. 从初始状态创建自动机对象。

在这种情况下，我们将编写一个自动机，它接受具有 n 个 0 后跟 n 个 1 的语言，并返回相应的 n 作为结果。

创建状态

要创建一个状态，只需实例化它。请记住使用泛型来指定您的产品。

let stateOne = State<Int>()
let stateTwo = State<Int>()

如果一个状态是最终状态，请做

let stateThree = State<Int>(finite: true)

转换

现在我们想让机器确定下一步去哪里。为此，我们定义转换。我们从在具有预期堆栈的状态中调用 when() 函数开始。

现在我们可以添加更多信息到这个。主要是它应该监听什么字符，它应该执行的堆栈操作，以及它应该转到哪个状态。

例如

stateOne.when("Z").goTo(stateThree)

表示我们可以从状态 1 到状态 3 创建一个空转移（epsilon transition），如果堆栈中的最后一个项是 Z。

stateOne.when("A").on("0").goTo(stateTwo).pop()

如果堆栈中的最后一个项是 A 并读取“1”，则将创建从状态 1 到状态 2 的转换。这样做后，它将弹出堆栈中的最后一个项。

此外，Pushie 存储了您的计算结果。这意味着您可以提供要将当前结果转换的函数。它应该接受字符串和您的结果，并返回新结果。因此，在我们的示例中，我们将存储 0 的数量

stateOne.when("Z").on("0").push("A").transform() { $1 + 1 }
stateOne.when("A").on("0").push("A").transform() { $1 + 1 }

最后，我们可以完成示例中的状态

stateTwo.when("A").on("1").pop()
stateTwo.when("Z").goTo(stateThree)

所以我们在以下图片中创建了所有转换

现在开始启动它

let automaton = Pushie(start: 0, state: stateOne)
automaton.stack.push("C")

automaton.handle("0011") // Optional(2)
automaton.handle("00011") // nil

创建上下文无关文法

创建自动机相当繁琐。这就是为什么 Pushie 允许您轻松定义上下文无关文法并将其转换为自动机。现在我们将使用之前的同一个示例。

为此，您只需定义您的变量

let A = Grammar<Int>()

现在您需要创建生成式。在此情况下，我们希望 A 可以转换为空字符串或一个 0 和一个 1，中间还有一个 A

A.to("0").and(A).to("1").transform() { $1 + 1 }
A.to("")

现在从 A 开始创建一个文法

let grammar = Grammar(startVariable: A)

就像之前一样，您现在可以调用 handle 函数，传入累加器的起始值和输入

grammar.handle(0, input: "0011") // Optional(2)
grammar.handle(2, input: "0011") // Optional(4)
grammar.handle(0, input: "00011") // nil

祝您使用 Pushie 一切顺利！

用心打造