序言 - 轉換迭代算法遞歸（函數解析器）

Question

我正在寫一個函數語法分析器，它分析這種功能：

<fsignature>"(" <term1>, <term2> ... <termn>")" 

之前，如果一個字符串由語言接受檢查，我改造它列入清單，然後發送給DCG規則。 我寫了這個爲：

is_funct(A) :- term_to_atom(A, X), atom_chars(X, L), phrase(expr, L). 

的事情是，代碼是相當殘酷的，只是豆腐塊每一個角色進入榜單，所以如果有一個簽名或文字長於一個字符，或者如果有嵌套函數，它只是不起作用。 正確的算法分塊的還要好，我想：

List L, Z; 
String F; 

for(int i=0; i<L.length; i++){ 
    if(L[i]=="(" || L[i]==","){ 
    for(int j=i; L[j]!=")"||L[j]!=","; j++) 
     F+=L[j]; 
    Z.append(F); 
    if(Z[j-1]==")") Z.append(")"); 
    } 
} 

或者，滾動列表，直到找到一個逗號或開括號，然後scoll向後並創建每個字符的字符串你會發現，直到你找到另一個括號或逗號，並且當您找到將字符串追加到列表中，並且如果您發現括號附加它。所以，你會得到類似

[foo, "(", bar, fizz, "(", buzz, ")", hello, ")"] 

要正確然後看看它是由語言所接受。

我該如何在Prolog中遞歸地轉換此算法？ 我試圖設想一個解決方案，那將是

1) Split term at every comma (,) and put splitted strings in L 
2) Find index of every bracket for ever element of L and split on the brackets 
3) Reinsert brackets into list at the indexes saved 

但它聽起來並不做正確的方式，這無論是不是遞歸！

解析字符串的正確方法是什麼？提前致謝！

Answer 1

以下是我如何處理您的問題，基於我認爲您的要求。你的問題對於我認爲是錯誤的方法的技術細節很重要，所以我不完全確定這是正確的方向，但這是我得到的。

首先，我認爲你的語法真正看起來是這樣的：

function ::= name '(' termlist ')'. 
termlist ::= [] | nonemptytermlist. 
nonemptytermlist ::= term | term ',' nonemptytermlist. 
term  ::= name 
      | function. 
name  ::= [A-Za-z][A-Za-z0-9_-]* 

我們在這裏做什麼Prolog的，所以你的問題的最「聲明」讀你能想出是你想要的編碼。只有在這之後你纔會嘗試優化它。 BNF語法在Prolog中非常普遍，語言內置了對它們的支持：明確的從句語法。

在這個語法中存在遞歸，但是這在語法中並不是一個大問題，只要它處於正確的位置，即通常不是的第一個或最左邊的位置。這是EBNF-ish，它應該很容易轉換爲DCG符號。

function --> fname, "(", termlist, ")". 
termlist --> [] | nonemptytermlist. 
nonemptytermlist --> term | term, ",", nonemptytermlist. 
term --> fname | function. 
fname --> [C], { char_type(C, alpha) }, namebody. 
namebody --> [C], { char_type(C, alnum) ; C = '_' ; C = '-' }, namebody. 
namebody --> []. 

這實際上似乎工作，但它不是巨大有用：

?- atom_codes("foo(this,bar(that),another)", X), phrase(function, X). 
X = [102, 111, 111, 40, 116, 104, 105, 115, 44|...] ; 

它可能不是很明顯這裏，但它已成功地解析這句話與function DCG規則。你只是沒有得到任何回報。所以接下來要做的就是讓你的語法規則構建你想要的結構。

function(F) --> 
    fname(Name), 
    "(", termlist(List), ")", 
    { F =.. [Name|List] }. 

termlist([]) --> []. 
termlist(List) --> nonemptytermlist(List). 

nonemptytermlist([X]) --> term(X). 
nonemptytermlist([X|Xs]) --> term(X), ",", nonemptytermlist(Xs). 

term(Term)  --> fname(Term). 
term(Function) --> function(Function). 

fname(Name) --> [C], { char_type(C, alpha) }, namebody(Cs), 
    { atom_codes(Name, [C|Cs]) }. 

namebody([C|Cs]) --> 
    [C], 
    { char_type(C, alnum) ; C = '_' ; C = '-' }, 
    namebody(Cs). 
namebody([]) --> []. 

所有我們在這裏所做的輕輕重組的事情，通過得到每個規則解析的DCG規則參數值傳回。現在你可以看到這個成功解析了複雜的結構：

?- atom_codes("foo(this,bar(qwerty,uiop),that(),little())", X), phrase(function(F), X). 
X = [102, 111, 111, 40, 116, 104, 105, 115, 44|...], 
F = foo(this, bar(qwerty, uiop), that, little) 

語法已成功地將字符串轉換爲Prolog術語。不幸的是，Prolog沒有看到太多指向foo()，所以這些括號已經被刪除。這是由於我們正在使用的「univ」運算符=..將函數名稱和參數列表轉換爲Prolog結構。可能出現的情況是，Prolog結構對於您來說不夠容易處理;在這種情況下刪除了「大學」踩function像這樣：

function([Name|List]) --> 
    fname(Name), 
    "(", termlist(List), ")". 

使用它返回：

?- atom_codes("foo(this,bar(qwerty,uiop),that(),little())", X), phrase(function(F), X). 
X = [102, 111, 111, 40, 116, 104, 105, 115, 44|...], 
F = [foo, this, [bar, qwerty, uiop], [that], [little]] ; 
false. 

你仍然不能從空的功能區分方面。你可以修復，通過使term//1更加明確：

function(Name, Args) --> 
    fname(Name), 
    "(", termlist(Args), ")". 
% ... 
term(term(Term))   --> fname(Term). 
term(function(Name, Args)) --> function(Name, Args). 

的影響是很多更詳細：

?- atom_codes("foo(this,bar(qwerty,uiop),that(),little())", X), phrase(function(F,A), X). 
X = [102, 111, 111, 40, 116, 104, 105, 115, 44|...], 
F = foo, 
A = [term(this), function(bar, [term(qwerty), term(uiop)]), function(that, []), function(little, [])] 

這可能是更容易還是困難，爲您處理。我的經驗法則是儘量保持與Prolog結構儘可能接近，但這可能會導致不適。

無論如何，我希望這有助於。