Разбор префикса с использованием пролога

Question

Итак, у меня есть эта грамматика:

  expr(op(T,B,E)) => [term(T), binop(B), expr(E)].
  expr(T) => [term(T)].

  term(N) => [num(N)].
  term(L) => [lvalue(L)].
  term(pre(O,L)) => [incrop(O), lvalue(L)].
  term(post(L,O)) => [lvalue(L), incrop(O)].
  term(E) => ['(', expr(E), ')'].

  lvalue($(E)) => [$, expr(E)].

  incrop(++) => [++].
  incrop(--) => [--].

  binop(+) => [+].
  binop(-) => [-].

  num(0) => [0].
  num(1) => [1].
  num(2) => [2].
  num(3) => [3].
  num(4) => [4].
  num(5) => [5].
  num(6) => [6].
  num(7) => [7].
  num(8) => [8].
  num(9) => [9].

и цель состоит в том, чтобы проанализировать ввод в соответствии с правилами и отделить оставшийся суффикс. Например,

| ?- parse_prefix(expr(E), [$,1,+,2], S).

E = op($(1),+,2)
S = [] ? ;

E = $(op(1,+,2))
S = [] ? ;

E = $(1)
S = [+,2] ? ;

no

и

| ?- parse_prefix(expr(E), [9], S).

E = 9
S = [] ? ;

no


| ?- parse_prefix(expr(E), [9,+,$,1,+], S).

E = op(9,+,$(1))
S = [+] ? ;

E = 9
S = [+,$,1,+] ? ;

Я написал следующие предикаты:

%Base Case: No Token, No Suffix
parse_prefix(_,[],[]).

%Direct Matching: ex) parse_prefix(num(9),[9],S)
parse_prefix(NT,[Head|Tail],S):-
    NT =>[Head],
    write('two '),
    parse_prefix(expr(E),Tail,S).
%General Matching: ex) parse_prefix(expr(E),_,S)
parse_prefix(NT,[Head|Tail],S):-
    NT => [Head1|Tail1],
    %write(Head1),
    %write('one\n'),
    parse_prefix(Head1,[Head|Tail],S).

и у меня много путаницы с рекурсией и возвратом ..

Я буду постоянно любить любого, кто может помочь мне в этом.

Заранее спасибо.

Answer 1

Вы уже близки к решению. Целесообразно определить свой собственный оператор => / 2, чтобы представлять свои собственные правила игры и не вступать в конфликт с -> / 2. Но у меня проблемы с представлением грамматических правил. Я не вижу, чтобы вы различали терминалы и нетерминалы в телах правил грамматики.

Одним из предложений было бы проголосовать за (A1, ..., An), чтобы представить соединение в теле, вместо [A1, .., An]. А затем используйте [T] для терминалов и NT для нетерминалов. Итак, следующее правило

term(E) => ['(', expr(E), ')'].

будет тогда читать:

term(E) => ['('], expr(E), [')'].

Затем вы можете адаптировать свои правила и определить parse_prefix / 3 следующим образом. Я показываю вам терминал и соединение и нетерминальный случай:

parse_prefix([T],I,O) :- !, I=[T|O].
parse_prefix((A,B),I,O) :- !, parse_prefix(A,I,H), parse_prefix(B,H,O).
parse_prefix(NT,I,O) :- (NT => Body), parse_prefix(Body,I,O).

Вы можете добавить дополнительные случаи для пустого производства ([]) и вспомогательных условий ({}) или сделать его более гибким, чтобы иметь возможность работать со списками клемм ([T1, .., Tn]). Также возможны дополнительные управляющие конструкции, но когда вы пытаетесь сделать разрез (!), Вещи становятся немного неприятными при следовании мета-интерпретатору.

Вместо написания мета-интерпретатора parse_prefix / 3 вы также можете приготовить свой собственный термин переписывания, чтобы наконец найти метод, который сначала преобразовал бы данные правила гамма-преобразования в обычный Prolog, а затем выполнил бы их оттуда. Вы найдете простой рецепт здесь:

http://www.jekejeke.ch/idatab/doclet/blog/en/docs/int/jan/098_2011/097_dcg_expansion/package.html

Bye