Prolog-반복 알고리즘을 재귀로 변환 (함수 파서)

여기에 당신이 묻는 것에 근거하여 당신의 문제에 접근하는 방법이 있습니다. 귀하의 질문은 내가 잘못된 접근 방식이라고 생각하는 기술적 세부 사항에 대해 무겁기 때문에 이것이 올바른 방향인지는 확실하지 않지만 내가 얻은 것입니다.

먼저, 문법이 정말 다음과 같다고 생각합니다.

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|...] ;

여기서는 명확하지 않을 수 있지만 functionDCG 규칙 으로이 문장을 성공적으로 구문 분석했습니다 . 당신은 아무것도 다시 얻지 못하고 있습니다. 따라서 다음으로 할 일은 문법 규칙이 원하는 구조를 구축하도록하는 것입니다.

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는 그다지 중요하지 않으므로 foo()괄호가 삭제되었습니다. 이는 =..함수 이름과 인수 목록을 Prolog 구조로 변환하는 데 사용 하는 "univ"연산자 때문입니다. Prolog 구조가 처리하기에 충분히 쉽지 않은 경우 일 수 있습니다. 이 경우 function다음과 같이 "univ"단계를 제거하십시오 .

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 구조에 가깝게 유지하는 것이지만 이로 인해 불편할 수 있습니다.

어쨌든 이것이 도움이되기를 바랍니다.