Простейший компилятор.

Алфавит - это любое множество символов. Понятие символа не определяется. Цепочка символов 0, 1, 2 записывается как «012» (или 012). Другие обозначения:

x^R - цепочка x с символами в обратном порядке

xⁿ - цепочка x, повторенная n раз

x* - цепочка x, повторенная 0 или более раз

x+ - цепочка x, повторенная 1 или более раз

xy - сцепление (конкатенация) цепочек x и y

|x| - длина (число символов) цепочки x

e - пустая цепочка

Цепочку из одного символа будем обозначать самим символом. Буквы x, y, z, u, v, w, t будем применять для обозначения цепочек. Множество всех цепочек из элементов множества E естественно обозначить через E*. Язык - это подмножество E*. Примеры языков: Си, русский - { 0 1 | n > = 0 }.

Язык программирования можно задать:

- перечислив все цепочки;

- написав программу-распознаватель, которая получает на вход цепочку символов и выдает ответ «да», если цепочка принадлежит языку и «нет» в противном случае;

- с помощью механизма порождения - грамматики.

Чтобы задать грамматику, требуется указать:

- множество символов алфавита (или терминальных символов) E. Будем обозначать их строчными символами алфавита и цифрами;

- множество нетерминальных символов (или метасимволов), не пересекающееся с E со специально выделенным начальным символом S. Будем обозначать их прописными буквами;

- множество правил вывода, определяющих правила подстановки для цепочек. Каждое правило состоит из двух цепочек (например, x и y), причем x должна содержать по крайней мере один нетерминал; и означает, что цепочку x в процессе вывода можно заменить на y. Вывод цепочек языка начинается с нетерминала S. Правило грамматики будем записывать в виде x: y. (Также употребляется запись x:: = y или x -> y)

Более строго, определим понятие выводимой цепочки:

- S - выводимая цепочка;

- если xyz - выводимая цепочка и в грамматике имеется правило y: t, то xtz - выводимая цепочка;

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

Примеры:

а) S: e б) S: e

S: 0S1 S: (S)

S: SS

Для сокращения записи принято использовать символ «или» - «|».

Короткая форма записи предыдущих примеров:

а) S: e | 0S1 б) S: e | (S) | SS

Более сложный пример:

в) S: aSBC | abC

CB: BC

bB: bb

cC: cc

bC: bc

n n n

Эта грамматика порождает язык a b c.

Грамматики в свою очередь образуют т.н. метаязык. Выше была описана «академическая» форма записи метаязыка. Существуют различные способы записи синтаксических правил, что в основном определяется условными обозначениям и ограничениями на структуру правил, принятыми в используемых метаязыках. Метаязыки используются для задания грамматики языков программирования со времен Алгола 60. Кратко рассмотрим основные вехи становления и развития метаязыков. Во всех случаях будем определять идентификатор.