Применение полуконтекстной нотации для передачи дополнительных аргументов

Это дополнительный вопрос из более раннего вопроса из ответа Мата

Начиная с этого

e([number(0)]           , t1        , Uc0    , Uc0, Bc0    , Bc0) --> [].
e([number(1)]           , t2        , Uc0    , Uc0, Bc0    , Bc0) --> [].
e([number(2)]           , t3        , Uc0    , Uc0, Bc0    , Bc0) --> [].

e([op(neg),[Arg]]       , u1(E)     , [_|Uc0], Uc1, Bc0    , Bc1) --> 
    [_],   
    e(Arg , E , Uc0, Uc1, Bc0, Bc1).
e([op(ln),[Arg]]        , u2(E)     , [_|Uc0], Uc1, Bc0    , Bc1) --> 
    [_],   
    e(Arg , E , Uc0, Uc1, Bc0, Bc1).

e([op(add),[Left,Right]], b1(E0,E1) , Uc0    , Uc2, [_|Bc0], Bc2) --> 
    [_,_], 
    e(Left, E0, Uc0, Uc1, Bc0, Bc1), 
    e(Right, E1, Uc1, Uc2, Bc1, Bc2).
e([op(sub),[Left,Right]], b2(E0,E1) , Uc0    , Uc2, [_|Bc0], Bc2) --> 
    [_,_], 
    e(Left, E0, Uc0, Uc1, Bc0, Bc1), 
    e(Right, E1, Uc1, Uc2, Bc1, Bc2).

e(U,B,EL,Es) :-
    length(UL, U),
    length(BL, B),
    phrase(e(EL,Es,UL,[],BL,[]), _).

e(N,EL,Es) :-
    length([_|Ls], N),
    phrase(e(EL,Es,_,[],_,[]),Ls).

e_count(E, Count) :-
    length([_|Ls], E),
    findall(., phrase(e(_,_,_,[],_,[]), Ls), Sols),
    length(Sols, Count).

затем чтение

Для одной переменной используйте список с одним элементом, который содержит только эту переменную. Если вы хотите передать больше, чем одну переменную, используйте список, который содержит один член формы f(...), захватывая все переменные, которые вы хотите передать. Это также стоит своего вопроса.

превратился в это

e( f([number(0)], t1, Uc0, Uc0, Bc0, Bc0) ) --> [].
e( f([number(1)], t2, Uc0, Uc0, Bc0, Bc0) ) --> [].
e( f([number(2)], t3, Uc0, Uc0, Bc0, Bc0) ) --> [].

e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, Bc0, Bc1) ) --> 
    [_], 
    e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).
e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, Bc0, Bc1) ) --> 
    [_], 
    e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).

e( f([op(add), [Left,Right]], b1(E0,E1) ,Uc0, Uc2, [_|Bc0], Bc2) ) --> 
    [_,_], 
    e(f(Left, E0, Uc0, Uc1, Bc0, Bc1) ), 
    e(f(Right, E1, Uc1, Uc2, Bc1, Bc2) ).
e( f([op(sub), [Left,Right]], b2(E0,E1) ,Uc0, Uc2, [_|Bc0], Bc2) ) --> 
    [_,_],
    e(f(Left, E0, Uc0, Uc1, Bc0, Bc1) ),
    e(f(Right, E1, Uc1, Uc2, Bc1, Bc2) ).

e(U,B,EL,Es) :-
    length(UL, U),
    length(BL, B),
    phrase(e(f(EL,Es,UL,[],BL,[])), _).

e_N(N,EL,Es) :-
    length([_|Ls], N),
    phrase(e(f(EL,Es,_,[],_,[])),Ls).

e_count(E, Count) :-
    length([_|Ls], E),
    findall(., phrase(e(f(_,_,_,[],_,[])), Ls), Sols),
    length(Sols, Count).

который работает, но это отмечено use a list that contains a single term of the form f(...), и здесь f(...) нет в списке

Я где-то ошибся?

дополнение

Рекомендации

Соглашение об именах переменных с неявной передачей состояния

