procedure divide;

var w; -

beginr ;= л; :i= 0; w := j; while w < r do w := 2*w; while w > J do

Ьфп^ := 2*; w := w/2; 5.15J

tf w < rthen

begin r :== r-w; g := q+1 end

end;

procedure gcd;

ytfyg; begin/:= x; g := y; while/ guo

begin if / < g then g := g-/;. ifg </then/:=/-g;

end ;

г:=/ end ; ... -

(5.16)

begin

л; := 7и; j; := и; call multiplyi л; := 25; у 3; call divide; X := 84; у := 36; callgct; end.

const 7и = 7, и = 85;

procedure multiply; var a,b;

beginc := л:; ft := z := 0;

while J > 0 do (5.14)

begin

if odd b then z z + a; V Й := 2*a; b := 6/2;

end ;

II 6.8. Программа грамматического разбора для ПЛ/О 858

йммам рис. 5.4. Правило 2 относится ко всем графам, которые могут проходиться без чтения какого-либо символа. Един-угвенный такой граф в синтаксисе ПЛ/0 - это тот, который Лйсывает операторы. Ограничение 2 требует, чтобы все на-дальные символы, которые могут стоять сразу после оператора, отличались от начальных символов операторов. Поскольку в дальнейшем будет полезно знать множества началь-0Х и последующих символов для всех графов, мы определим ,гй множества для всех 7 нетерминальных символов (графов) ( йнтаксиса ПЛ/0 (кроме программы ). Используя табл. 5.2, йожно убедиться в соблюдении нужного условия, т. е. в том, JTO множества начальных и последующих символов операторов не пересекаются. Тем самым разрешается применение тавил построения программы грамматического разбора В1-В7.

Таблица 5.2. Начальные и внешние символы в ПЛ/0

ищльный Нача.чьные символы Внешние символы

символ S (S) PiS)

Блок const var . j

procedure идентификатор if call begin while

Оператор идентификатор call , ; end

begin if while

Условие odd -f - ( then do

идентификатор число

Выражение -f--( . ; ) R

идентификатор число end then do

Слагаемое идентификатор число ( *.,) R -f -

end then do

Множитель идентификатор число ( . ; ) R --- f

end then do

Внимательный читатель должен был заметить, что основ-е символы ПЛ/0 не являются обычными отдельными бук-ми, как было в предыдущих примерах. Они могут быть та-и последовательностями, как, например, BEGIN или (: -). Дк и в программе 5.3, для работы с чисто внешними пред-авлениями или при лексической обработке входной последо-тельности символов используется так называемый сканер, оформлен в виде процедуры getsym, задача которой - вы-ать из входного файла очередной основной символ. Сканер Мполняет следующие действия:

Пропускает разделители (пробелы).

Распознает зарезервированные слова, такие, кас BEGIN, END и т. п.

программа

Т

5лок

3. Распознает незарезервированные слова в качестве иденти фикаторов. Текущий идентификатор присваивается гло бальной переменной, называемой id.

4. Распознает последовательности цифр в качестве чисеч Значение числа присваивается глобальной переменной пи

5. Распознает пары специальных знаков такие, как (: = ).

При чтении входной последовательности сканер getsym использует локальную процедуру getcfi, которая читает очередной символ. Кроме этой основной задачи getcti также:

1. Распознает и пропускает информацию о концах строк.

2. Переписывает входной файл в выход-ной, формируя, таким образом, распечатку программы.

Печатает в начале каждой строки ее номер или другую подобную информацию.

Оператор

условие

выражение

слагаемое

Рис. 5.5. Диаграмма зависимости для ПЛ/0.

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

Подробно эти процедуры показаны в программе 5.4, которая представляет собой полную программу грамматического разбора для ПЛ/0. В действительности она уже несколько расщирена в том смысле, что попутно собирает идентификаторы описанных констант, переменных и процедур в таблицу-При появлении идентификатора внутри оператора он ищется в этой таблице, так как нужно установить, был ли идентификатор должным образом описан. Отсутствие такого описания можно рассматривать как синтаксическую ошибку, поскольку это формальная ошибка при построении текста программы', а именно использование незаконного символа. Тот факт, что эту ошибку можно обнаружить лишь с помощью хранения информации в таблице, есть следствие присущей языку контекстной зависимости, проявляющейся в следующем правиле: все идентификаторы соответствующего контекста долЖНЫ быть описаны. На самом деле практически все языки программирования в этом смысле контекстно зависимы; тем не менее