Грамматика для описания языка, синтаксические диаграммы

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

1) с использованием формальных грамматик;

2) с использованием синтаксических диаграмм.

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

1) Вводится множество терминальных символов, которые заключаются в одиночных кавычках. Под терминальным символом понимается неделимый символ языка, например ‘Begin’, ‘Program’, ‘1’, ‘5’. Иногда для сокращения кавычки можно опускать, если смысл конструкции при этом остается понятным.

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

3) Вводится операция «=::» (или «→»), которая читается, как: «это есть», «является», «состоит из» и предназначено для уточнения состава нетерминальных символов.

4) Для обозначения альтернативных вариантов написания терминов в языке вводится синтаксическая конструкция «альтернатива», которая обозначается вертикальной чертой «|» и может читаться как союз «или», например, такая конструкция «<операция> → ‘*’ | ‘/’ | ‘–‘ | ‘+’» обозначает следующее: «нетерминальный символ <операция> это есть терминальный символ ‘*’, или символ ‘/’, или символ ‘–‘ или, символ ‘+’».

5) Для необязательных конструкций языка, которые в одном случае могут присутствовать, а в другом могут отсутствовать используется конструкция «квадратные скобки». Ими обрамляются необязательные символы, например такое описание «<целое число> → [+] | – <цифры>» обозначает, что «конструкция <целое число> есть <цифры>, перед которыми необязательно присутствует знак ‘+’, либо обязательно знак ‘–‘».

6) Для повторяющихся конструкций используется два вида записи: либо с помощью многоточия «…» (если очевидно какая конструкция повторяется), либо повторяющиеся конструкции берутся в фигурные скобки. Иногда такая конструкция называется «итерация» или «повторение», например «< целое число> → [+] | – {<цифра>}», либо «<целое число>→ [+] | – <цифра><цифра>…».

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

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

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

Пример 8. СД для понятия “целое число” (целое со знаком) (рис.18).

При построении СД используется 5 основных конструкций:

1) Последовательность (рис.19).

Порождает синтаксическую конструкцию (иногда говорят цепочку символов) C₁C₂C₃…C_N.

2) Альтернатива (рис.20).

3) Альтернатива с пустой цепочкой (рис.21).

4) Итерация с пустой цепочкой (рис.22).

5) Итерация без пустой цепочки (рис.23).

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