Обычно при использовании /questions/tagged/implict-state-passing переменные называются

S0 → S1 →... → S

Однако для моих примеров унитарного бинарного дерева я называю их как

S0 → S1 →... → Sn

заканчивая Sn вместо S,

например

стандарт

e(S0,S) :-

Вот

 e(S0,S2) :-

причина в том, что этот пример имеет довольно редкое свойство каждого предиката DCG, имеющего увеличивающуюся длину,

например

e([number(0)]           , t1        , Uc0    , Uc0, Bc0    , Bc0) -->  
e([op(neg),[Arg]]       , u1(E)     , [_|Uc0], Uc1, Bc0    , Bc1) -->   
e([op(add),[Left,Right]], b1(E0,E1) , Uc0    , Uc2, [_|Bc0], Bc2) -->

так заканчивается xn дает мне еще одну проверку на точность.

Ссылка: ISO / IEC DTR 13211–3: 2006 Правила грамматики в определенном разделе

6.1.3 Соглашение об именах переменных для терминальных последовательностей

Этот TR использует переменные с именами S0, S1, ..., S для представления терминальных последовательностей, используемых в качестве аргументов при обработке грамматических правил или при расширении грамматических правил в предложения. В этих обозначениях переменные S0, S1, ..., S могут рассматриваться как последовательность состояний, где S0 представляет начальное состояние, а переменная S представляет конечное состояние. Таким образом, если переменная Si представляет терминальную последовательность в данном состоянии, переменная Si+1 будет представлять оставшуюся терминальную последовательность после анализа Si с помощью правила грамматики.

Источник

1 ответ

Решение

DCG всегда описывает список.

Но какой список? Вы должны решить, как выделить механизм!

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

Это совершенно нормально и очень естественное использование DCG.

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

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

Например, давайте возьмем только этот фрагмент:

e (f ([op (neg), [Arg]], u1 (E), [_ | Uc0], Uc1, Bc0, Bc1)) -> 
    [_], 
    e( f(Arg, E, Uc0, Uc1, Bc0, Bc1)).
e( f([op(ln), [Arg]], u2(E), [_|Uc0], Uc1, Bc0, Bc1)) -> [_], e (f (Arg, E, Uc0, Uc1, Bc0, Bc1)).

Давайте избавимся от синтаксиса DCG и напишем его, например, так:

e (f ([op (neg), [Arg]], u1 (E), [_ | Uc0], Uc1, Bc0, Bc1, [_ | Rest0], Rest)): - 
    e (f (Arg, E, Uc0, Uc1, Bc0, Bc1, Rest0, Rest)).
e (f ([op (ln), [Arg]], u2 (E), [_ | Uc0], Uc1, Bc0, Bc1, [_ | Rest0], Rest)): - 
    e (f (Arg, E, Uc0, Uc1, Bc0, Bc1, Rest0, Rest)).

(Обратите внимание, что вы не должны полагаться на какой-либо конкретный метод расширения, но всегда используйте phrase/2 интерфейс для вызова DCG. Тем не менее, вышеизложенное является одним из способов выполнить такое расширение, получив обычный код Пролога.)

Переключение аргументов

Предположим, мы хотим снова использовать нотацию DCG, потому что это очень удобно. Например, нам, очевидно, нужно думать о меньшем количестве переменных при использовании нотации DCG, и это само по себе уже может быть огромным преимуществом.

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

Но мы также можем сделать что-то еще!

Например, в приведенном выше фрагменте мы отмечаем, что Bc0 а также Bc1 только через: ни один из пунктов действительно не заботится об этих аргументах. Итак, предположим, что мы посвящаем механизм DCG для описания этих двух аргументов.

Это может выглядеть, например, следующим образом:

e (f ([op (neg), [Arg]], u1 (E), [_ | Uc0], Uc1, [_ | Rest0], Rest)) ->
    e( f(Arg, E, Uc0, Uc1, Rest0, Rest)).
