1. Описание синтаксиса входного языка
Разработка нового языка программирования начинается с определения его синтаксиса. Естественный язык мало пригоден для этой цели, поэтому для точного описания синтаксиса языка программирования, в свою очередь, также нужен некоторый язык. Язык, предназначенный для описания другого языка, называется метаязыком.
Метаязык задает систему обозначений, понятий языка и образованных из них конструкций, позволяющих представить описываемый язык с помощью определенных ранее понятий языка и отношений между ними. При этом каждое понятие языка подразумевает некоторую синтаксическую единицу (конструкцию) и определяемые ею свойства программных объектов или процесса обработки данных.
Для описания синтаксиса языка наибольшее распространение получили металингвистические формулы Бэкуса-Наура, или нормальные формы Бэкуса-Наура (сокращенно БНФ) [1] и их различные модификации.
Нормальные формы Бэкуса
В БНФ каждое определяемое понятие есть металингвистическая переменная. Значением металингвистической переменной может быть любая конструкция из некоторого фиксированного для этого понятия набора конструкций.
Каждая металингвистическая формула (форма) определяет одну металингвистическую переменную и состоит из двух частей: левой и правой. В левой части записывается определяемая металингвистическая переменная, которая заключается в угловые скобки “<” и “>” (предполагается, что эти скобки являются метасимволами и не принадлежат алфавиту определяемого языка), например <двоичный код>, <метка>, <арифметическое выражение>. В правой части формулы записываются все варианты определения конструкции, определяемой этой формулой. Каждый вариант представляет собой цепочку основных символов определяемого языка и металингвистических переменных. Варианты разделяются металингвистической связкой “|”, имеющей смысл “или”. Левая и правая части формулы разделяются метасимволом “::=”, означающим “по определению есть”.
Например, следующие металингвистические формулы определяют множество целых чисел:
<целое число> ::= <целое без знака> | + <целое без знака> | – <целое без знака>
<целое без знака> ::= <двоичное целое> | <восьмеричное целое> |
<десятичное целое> |
<шестнадцатеричное целое>
<двоичное целое> ::= <двоичная цифра> |
<двоичное целое><двоичная цифра>
<двоичная цифра> ::= 0 | 1
<восьмеричное целое> ::= <восьмеричная цифра> |
<восьмеричное целое><восьмеричная цифра>
<восьмеричная цифра> ::= <двоичная цифра> | 2 | 3 | 4 | 5 | 6 | 7
<десятичное целое> ::= <десятичная цифра> |
<десятичное целое><десятичная цифра>
<десятичная цифра> ::= <восьмеричная цифра> | 8 | 9
<шестнадцатеричное целое> ::= <шестнадцатеричная цифра> |
<шестнадцатеричное целое><шестнадцатеричная цифра>
<шестнадцатеричная цифра> ::= A | B | C| D | E | F
Характерной особенностью многих металингвистических формул является наличие в них рекурсии. Рекурсия имеет место в том случае, когда для определения конструкций языков программирования используются металингвистические переменные, обозначающие саму определяемую конструкцию. Рекурсия может быть явной или неявной. Явная рекурсия используется, например, в определении конструкции “двоичный код”. Неявная рекурсия имеет место в случае, когда металингвистическая переменная, обозначающая какую-либо конструкцию, используется на некотором промежуточном шаге определения этой конструкции.
Наличие рекурсивных определений затрудняет чтение и понимание металингвистических формул, хотя и является наиболее удобным способом описания бесконечных языков с помощью конечного числа правил. На практике для описания синтаксиса языков программирования часто используют расширения БНФ, позволяющие более естественно представлять альтернативные, необязательные и повторяющиеся части металингвистических формул. Так, одно из расширений БНФ разрешает использовать следующие упрощения:
необязательные элементы синтаксической конструкции заключаются в квадратные скобки [ и ];
элементы синтаксической конструкции, повторяющиеся нуль и более раз, заключаются в фигурные скобки { и }.
С учетом указанных расширений приведенное ранее определение множества целых чисел можно записать в виде:
<целое число> ::= [ + | – ] <целое без знака>
<целое без знака> ::= <двоичное целое> | <восьмеричное целое> |
<десятичное целое> |
<шестнадцатеричное целое>
<двоичное целое> ::= <двоичная цифра> {<двоичная цифра>}
<двоичная цифра> ::= 0 | 1
<восьмеричное целое> ::= <восьмеричная цифра>
{<восьмеричная цифра>}
<восьмеричная цифра> ::= <двоичная цифра> | 2 | 3 | 4 | 5 | 6 | 7
<десятичное целое> ::= <десятичная цифра>{<десятичная цифра>}
<десятичная цифра> ::= <восьмеричная цифра> | 8 | 9
<шестнадцатеричное целое> ::= <шестнадцатеричная цифра> {<шестнадцатеричная цифра>}
<шестнадцатеричная цифра> ::= A | B | C| D | E | F
Такое описание более компактно и естественно. Однако оба описания эквивалентны. Любая синтаксическая конструкция, полученная с помощью расширенной БНФ, может быть получена с помощью БНФ без расширений и наоборот. Следует отметить, что нормальные формы Бэкуса являются более формальным средством описания языка, чем БНФ с расширениями.
БНФ не позволяют описывать контекстные зависимости в языке программирования. Например, такое ограничение языка, как “идентификатор не может быть описан в одном и том же блоке более одного раза”, нельзя описать средствами БНФ. Вместе с тем БНФ дают возможность включить в описание синтаксиса языка элементы семантики за счет того, что входящие в металингвистические формулы металингвистические переменные являются осмысленными названиями описываемых конструкций. При использовании автоматических методов анализа языков элементы семантики, заложенные в БНФ, теряют смысл, поэтому в теории и практике проектирования компиляторов для формального описания синтаксиса языков программирования используются формальные грамматики.