Генерирование команд по ПОЛИЗу

Пример 7.2.

На рис. 7.1 показан пример интерпретации строки ПОЛИЗа AB@CD*++ , полученной из инфиксного выражения A+(-B+C*D). Значения в стеке отделены друг от друга вертикальной чертой.

ž

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

Алгоритм генерации команд состоит в том, что строка ПОЛИЗа просматривается один раз слева направо и при встрече операндами (идентификаторами или константами) их имена (символические значения, адреса) заносятся в стек. При встрече с оператором из таблицы выбирается соответствующая ему кодовая продукция. В нее подставляются имена (адреса) операндов, извлеченные из стека, а так же сформированное имя (адрес) результата. Последнее имя замещает операнды данного оператора в стеке, а сформированная продукция помещается в выходной файл. Ниже все примеры даются с использованием языка ассемблера для IBM PC (процессор Intel 8x86). Если Вы еще не знакомы с этим языком, то надеемся, что комментарии к командам позволят понять их смысл.

Пример 7.3.

На рис. 7.2 показан пример генерирования команд для уже известной нам строки ПОЛИЗа AB@CD*++.

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

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

<оператор>, <операнд ₁>, < операнд ₂>, <результат> ,

где <операнд ₁> и <операнд ₂> специфицируют аргументы, а <результат> – результат выполнения оператора над аргументами. Таким образом, A*B мы могли бы представить как

*, A, B, M ,

где M – некоторая временная переменная, которой присваивается результат вычисления A*B. Аналогично A*B+C*D представляется в виде следующей последовательности тетрад:

*, A, B, M1

*, C, D, M2

+, M1, M2, M3

Важно отметить, что в отличии от обычной инфиксной записи тетрады располагаются в том порядке, в котором они должны выполняться. Унарные операторы также оформляются в виде тетрад, но <операнд ₂> остается в них пустым. Так, вместо -A появится тетрада “-, A, , M”, что означает “присвоить M значение -A”. Унарный минус, также как и в ПОЛИЗе, мы могли бы заменить другим символом (кодом), чтобы отличать его от бинарного.

Кроме традиционной арифметики в виде тетрад можно представить и любой другой оператор, имевший место в польской записи. Оператор присваивания A:=B представим в виде тетрады “ :=, B, , A ”, а оператор УПЛ запишется в виде тетрады “ УПЛ, <выр>, <m> , ”, где <m> – номер тетрады, на которую будет осуществляться переход, если значение логического выражения (<выр>) – равно нулю (ложно).

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

<оператор> <операнд ₁>, < операнд ₂>

В триаде нет поля для результата. Если позднее какой–либо операнд окажется результатом данной операции, то он будет непосредственно на нее ссылаться (на операцию, а точнее соответствующую триаду). Например, выражение A+B*C будет представлено следующим образом:

(1) * B, C

(2) + A, (1)

Здесь (1) – ссылка на результат первой триады, а не константа, равная 1. Выражение 1+B*C будет записываться так:

(1) * B, C

(2) + 1, (1)

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

Достоинства использования тетрад и триад с точки зрения машинно–независимой оптимизации по сравнению с ПОЛИЗом очевидны. Представляя их в виде таблицы (односвязного или двухсвязного списка), тетрады или триады можно легко переставлять или удалять “лишние”.

7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ

Арифметические выражения чаще всего встречались при практическом программировании, особенно на ранних стадиях использования вычислительной техники. Поэтому для них немецкими математиками К. Замельсоном и Ф. Бауэром был предложен достаточно простой метод перевода инфиксных арифметических выражений в ПОЛИЗ с одновременным контролем отдельных ошибок. Предложенный ими метод не использует грамматик в явном виде но в основе приоритетов операций о которых речь пойдет ниже лежат традиционные функции предшествования.

Метод Замельсона–Бауэра для перевода инфиксных арифметических выражений в ПОЛИЗ:

Вход. Строка, содержащая инфиксное арифметическое выражение.

Выход. Польская инверсная запись исходного выражения.

Метод. Суть метода состоит в том, что для каждого знака–разделителя (операции, скобки и т.п.) вводят два числа: сравнительный приоритет – P_C и магазинный приоритет – P_M. Исходное выражение просматривается один раз слева направо. При этом:

Идентификаторы и константы переписываются в выходную строку ПОЛИЗа.

При обнаружении разделителя его сравнительный приоритет P_C сравнивается с магазинным приоритетом P_M разделителя из вершины магазина операций. Если P_C > P_M, то разделитель входной строки помещается в магазин (разделитель из исходной строки поступает в магазин и в том случае, когда магазин пуст). Если P_C £ P_M, то символ извлекается из магазина и записывается в выходную строку ПОЛИЗа. Далее повторяется пункт (2) все для того же входного символа.

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

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

На рис. 7.3 представлена таблица приоритетов операций и скобок для упрощенных арифметических выражений, а на рис. 7.4 разобран по шагам пример перевода в ПОЛИЗ инфиксного выражения по методу Замельсона–Бауэра. (На рис. 7.4 вершина магазина операций расположена справа).

Предложенный метод можно модифицировать таким образом, что он позволит обрабатывать и операции сравнения, логические операции, операторы присваивания, управляющие конструкции типа IF–THEN–ELSE, WHILE–DO и т. п. Таблица приоритетов для этого случая представлена на рис. 7.5. То, что в ней приоритеты операций изменены, по сравнению с рис. 7.3, роли не играет. Важны отношения между значениями приоритетов, а не сами значения. Обработка скобок, к которым здесь можно отнести и операцию присваивания – ‘:=’, и знак конца оператора – ‘;’, и элементы управляющих конструкций (IF, THEN, ELSE, WHILE и т.п.) выполняется по особым алгоритмам, часть из которых была предложена в работе Л.Ф. Штернберга [17]. При дальнейших рассуждениях, для того чтобы упростить изложение, будем считать, что любая управляющая конструкция, будь то оператор IF–THEN–ELSE или WHILE–DO, не содержит BEGIN, но всегда завершается терминалом END, независимо от количества операторов в отдельной ветви или теле цикла. (Смотрите, например язык МОДУЛА–2).

