Некоторые сомнения в отношении грамматик BNF и грамматик DCG Prolog

Question

Я изучаю грамматики в Prolog, и у меня есть сомнение относительно конверсий из классических грамматик BNF в форму граммов Prolog DCG.

Например, у меня есть следующий BNF грамматика:

<s> ::= a b 
<s> ::= a <s> b 

, что переписывание, порождает все строки типа:

ab 
aabb 
aaabbb 
aaaabbbb 
..... 
..... 
a^n b^n 

Глядя на книги Программирование Иван Братка для искусственного интеллекта он конвертировать эта грамматика BNF в грамматику DCG таким образом:

s --> [a],[b]. 
s --> [a],s,[b]. 

At af рвые выглядеть это мне кажется очень похожа на классическую форму грамматики BNF, но у меня есть только сомнения, связанные с , символ используется в DCG

Это не символ логического ИЛИ в Прологе, но это является только разделителем от символа в сгенерированной последовательности.

Правильно ли это?

Answer 1

Вы можете прочитать в DCGs как "а затем"/"сцепленных с":

s --> 
    [a], 
    [b]. 

и

t --> 
    [a,b]. 

тот же:

?- phrase(s,X). 
X = [a, b]. 

?- phrase(t,X). 
X = [a, b]. 

Это отличное от, в правиле пролога, которое означает логическую связь:

a. 
b. 

u :- 
a, 
b. 

?- u. 
true. 

i.и.и. истинно, если a и b являются истинными (что здесь имеет место).

Другим отличием является также то, что предикат s/0 не существует:

?- s. 
ERROR: Undefined procedure: s/0 
ERROR:  However, there are definitions for: 
ERROR:   s/2 
false. 

Причина этого заключается в том, что правила грамматики s переводится в прологе предиката, но это требует дополнительных аргументов. Предполагаемый способ оценки правила грамматики заключается в использовании фразы/2, как указано выше (фраза (startrule, List)). Если вам нравится, я могу добавить объяснения о переводе из dcg в пролог, но я не знаю, не слишком ли запутанно, если вы новичок в прологе.

Добавление: Еще лучше пример был бы определить т как:

t --> 
    [b], 
    [a]. 

Если оценка с фразой результатов в списке [Ь, а] (который, безусловно, отличается от [а, Ь ]):

?- phrase(t,X). 
X = [b, a]. 

Но если изменить порядок целей в правиле, случаи, в которых предикат является истинным не меняется (*), так что в нашем случае, задающие

v :- 
    b, 
    a. 

эквивалентен u.

(*) Поскольку пролог использует поиск по глубине для поиска решения, возможно, ему понадобится бесконечное количество кандидатов, прежде чем он найдет решение после переупорядочения. (В более технических терминах решения не меняются, но ваш поиск может не завершиться, если вы переупорядочиваете цели).