在序言

Question

轉換上下文無關文法來下推自動機我需要在DCG形式的上下文無關文法非確定下推自動機的delta函數，算法做這個很簡單：

---

對於語法中的每個規則A --> B，向delta函數添加轉換[q1, lambda, A] --> [B]。

對於語法中的每個規則E --> c，向delta函數添加轉換[q1, c, c] --> [lambda]。

向delta函數添加轉換[q0, lambda, z0] --> [q1, S*z0]和[q1, lambda, z0] --> [q2, z0]。

每個大寫字母都是非終端符號，每個小寫字母都是終端符號。 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來做這件事毫無意義。

也許有這個問題更優雅的解決方案，所以我想知道這種解決方案是否存在。

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] - >λ）尚未應用於您的示例。