Операция присваивания ‘:=’ играет роль открывающей скобки для символа ‘;’ (или управляющей конструкции, типа ELSE или END, если символ ‘;’ перед ними необязателен). По ‘;’ из магазина выталкивается все вплоть до операции присваивания и она сама извлекается из магазина и переписывается в ПОЛИЗ. При этом, если символу присваивания в магазине предшествуют “открывающие скобки” иного рода, то это является признаком ошибки. Пример перевода в ПОЛИЗ группы операторов присваивания представлен на рис. 7.6.

Как и всякая открывающая скобка, ключевое слово IF поступает в магазин. Логическое условие, следующее за IF, обрабатывается по общему алгоритму. Терминал THEN в соответствии со своим приоритетом выталкивает из магазина все вплоть до IF. (Если IF не обнаружено, или ему предшествуют другие “открывающие скобки” то это говорит об ошибке в исходном выражении.) Терминал IF также выталкивается из магазина и в ПОЛИЗ записывается операция УПЛ, где метка перехода пока не определена. Ключевое слово THEN помещается в магазин вместо IF вместе с номером позиции в строке ПОЛИЗа, соответствующей метке для УПЛ. В магазине THEN “ведет себя” как открывающая скобка для соответствующей “закрывающей скобки” (для ELSE или END).

Терминал ELSE выталкивает из магазина в ПОЛИЗ все вплоть до THEN, контролируя возможные ошибки. При извлечении из магазина THEN в строку ПОЛИЗа записывается операция БП с неопределенной меткой. На место метки оператора УПЛ, номер позиции которой был записан вместе с извлекаемым THEN, записывается значение индекса по строке ПОЛИЗа, соответствующее позиции, следующей за сформированным БП. Ключевое слово ELSE помещается в магазин вместе с номером позиции для метки операции БП и играет роль “открывающей скобки” для END данного IF – THEN – ELSE.

Терминал END - это “закрывающая скобка” для ELSE, THEN или DO в операторе WHILE - DO, о котором речь пойдет ниже. При встрече с END в исходной строке из магазина в ПОЛИЗ переписывается все вплоть до соответствующей “открывающей скобки”. Последняя также извлекается из магазина, а индекс, указанный вместе с ней, делает тривиальным процесс формирования метки в соответствующем операторе БП или УПЛ.

На рис. 7.7. представлены основные шаги перевода в ПОЛИЗ полного оператора IF - THEN - ELSE, а на рис. 7.8. - перевод в инверсную запись оператора ветвления, в котором ветвь ELSE отсутствует. (Чтобы подчеркнуть отдельные моменты перевода над строкой ПОЛИЗа в ряде случаев отмечаются номера позиций символов строки, а строчные буквы в ключевых словах используются для более компактной записи.)

На рис. 7.8. представлены отдельные шаги перевода в ПОЛИЗ простейшего оператора цикла.

Большинство шагов связанных с арифметикой и операторами присваивания здесь опущены, и внимание концентрируется на представлении самого цикла. Терминал WHILE переписывается из исходной строки в магазин с указанием очередной позиции строки ПОЛИЗа (while, 4). Начиная с этой позиции (позиции 4) будет в дальнейшем записано логическое условие для данного цикла и именно на эту позицию необходимо будет передать управление по завершении цикла. “Закрывающей скобкой” для WHILE, характеризующей завершение условия будет терминал DO. Он традиционно “вытолкнет из стека и перепишет в ПОЛИЗ” все операции предшествующие WHILE.

В строку ПОЛИЗа запишется также операция УПЛ с неопределенной меткой, а WHILE в магазине заменит DO, который вместе с позицией начала условия сохранит и позицию для последующего формирования метки перехода для УПЛ . Это DO станет “открывающей скобкой” для терминала END, завершающего цикл и приводящего, кроме обычных действий по переносу операций из магазина в ПОЛИЗ, формирование операции безусловного перехода на начало цикла - БП, метка перехода для которого уже известна и хранится вместе с DO в магазине. Кроме того, по END в сформированную ранее операцию УПЛ из начала цикла в качестве метки заносится значение индекса конца цикла (позиция в строке ПОЛИЗа, следующая за БП).

Читателям пособия предлагается в качестве упражнения подумать над алгоритмами перевода в ПОЛИЗ циклов с параметром FOR - TO - BY - DO, циклов REPEAT - UNTIL, операторов выбора CASE или переключателей SWITCH и операций индексирования переменных.

7.5. Атрибутные грамматики

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

Двухуровневые грамматики W-грамматики (с их помощью описан язык ALGOL-68),

Венский метаязык (описан PL/1),

Атрибутные.
Ниже рассмотрен один из перечисленных видов грамматик, а именно – атрибутные грамматики [12]. Атрибут- это свойство объекта; под атрибутом в грамматиках понимаются значение или семантический смысл (значимость) объекта. Атрибутная грамматика – это КС-грамматика, с узлами дерева вывода которой связаны атрибуты (семантические правила). КС-правилам сопоставляются правила вычисления атрибутов. Правило вычисления значений атрибутов, соответствующее данному КС-правилу, применяется для всех вхождений этого правила в дерево вывода.

Атрибуты могут быть двух видов - синтезированные и унаследованные.

Синтезированные атрибуты вычисляются с учетом значений атрибутов узлов потомков.

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

Формально атрибутная грамматика – это пятёрка объектов:

, где

- множество терминальных символов

- множество нетерминальных символов

- начальный выделенный символ

- это правила вывода

,где

- это множество атрибутов

=где

- множество унаследованных атрибутов

- множество синтезированных атрибутов

È=Æ

=Æ

=Æ

" Î

