Xóa đệ quy trái trong DCG - Prolog

Question

Tôi gặp vấn đề nhỏ với đệ quy trái trong ngữ pháp này. Tôi đang cố gắng viết nó trong Prolog, nhưng tôi không biết cách loại bỏ đệ quy trái.

<expression> -> <simple_expression> 
<simple_expression> -> <simple_expression> <binary_operator> <simple_expression> 
<simple_expression> -> <function> 
<function> -> <function> <atom> 
<function> -> <atom> 
<atom> -> <number> | <variable> 

<binary_operator> -> + | - | * |/

expression(Expr) --> simple_expression(SExpr), { Expr = SExpr }. 
simple_expression(SExpr) --> simple_expression(SExpr1), binary_operator(Op), simple_expression(SExpr2), { SExpr =.. [Op, SExpr1, SExpr2] }. 
simple_expression(SExpr) --> function(Func), { SExpr = Func }. 
function(Func) --> function(Func2), atom(At), { Func = [Func2, atom(At)] }. 
function(Func) --> atom(At), { Func = At }. 

Tôi đã viết một cái gì đó tương tự, nhưng nó sẽ không hoạt động chút nào. Làm thế nào để thay đổi nó để có được chương trình này làm việc?

Answer 1

Sự cố với chương trình của bạn thực sự là đệ quy trái; nó cần được loại bỏ nếu không bạn sẽ gặp khó khăn trong một vòng lặp vô hạn

Để loại bỏ đệ quy ngay lập tức rời khỏi bạn thay thế từng cai trị của hình thức

A->A a1|A a2|....|b1|b2|....

với:

A -> b1 A'|b2 A'|.... 
A' -> ε | a1 A'| a2 A'|.... 

nên chức năng sẽ là

function -> atom, functionR. 
funtionR -> []. 

wiki page

Answer 2

Câu trả lời từ @thanosQR khá tốt, nhưng áp dụng cho ngữ cảnh chung hơn DCG và yêu cầu thay đổi trong cây phân tích cú pháp. Có hiệu quả, 'kết quả' của phân tích cú pháp đã bị loại bỏ, điều đó không tốt.

Nếu bạn quan tâm đến việc phân tích cú pháp cụm từ, tôi đã đăng here điều gì đó hữu ích.

Answer 3

Sự cố chỉ phát sinh do bạn đang sử dụng chuỗi bị lạc hậu. Về phía trước, có thể xử lý trực tiếp các quy tắc ngữ pháp đệ quy trực tiếp. Cung cấp các quy tắc ngữ pháp của biểu mẫu:

NT ==> NT' 

Không tạo thành chu kỳ. Bạn cũng có thể sử dụng tính toán phụ trợ, tức là {}/1, nếu bạn đặt chúng sau khi không phải là thiết bị đầu cuối của cơ thể và nếu không phải thiết bị đầu cuối trong đầu không có thông số độc quyền đi vào các tính toán phụ trợ. tức là điều kiện từ dưới lên.

Dưới đây là một ví dụ trái recursive ngữ pháp mà làm việc một cách hoàn hảo theo cách này trong xâu chuỗi về phía trước:

:- use_module(library(minimal/chart)). 
:- use_module(library(experiment/ref)). 

:- static 'D'/3. 

expr(C) ==> expr(A), [+], term(B), {C is A+B}. 
expr(C) ==> expr(A), [-], term(B), {C is A-B}. 
expr(A) ==> term(A). 

term(C) ==> term(A), [*], factor(B), {C is A*B}. 
term(C) ==> term(A), [/], factor(B), {C is A/B}. 
term(A) ==> factor(A). 

factor(A) ==> [A], {integer(A)}. 

Đây là một link vào mã nguồn của bộ phân tích biểu đồ. Từ liên kết này, mã nguồn của bộ chuyển tiếp cũng có thể được tìm thấy. Trong một phiên ví dụ sau được hiển thị:

?- use_module(library(minimal/hypo)). 

?- chart([1,+,2,*,3], N) => chart(expr(X), N). 
X = 7 

Trong khi phân tích cú pháp trình phân tích biểu đồ sẽ điền biểu đồ theo kiểu dưới lên. Đối với mỗi p/n không phải của thiết bị đầu cuối trong các sản phẩm trên, sẽ có các sự kiện p/n + 2. Đây là kết quả của biểu đồ cho ví dụ trên:

:- thread_local factor/3. 
factor(3, 4, 5). 
factor(2, 2, 3). 
factor(1, 0, 1). 

:- thread_local term/3. 
term(3, 4, 5). 
term(2, 2, 3). 
term(6, 2, 5). 
term(1, 0, 1). 

:- thread_local expr/3. 
expr(3, 4, 5). 
expr(2, 2, 3). 
expr(6, 2, 5). 
expr(1, 0, 1). 
expr(3, 0, 3). 
expr(7, 0, 5). 

Answer 4

Nhiều hệ thống Prolog cung cấp tabling. Với việc chấm dứt tab cũng có thể được mở rộng sang các ngữ pháp đệ quy trái trong nhiều tình huống. Dưới đây là một giải pháp mà làm cho việc sử dụng tính năng mới vẫn tuân theo SWI-Prolog:

:- use_module(library(tabling)). 
:- table expr/3. 
:- table term/3. 
:- table factor/3. 

expr(C) --> expr(A), [+], term(B), {C is A+B}. 
expr(C) --> expr(A), [-], term(B), {C is A-B}. 
expr(A) --> term(A). 

term(C) --> term(A), [*], factor(B), {C is A*B}. 
term(C) --> term(A), [/], factor(B), {C is A/B}. 
term(A) --> factor(A). 

factor(A) --> [A], {integer(A)}. 

Kể từ feature này là tương đối mới trong SWI-Prolog, nó chỉ tác phẩm cho thời điểm khi bạn bật chế độ gỡ lỗi:

?- debug. 

?- phrase(expr(X), [1,+,2,*,3], []). 
X = 7