гиперправиле с помощью терминальных порождающих метаправил, пользуясь метаправилами языка. Метаправила образуют контекстно-свободную грамматику, метапонятия которой являются нетерминалами, а терминальные метаправила (не содержащие заглавных букв) - терминалами. Заметим, что в этой грамматике отсутствует понятие начального символа. / В качестве примера рассмотрим (несколько упрощенное) метаправило:

В этом метаправиле «::» заменяет «:», а «;» используется (как в гиперправиле) для разделения вариантов.

Ни один из вариантов в (2) не является терминальным метаправилом, так что нельзя вывести порождающее правило Алгола 68 из (1), пользуясь только метаправилом (2). Однако другим метаправилом может быть следующее:

и у нас также есть

где одним из вариантов для SIZETY будет пустая строка.

Исследуя все возможные варианты, находим, что метапонятие может генерировать бесконечное число терминальных метаправил в соответствии с бесконечным числом видов в языке. (Например, SIZETY может генерировать любое число LONG).

Согласованная подстановка дает, например.

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

не является порождающим правилом языка из-за того, что не соблюдается

правило согласованной подстановки.

Полный синтаксис Алгола 68 описывается с помощью двухуровневой грамматики. Двухуровневые грамматики используются также для описания семантики языков программирования [44].

Другой метод определения синтаксиса языка программирования - с помощью атрибутивной грамматики [34]. Сифоне, применил атрибутивную грамматику для описания подмножества Алгола 68 [5.1].

Рассмотрим назначение атрибутивных грамматик на примере одной из них, служащей для описания простого языка программирования. У этого языка такая же блочная структура, как у Алгола 60 или Алгола 68* и мы ассоциируем с каждым блоком список идентификаторов и их видов (или типов). Идентификаторы могут иметь один из двух видов int и bool и являются терминалами грамматики на этом уровне определения. Описания можно специфировать с помощью контекстно-свободных порождающих правил

dec-*-int id dec-booi id

Здесь мы отступили от нашей обычной практики пользоваться строчными буквами только для терминалов.

Описав идентификатор, мы хотим запомнить его вид. Этот вид будет свойством описания, и можно видоизменить грамматику, чтобы это указать:

То же самое относится к описанию идентификатора вида bool. MODE, MODEl, ID, IDl пишутся в скобках после терминала или нетерминала грамматики и представляют собой его признаки, или атрибуты. С нетерминалом dec ассоциируются два атрибута; значение точки мы вскоре объясним. В соответствии с модифицированным контекстно-свободным порождающим правилом между атрибутами устанавливаются два соотношения. Таким образом, идентификатором, ассоциируемым с описанием, будет идентификатор, появляющийся после int, а видом, ассоциируемым с описанием,- вид int.

Теперь можем определить последовательность описаний:

decs {,UST)dec (.W; MODE) UST=(ID: MODE)

decs i.LIST)decs {.U$Tt);dec {.ID, MODE) USTUSTl + (ID. MODE) ID is not contained in LIST!

Таким образом, LIST состоит из одной пары (ID, MODE) в случае одного описания (или первого описания) либо из последовательности идентификаторов и видов («+» означает конкатенацию). Ограничение

гарантирует, что ни один из идентификаторов не будет описан дважды в одном и том же блоке.

Теперь блок можно частично определить с помощью контекстно-свободного порождающего правила:

block-begm decs; siats end

Налагаем контекстно-зависимые требования:

Языковой обстановкой, в которой выполняется stats, является среда самого блока, увеличенная на decs. Эта обстановка передается отдельным оператором

и мы допускаем для упрощения, что stat принимает одну из форм:

siat {ENV)id {MODEIJDI) : id {MODE2.1D2) MODE I = search (ID J. ENV) M0DE2=search (W2. ENV) M0DEJ=M0DE2

Функция search будет искать обстановку снаружи, чтобы найти соответствующее описание идентификатора, а следовательно, и его вид. Если подходящее описание найти нельзя, выдается сообщение об ошибке.

Атрибуты применяются для описания контекстно-зависимых (или, правильнее, контекстно-несвободнтх) аспектов языка программирования. Их можно использовать для передачи информации из левой части порождающего правила в правую, как в (4). Такие атрибуты называются унаследованными. Атрибуты также можно использовать для передачи информации из правой части порождающего правила в левую, как в (3), тогда их называют синтезированными атрибутами. В приведенном выше примере в каждой паре скобок унаследованные атрибуты предшествуют синтезированным, элементы каждого списка разделяются запятыми, а два списка - точкой.

Преимущество атрибутивных грамматик заключается в том, что они выглядят как контекстно-свободные, но могут специфицировать контекстно-зависимые конструкции языка. Фактически любой язык типа 0 можно описать с помощью атрибутивной грамматики. Поскольку языки программирования представляются как контекстно-свободные, к которым добавляются контекстные ограничения, атрибутивные грамматики хорошо подходят для их описания. Существуют, кроме того, методы автоматического получения эффективных анализаторов из соответствующих атрибутивных грамматик. Этот факт, а также их удобочитаемость свидетельствуют о том, что атрибутивные грамматики близки к осуществлению двух основных назначений определения языка, упомянутых в начале данного раздела.

Среди других хорошо известных методов описания синтаксиса языков программирования следует упомянуть Vienna Definition Language для ПЛ/1 [42] и порождающие системы Ледгара [41].

2.4. ПРОБЛЕМА РАЗБОРА

Мы показали, как можно использовать грамматику для генерирования программ на заданном языке программирования. Однако компилятор должен решить не проблему генерирования программ, а проблему проверки строк символов, чтобы определить, принадлежат ли они данному языку, и если да, то распознать структуру строк в термина порождающих правил грамматики. Эта проблема известна как проблема разбора, и, прежде чем приступить к ее рассмотрению, введем новые понятия.

Исследуем грамматику с порождающими правилами