DC-грамматика
Материал из Википедии — свободной encyclopedia
Грамматика, построенная на определённых предложениях (сокр. DC-грамматика, DCG; от англ. Definite clause grammar) — это способ построения грамматики в логических языках программирования, например, Пролог. DC-грамматика обычно ассоциируется с Прологом, но и другие языки, например, Mercury, также могут использовать DC-грамматику. Словосочетание «определенные предложения» используется в названии потому, что эта грамматика основывается на дизъюнкте Хорна в логике первого порядка.
Определение DCG ссылается на специфичные типы выражений в Пролог и других подобных ему языках. Не все способы выражения грамматики, использующие определённые предложения, рассматриваются с помощью DC-грамматики. Однако все возможности и свойства DC-грамматики будут точно такими же для любой грамматики, которая использует определённые предложения точно так же, как и Пролог.
Чтобы яснее представить себе, что же такое DC-грамматики, можно провести следующее гипотетическое сопоставление: множество определённых предложений можно рассмотреть как множество аксиом, а корректность входной строки и существование для неё дерева разбора — как теорему, доказательство которой строится на этих аксиомах [1]. Такое представление имеет преимущество, так как распознавание и разбор выражений языка превращается в доказательство выражений, точно так же, как это делается в логических языках программирования.