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

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

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

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

Формальная грамматика или просто грамматика в теории формальных языков — способ (правило) описания формального языка, то есть выделение некоторого подмножества из множества всех слов некоторого конечного алфавита.

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

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

Грамматики и распознаватели — два независимых метода, которые реально могут быть использованы для определения какого-либо языка. Однако при создании компилятора для некоторого языка программирования возникает задача, которая требует связать между собой эти методы задания языков. Разработчиков компиляторов интересуют, прежде всего, синтаксические конструкции языков программирования. Для этих конструкций доказано, что задача разбора для них разрешима. Более того, для них найдены формальные методы ее решения. Поскольку языки программирования не являются чисто формальными языками и несут в себе некоторый смысл (семантику), то задача разбора для создания реальных компиляторов понимается несколько шире, чем она формулируется для чисто формальных языков. Компилятор должен не просто установить принадлежность входной цепочки символов заданному языку, но и определить ее смысловую нагрузку. Для этого необходимо выявить те правила грамматики, на основании которых цепочка была построена.

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

Различают следующие способы описания языков (с 57):

1) порождающие, которые предполагают наличие алгоритма, последовательно порождающего все правильные предложения языка (грамматики);

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

Основные понятия (с56)

Порождающие грамматики были введены Н. Хомским в конце 1950-х годов прошлого века как средство описания формальных языков.

Алфавит - это непустое конечное множество символов.

Цепочка над алфавитом V={а1, а2, …, аn} есть конечная последовательность символов аi.

Пустая цепочка не содержит ни одного символа. Для ее обозначения будем использовать символ ε.

Множество всех цепочек над алфавитом V, включая пустую цепочку, обозначается V*.

Длина цепочки α равна числу ее элементов и обозначается |α|. Длина ε равна 0.

Цепочки α и β равны, если они одинаковой длины и совпадают с точностью до порядка символов, из которых они состоят.

Над цепочками α и β определена операция сцепления (конкатенации, произведения), которая получается дописыванием символов цепочки β за символами цепочки α.

Для любой цепочки α всегда αε = εα = α.

Обращением (или реверсом) цепочки α называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки α будем обозначать α^R.

n-ой степенью цепочки α (будем обозначать αⁿ) называется конкатенация n цепочек α. α⁰ = ε; αⁿ = αα^n-1 = α^n-1α.

Язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

Обозначим через V⁺ множество, содержащее все цепочки конечной длины в алфавите V, исключая пустую цепочку ε. Следовательно, V* = V⁺ {ε}.

Ясно, что каждый язык в алфавите V является подмножеством множества V*.

Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.

Нетерминальные символы (промежуточные) - это символы, используемые в создании (порождении) слов языка.

Формальный язык L над алфавитом V - это язык, выделенный с помощью конечного множества некоторых формальных правил. (с58-60)