сист пр об ч 3 (Лекции по СПО), страница 4

единицы

Таблица, идентификаторов

ИМЯ

WCM

RАТЕ

SТАRТ

FIINISН

С0SТ

Атрибуты
Заполняется более поздними фазами

Таблица литералов

Литерал Основание Формат Точность Другие Адрес

31 DECIMAL FIXED 2

2 DECIMAL FIXED 1

100 DECIMAL FIXED 3

Рис. 8.14. Лексическая фаза — таблицы терминальных символов, идентифи­каторов, литералов и стандартных символов для нашего примера.

удовлетворяют лексическим правилам, описывающим идентифи­катор, классифицируются как «возможные идентификаторы». В языке ПЛ/1 идентификаторами служат строки, начинающиеся с буквы и содержащие еще до 30 буквенно-цифровых символов или подчеркиваний. Если лексическая единица не подходит ни к одной из этих категорий, выдается сообщение об ошибке.

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

Числа, строки символов, заключенные в кавычки, и другие самоопределенные данные классифицируются как «литералы». После того как лексическая единица классифицирована как ли­терал, опрашивается таблица литералов. Если литерала там еще нет, то создается новый элемент. В отличие от идентифика­торов, литералы позволяют определить их атрибуты и внутрен­нее представление при просмотре составляющих их символов: Таким образом, каждый новый элемент, создаваемый в таблице, состоит из литерала и всех его атрибутов. Не зависимо от того, создан новый элемент таблицы литералов или нет, создается стандартный символ типа LIT и помещается в таблицу стандарт­ных символов.

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

8.2.1.4. Пример

На рис. 8.15 определены символы трех типов, используемые в нашем примере (идентификатор, литерал, терминал).

<идентификатор>:: = <буква> | <буква> <буква_цифра>

<буква_цифра>:: = <буква> | <цифра>

<буква>:: = А|В| ... |Z

<цифра>::==0|1|2|3|4|5|6|7|8|9

<литерал>:: = <цифра>

<терминал>:: = <операция> | DECLARE | END| PROCEDURE | RETURN

(|) |; |: |, | STATIC | FIXED | BINARY | пробел

операция :: = + | — | * | ** | =

Рис. 8.15. Представление лексических правил в БНФ.

Они переводятся в стандартные символы (IDN,LIT,ТRМ). Стандарт­ный символ создается для каждой лексической единицы, а эле­мент таблиц идентификаторов и литералов — для каждого иден­тификатора или литерала (см., например, рис. 8.14).

8.2.2. СИНТАКСИЧЕСКАЯ ФАЗА

Функция синтаксической фазы — распознать основные кон­струкции языка и вызвать соответствующие программы интер­претации, которые будут генерировать промежуточную форму или матрицу для этих конструкций. В некоторых компиляторах эта фаза реализована в виде одной большой программы, кото­рая распознает каждую конструкцию. Мы предпочитаем дать более общую реализацию. Наша синтаксическая фаза будет интерпретатором общих правил или редукций. Эти правила определяют основные конструкции языка и соответствующие программы интерпретации, которые будут вызываться для ка­ждой конструкции.

Редукции зависят от синтаксиса исходного языка и поэтому должны быть модифицированы в случае его изменения. Формат редукций совершенно произволен, но информация, содержащая­ся в них, существенна. Позже мы увидим, что необходим ком­промисс между функциями синтаксической фазы и программами интерпретации фазы интерпретации. Из соображений эффектив­ности синтаксические фазы многих компиляторов построены не на основе интерпретации, а в виде фиксированной программы. Если требуется обеспечить более высокую эффективность ком­пилятора, можно «прокомпилировать» редукции. Мы видим, что редукций представляют собой систематический подход к реали­зации синтаксической фазы; если разработчик захочет, он смо­жет потом вручную оттранслировать редукции в единую про­грамму.

8.2.2.1. Базы данных

Таблица стандартных символов — создается фазой лексиче­ского анализа и содержит исходную программу в форме стан­дартных символов. Она используется синтаксической фазой и фазой интерпретации в качестве источника входной информации для стека. Каждый символ из таблицы стандартных символов помещается в стек только один раз. Элемент таблицы стандарт­ных символов выглядит так:

Стек — это набор стандартных символов, обрабатываемый фазами синтаксического анализа и интерпретации. Запись в стек или вычеркивание из стека производятся фазой, использующей его. Стек организован по принципу «последним вошел — первым обслуживается» (LIFO). В данной книге верхушка стека всегда изображается обращенной к низу страницы. Термин «верхушка

стека» относится к самому новому элементу, а «основание сте­ка» — к самому старому. Стек может быть встроен в таблицу стандартных символов или наоборот.

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

