Формальная грамматика

Алгоритм был ранее определен как алфавитный оператор с конечной системой правил преобразования. Для записи входных, промежуточных и выходных слов используется некоторый алфавит. Каким-то образом должны быть описаны и правила преобразования. Очевидно, для этого требуется некоторый язык. Пригоден ли для описания алгоритма обычный разговорный язык?

Любой естественный язык возникал как средство общения людей. Именно по этой причине ему присущи такие особенности как:

· изменчивость, которая состоит в непостоянстве словарного состава языка;

· неоднозначность трактовки фраз различными людьми;

· избыточность, о чем шла речь в главе «Кодирование символьной информации».

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

В любом языке - естественном или искусственном - можно выделить две составляющие: синтаксис и семантику. Синтаксис (грамматика языка) - это совокупность правил, согласно которым строятся допустимые в данном языке конструкции. Семантика -смысловая сторона языка - она соотносит единицы и конструкции языка с некоторым внешним миром, для описания которого язык используется.

Для описания формального языка необходим другой язык, с помощью которого будут создаваться языковые конструкции. Описываемый формальный язык называется языком-объектом, а язык, средствами которого производится описание - метаязыком. Метаязык должен обеспечивать как описание структурных единиц языка и правил объединения их в допустимые предложения, так и содержательную (смысловую) сторону языковых конструкций.

Любая грамматика начинается с указания алфавита, т.е. набора символов, посредством которого строятся конструкции языка.

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

Помимо синтаксиса устанавливается система правил, позволяющих конструкциям языка придать смысл - эти правила образуют семантику языка.

Формальная грамматика - система правил, описывающая множество конечных последовательностей символов формального алфавита.

Конечные цепочки символов называются предложениями формального языка,а само множество цепочек - языком,описываемым данной грамматикой.

Набор синтаксических правил формального языка аналогичен системе подстановок, используемых в нормальных алгоритмах Маркова. Вывод в данной порождающей грамматике есть последовательность цепочек, в которой любая, начиная со второй, получается из предыдущей применением какого-либо правила вывода.

Формальная грамматика задается упорядоченной четверкой {T, N, S, Р}, где Т и N - непересекающиеся конечные множества, образующие алфавит или словарь порождаемого формального языка; Т называется множеством (словарем) терминальных символов; N - множеством (словарем) нетерминальных (вспомогательных) символов. S - начальный (выделенный) вспомогательный символ из множества N. Р - набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного символа, имеющие вид g→ h, где g и h - цепочки, состоящие как из терминальных, так и нетерминальных символов.

Подстановки работают следующим образом: если в преобразуемой цепочке есть слово g, то оно заменяется словом h. Единственное ограничение на вид подстановок состоит в том, что слово g не может состоять только из терминальных символов. Это означает, что получение на некотором шаге цепочки, состоящей только из терминальных символов, свидетельствует о прекращении процесса порождения - эта цепочка является правильной, завершенной конструкцией порождаемого языка. Подстановки Р могут применяться к трансформируемой цепочке в произвольном порядке.