Унаследованные атрибуты левой части КС-правила и синтезированные атрибуты правой части получают значения, переданные от окружающих ветвлений дерева вывода. Правила вычисления значений атрибутов, связанные с каким-либо КС-правилом, определяют метод вычисления значений других атрибутов, а именно – унаследованных атрибутов правой части и синтезированных атрибутов левой части. Значения этих атрибутов передаются окружающим узлам. Или иначе можно сказать, что синтезированные атрибуты некоторого узла содержат информацию, которая синтезируется из поддерева данного узла и передаётся вверх к корню дерева вывода, а в унаследованных атрибутах хранится информация, передаваемая вниз, от корня дерева к его листьям. Унаследованные атрибуты характеризуют контекст, в котором находится его узел и его поддерево. Правила вычисления значений атрибутов записываются разными способами. Аппарат атрибутных грамматик не является законченным методом формального описания языка. Для того, чтобы им можно было воспользоваться, его необходимо дополнить методом записи правил вычисления значений атрибутов.

Один из возможных методов записи правил вычисления значений атрибутов рассмотрим на примере атрибутной грамматики чисел в двоичной системе записи.

, ,0

Здесь нетерминал S используется для вывода числа в двоичной системе записи, нетерминал L – для вывода списка бит (0 и 1), нетерминал B – позволяет вывести один бит ( 0 или 1). В эту грамматику включим атрибуты (семантические правила), позволяющие в процессе анализа правильной цепочки получить значение двоичного числа в десятичной системе счисления. Для этого каждому нетерминалу припишем атрибуты следующим образом:

. Каждое число (нетерминал ) имеет один атрибут , равный значению числа в десятичной системе счисления.
. Каждый список битов (нетерминал ) имеет два атрибута - значение последнего бита и длину .
. Каждый бит (нетерминал ) имеет один атрибут- значение .

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

С учетом этих правил построим атрибутную грамматику:

;

LB ,

B0

B1

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

Ниже построено дерево вывода для числа 101.01, а в скобках получено значение числа в десятичной системе счисления.

101.01 (5.25)

Упражнения

7.1. Перевести в ПОЛИЗ, используя метод Замельсона – Бауэра, следующий фрагмент программы:

i:=a+b*c;

if ( (i > 0) and (y < x+10) ) then begin

x := b+10*a*y/(b-x); j:=15;

while (j < 20) do begin y:=(y+2)*a; j:=j+1; end;

i:=(i -a)*b/c;

end; a:=a -b/c -d;

Проинтерпретируйте полученную строку ПОЛИЗа.

7.2. Перевести в тетрады, используя метод Замельсона – Бауэра, следующий фрагмент программы:

if ( (x <= 100) or (y < > x+10) and (y > b) then

x := -(a+b DIV 10)*y MOD b-x;

else begin y:=a-b*c+d; if y < a then y:=y+2*a; x :=y+a-b; end;

a:=a*b+c*d;

Глава 8. ОСНОВНЫЕ ФАЗЫ КОМПИЛЯЦИИ

Транслятор – это программа перевода текста (программы) с одного языка (исходного) на другой (объектный). Трансляторы различают компилирующего и интерпретирующего типов. Компилятор переводит всю программу, затем её выполняет. Интерпретатор переводит по отдельным операторам программу и сразу каждый из операторов исполняет.

Компилятор должен выполнить анализ исходной программы, а затем синтез объектной. Сначала исходная программа разлагается на составные части, затем из них строятся фрагменты эквивалентной объектной программы. Для этого на этапе анализа компилятор использует и строит целый ряд таблиц, структур данных, которые затем используются как при анализе, так и синтезе. Анализ процессов компиляции позволяет выделить 7 различных логических задач – фаз компиляции. В практических реализациях грани между этими фазами размыты, часть из них может отсутствовать, совмещаться одна с другой.

На рис. 8.1 представлена структурно–функциональная схема компилятора, где выделены основные фазы и базы данных “типичного” компилятора. Отдельные фазы компилятора (функциональные блоки) помечены на рисунке цифрами, а структуры данных (таблицы) компилятора – буквами, управляющие связи изображаются сплошной, а информационные – пунктирной стрелкой. В

этой главе мы лишь кратко остановимся на основных фазах и базах данных компилятора.

1). Лексический анализ – распознавание базовых элементов языка, перевод исходной программы в таблицу стандартных символов (лексем), которые в отличие от элементов исходной программы имеют постоянную длину, что делает последующие фазы компиляции более простыми. Лексический анализатор или сканер группирует определенные терминальные символы исходной программы в единые синтаксические объекты – лексемы. Какие объекты считать лексемами, зависит от определения языка программирования. Лексема – это пара вида: тип лексемы, некоторые данные. Первой компонентой пары является синтаксическая категория, такая как “константа”, “идентификатор” или “терминал” (ключевое слово языка или специальный символ: знак операции, разделитель и т.п.), а вторая – указатель: в ней указывается номер элемента таблицы, хранящий подробную информацию об этой конкретной лексеме. Входной информацией сканера является исходная программа и таблица терминалов языка, выходом – цепочка лексем, таблицы идентификаторов и констант.

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

3). Семантический анализ – определение смыслового значения базовых синтаксических конструкций. Этот процесс синтаксически управляем. То есть фазы 2 и 3 тесно связаны (объединены).

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

Когда встречается оператор присваивания вида

<переменная>:=<выражение>,

семантическая программа проверяет переменную и выражение на соответствие типов, а затем заносит информацию об инструкции присваивания во внутреннюю форму программы (ВФП).

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

4). Машинно–независимая оптимизация ВФП – вынесение общих подвыражений, вычисления над константами, оптимизация переходов в сложных условных операторах, вынесение инвариантных вычислений за цикл и т.п.

5). Распределение памяти – модификация таблиц идентификаторов и констант. Определение адресов идентификаторов и констант. Вставки в ВФП, для генерации и распределения динамической памяти. Выделение временной памяти, выравнивание и т.п.

6). Генерация кода и машинно–зависимая оптимизация. С каждой операцией из ВФП связана кодовая продукция, которая и выносится в код сборки. Оптимизация же проводится с целью более эффективного использования регистров ЭВМ, удаление “лишних” команд, связанных с сохранением и загрузкой промежуточных данных на этапе вычислений и т.п.

