RegEx Parser được viết bằng Prolog

Question

Tôi đã đập đầu vào tường trên vấn đề bài tập về nhà này trong vài giờ. Chúng ta phải phân tích một biểu thức chính quy với Prolog. Đối với hầu hết các phần, các biến vị ngữ mà tôi đã làm việc, nhưng có một vài biểu thức chính quy và các chuỗi combo khiến chúng chạy ra khỏi không gian ngăn xếp trong SWI-Prolog. Dưới đây là mẫu có hai trong số các kết hợp chuỗi Regex, một trong số đó hoạt động và một trong số đó không:

star(star(char(a))), [] 
star(star(char(a))), [a] 

Công trình đầu tiên và thứ hai chạy hết.

Đây là vị Tôi đang sử dụng:

re_match(epsilon, []). 
re_match(char(Letter), [Letter]). 
re_match(star(_), []). 
re_match(seq(Rx1, Rx2), List) :- append(List1, List2, List), re_match(Rx2, List2), re_match(Rx1, List1). 
re_match(alt(Rx1, Rx2), List) :- re_match(Rx1, List); re_match(Rx2, List). 
re_match(star(Rx), List) :- append(List1, List2, List), re_match(Rx, List1), re_match(star(Rx), List2). 

Tôi không chắc chắn những gì thay đổi tôi cần phải thực hiện để làm cho nó hoạt động đúng, nhưng tôi không chắc chắn những gì khác để làm.

Ngoài ra, thay đổi Danh sách: - nối thêm (List1, List2, List) vào [H | T] không được đánh giá là đúng cho một trong các ví dụ.

Answer 1

Tôi không có quyền truy cập vào SWI Prolog ngay bây giờ, nhưng đây là một đoán:

Hãy thử thay đổi

re_match(star(Rx), List) :- append(List1, List2, List), 
          re_match(Rx, List1), 
          re_match(star(Rx), List2). 

để

re_match(star(Rx), List) :- append([H|List1], List2, List), 
          re_match(Rx, [H|List1]), 
          re_match(star(Rx), List2). 

để buộc re_match để "ăn một cái gì đó "khi nó lặp lại trên cấu trúc ngôi sao.

Answer 2

Xem xét sử dụng ký hiệu DCG để có thể đọc tốt hơn và dễ dàng hơn lý do về tính chấm dứt:

:- op(100, xf, *). 

rexp(eps)  --> []. 
rexp([T])  --> [T]. 
rexp(_*)  --> []. 
rexp(R*)  --> rexp(R), rexp(R*). 
rexp(s(R1,R2)) --> rexp(R1), rexp(R2). 
rexp((R1|R2)) --> (rexp(R1) ; rexp(R2)). 

Ví dụ sử dụng chiều dài/2 để tạo ra ngày càng còn liệt kê để tạo ra chuỗi được kết hợp bởi các regexp:

?- length(Ls, _), phrase(rexp(s(([a]|[b]),[c]*)), Ls). 
Ls = [a] ; 
Ls = [b] ; 
Ls = [a, c] ; 
Ls = [b, c] ; 
Ls = [a, c, c] ; 
etc.