Введение. 
Описание синтаксиса языка с помощью формальных грамматик

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

Формальные грамматики являются не только синтаксисом, но и основным инструментом для синтаксического анализатора. Самая общая схема синтаксического анализатора, построенная на основе формальных методов:

Описание синтаксиса языка дается исключительно средствами формальных грамматик.

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

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

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

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

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

Описание синтаксиса в виде формальных грамматик является ее исходным текстом.

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

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

Из всех классов формальных грамматик только КС грамматики продуктивно используются в синтаксическом анализе. Они дают дополнительный смысл понятию нетерминальный смысл.

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

Основные понятия и определения.

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

Например, алфавит.

A = {a, b, c, +,!}.

содержит 5 букв, а алфавит.

B = {00, 01, 10, 11}.

содержит 4 буквы, каждая из которых состоит из двух символов.

Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.

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

Более формально цепочка символов в алфавите V определяется следующим образом:

• 1) — цепочка в алфавите V;
• 2) если б — цепочка в алфавите V и a — символ этого алфавита, то бa или, а — цепочка в алфавите V;
• 3) в — цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Если б и в — цепочки, то цепочка бв называется конкатенацией (или сцеплением) цепочек б и в.

Например, если б = ab.

в = cd,.

то бв = abcd.

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

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

Обращение цепочки б будем обозначать б^R.

Например, если б = abcdef,.

то б^R = fedcba.

Для пустой цепочки:

= ^R.

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

Длина цепочки — это число составляющих ее символов.

Например, если б = abcdefg,.

то длина б равна 7.

Длину цепочки б будем обозначать |б|. Длина равна 0.

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

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

Например, если V={0,1}, то.

V^* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011,. }.

Обозначим через V⁺ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку .

Следовательно,.

V^* = V⁺ U {}.

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

Известно несколько различных способов описания языков. Один из них использует порождающие грамматики. Именно этот способ описания языков используется чаще всего.