сист пр об ч 3 (1085772), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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. ФАЗА ИНТЕРПРЕТАЦИИ

Характеристики

Список файлов лекций