7). Сборка и выдача – разрешение символических адресов (трансляция с языка ассемблера) и формирование объектного модуля – (машинного кода и информации для компоновщика и загрузчика).

Сразу же отметим, что фазы 1 – 4 – машинно–независимы и определяются только исходным языком, а фазы 5 – 7 машинно–зависимы и не зависят от исходного языка.

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

а). Исходная программа – это программа на исходном языке программирования, например, С или Паскаль.

б). Таблица терминальных символов – постоянная таблица, в которой записаны все ключевые слова (IF, THEN, ELSE, WHILE и т.п.) и специальные символы языка (пробел, ‘,’, ‘;’, ‘*’, ‘+’ и т.п.) в символьной форме. На них ссылаются стандартные символы – лексемы программы.

в) Таблица (строка) лексем (стандартных символов) – состоит из полного или частичного списка лексических единиц, расположенных в том порядке, в каком они встречаются в программе (например, TRM(1¸n), IDN(1¸m), CON(1¸k)). Они создаются при лексическом анализе и используются на этапах синтаксического и семантического анализа.

г). Таблица идентификаторов – содержит информацию обо всех переменных программы, в том числе и временных переменных, хранящих промежуточные результаты вычислений, и информацию, необходимую для ссылок (адресации) и отведения памяти. Создается на фазе лексического анализа (1) (на элементы таблицы идентификаторов ссылаются лексемы), модифицируется на фазах семантического анализа (3) и распределения памяти (5), используется также на фазах генерации кода (6), сборки и выдачи (7).

д). Таблица констант – содержит все константы исходной программы и дополнительную информацию о них. Создается на фазе лексического анализа (1) (на нее ссылаются лексемы), модифицируется на фазе семантического анализа и распределения памяти, используется при генерации кода, сборке и выдаче.

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

ж). Внутренняя форма программы (ВФП) – форма обеспечивающая однопроходную генерацию кодов (в компиляторе) или интерпретацию (выполнение интерпретатором). Пример ВФП – ПОЛИЗ (польская инверсная запись) – где арифметические выражения, да и вся программа представляется не в традиционной инфиксной форме, а в постфиксной или суффиксной бесскобочной формах. В ПОЛИЗе операции располагаются за операндами, над которыми они выполняются в порядке их выполнения. Например, оператор

a:=b+c*d/(b–c)–10; в ПОЛИЗе примет вид abcd*bc–/+10–:=

Еще чаще в компиляторах в качестве ВФП используется матрица тетрад, где выражение представляется в форме тетрад (оператор, операнд, операнд, результат) в порядке их выполнения.

ВФП создается на фазе семантического анализа, модифицируется (оптимизируется) на фазе машинно–независимой оптимизации и используется при генерации кода.

з). Кодовые продукции – постоянная таблица, имеющая отдельные элементы, определяющие код для каждой возможной операции ПОЛИЗа или матрицы тетрад (т.е. ВФП). Например, тетрада +, операнд_1, операнд_2, результат или более конкретно +, A, B, M10 может быть представлена следующей кодовой продукцией:

MOV ax, A

ADD ax, B

MOV ax, M10

а тетрада :=, операнд_1,, результат (:=, M20,,ABC) – продукцией

MOV ax, M20

MOV ABC, ax

Таблица кодовых продукций используется на фазе генерации кода.

и). Код сборки – версия программы на языке сборки (аналог языка ассемблера). Создается на фазе генерации кода и используется фазой сборки.

к). Перемещаемый объектный модуль – результат фазы сборки и всей трансляции в целом. Является входной информацией для компоновщика или загрузчика.

Более подробно описание каждой фазы компиляции рассмотрено, например, в [7,11].

Заключение

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

ПРИЛОЖЕНИЕ

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

Если это не оговорено дополнительно, то используются следующие группы метасимволов:

< ... > - нетерминал;

::= - разделитель левой и правой частей правил и обозна­ча­ет: “это есть” или “состоит из”;

[ ... ] - факультативный (необязательный) элемент;

{ ... } - итерация, т.е. элемент повторяется 0 или более раз;

? ... ¦ ... ¦ ... ? - альтернатива;

Используются также следующие сокращения: @ - произвольный идентификатор; k - константа, если не оговорено,- то целая. Терминальные символы, а к ним здесь относятся и идентификаторы, и константы, выделены жирно.

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

Во всех заданиях выдавать предупреждающие сообщения при переполнении констант и в случаях, когда количество символов в идентификаторах больше 8-ми. Сравнение идентификаторов проводить по первым 8-ми символам.

Вариант 1

Построить синтаксический анализатор для цепочек автоматного языка операторов присваивания (ПЛ/1), имеющих вид:

<оператор присваивания> ::= {<метка>:}<левая часть>=<правая часть>;

<метка> ::= @

<левая часть> ::= @[(<список индексов>)]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= ? <левая часть>{<оп1><левая часть>} ¦ k ?

<оп1> ::= ? + ¦ - ¦ * ¦ / ?

<правая часть> ::= <операнд>{<оп2><операнд>}

<операнд> ::= ? <левая часть> ¦ k1 ?

где k1 - целая или действительная константа

<оп2> ::= ? <оп1> ¦ OR ¦ AND ?

Примеры правильных цепочек:

abc: ac123: a1(i+j/10,j*k,10,a2(1,i,15)-a2(1,2*i,7)+15,l)=

1234+a2(1,i,15)*1234.56E-3/aqs(3,a2(j,a2(1,2,3),15));

abcde=123; aaa=aaa OR bbb OR ccc AND 1;

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

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

Вариант 2

Построить синтаксический анализатор для цепочек автоматного языка операторов описания типов (Модула-2), имеющих вид:

<описания типов> ::= TYPE <описание типа>; {<описание типа>;}

<описание типа> ::= @=? <простой тип> ¦ <массив> ¦ <множество> ¦ <запись> ¦ <указатель> ?