В дальнейшем используются следующие соглашения:

1. Метка — необязательна.

2. Старая верхушка стека — должна сравниваться с верхуш­кой стека.

а) Пробел или нуль всегда указывают на соответствие вне
зависимости от того, что находится в стеке.

б) Не пробел — один или более образцов следующих кате­-
горий:

1) (синтаксический тип), такой, как идентификатор
или литерал — соответствует любому стандартно­-
му символу этого типа.

2) (любой) — соответствует стандартному символу любого типа.

3) символьное представление ключевого слова типа
«PROCEDURE» или «IF» или «:» соответствует
только стандартному символу, представленному
этим ключевым словом.

3. Программы интерпретации —должны вызываться в том слу­-
чае, если старая верхушка стека соответствует верхушке стека.

а) Пробел или нуль — программы интерпретации не вызы­-
ваются.

б) Имя программы (программ) интерпретации — вызы-­
вается программа (программы) с данным именем (име-­
нами).

4. Новая верхушка стека — определяет изменения, которые
должны быть сделаны в верхушке стека после выполнения
программы интерпретации.

а) Пробел или нуль — изменения не вносятся.

б) Символ " — вычеркивается верхушка стека.

в) Синтаксический тип, ключевое слово или элемент стека
(S_m) — вычеркивается верхушка стека и замещается
этим элементом (элементами).

г) Символ * — следующий стандартный символ из табли­-
цы стандартных символов помещается в верхушку
стека.

5. Следующая редукция.

а) Пробел или нуль — интерпретируется следующая по по-­
рядку редукция.

б) n — интерпретируется n-я редукция.

В правилах редукций мы записываем в обоих стековых полях самый старый элемент слева, а самый новый — справа. S_mS_m-1 ... S₂ S₁ означает поле длины т, где S₁ — относится к верхушке стека, S_m2 — ко второму элементу стека и т. д. Запись S_n будет использована в поле новой верхушки стека для того, чтобы представить n-й элемент стека. Мы также поместили в поле старой верхушки стека символьное представление терми­нальных символов вместо соответствующих им стандартных символов, которые в эффективных реализациях редукций могут использоваться в качестве фактических элементов стека.

8.2.2.2. Алгоритм

Фаза синтаксического анализа работает следующим образом:

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

2. После этого программы, определенные в поле программ интерпретации, выполняются последовательно слева направо.

3. После того как управление возвращается синтаксическому анализатору, он изменяет верхушку стека в соответствии с по­лем новой верхушки стека.

4. Затем повторяется шаг 1, начиная с редукции, определен­ной в поле «Следующая редукция».

8.2.2.3. Пример

После описания фазы интерпретации будет дан подробный пример анализа нашей программы. Здесь мы ограничимся по­яснением действия следующих трех редукций. / / * * * I

2: <идентификатор>: PROCEDURE /начало_процедуры/

<любой> <любой> <любой> /ОШИБКА/ S2S1*/2. Эти редукции будут первыми тремя редукциями в примере, приведенном в следующем разделе. Если читатель попробует сам интерпретировать их, как это делает синтаксическая фаза, то он должен будет сделать следующее:

1. Поместить первые три стандартных символа из таблицы стандартных символов в стек.

2. Проверить, соответствуют ли верхние три элемента вер­хушки стека полю редукции (идентификатор) * PROCEDURE?

Если соответствует, вызвать программу интерпретации «нача-ло_процедуры», вычеркнуть метку и символ «:», поместить сле­дующие четыре стандартных символа из таблицы стандарт­ных символов в стек и перейти к редукции 4. Если про­верка оказалась неудачной, вызвать программу интерпретации ОШИБКА, удалить третий стандартный символ из стека, взять еще один символ из таблицы стандартных символов и перейти к редукции 2.

По существу, редукции устанавливают, что все программы должны начинаться с конструкций '(метка) : PROCEDURE'. По­сле распознавания оператора PROCEDURE программа интер­претации «начало-процедуры» классифицирует как метку эле­мент таблицы идентификаторов, соответствующий синтаксиче­скому типу (метка). Затем синтаксическая фаза вычеркивает метку и символ «:», берет следующие четыре лексические еди­ницы и интерпретирует редукцию 4, которая начнет граммати­ческий разбор тела процедуры. Если первый оператор не являет­ся конструкцией вида (метка): PROCEDURE, вызывается про­грамма ОШИБКА, которая печатает диагностическое сообще­ние. После того как будет вычеркнут S3, в стек помещается новая лексическая единица и снова применяется редукция 2. Эти проверки делаются до тех пор, пока не будет обнаружено соответствие или не будут исчерпаны все символы таблицы стандартных символов.

8.2.3. ФАЗА ИНТЕРПРЕТАЦИИ