3 Способы описания языка
Для описания синтаксиса языка наибольшее распространение получили:
Форма Бэкуса-Наура и его различные модификации
Синтаксические диаграммы Вирта
Формальные грамматики
Форма Бэкуса-Наура (БНФ)
В БНФ каждое определяемое понятие – это металингвистическая переменная.
Значением металингвистической переменной может быть любая конструкция из некоторого фиксированного для этого понятия набора конструкций.
Каждая металингвистическая форма определяется одну металингвистическую переменную и состоит из двух частей: слева – сама переменная, справа – все варианты определения конструкции, задаваемой этой формой. Варианты разделяются металингвистической связкой ‘|’ (или). Левая и правая части соединяются метасимволом :=, означающим «по определению есть».
Например, следующие металингвистические формы определяют множество целых чисел (символ ‘::=’ читается как «по определению есть»):
<целое число>::=<целое без знака> | +<целое без знака> | -<целое без знака>
<целое без знака>::=<цифра>|<целое без знака><цифра>
<цифра>::=0|1|2|3|4|5|6|7|8|9
Характерной особенностью многих металингвистических форм является наличие в них рекурсии.
4 Формальные языки и грамматики. Основные термины и определения
Алфавит – конечное непустое множество символов.
Термин символ следует понимать здесь в самом широком смысле слова. Символом можно считать любой знак или совокупность знаков, рассматриваемую как нечто неделимое (буква, цифра, знак препинания, служебное слово, иероглиф и т.д.).
Будем обозначать алфавит
символом
(sigma). Т.к. алфавит – это
множество, поэтому при перечислении
его элементов используются фигурные
скобки.
Примеры алфавитов:
Под
подразумевается алфавит языка Паскаль.
Цепочка над алфавитом - произвольная конечная последовательность символов из .
Примеры цепочек над
алфавитом
:
Цепочки будем обозначать греческими буквами.
Характеристикой
цепочки является ее длина. Длиной
цепочки называется число символов,
образующих цепочку. Длина цепочки
равна 9 и обозначается |
Пустая
цепочка – цепочка, не содержащая
символов (содержащая ноль символов).
Обозначается буквой
(epsilon).
Если
и
цепочки, то запись
означает их конкатенацию (слияние).
Если
- цепочка, то запись
означает цепочку, образованную n-кратным
повторением цепочки
:
n-раз
Будем обозначать
-
бесконечное множество всех цепочек над
алфавитом
,
включая пустую цепочку,
-
множество всех цепочек над алфавитом
,
не включая пустой цепочки.
Например,
если
,
представляет собой множество всех
цепочек, которые могут быть составлены
из символов 0 и 1, включая пустую цепочку:
Языком над алфавитом называется произвольное множество цепочек, составленных из символов .
Принадлежащие языку цепочки называют также предложениями языка.
Отметим, что множество цепочек всегда бесконечно, в то время как множество цепочек, образующих язык может быть конечным.