Грамматики DCG

Учимся описывать структуру языка декларативной грамматикой и разбирать ею списки слов.

DCG (Definite Clause Grammar, определённо-клаузальная грамматика) — встроенный в Prolog способ записывать грамматики правилами вида «целое состоит из частей», который компилятор автоматически превращает в обычные предикаты с разностными списками.

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

Зачем нужны DCG

Представьте, что вы вручную пишете разбор предложения списком фактов и рекурсией по списку. Придётся повсюду таскать «остаток ещё не разобранного ввода» и аккуратно его передавать между предикатами. Это шумно и легко ошибиться. DCG прячет эту бухгалтерию: вы пишете грамматику, а компилятор сам добавляет аргументы для «входа» и «остатка».

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

Нотация стрелки

Правило DCG записывают через стрелку «двойной дефис плюс угловая скобка». Слева — нетерминал (понятие), справа — из чего оно состоит. Терминалы (конкретные слова) пишут списком.

предложение --> группа_подлежащего, группа_сказуемого.

группа_подлежащего --> артикль, существительное.
группа_сказуемого --> глагол, группа_подлежащего.

артикль --> [the].
существительное --> [cat].
существительное --> [dog].
глагол --> [sees].

Читается это так: предложение — это группа подлежащего, за которой следует группа сказуемого. Группа подлежащего — артикль и существительное. Запятая в DCG означает «затем идёт», то есть конкатенацию по входному потоку, а вовсе не логическое «и» в обычном смысле.

Запуск через phrase/2

Чтобы применить грамматику к списку токенов, вызывают встроенный предикат phrase/2: первым аргументом — стартовый нетерминал, вторым — список слов.

?- phrase(предложение, [the, cat, sees, the, dog]).
true.

?- phrase(предложение, [cat, the, sees]).
false.

Вывод:

?- phrase(предложение, [the, cat, sees, the, dog]).
true.
?- phrase(предложение, [cat, the, sees]).
false.

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

Извлечение значений и аргументы

Нетерминалы могут нести аргументы — это превращает грамматику из распознавателя в полноценный синтаксический анализатор, строящий дерево разбора или значение.

цифра(D) --> [D], { number(D), D >= 0, D =< 9 }.

число([D|T]) --> цифра(D), число(T).
число([D])   --> цифра(D).

Фигурные скобки { ... } внутри DCG-правила — это «обычный» Prolog-код, который не потребляет токены из входа, а просто проверяет условие или вычисляет. Здесь они проверяют, что D — цифра от нуля до девяти. Так в грамматику встраивают произвольную логику.

Как работает под капотом

Магии нет: DCG — это синтаксический сахар. Компилятор переписывает каждое правило, добавляя два дополнительных аргумента — список «на входе» и список «остатка». Эта пара называется разностным списком (difference list): разобранная часть — это разность между входом и остатком.

Правило предложение --> группа_подлежащего, группа_сказуемого разворачивается примерно в такой обычный предикат:

предложение(S0, S) :-
    группа_подлежащего(S0, S1),
    группа_сказуемого(S1, S).

Здесь S0 — весь вход, S1 — то, что осталось после разбора подлежащего, S — то, что осталось после сказуемого. Остаток одного нетерминала становится входом следующего — слова «протекают» сквозь цепочку. Терминал [the] превращается в проверку, что вход начинается с the:

артикль(S0, S) :- S0 = [the | S].

А phrase(предложение, Слова) — это просто вызов предложение(Слова, []): разобрать весь вход так, чтобы остаток был пустым. Понимание этого разворота снимает всю «загадочность» DCG: вы пишете правила, компилятор продевает через них разностный список.

+---------- S0 (весь вход) ----------+
[ the , cat ][ sees , the , dog ]
  \___подлеж.__/\______сказуемое_____/
остаток после подлежащего = [sees,the,dog] = S1
остаток после сказуемого  = []            = S

Генерация той же грамматикой

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

?- phrase(предложение, S).
S = [the, cat, sees, the, cat] ;
S = [the, cat, sees, the, dog] ;
S = [the, dog, sees, the, cat] ;
S = [the, dog, sees, the, dog] ;
...

Backtracking перебирает все варианты существительных и выдаёт каждое грамматически корректное предложение. Один и тот же код — и парсер, и генератор. Это прямое следствие декларативности: правило задаёт отношение, а не процедуру в одну сторону.

Частые ошибки

• Путать запятую DCG и обычную конъюнкцию. В теле DCG-правила запятая — это последовательность по входу. Если вам нужна проверка, не потребляющая токены, оборачивайте её в фигурные скобки { ... }.
• Вызывать DCG-нетерминал как обычный предикат. предложение([the,cat]) не сработает: у развёрнутого предиката два аргумента. Используйте phrase/2 или phrase/3.
• Левая рекурсия. Правило вида выражение --> выражение, [+], число уводит стандартный разбор в бесконечный цикл, как и обычная левая рекурсия в Prolog. Переписывайте через правую рекурсию или вспомогательные нетерминалы.
• Забыть пустой остаток. Если разбирать «вручную» без phrase/2, легко забыть потребовать пустой остаток [] и принять цепочку, у которой остался «хвост».
• Терминал не списком. Терминал пишут как список [the], а не как атом the в правой части.

Итог

• DCG — декларативный способ описывать грамматики; стрелка «двойной дефис + угол» отделяет понятие от его частей.
• Запятая в теле DCG — это «затем по входу», а фигурные скобки { } вставляют обычный Prolog без потребления токенов.
• phrase(Нетерминал, Список) запускает грамматику на разбор; со свободной переменной — на генерацию.
• Под капотом DCG разворачивается в предикаты с двумя лишними аргументами — разностным списком «вход/остаток».
• Одна и та же грамматика работает в обе стороны: распознаёт и порождает.