soạn ngữ pháp ngữ pháp miễn phí trong prolog

Question

giả sử tôi có bối cảnh ngữ cảnh miễn phí sau đây.

S -> A 
A -> mAn 
A -> o 

Điều này trông như thế nào? Đây là những gì tôi đã thử nhưng nó không hoạt động. Dòng thứ hai có vẻ là vấn đề.

S(Z) :- A(Z). 
A(Z) :- append([m],X,Z2), A(X), append(Z2,[n],Z). 
A([o]). 

Answer 1

từ ngữ pháp không phải là trái đệ quy, chúng ta có thể sử dụng một DCG:

s --> a. 
a --> [m], a, [n]. 
a --> [o]. 

sau đó chúng ta có thể phân tích cú pháp hoặc tạo ra tất cả các chuỗi chấp nhận. Ví dụ, tạo:

?- length(L, _), phrase(s, L). 
L = [o] 
L = [m, o, n] 
L = [m, m, o, n, n] 
... 

để kiểm tra mã Prolog:

?- listing(s). 
s(A, B) :- 
    a(A, B). 

?- listing(a). 
a([m|A], C) :- 
    a(A, B), 
    B=[n|C]. 
a([o|A], A). 

không append/3 yêu cầu, nhờ vào sự khác biệt liệt kê

chỉnh sửa sử dụng bổ sung/3

s(Z) :- a(Z). 
a(Z) :- append([m|X],[n],Z), a(X). 
a([o]). 

SWI-Prolog đã thêm/2 (chỉ dựa trên ứng dụng cuối/3 xích đúng), mà cung cấp cho một thể đọc được thay thế hơn

a(Z) :- append([[m],X,[n]], Z), a(X). 

dù sao, chúng ta phải gọi một/1 đệ quy sau danh sách đã được xây dựng/chia

Answer 2

Trong câu trả lời này, chúng tôi sử dụng vị ngữ thường có sẵn append/3.

 
s(Xs) :- 
    a(Xs). 

a([o]). 
a([m|Xs]) :- 
    append (Xs0,[n],Xs), 
    a(Xs0). 

truy vấn mẫu:

 
?- length (Xs,_), s(Xs). 
    Xs = [o] 
; Xs = [m,o,n] 
; Xs = [m,m,o,n,n] 
; Xs = [m,m,m,o,n,n,n] 
... 

LƯU Ý: Sử dụng append/3 thay vì dcg là, nói chung, một sự lựa chọn xấu và có thể đóng góp cho cả hiệu suất thời gian chạy thấp hơn và khả năng đọc mã. Bất cứ khi nào có thể, hãy sử dụng dcg để thay thế!