<простой тип> ::= ? CARDINAL ¦ INTEGER ¦ REAL ¦ CHAR ¦ SHORTCARD ¦ SHORTINT ¦ LONGCARD ¦ LONGINT ¦ LONGREAL ¦ BOOLEAN ¦ ADDRESS ¦ BYTE ¦ WORD ¦ <перечисление> ¦ <диапазон> ?

<перечисление> ::= (@{,@})

<диапазон> ::= [k1..k2]

<массив> ::= ARRAY <диапазоны> OF <тип>

<диапазоны> ::= <диап1>{,<диап1>}

<диап1> ::= ? <диапазон> ¦ @T1 ?

<тип> ::= ? <простой тип> ¦ @T ? ,

где @T - имя типа, определенного выше в анализируемом Вами операторе, @T1 - имя типа-дипазона

<множество> ::= SET OF <простой тип>

<запись> ::= RECORD <элемент> {;<элемент>} END

<элемент> ::= @{,@}: <тип>

<указатель> ::= POINTER TO <тип_1>

<тип_1> ::= ? <простой тип> ¦ @T2 ? ,

где @T2 - имя типа, определенного выше или ниже в анализируемом Вами операторе.

Пример правильной цепочки:

TYPE Color = ( Red, Blue, White, Black );

diap = [10..25]; BitSet = SET OF WORD;

Mas = ARRAY [0..100], [0..3], diap OF BitSet;

PTab = POINTER TO Tab;

Tab = RECORD a1, a2, a3: CARDINAL; col: Color;

St: ARRAY [0..79] OF CHAR;

left, right: PTab

END;

MTab = ARRAY [0..100] OF Tab;

Семантика: Сформировать список определяемых типов с указанием объема памяти, отводимого под тип.

Вариант 3

Построить синтаксический анализатор для цепочек автоматного языка операторов описания констант (Модула-2), имеющих вид:

<описания констант> ::= CONST <описание>; {<описание>;}

<описание> ::= @=<выражение>

<выражение> ::= ? <операнд>{<операция><операнд>} ¦ '<текст>'?

<операнд> ::= ? k ¦ @C ? ,

где k - целая или вещественная; @C - имя константы, определенной выше в анализируемом Вами операторе;

<текст> - произвольный набор символов.

<операция> ::= ? + ¦ - ¦ * ¦ / ¦ DIV ¦ MOD ?

Пример правильной цепочки:

CONST Abc = 1024 DIV 7 + 35 MOD 17; text = 'All right';

Cde = 1234 - 32*13; rur = 3.14;

rir= 123.*rur/12.3E-5+rur; Fg = Abc - Cde + 15;

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

Вариант 4

Построить синтаксический анализатор для цепочек автоматного языка операторов описания пеpеменных (ПЛ/1), имеющих вид:

<описания пеpеменных> ::= ? DCL ¦ DECLARE ? <список описа­ний>;

<список описа­ний> ::= <описание>{,<описание>}

<описание> ::= ? <пеpеменная> [<атpибут>] ¦ (<список пеpемен­ных>)<атpибут> ?

<пеpеменная> ::= @[(<список pазмеpностей>)]

<список pазмеpностей> ::= <pазмеpность>{,<pазмеpность>}

<pазмеpность> ::= k1[:k2] ,

где k1 и k2 - целые числа со знаком

<атpибут> ::= ? BIN[ARY] FIXED ¦ FLOAT ¦ CHAR[ACTER](k) ?

Примеры правильных цепочек:

DCL IND1, JIG, LOO, SUM, E123 BIN FIXED, III FLOAT, ST CHAR(10),

STR CHARACTER(25), SUSPEED BINARY FIXED, IMAS(100),

(ABC(10,-15:20,0:23), MICRO, MACRO(5:40), ERCOD) BIN FIXED;

DECLARE SSS(10:20,50) CHAR(1);

Семантика: По умолчанию, пеpеменные, имена котоpых начинаются с букв I,J,K,L,M,N имеют тип BIN FIXED, остальные - FLOAT. Сообщать об ошибках, если k1 > k2, pазмеp стpоки больше 256 символов и pазмеp массива больше 64 Kбайт. Сфоpмиpовать упорядоченный список-таблицу пеpеменных с указанием имени, типа, pазмеpности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух полей формируемой таблицы, все остальные поля в числовой форме). Напоминаем, что переменная типа BIN FIXED занимает 2 байта памяти, FLOAT - 4 байта, CHAR(1) - 1 байт.

Вариант 5

Построить синтаксический анализатор для цепочек автоматного языка операторов описания форматов (ПЛ/1), имеющих вид:

<описание форматов> ::= FORMAT(<элемент>{,<элемент>});

<элемент> ::= ? <формат> ¦ k1(<формат>{,<формат>}) ?

<формат> ::= ? A(k2) ¦ X(k2) ¦ SKIP(k1) ¦ F(k4[,k5]) ¦ E(k6,k7) ¦ <элемент> ?

где k1 - k7 - целые числа без знака.

Семантика: Сообщать об ошибках, если k1 > 10; k2 > 50; k4 > 33 и k4 < 4, если присутствует k5 ; k5 > k4-3; 8 > k6 > 37; k7 > k6-7. Осуществить вывод на экран информации по заданному формату: SKIP - переход на новую строку, с обозначением "|" для пустой стpоки, Х - обозначить символом "-", A - "А", знак числа и порядка - "З", цифр мантиссы и порядка - "Ц".

Пример правильной цепочки:

FORMAT (X(5),3(A(2),X(2),F(3),X(1)), SKIP(3), X(7), 2(F(10,5)), X(2), E(10,4), SKIP(2), 4(X(10), A(5), F(5), 2(X(3), A(2), 3(F(2), A(1))), SKIP(1)), X(20),A(10));

Результат работы программы для данного оператора:

-----АА--ЗЦЦ-АА--ЗЦЦ-АА--ЗЦЦ-

|

|

-------ЗЦЦЦ.ЦЦЦЦЦЗЦЦЦ.ЦЦЦЦЦ--ЗЦ.ЦЦЦЦЕЗЦЦ

|

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

