ТОИ 12/04/2004
Умов Сергей
Метаязыки описания языков программирования
Интерпретация конструкций языка программирования должна быть абсолютно однозначной, так как фраза на языке программирования превращается в машинный код автоматически, с помощью программы-транслятора, и любой намек на неоднозначность либо делает эту фразу непереводимой, либо приводит к ошибке. В этом отношении языки программирования значительно отличаются от естественных языков, допускающих неоднозначно интерпретируемые фразы, рассчитанные на здравый смысл и жизненный опыт человека - слушателя и исполнителя, способного додумать содержание фразы. "Додумывание" не входит в способности компьютеров, поэтому необходимы приемы описания конструкций языков программирования типа: "Оператором присваивания называется …", причем продолжение подобной фразы на естественном языке чаще всего оказывается либо слишком громоздким, либо недостаточным, либо и тем, и другим одновременно.
Для строгого и точного описания синтаксиса языка программирования, как правило, используют специальные метаязыки (языки для описания других языков). Наиболее распространенными метаязыками являются металингвистические формулы Бэкуса-Наура (язык БНФ) и синтаксические диаграммы Вирта .
Язык БНФ (называемый также языком нормальных форм) представляет компактную форму в виде некоторых формул, похожих на математические. Для каждого понятия языка существует единственная метаформула (нормальная формула). Она состоит из левой и правой частей. В левой части указывается определяемое понятие, а в правой - задается множество допустимых конструкций языка, которые объединяются в это понятие. В формуле используют специальные метасимволы в виде угловых скобок, в которых заключено определяемое понятие (в левой части формулы) или ранее определенное понятие (в ее правой части), а разделение левой и правой частей указывается метасимволом "::=", смысл которого эквивалентен словам "по определению есть".
Например, метаформулы
<переменная>::=A|B
<выражение>::=<переменная>+<переменная>|<переменная>-<переменная>
Означают, что в том (сугубо модельном) языке, на который эта метаформула распространяется, под термином <переменная> понимается любая из букв А или В, а под термином <выражение> - любая из следующих 10 записей: A; B; A+A; A+B; B+A; B+B; A-A; A-B; B-A; B-B; знак | следует читать "или".
Правая часть метаформулы может содержать правило построения допустимых последовательностей. Допускаются рекурсивные определения терминов и понятий, т.е. когда в правой части формулы участвует понятие, определяемое левой частью. Например, пусть необходимо ввести понятие <двоичный>, под которым понимается любая непустая последовательность цифр 0 и 1. Тогда простое и компактное рекурсивное определение с помощью метаформулы выглядит так:
<двоичная цифра>::=0|1
<двоичный код>::=<двоичная>|<двоичный код><двоичная>
Рекурсия здесь не мешает конструктивному построению понятия <двоичный>, так как по принятым правилам при первом обращении к рекурсивно определяемому понятию следует ограничиться нерекурсивной частью формулы, т.е. под двоичным кодом понимать двоичную цифру - 0 или 1. Но при втором обращении к метаформуле, определяющей двоичный код, мы имеем варианты понятия <двоичный>, и можем применить рекурсию, которая даст нам следующие варианты этого понятия : 0 1 00 01 10 11, т.е. все возможные одно- и двухцифровые двоичные коды. Очевидно, что при следующих применениях рекурсии мы получим любой возможный двоичный код.
Синтаксическая диаграмма является графическим представлением значения метапеременной метаязыка. Диаграмма состоит из основных символов или понятий языка.
Каждая диаграмма имеет входящую и выходящую стрелки, означающие начало и конец синтаксической конструкции и отражающие процесс ее чтения и анализа. Из каждого элемента выходит одна или несколько стрелок, указывающих на те элементы, которые могут следовать непосредственно за данным элементом.
Для сравнения с метаформулами приведем несколько примеров:
Синтаксическая диаграмма
<переменная>::=
эквивалентна метаформуле <переменная>::=A|B
Металингвистические формулы в некотором виде заложены в трансляторы; с их помощью ведется проверка конструкций, используемых программистом, на формальное соответствие какой-нибудь из конструкций, синтаксически допустимых в этом языке.