e( f([op(ln), [Arg]], u2(E), [_|Uc0], Uc1, [_|Rest0], Rest)) ->
    e (f (Arg, E, Uc0, Uc1, Rest0, Rest)).

Здесь я начал с обычной версии Prolog, ввел нотацию DCG и просто включил Bc0 а также Bc1 в неявные аргументы! Они больше не появляются здесь. Только если мы снова развернем это обратно в Пролог, они станут видимыми, или, по крайней мере, это один из способов сделать это.

Но есть две проблемы, которые остаются:

Во-первых, что если мы действительнохотим получить доступ к этим аргументам? Конечно, не все пункты только пронизывают их так. Нам также нужно где-то получить к ним доступ. И во-вторых, есть еще более фундаментальная проблема: мы хотим поговорить об одном аргументе, который может быть любым термином, но DCG всегда описывают список!

Итак, как нам все это согласовать?

Самое главное, нам нужно поговорить о списках, поэтому решение простое: давайте поговорим о списке с одним элементом, то есть списком [Bc0] а также [Bc1], Это делает запись DCG применимой вообще в этом случае.

Далее, как мы выражаем связь между Bc0 а также Bc1 в DCG? Для этого мы используем полуконтекстную нотацию: она позволяет говорить об элементах, которых ранее не было в списке, который мы описываем.

Как отмечено в учебнике по DCG, нетерминал в следующей форме будет полезен:

состояние (S0, S), [S] -> [S0].

Вы можете прочитать нетерминал state(S0, S) как: текущее состояние S0и впредь это S,

Таким образом, если вы хотите получить доступ Bc0 и связать это с Bc1 в одном из ваших пунктов вы можете сделать это так:

e (f ([op (neg), [Arg]], u1 (E), [_ | Uc0], Uc1, [_ | Rest0], Rest)) ->
    состояние (Bc0, Bc1),... (что-то с участием Bc0 и Bc1) ...
    e( f(Arg, E, Uc0, Uc1, Rest0, Rest)).

Основное преимущество заключается в следующем: эта нотация позволяет вам скрывать дополнительные аргументы, и, тем не менее, позволяет явно обращаться к ним, если вам это нужно, используя state//2 (или полуконтекстная запись напрямую).

Это, очевидно, становится все более привлекательным, чем меньше аргументы фактически используются в вашем коде. Если почти все ваши предложения имеют доступ к аргументам, нет смысла их скрывать. Тем не менее, довольно часто вы будете описывать термины, которые пронизаны, в то время как только очень немногие из ваших предложений DCG действительно получают к ним доступ. В таких случаях рассмотрите возможность использования нотации DCG для их неявной передачи.

Но есть еще одна проблема: что делать, если мы хотим обойти не только один термин, но два или более? Для этого есть очень простое решение: давайте все же рассмотрим список с одним элементом, но пусть этот элемент будет просто составным термином формы f(Arg1,Arg2,...,Arg_n), Таким образом, ваш вызов вашего нетерминала e//N может выглядеть так:

? - фраза (e(Arg1,Arg2,...,Arg_N), [f(B1,B2,...,B_M)], [Результат]).

Вот, B1, B2 и т.д. - это аргументы, которые вы хотели бы передать неявно, в форме списка с одним элементом, который объединяет все эти аргументы.

Предполагая, что это отвечает на ваш вопрос, подходящим заголовком может быть: "Применение полуконтекстной нотации для передачи дополнительных аргументов". Фактический вопрос проясняет, и я думаю, что в этом случае крайне важно, что вы хотите применить полуконтекстную нотацию для передачи дополнительных аргументов, даже если вы уже выделили нотацию DCG для описания чего-то еще. Подводя итог, можно сказать, что решение этой проблемы - сначала освободить нотацию DCG, чтобы вы могли использовать описанный список для передачи дополнительных аргументов.

Обратите внимание, что есть и другие решения: например, вы можете разработать свою собственную пользовательскую нотацию, полностью аналогичную нотации DCG, но расширенную таким образом, что она позволяет описывать два независимых списка одновременно. Я оставляю это как упражнение.

Источник
Другие вопросы по тегам