--------------------АААААААААА

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

Вариант 6

Построить синтаксический анализатор для цепочек автоматного языка операторов описания пеpеменных (Модула-2), имеющих вид:

<описание пеpеменных> ::= VAR <описание>;{<описание>;}

<описание> ::= @{,@}:[ARRAY <диапазон>{,<диапазон>} OF]<тип>

<диапазон> ::= [k1..k2]

<тип> ::= ? CARDINAL ¦ INTEGER ¦ REAL ¦ CHAR ¦ SHORTCARD ¦ SHORTINT ¦ LONGCARD ¦ LONGINT ¦ LONGREAL ¦ BOOLEAN ¦ ADDRESS ¦ BYTE ¦ WORD ?

Пpимеp пpавильного оператора:

VAR abc, A12C3,Ijk: CARDINAL;

s,st,S: ARRAY [0..79] OF CHAR; abcdef: LONGINT;

MasF: ARRAY [10..20],[5..19] OF BOOLEAN; Re: REAL;

Семантика: Сообщать об ошибках, если k1 > k2, объем памяти под переменную больше 64 Кбайт. Сфоpмиpовать упорядоченный по именам список-таблицу пеpеменных с указанием имени, типа, pазмеpности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух символьных полей таблицы, все остальные поля представлять в числовой форме).

Вариант 7

Построить синтаксический анализатор для цепочек автоматного языка операторов заголовка цикла (Модула-2), имеющих вид:

<заголовок цикла> ::= FOR <паpаметp>:=<значение> TO <значение>

[BY <значение>] DO

<параметр> ::= @[[<список индексов>]]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция> ::= ? + ¦ - ¦ * ¦ MOD ¦ DIV ?

<значение> ::= <операнд2>{<операция><операнд2>}

<операнд2> ::= ? <параметр> ¦ k ?

Примеры правильных цепочек:

FOR par[1,yy+23 MOD 7 DIV 2-1*3,kkk]:=ijk+aa[1,h-2] TO kkk*24 DIV 3

BY aa[3,4]-3 DO

FOR ijk:=1444-7 DIV 12 * 3 TO 12345 BY 23-1*5 DIV 2 DO

Семантика: Сформировать списки @ и k в числовой форме. Если все значения в операторе представляют собой выражения над константами, то определить сколько раз будет выполняться цикл.

Вариант 8

Построить синтаксический анализатор для цепочек автоматного языка операторов цикла (Модула-2), имеющих вид:

<цикл> ::= REPEAT {<присваивание>;} UNTIL <условие>;

<присваивание> ::= <левая часть>:=<правая часть>

<левая часть> ::= @[[<список индексов>]]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция1><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция1> ::= ? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ >> ¦ << ?

<правая часть> ::= <операнд2>{<операция1><операнд2>}

<операнд2> ::= ? <левая часть> ¦ k ?

<условие> ::= <правая часть1>{<операция2><правая часть1)}

<операция2> ::= ? = ¦ # ¦ < ¦ > ¦ >= ¦ <= ¦ <> ¦& ¦ AND ¦ OR ?

<правая часть1> ::= [ ? NOT ¦ ~ ? ]<правая часть2>

<правая часть2>::=? (<правая часть>) ¦ (k IN <левая часть>) ?

Примеры правильных цепочек:

REPEAT UNTIL (7 IN abcd) & ~(5 IN aa[1,i+k MOD 4]);

REPEAT

aaa:=a+b-c[11,i*j DIV 2 -1,k+zzz123z]*1234 MOD 25;

bb[j+i>>2,12,34,ikj]:=bb[j+i>>2,12,34,ikj]+1;

i:=i-2; j:=i*k+3;

UNTIL (aaa) > (j+2) OR (i+c[1,i DIV 2,k+zzz123z] MOD 5)=(0) AND NOT(3 IN xx);

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Вариант 9

Построить синтаксический анализатор для цепочек автоматного языка операторов цикла (Модула-2), имеющих вид:

<цикл> ::= WHILE <условие> DO {<присваивание>;} END;

<присваивание> ::= <левая часть>:=<правая часть>

<левая часть> ::= @[[<список индексов>]]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция1><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция1> ::= ? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ >> ¦ << ?

<правая часть> ::= <операнд2>{<операция1><операнд2>}

<операнд2> ::= ? <левая часть> ¦ k ?

<условие> ::= <правая часть1>{<операция2><правая часть1)}

<операция2> ::= ? = ¦ # ¦ < ¦ > ¦ >= ¦ <= ¦ & ¦ AND ¦ OR ?

<правая часть1> ::= [ ? NOT ¦ ~ ? ]<правая часть2>

<правая часть2>::=? (<правая часть>) ¦ (k IN <левая часть>) ?

Примеры правильных цепочек:

WHILE (7 IN abcd) & ~(5 IN aa[1,i+k MOD 4]) DO END;

WHILE (aaa) > (j+2) OR (i+c[1,i DIV 2,k+zzz123z] MOD 5)=(0)

AND NOT(3 IN xx) DO

aaa:=a+b-c[11,i*j DIV 2 -1,k+zzz123z]*1234 MOD 25;

bb[j+i>>2,12,34,ikj]:=bb[j+i>>2,12,34,ikj]+1;

i:=i-2; j:=i*k+3;

END;

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Вариант 10

Построить синтаксический анализатор для цепочек автоматного языка операторов ветвления (Модула-2), имеющих вид:

<ветвление> ::= IF <условие> THEN {<присваивание>;}

{ELSIF <условие> THEN {<присваивание>;}}

[ELSE {<присваивание>;}]

END;

<присваивание> ::= <левая часть>:=<правая часть>

<левая часть> ::= @[[<список индексов>]]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция1><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция1> ::= ? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ >> ¦ << ?

<правая часть> ::= <операнд2>{<операция1><операнд2>}

<операнд2> ::= ? <левая часть> ¦ k ?

<условие> ::= <правая часть1>{<операция2><правая часть1)}

