用Prolog編寫的RegEx解析器

現在，我已經在這個作業問題上撞牆了。我們必須用Prolog解析正則表達式。大多數情況下，我有工作的謂詞，但是有一些正則表達式和字符串組合會導致它們在SWI-Prolog中用完堆棧空間。下面是兩個正則表達式的字符串組合是沒有一個樣本，一個工程和一個：用Prolog編寫的RegEx解析器

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

的第一個作品，第二個用完棧。

下面是我使用的謂詞：

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).

我不知道我需要什麼樣的變化，使得到它的工作權利，但我不知道還能做什麼。另外，更改List： - 追加（List1，List2，List）爲[H | T]對於其中一個示例的求值不爲真。

來源

2011-01-22 mnuzzo

我可以報告說，它在GNU Prolog中工作得很好...... – aioobe 2011-01-22 08:03:52

我沒有獲得SWI Prolog的權利，但這裏有一個猜測：

嘗試改變

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).

迫使re_match「吃東西「當它在星形結構上迭代時。

來源

2011-01-22 08:05:58 aioobe

考慮使用DCG符號爲更好的可讀性和更容易地推理終止性質：

:- 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)).

使用長度/ 2逐漸變長的產生實施例列出，以生成由正則表達式匹配的字符串：

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

來源

2011-01-22 10:05:17 mat

終止參數無效。反例：短語（rexp（eps *），[a]）。「這個列表的長度是固定的，但是目標不會終止。 – false 2012-09-25 08:18:26

用Prolog編寫的RegEx解析器

回答

相關問題