在Prolog中将上下文无关语法转换为下推自动机

Question

我需要从DCG格式的上下文无关语法中获得非确定性下推自动机的delta函数，实现此目的的算法非常简单：

对于语法中的每个规则A-->B，将一个转换[q1, lambda, A] --> [B]添加到delta函数中。

对于语法中的每个规则E-->c，将一个转换[q1, c, c] --> [lambda]添加到delta函数中。

将转换[q0, lambda, z0] --> [q1, S*z0] 和 [q1, lambda, z0] --> [q2, z0]添加到delta函数中。

每个大写字母表示一个非终止符号，每个小写字母表示一个终止符号。lambda表示空字符串，S是语法的初始符号，*是连接运算符，z0是堆栈顶部的符号。

这意味着该语法为：

S --> A*b | B | y
A --> w*x | x
B --> A*b

生成具有 delta 函数的下推自动机。

[q0, lambda, z0] --> [q1, S*z0]
[q1, lambda, S] --> [q1, A*b]
[q1, lambda, S] --> [q1, B]
[q1, lambda, S] --> [q1, y]
[q1, lambda, A] --> [q1, w*x]
[q1, lambda, A] --> [q1, x]
[q1, lambda, B] --> [q1, A*b]
[q1, b, b] --> [q1, lambda]
[q1, w, w] --> [q1, lambda]
[q1, x, x] --> [q1, lambda]
[q1, y, y] --> [q1, lambda]
[q1, lambda, z0] --> [q2, z0]

我需要在Prolog中实现这个算法（从用户获取语法并返回delta函数），但我感到困惑，因为这是我第一次使用逻辑编程语言。

我想我可以将语法翻译成谓词形式，然后“迭代”所有谓词，并将已经“遍历”的谓词添加到列表中，以便我可以处理此列表并返回delta函数。但我认为这是某种非常复杂的命令式做事方式，使用Prolog进行此操作将毫无意义。

也许有更优雅的解决方案，所以我想知道是否存在这样的解决方案。

- user1002327

---

我认为你应该标记为作业，并展示一些解决问题的努力。 - CapelliC

已经标记为作业了，很抱歉。我已经尝试从文件中读取语法并添加文本，但我意识到这是另一种命令式解决方案，因为我需要一个条件来确定符号是终端还是非终端的。 - user1002327

Answer 1

这里是一段可能的编码。

g2nfa(Grammar, Delta) :-
    maplist(transitions, Grammar, DeltaT),
    append(DeltaT, DeltaF),
    Initial = (q0, lambda, z0 --> q1, 'S'*z0),
    Final = (q1, lambda, z0 --> q2, z0),
    append([[Initial], DeltaF, [Final]], Delta).

transitions(Sym --> Alternatives, Transitions) :-
    phrase(transition(Sym, Alternatives), Transitions).

transition(Sym, A|As) --> state(Sym, A), !, transition(Sym, As).
transition(Sym, A) --> state(Sym, A).
state(Sym, A) --> [(q1, lambda, Sym --> q1, A)].

test :-
    g2nfa([( 'S' --> 'A'*b | 'B' | y ),
           ( 'A' --> w*x | x ),
           ( 'B' --> 'A'*b )
          ], T), maplist(writeln, T).

这似乎符合您的要求

?- test.
q0,lambda,z0-->q1,S*z0
q1,lambda,S-->q1,A*b
q1,lambda,S-->q1,B
q1,lambda,S-->q1,y
q1,lambda,A-->q1,w*x
q1,lambda,A-->q1,x
q1,lambda,B-->q1,A*b
q1,lambda,z0-->q2,z0
true.

所以你可以研究句法细节。请注意，在您的示例中未应用第二条重写规则（对于语法中的每个规则 E --> c，向 delta 函数添加过渡 [q1，c，c] --> [lambda]。）。

- CapelliC

---

哦，你说得对，我忘记应用第二条规则了。但这正是我需要的。谢谢。 - user1002327