Потоковое состояние/контекст в DCG при разборе текста

Question

Как передать состояние (и изменить его, когда мне нужно) при разборе текста!?

https://www.metalevel.at/prolog/dcg

пример делает подсчет..

Не знаю, как я должен пройти начальное состояние. Должен ли я делать это как параметр вызова или как первый элемент в списке? Всякий раз, когда я хочу использовать состояние, должен ли я включать состояние (S) в качестве первой цели?

======

Скажем, мне нужно проанализировать строку «добавить элемент 5».

Если состояние "список", скажем, должно быть напечатано "5=>список"

если "установить", то "5=>установить"

или может быть более сложной строкой "новый список. добавить 5"... где синтаксический анализ "новый список" должен установить состояние = список, чтобы синтаксический анализ следующей части знал о контексте, а интерпретация была "добавить 5 в список " vs "добавить 5 к набору".

Нет необходимости использовать эти примеры, я просто пытаюсь понять, когда использовать полуконтекстную нотацию и как передать контекст в качестве параметра в правиле first/top.

Как вы можете видеть, я запутался, но это был единственный пример в Интернете, который я смог найти, а документы по прологу, как всегда, плотные, краткие и не очень полезные ;( без примеров.

---

Чтобы уточнить:

      sent([X,Y],Ctx) -->  make(X,Ctx), add(Y,Ctx).
make(V,Ctx) --> [make,V], {say(">make ~w |ctx: ~w", [V,Ctx])}.
add(V,_Ctx) --> [add,V], {say(">add ~w", [V])}.

В этом примере я передаю контекст на каждом уровне, даже если я не использую его в add(). Я могу удалить его для add(), но если есть подправило, я должен его сохранить.

Я понял, что при использовании State threading нужно объявлять Ctx только в верхнем правиле и всякий раз, когда он используется.

Answer 1

DCG — это подход к синтаксическому анализу, который вызвал некоторый интерес из-за его тесной и легкой интеграции с основным языком — Прологом, конечно. Настолько легкий, что в предложении DCG нет буквально ничего конкретного для синтаксического анализа, воплощенного в предложении DCG, только (довольно) эффективное сопоставление с образцом, которое стало возможным благодаря спискам различий .

Если вы используете DCG для синтаксического анализа, вы не можете распределить состояние между различными предложениями, потому что список различий используется для сопоставления токенов.

Итак, используйте традиционный способ, вручную передавая состояние в аргументах, или переключитесь на расширенный DCG — например, pack(edcg).

Answer 2

Может быть, этот пример поможет. Я пока оставлю трюк с полуконтекстом, чтобы обсудить его позже.

Мы хотим подсчитать количество вхождений и и в атоме. Любые другие символы объединяются в категорию (но также учитываются).

Таким образом, "состояние" - это текущий счет для a, b, c, dropped. Состояние должно быть реализовано с использованием карты, в данном случае SWI-Prolog dict.

Три способа сделать это:

1. С foldl/4
2. С phrase/3
3. Использование ванильного Пролога

С кодом ниже:

      ?-
count_with_foldl(abgdbabba,DictWithCounts).
DictWithCounts = counts{a:3,b:4,dropped:2}.

?- 
count_with_phrase(abgdbabba,DictWithCounts).
DictWithCounts = counts{a:3,b:4,dropped:2} ;
false.

?- 
count_with_recursion(abgdbabba,DictWithCounts).
DictWithCounts = counts{a:3,b:4,dropped:2}.

Код:

      % ===
% Morph DictIn to DictOut so that:
% Only for Keys [a,b,c]:
% If Key exists in DictIn, DictOut is DictIn with the count for Key incremented
% If Key notexists in DictIn, DictOut is DictIn with a new entry Key with count 1
% ===

inc_for_key(Key,DictIn,DictOut) :-
   memberchk(Key,[a,b,c]),
   !,
   add_it(Key,DictIn,DictOut).
   
inc_for_key(Key,DictIn,DictOut) :-
   \+memberchk(Key,[a,b,c]),
   add_it(dropped,DictIn,DictOut).

add_it(Key,DictIn,DictOut) :-
   (get_dict(Key,DictIn,Count) -> succ(Count,CountNew) ; CountNew=1),
   put_dict(Key,DictIn,CountNew,DictOut).

% ===
% Using foldl to count
% ===

count_with_foldl(Atom,DictWithCounts) :-
   atom_chars(Atom,Chars),
   foldl(inc_for_key,Chars,counts{},DictWithCounts).

% ===
% Using a DCG to count
% ===

dcg_count(Dict,Dict)      --> [].
dcg_count(DictIn,DictOut) --> [C], { inc_for_key(C,DictIn,Dict2) }, dcg_count(Dict2,DictOut).

count_with_phrase(Atom,DictWithCounts) :-
   atom_chars(Atom,Chars),
   phrase(dcg_count(counts{},DictWithCounts),Chars).

% ===
% Using standard Prolog to count
% ===

count_with_recursion(Atom,DictWithCounts) :-
   atom_chars(Atom,Chars),
   count_rec(Chars,counts{},DictWithCounts).
   
count_rec([],Dict,Dict).
count_rec([C|Cs],DictIn,DictOut) :- inc_for_key(C,DictIn,Dict2), count_rec(Cs,Dict2,DictOut).

Сplunitтесты:

      :- begin_tests(counting).

test("count using foldl/4, #1", true(DictWithCounts == counts{a:3,b:4,dropped:2})) :-
   count_with_foldl(abgdbabba,DictWithCounts).
   
test("count whith phrase/2, #1", [true(DictWithCounts == counts{a:3,b:4,dropped:2}),nondet]) :- 
   count_with_phrase(abgdbabba,DictWithCounts).

test("count whith recursion, #1", [true(DictWithCounts == counts{a:3,b:4,dropped:2})]) :- 
   count_with_recursion(abgdbabba,DictWithCounts).
   
:- end_tests(counting).

Одна переменная состояния в DCG

В приведенном выше DCG принимают «входное состояние» в позиции аргумента 1, которое они превращают в «выходное состояние», которое в конечном итоге возвращается в позиции аргумента 2.

      dcg_count(DictIn,DictOut)

Это полностью аналогично функциональному программированию, когда неизменяемые структуры передаются в функции и возвращаются функциями. Здесь структуры «связаны» с помощью предиката, что представляет собой еще один способ смотреть на вещи (способ, который иногда сталкивается с реальностью машины, которая обязательно вычисляет вперед во времени).

Обратите внимание, что выше переменные состояния зашлифованы, а не переменные.

Одной переменной состояния достаточно, если эта переменная состояния является именем «пустой ячейки» на листе более крупной структуры. Более крупная структура «растет на своих листьях», DCG заполняет пустую ячейку, но оставляет другую пустую ячейку для следующего вызова.

Например, вот DCG, в конце которого растет «открытый список». всегда является несвязанной переменной, которая должна быть заполнена по правилу:

Заменять tagпо :в атоме :

      collect(Fin) --> [],         { Fin = [] }.
collect(Fin) --> [t,a,g], !, collect(Fin2), { Fin = [':'|Fin2] }.
collect(Fin) --> [C],        collect(Fin2), { Fin = [C|Fin2] }.

collect(Atom,Collected) :-
   atom_chars(Atom,Chars),
   phrase(collect(Collected),Chars).

      ?- collect(xytagyx,Out).
Out = [x,y,:,y,x] ;
false.

Код DCG традиционно пишется более компактно (это также делает его поддающимся оптимизации tail-call, что нельзя игнорировать):

      collect([])        --> [].
collect([':'|Fin]) --> [t,a,g], !, collect(Fin).
collect([C|Fin])   --> [C],        collect(Fin).

collect(Atom,Collected) :-
   atom_chars(Atom,Chars),
   phrase(collect(Collected),Chars).

В этом случае каждый вызов DCG видит только пустую ячейку в дальнем конце открытого списка, тогда как Collectecdобозначает его начало:

      Collected ----> [|]        
               /   \       
              x    [|]     
                  /   \    
                 :   ~empty cell~ <--- Fin

Так, при встрече yправило

      collect([C|Fin]) --> [C], collect(Fin).

просто выполняет свою часть работы Finи увеличивает список на 1 listcell, но оставляет его «открытым списком» для продолжения добавления:

      Collected ----> [|]        
               /   \       
              x    [|]     
                  /   \    
                 :    [|]
                     /   \
            C ----> y   ~empty cell~ <--- Fin

Правило

      collect(Fin) --> [], { Fin = [] }.

преобразует открытый список в правильный список, устанавливая пустую ячейку в []:

      Collected ----> [|]        
               /   \       
              x    [|]     
                  /   \    
                 :    [|]
                     /   \
                    y    []

Это, конечно, именно то, что происходит в примере дерева DCG Primer:

      tree_nodes(nil) --> [].
tree_nodes(node(Name, Left, Right)) -->
        tree_nodes(Left),
        [Name],
        tree_nodes(Right).

Здесь структура данных, которая растет на его листьях, — это не список, а бинарное дерево.