<операция2> ::= ? = ¦ # ¦ < ¦ > ¦ >= ¦ <= ¦ & ¦ AND ¦ OR ?

<правая часть1> ::= [ ? NOT ¦ ~ ? ]<правая часть2>

<правая часть2>::=? (<правая часть>) ¦ (k IN <левая часть>) ?

Пример правильной цепочки:

IF (7 IN abcd) & ~(5 IN aa[1,i+k MOD 4]) THEN l:=l+1;

ELSIF (aaa) > (j+2) OR (i+c[1,i DIV 2,k+zzz123z] MOD 5)=(0)

AND NOT(3 IN xx) THEN

aaa:=a+b-c[11,i*j DIV 2 -1,k+zzz123z]*1234 MOD 25;

bb[j+i>>2,12,34,ikj]:=bb[j+i>>2,12,34,ikj]+1;

i:=i-2; j:=i*k+3;

ELSIF aabbcc THEN

i:=i+1;

ELSE i:=j+b<<4*kkk[1,hg];

END;

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Вариант 11

Построить синтаксический анализатор для цепочек автоматного языка заголовков процедур (Модула-2), имеющих вид:

<заголовок процедуры> ::= PROCEDURE <заголовок>;

<заголовок> ::= ? @[(<параметры>)] ¦ @([<параметры>]):<тип> ?

<параметры> ::= <описание>{;<описание>}

<описание> ::= [VAR] @{,@}:<тип1>

<тип1> ::= [ARRAY <диапазоны> OF ] <тип>

<тип> ::= ? CARDINAL ¦ INTEGER ¦ REAL ¦ CHAR ¦ SHORTCARD ¦ SHORTINT ¦ LONGCARD ¦ LONGINT ¦ LONGREAL ¦ BOOLEAN ¦ ADDRESS ¦ BYTE ¦ WORD ?

<диапазоны> ::= <диапазон>{,<диапазон>}

<диапазон> ::= [k1..k2]

Примеры правильных цепочек:

PROCEDURE Aabb( ):BOOLEAN;

PROCEDURE n1m2;

PROCEDURE Examp ( s: ARRAY OF CHAR;

aa, AA: ARRAY [0..10],[3..8] OF SHORTCARD;

VAR rez, sum: LONGREAL): CHAR;

Семантика: Сформировать безповторные упорядоченные списки-таблицы @ с указанием объема памяти, отводимой под параметр в процедуре. Сообщать об ошибках при дублировании имен в одном операторе.

Вариант 12

Построить синтаксический анализатор для цепочек автоматного языка заголовков цикла (ПЛ/1), имеющих вид:

<заголовок цикла> ::= DO [<переменная>=<параметры>] [WHILE(<условие>)] ;

<параметры> ::= <параметр>{,<параметр>}

<переменная> ::= @[(<список индексов>)]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция1><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция1> ::= ? + ¦ - ¦ * ¦ / ?

<параметр> ::= ? k [BY k] [TO k] ¦ k [TO k] [BY k] ?

<условие> ::= <выражение>{<опекрация2><выражение>}

<выражение> ::= <операнд2>{<операция1><операнд2>}

<операнд2> ::= ? k ¦ <переменная> ?

<операция2> ::= ? = ¦ <> ¦ > ¦ < ¦ >= ¦ <= ¦ AND ¦ OR ?

Примеры правильных цепочек:

DO I=1;

DO J=5 TO 20 BY 2;

DO KLMN(1,J+I-3,21-L)=1 TO 7, 12 TO 36 BY 3;

DO IKL=7 BY 1;

DO IJK(1,I+J)=5 TO 10, 40 TO 15 BY -3 WHILE(AB+K(I,J)*4 > 7 AND AI);

DO I=1 TO 17, WHILE (J<KL(1,2,3));

Семантика: Сформировать бесповторные упорядоченные списки @ и k в числовой форме. Определить сколько раз будет выполняться цикл без учета WHILE.

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

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. - М.: Мир, 1978.

2. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция. - М.:Мир, 1978.

3. Братчиков И.Л. Синтаксис языков программирования. - М.: Наука, 1975.

4. Гилл А. Введение в теорию конечных автоматов. - М.: Наука, 1966.

5. Гинзбург С. Математическая теория контекстно-свободных языков. - М.: Мир, 1970.

6. Гладкий А.В. Формальные грамматики и языки. - М.: Наука, 1973.

7. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. - М.: Мир, 1975.

8. Гросс М., Лантен А. Теория формальных грамматик. - М.: Мир, 1971.

9. Донован Д. Системное программирование.- М.:Мир, 1975 г.

10.Лебедев В.Н. Введение в системы программирования.- М.:Статистика, 1975 г.

11. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.

12. Семантика языков программирования. Сборник статей.- М.:Мир,1980.

13.Теория формальных языков. Грамматики и автоматы. Учебное пособие./М.А.Шамашов.-Самара: Самарский муниципальный комплекс непрерывного образования «Университет Наяновой», 1996, 92 с.

14. Хантер Р. Проектирование и конструирование компиляторов. – М.:Финансы и статистика, 1984.

15. Хомский Н. Формальные свойства грамматик. // Кибернетический сборник, новая серия, вып. 2. - М.: ИЛ, 1966.

16.Хомский Н., Шютценберже М. Алгебраическая теория контекстно-свободных языков. // Кибернетический сборник, новая серия, вып. 3. - М.: ИЛ, 1966.

17. Хопгуд Ф. Методы компиляции М.:Мир, 1972.

18. Форстер Дж. Автоматический синтаксический анализ.-М.:Мир, 1972.

19. М.А. Шамашов. Основные структуры данных и алгоритмы компиляции. Учебное пособие/ Самара: Научно-внедренческая фирма «Сенсоры, модули, системы», 1999 –115 с.

20. Шамашов М.А. , Штернберг Л.Ф. Синтаксический анализ автоматных языков. Метод. указания. - Куйбышев: КуАИ, 1990.

21. Штернберг Л.Ф. Теория формальных грамматик. - Куйбышев: КуАИ, 1979.

