do read (in) od;

if in = then read (in) else error fi;

if digit (in) then read (in) else error fi; while digit (in) do

read (in) od;

if in= " 10" then read (in);

if sign (in) then read (in) fi;

if digii (in) then read (in) else error fi ;

while digit (in) do read (in)

backspace (standin) end

error - это процедура, которая, как предполагается, принимает соответствующие меры, когда возникает ошибка.

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

3.2. ВЫХОД ИЗ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА

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

Коды, создаваемые для слов языка, не зависят от программы. Например, begin может быть заменено на 11, a for - на 22. Однако стандартные идентификаторы, такие, как read, print, pi, всегда должны иметь одинаковые коды, а идентификаторам, определяемым пользователем, код выдается лексическим анализатором в том порядке, в котором они встречаются. Например, первым идентификатором будет I1, вторым -12 и т. д. Каждый

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

Для хранения таблицы идентификаторов в памяти обычно требуется структура данных, которая допускает включение идентификаторов произвольной длины. Очевидное решение - применение списков, где каждый элемент соответствует букве идентификатора, а □ представляет нулевой указатель (рис. 3.5).

Рис. 3.5

В Алголе 68 описания вида

для таблицы идентификаторов применяются

mode list = struct (char 1, ref list next); mode idtable- [1 : p] struct (int code, ref list ident)

Большое число указателей в этой структуре ведет к излишней трате объема памяти. Другой вариант представления букв идентификатора заключается в использовании строки литер или ссылки на строку литер, например

mode idtable1 = [1 : р] struct (int code, ref[ ]char ident)

В любом случае сама таблица идентификаторов должна быть расширяемой. Для этого можно сделать таблицу списком, но лучшим решением будет, вероятно, применение гибкого массива. Однако вместо того, чтобы расширять массив поэлементно, эффективнее начать с массива, состоящего, скажем, из 50 элементов, и добавлять по 10 или 20 элементов всякий раз, когда его нужно расширить. Эффект гибкости в Алголе 68 (и, возможно, в других языках) может быть также обеспечен введением ссылки на вид строки и помещением копий

элементов в большую строку в тех ситуациях, когда таблицу необходимо расширять.

Несколько иной подход к реализации таблицы идентификаторов заключается в том, что все литеры, образующие различные идентификаторы, хранятся в едином массиве литер, а в каждой записи в таблице содержится указатель на начало строки литер, соответствующих конкретному идентификатору, и счетчик числа содержащихся в ней литер. Чтобы проверить, находится ли какой-либо определенный идентификатор в таблице, нужно осуществить только политерное сравнение с теми идентификаторами, уже находящимися в таблице, которые имеют соответствующую длину (рис. 3.6).

U N E

Рис. 3.6

Аналогичная таблица нужна и для констант. Некоторые компиляторы проверяют длину констант и вычисляют их в процессе лексического анализа. Однако допустимая длина константы зависит обычно от основной машины, и лучше просто держать константы произвольной длины в таблице во время лексического анализа, чем вводить зависимость от машины на такой ранней стадии процесса компиляции. Таблица констант потребуется на поздней стадии компиляции, а лексический анализатор должен передать синтаксическому анализатору лишь то, что константа определенного типа хранится в соответствующей таблице по указанному адресу. Значение, хранящееся по этому адресу, может не понадобиться до последней фазы генерирования кода, но его тип должен быть известен на стадии анализа. Лексический анализатор передаст синтаксическому анализатору код в виде ТХХХ (XXX обозначает запись в таблице констант, где хранится значение, а Т - его тип). «Небольшие» целочисленные константы можно передавать в таблицу констант как литералы, а не указатели. Например, С001 С009 могут представлять целые числа от 1 до 9.

В программах, написанных на Алголе 68, могут содержаться определяемые пользователем выделенные идентификаторы (или выделенные слова), такие, как

list max

которые служат для спецификации видов или обозначения операций. Лексический анализатор обращается с ними, как с идентификаторами, помещая