22. Языки и автоматы. Сборник статей. - М.: Мир, 1975.

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Автомат (automaton, machine) [см. Распознаватель, Преобразователь] 23

- конечный (finite) 25 - 29, 30 - 34, 35 - 37

- - детерминированный (deterministic) 26 - 29

- - недетерминированный (nondeterministic) 26 - 29

А-грамматика [см. Грамматика автоматная] 12

Алфавит (alphabet) 5

- входной (input) [см. Символ входной] 23, 26

- выходной (output) [см. Символ выходной] 74

Анализ (analysis)

- синтаксический (syntactical, parse) [см. Разбор] 18, 57 - 59

- - восходящий (bottom-up) 69

- - нисходящий (top-down) 69, 70

Анализатор (parser)

- левый (left) 75 - 76

- правый (right) 76 - 77

А-язык [см. Язык автоматный] 12, 25, 48 - 49

Вершина (графа) (node, vertex) 16 - 18

Вывод (derivation) 6, 7

- левый (leftmost) 8, 68, 69, 75

- правый (rightmost) 8, 70

Грамматика (grammar) 4, 6, 11

- автоматная (automaton) 12

- - детерминированная (deterministic) 17, 29 - 30

- - недетерминированная (nondeterministic) 17, 29 - 30

- бесконтекстная [см. Грамматика контекстно-свободная] 12

- контекстно-зависимая(context-sensitive) 12

- контекстно-свободная (context-free) 12, 40 - 47, 68 - 72

- неоднозначная (ambiguous) 11, 60 - 62

- однозначная (nonambiguous) 11

- праворекурсивная (right recursive) 10

- регулярная (regular) [см. Грамматика автоматная] 12

- рекурсивная (recursive) 10, 60, 61

Граф (graph)

- переходов (автомата, грамматики) (transition) [см. Граф состояний] 16

- состояний (state) 16 - 18

Дерево (tree)

- вывода (derivation) [см. Дерево разбора] 10, 29, 40, 50, 70, 75

- разбора (parse) 4, 75

- синтаксическое (syntax) [см. Дерево разбора] 10

Длина (length)

- вывода (of a derivation) 9

- цепочки (of a string) 5

Дополнение (множества, языка) (complementation) 51, 53

Дуга (в графе) (arc, edge) 17

Замкнутость (относительно операций) (closure) 52, 53

Иерархия Хомского (Chomsky hierarchy) 11 - 13, 25

Итерация (языка) (closure) 51, 52, 54

КЗ-грамматика [см. Грамматика контекстно-зависимая] 12

Конкатенация (concatenation) 5, 51, 52, 54

КС-грамматика [см. Грамматика контекстно-свободная] 12, 40 - 47, 68 - 72

КС-язык [см. Язык контекстно-свободный] 12, 25, 49 - 51, 73

Магазин (pushdown list) 24, 63,

Метаязык (meta-language) 7

МП-автомат [см. Автомат с магазинной памятью] 25, 63 - 73

Нетерминал (nonterminal) 6, 8

- аннулирующий (nullable) 43 - 45

- начальный (starting) 6, 7

Обращение (цепочки или языка) (reversal) 5, 51, 52 - 53, 54

Объединение (union) 51, 52, 53

Основа (правовыводимой цепочки) (handle of a right sentential form) 10, 70

Память (распознавателя) (memory) 24

Пересечение (множеств, языков) (intersection) 51, 53, 56

Подстановка (языков) (substitution) 51, 52, 55

Правило (грамматики) (production) 6

Предложение (sentence) [см. Цепочка] 3, 5

Преобразователь (transducer) 24

- с магазинной памятью (pushdown) 73

- - - - детерминированный (deterministic)

- - - - расширенный (extended)

Продукция (production) [см. Правило (грамматики)] 6

Разбор (как синтаксический анализ) (parsing)

- восходящий (bottom-up) 69

- нисходящий (top-down) 69, 70

- с возвратами (backtrack) 77

Разбор (как результат синтаксического анализа) (parse) 75

- левый (left) [см. Вывод левый] 75

- правый (right) [см. Вывод правый] 75

Разность (множеств, языков) (difference) 51, 53

Рекурсия (recursion) 10, 46, 61, 62

Свертка (цепочки) (reduction) [см. Разбор типа “перенос-свертка”] 8, 70

Семантика (semantics) 4

Символ (symbol) 5

- бесполезный (в грамматике) (useless) [см. Тупик] 41 - 43

- вспомогательный [см. Нетерминал] 6

- входной (input) 23, 25, 63

- выходной (output) 74

- начальный (initial, starting) 6

- нетерминальный (nonterminal) [см. Нетерминал] 6

- терминальный (terminal) [см. Терминал] 6

Синтаксис (syntax) 4

Состояние (автомата, преобразователя, распознавателя) (state) 24, 25, 63

- допускающее (accepting) 26

- заключительное (final) [см. допускающее] 25, 26, 63

- начальное (initial) 25, 26, 63

- недостижимое (unreachable, extraneous) 33

- отвергающее (rejecting) 26

Форма Бэкуса-Наура (Backus-Naur form) 7

Цепочка (sequence, string) 5

- выводимая (sentential form) 4, 9

- допустимая (accepted) 25, 27, 64

- пустая (empty, null) 5

Эквивалентность (equivalence)

- автоматов (mashine) 27, 31

- грамматик (grammar) 9, 29, 40

Язык (language) 4, 6, 9, 25, 64

- автоматный (automaton) 12, 25, 48 - 49, 53 - 55

- ассемблера (assambly) 3

- бесконтекстный (context-free) [см. Язык контекстно-свободный] 12

- детерминированный (deterministic) 73

- естественный (natural) 3

- контекстно-зависимый (context-sensitive) 12, 25

- контекстно-свободный (context-free) 12, 25, 49 - 51, 52 - 53, 68 - 73

- неоднозначный (ambiguous) 4, 60, 61

- однозначный (unambiguous) 4

- программирования (programming) 3

- регулярный (regular) [см. Язык автоматный] 12