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

Многие методы, технические приемы и их реализация в курсовой работе будут взяты из лабораторных работ № 1–4, которые были рассмотрены ранее. Другие методы, наоборот, будут реализованы иначе, чтобы проиллюстрировать все существующие возможности, их преимущества и недостатки. В каждом случае будет дано пояснение, почему использован тот или иной метод.

В примере проиллюстрированы следующие интересные моменты:

• разделение лексического и синтаксического анализаторов с целью упрощения работы последнего (на примере унарной арифметической операции «-» и операции сравнения типа «не равно»);

• обнаружение присваивания значений константам на этапе синтаксического разбора (в лабораторных работах № 3 и 4 эта же операция выполнялась на этапе семантического анализа перед генерацией кода);

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

• модификация остовной грамматики при необходимости различать правила;

• методы обработки логических операций и операций сравнения;

• простейший семантический анализ и модификация результирующего кода на этапе семантического анализа (на примере обработки переменных InpVar и CornpileTest);

• элементарные методы машинно-зависимой оптимизации результирующего кода.

Для реализации курсовой работы будут использоваться программные модули, созданные при выполнении лабораторных работ № 1–4, код которых не зависит от входного языка. Такой подход иллюстрирует, насколько удобно и эффективно выделять не зависящую от входного языка часть компилятора в отдельные модули или библиотеки.

 

Задание для примера выполнения работы

В качестве примера возьмем следующие условия для входного языка:

1. Тип допустимых констант: десятичные.

2. Дополнительная операция: унарный арифметический минус (-).

3. Оператор цикла: while (<выражение>) do <оператор>.

4. Оптимизация: оба метода (1 и 2).

5. Тип данных: Long integer (longint, 32 бит).

6. Тип комментария: фигурные скобки ({… }).

Кроме того, модифицируем синтаксис условного оператора (два типа):

• if (<выражение>) <оператор> else <оператор>;

• if (<выражение>) <оператор>;

и дополним перечень операций сравнения операцией «не равно» (<>).

Получим входной язык, сочетающий в себе элементы синтаксиса языков C++ (элементы оператора цикла и условный оператор) и Object Pascal (оператор цикла, составной оператор begin… end, оператор присваивания и комментарии).

В качестве результирующего (выходного) языка компилятора будем использовать язык ассемблера процессоров типа Intel 80386 и более поздних модификаций в модификации для системы программирования Delphi 5 [9, 23, 28, 41, 44]. Чтобы исключить неоднозначности при работе с этой системой программирования, изменим семантические ограничения входного языка:

• сделаем допустимым использование имени переменной CompileTest в любых операторах входного языка (а не только в операторах присваивания);

• запретим использование переменных с именем Result, так как такое имя переменной является предопределенным в целевой вычислительной системе.

Кроме того, в именах переменных во входном языке не должны различаться строчные и прописные буквы (например, переменные с именами i и I должны восприниматься как одна и та же переменная).

 

Грамматика входного языка

Грамматику входного языка построим на основе фрагментов грамматик, рассмотренных в заданиях по лабораторной работе № 3. Там имеются правила для линейных операций (арифметические и логические операции) и для условного оператора. По аналогии с условным оператором построим оператор цикла. Для составного оператора и всей программы в целом останется определить еще одно понятие – последовательность операторов. Будем рассматривать последовательность операторов как цепочку операторов, разделенных знаком «точка с запятой».

В результате получим КС-грамматику в форме Бэкуса—Наура:

G({prog,end.,if,else, begin, end,while, do, or,xor,and,not,<,>,=, <>, (,), – ,+,um,a,c,=},

{S,L, 0,B,C,D,E, T,F},P,S)

с правилами P:

S → prog L end.

L → О | L;0 | L;

О → if(B) О else О | if(B) О | begin L end | while(B)do О | a:=E

В → В or С | В xor С | С

С → С and D | D

D → EE | E=E | E<>E | (В) | not(B)

E → E-T | E+T | T

T → um T | F

F → (E) | a | с

Жирным шрифтом выделены терминальные символы.

Всего в построенной грамматике G 28 правил. Нетерминальные символы грамматики имеют следующий смысл:

• S вся программа;

• L последовательность операторов (может состоять и из одного оператора);

• О – оператор (пять видов: полный условный оператор, неполный условный оператор, составной оператор, оператор цикла, оператор присваивания);

• В, С – логическое выражение и его элементы;

• D операция сравнения или логическое выражение в скобках;

• Е,Т, F – арифметическое выражение и его элементы.

Можно обратить внимание на следующие моменты в грамматике:

• операция um («унарный минус») обозначена отдельным терминальным символом, не совпадающим со знаком арифметической операции вычитания («-»), хотя в тексте исходной программы эти два символа идентичны;

• константы и переменные обозначены двумя различными терминальными символами – а и с соответственно – это говорит о том, что они должны различаться на этапе синтаксического анализа;

• операция отрицания not обязательно требует после себя выражения в скобках, что не совсем соответствует традиционной записи логических операций (но не противоречит заданию!), традиционная запись могла бы быть записана в виде правил:

D → not D | G

G → EE | E=E | E<>E | (B)

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

 

Описание выбранного способа организации таблицы идентификаторов

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

В качестве такого способа возьмем комбинацию хэш-адресации и бинарного дерева, которая была использована при выполнении лабораторной работы № 1.

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

 

Описание лексического анализатора

Для построения лексического анализатора воспользуемся подходом, использованном в лабораторной работе № 2.

Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются:

• двенадцать ключевых слов языка (prog, end., if, else, begin, end, while, end, not, or, xor и and);

• разделители: открывающая и закрывающая круглые скобки, точка с запятой;

• знаки операций: присваивание, сравнение (четыре знака), сложение, вычитание и унарный минус;

• идентификаторы;

• целые десятичные константы без знака.

Можно заметить, что end и end. – это разные лексемы.

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

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

Если не делать различий между унарным минусом и бинарным, то правила грамматики G для символов E, T и F имели бы следующий вид:

E → E—T | E+T | T

T → —T | F

F → (E) | a | c

Однако такая грамматика будет очень сложна для синтаксического анализа, поскольку в ней возникает проблема выбора правила между E—T и – T при выполнении свертки (можно проверить и прийти к выводу, что она, например, не является грамматикой операторного предшествования). Преобразования для этой грамматики неочевидны.

Но возможно более простое решение, если понять, как различить две операции (унарный и бинарный знаки «минус») на этапе лексического анализа. Различие можно сделать, если заметить, что бинарный минус всегда следует после операнда (переменной или константы) или после закрывающей круглой скобки, в то время как унарный минус – или после знака операции, или после открывающей круглой скобки. Такой анализ вполне по силам КА, если в него добавить еще одно состояние, которое будет определять, какую лексему (унарный или бинарный минус) сопоставлять с входным символом «—». Поскольку перед унарным минусом, как и перед любыми другими лексемами, может быть комментарий, то придется добавить два состояния (чтобы различать, в каком месте КА встретилось начало комментария, и после завершения комментария вернуться в то же место).

Таким образом, незначительное усложнение КА лексического анализатора позволит избежать серьезных проблем на этапе синтаксического анализа.

Данный пример иллюстрирует, как важно рационально провести границу между лексическим и синтаксическим анализом.

Другой пример из заданного входного языка еще более очевиден, хотя он и не ведет к столь серьезным осложнениям при лексическом разборе: это знак операции «не равно» – «<>». Его можно рассматривать как две лексемы или как одну. В первом случае проверка правильности этой операции будет идти на этапе синтаксического анализа, во втором случае – на этапе лексического анализа. Оба варианта могут быть без проблем реализованы, но второй из них представляется все же более логичным.

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

Например, в том же входном языке сочетания if(и while(могут быть рассмотрены как единые лексемы (обозначим их if_ и w_l) и выявлены на этапе лексического анализа. При этом синтаксический анализатор не получает никаких преимуществ, но правила грамматики для нетерминального символа будут иметь вид:

О → if_ В) О else О | if_ В) О | begin L end | w_l B)do О | а:=Е

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

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

Приняв во внимание правила и соглашения, рассмотренные для КА в лабораторной работе № 2, полностью КА можно описать следующим образом:

M(Q,Σ,δ,q0,F):

Q = {H, C, C1, G, S, L, V, D, P1, P2, P3, P4, E1, E2, E3, I1, I2, L2, L3, L4, B1, B2, B3, B4,

B5, W1, W2, W3, W4, W5, O1, O2, D1, D2, X1, X2, X3, A1, A2, A3, N1, N2, N3, F};

Σ = А (все допустимые алфавитно-цифровые символы);

q0 = H;

F = {F, S}.

Функция переходов (δ) для этого КА приведена в приложении 2.

Из начального состояния КА литеры «p», «e», «i», «b», «w», «o», «x», «a» и «n» ведут в начало цепочек состояний, каждая из которых соответствует ключевому слову (цепочка, начинающаяся с «e», соответствует трем ключевым словам):

• состояния P1, P2, P3, P4 – ключевому слову prog;

• состояния E1, E2, E3 – ключевым словам end и end.;

• состояния I1, I2 – ключевому слову if;

• состояния B1, B2, B3, B4, B5 – ключевому слову begin;

• состояния W1, W2, W3, W4, B5 – ключевому слову while;

• состояния E1, L2, L3, L4 – ключевому слову else;

• состояния D1, D2 – ключевому слову do;

• состояния O1, O2 – ключевому слову or;

• состояния X1, X2, X3 – ключевому слову хог;

• состояния A1, A2, A3 – ключевому слову and;

• состояния N1, N2, N3 – ключевому слову not.

Остальные литеры ведут к состоянию, соответствующему переменной (идентификатору) – V. Если в какой-то из цепочек встречается литера, не соответствующая ключевому слову, или цифра, то КА также переходит в состояние V, а если встречается граница лексемы – запоминает уже прочитанную часть ключевого слова как переменную (чтобы правильно выделять такие идентификаторы, как «i» или «els», которые совпадают с началом ключевых слов).

Цифры ведут в состояние, соответствующее входной константе, – D. Открывающая фигурная скобка ведет в состояние C, которое соответствует обнаружению комментария – из этого состояния КА выходит, только если получит на вход закрывающую фигурную скобку. Еще одно состояние – G – соответствует лексеме «знак присваивания». В него КА переходит, получив на вход двоеточие, и ожидает в этом состоянии символа «равенство».

Рис. 5.1. Граф переходов сокращенного КА (без учета ключевых слов).

Знаки арифметических операций («+» и «—»), знаки операций сравнения («<.», «.>» и «=.»), открывающая круглая скобка, а также последние символы ключевых слов переводят КА в состояние S, которое отличается от начального состояния тем, что в этом состоянии КА воспринимает символ «—» как знак унарной операции отрицания, а не как знак операции вычитания. Если в состоянии S на вход КА поступает открывающая фигурная скобка, то он переходит в состояние C1 (а не в состояние C), из которого по закрывающей фигурной скобке опять возвращается в состояние S.

В еще одно состояние – состояние L – КА переходит, когда на его вход поступает знак «<.». В состоянии L автомат проверяет, является ли знак «<.» началом лексемы «<>» («неравно») или же это отдельная лексема «<.» («меньше»).

Состояние H – начальное состояние КА, а состояния F и S – его конечные состояния. Поскольку КА работает с непрерывным потоком лексем, перейдя в конечное состояние H, он тут же должен возвращаться в начальное состояние, чтобы распознавать очередную лексему. Поэтому в моделирующей программе два состояния (H и F) можно объединить в одно.

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

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

Реализация данного КА выполнена аналогично реализации КА, построенного в лабораторной работе № 2. Для описания структур данных лексем, которые не зависят от входного языка, используется модуль LexElem, который был создан при выполнении лабораторной работы № 2 (листинг П3.4, приложение 3). Типы допустимых лексем описаны в модуле LexType (листинг П3.3, приложение 3), а функционирование автомата моделируется в модуле LexAuto (листинг П3.5, приложение 3).

 

Описание синтаксического анализатора

Для построения синтаксического анализатора будем использовать анализатор на основе грамматик операторного предшествования. Этот анализатор является линейным распознавателем (время анализа линейно зависит от длины входной цепочки), для него существует простой и эффективный алгоритм построения распознавателя на основе матрицы предшествования [1–3, 7]. К тому же алгоритм «сдвиг-свертка» для данного типа анализатора был разработан при выполнении лабораторной работы № 3, а поскольку он не зависит от входного языка, он может быть без модификаций использован в данной работе.

Построение распознавателя

Для построения анализатора на основе грамматики операторного предшествования необходимо построить матрицу операторного предшествования (порядок ее построения был детально рассмотрен при выполнении лабораторной работы № 3).

Построим множества крайних левых и крайних правых символов грамматики G. На первом шаге получим множества, приведенные в табл. 5.3.

Таблица 5.3. Множества крайних левых и крайних правых символов. Шаг 1

После завершения построения мы получим множества, представленные в табл. 5.4 (детальное построение множеств крайних левых и крайних правых символов описано при выполнении лабораторной работы № 3).

Таблица 5.4. Множества крайних левых и крайних правых символов. Результат

После этого необходимо построить множества крайних левых и крайних правых терминальных символов. На первом шаге возьмем все крайние левые и крайние правые терминальные символы из правил грамматики G. Получим множества, представленные в табл. 5.5.

Таблица 5.5. Множества крайних левых и крайних правых терминальных символов. Шаг 1

Дополним множества, представленные в табл. 5.5, на основе ранее построенных множеств крайних левых и крайних правых символов, представленных в табл. 5.4 (алгоритм выполнения этого действия подробно рассмотрен при выполнении лабораторной работы № 3). Получим множества крайних левых и крайних правых терминальных символов, которые представлены в табл. 5.6.

Таблица 5.6. Множества крайних левых и крайних правых терминальных символов. Результат

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

Преобразование грамматики, модификация языка и другие способы разрешения конфликтов

Однако при заполнении матрицы операторного предшествования возникает проблема: символ) стоит рядом с символом else в правиле О → if(B) О else О (между ними один нетерминальный символ О). Значит, в клетке матрицы операторного предшествования на пересечении столбца, помеченного else, и строки, помеченной), должен стоять знак «=.» («составляют основу»). Но в то же время символ else стоит справа от нетерминального символа О в том же правиле О → if(B) О else О, а в множество крайних правых терминальных символов Rt(0) входит символ). Тогда в клетке матрицы операторного предшествования на пересечении столбца, помеченного else, и строки, помеченной), должен стоять знак «.>» («следует»). Получаем противоречие (в одну и ту же клетку матрицы предшествования должны быть помещены два знака – «=.» и «>»), которое говорит о том, что исходная грамматика G не является грамматикой операторного предшествования.

Как избежать этого противоречия?

Во-первых, можно изменить входной язык так, чтобы он удовлетворял требованиям задания на курсовую работу, но не содержал операторов, приводящих к таким неоднозначностям. Например, добавив во входной язык ключевые слова then и endif, для нетерминального символа О получим правила:

O → if B then O else O endif | if B then O endif | begin L end | while(B)do O | a:=E

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

Во-вторых, можно, не изменяя языка, попытаться преобразовать грамматику G к такому виду, чтобы она удовлетворяла требованиям грамматик операторного предшествования (как уже отмечалось ранее, а также как сказано в [1, 3, 7], известно, что формальных рекомендаций по выполнению таких преобразований не существует).

Например, если добавить во входной язык только ключевое слово then, то для нетерминального символа O получим правила:

O → if B then O else O | if B then O | begin L end | while(B)do O | a:=E

В этом случае в матрице операторного предшествования для ключевых слов then и else возникнет противоречие, аналогичное рассмотренному ранее противоречию для лексем (и else. Добавив в грамматику G еще один нетерминальный символ R, получим правила, аналогичные правилам, приведенным в задании по лабораторной работе № 3:

O → if B then R else O | if B then O | begin L end | while(B)do O | a:=E

R → if B then R else R | begin L end | while(B)do O | a:=E

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

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

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

Если посмотреть, к чему ведет размещение в одной клетке матрицы операторного предшествования двух знаков – «=·» и «·>», то можно заметить, что это означает конфликт между выполнением свертки и выполнением переноса при разборе условного оператора. Почему такой конфликт возникает? Этому есть две причины:

• во-первых, распознаватель не может определить, к какому оператору if относить очередную лексему else (такой конфликт можно наглядно проиллюстрировать на примере оператора: if(a

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

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

Следовательно, из двух знаков, которые могут быть помещены в клетку матрицы операторного предшествования на пересечении столбца, помеченного else, и строки, помеченной), следует выбрать знак «=.» («составляет основу»), имея в виду, что он требует дополнительного анализа второго символа от верхушки стека. Поскольку других конфликтов в исходной грамматике нет, то можно заполнить матрицу операторного предшествования, которая представлена в табл. 5.7 (чтобы сократить размер таблицы, отношения предшествования в ней обозначены символами «<.», «.>» и «=.» без точки «»).

Более подробно о вариантах модификаций алгоритма «сдвиг-свертка» для различных грамматик, в которых присутствуют противоречия между выполнением операций «сдвиг» и «свертка» на этапе синтаксического разбора, можно узнать в [1, 2].

Для проверки условия наличия логического выражения перед закрывающей скобкой и разрешения конфликта между переносом и сверткой для символа else используется функция корректировки отношений предшествования CorrectRul е (модуль SyntRule, листинг П3.6 в приложении 3).

Внимание!

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

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

Например, если бы правила грамматики G для символа O выглядели бы следующим образом (без использования ключевого символа do):

O → if(B) O else O | if(B) O | begin L end | while(B) O | a:=E

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

if (а<0) while (а<10) а:=а+1 else а:=1;

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

Таблица 5.7. Матрица операторного предшествования

В таком случае проблематично выполнить преобразования грамматики и привести ее к виду грамматики операторного предшествования без добавления в язык новых ключевых слов. Поскольку приведенный выше синтаксис оператора while соответствует языкам C и C++, можно проиллюстрировать, как указанная проблема решается в этих языках [13, 25, 32, 39]. Тогда в грамматику надо включить сразу два новых нетерминальных символа (обозначим их Р и R), а блок правил грамматики G для нетерминальных символов L и О будет выглядеть следующим образом:

L → Р| L;P | L;

О → if(B) О; else Р | if(B) R else Р | if(B) Р | while(B) Р | а:=Е

R → begin L end

Р → О | R

И показанный выше оператор будет выглядеть так:

if (а<0) while (а<10) а:=а+1; else а:=1;

В языках C и C++ операторным скобкам begin и end соответствуют лексемы { и }, а оператор присваивания обозначается одним символом: =. Но суть подхода этот пример иллюстрирует верно: в этих языках для условного оператора правила различны в зависимости от того, входит в него составной оператор или одиночный оператор (точка с запятой ставится перед else для одиночных операторов в отличие от языка Pascal, где этой проблемы нет, так как конфликт между then и else может быть разрешен указанным выше способом, как в табл. 5.7). Желающие могут построить для такого языка матрицу операторного предшествования и убедиться, что она строится без конфликтов.

Построение остовной грамматики

После того как заполнена матрица операторного предшествования, на основе исходной грамматики G можно построить остовную грамматику G'({prog,end.,if, else,begin,end,while,do,or,xor,and,not,<,>,=,<>,(,), – ,+,um,a,c,=}, {E},P',E) с правилами P':

E → prog E end. – правило № 1

E → E | E;E | E; – правила № 2, 3 и 4

Е → if(E) Е else Е | if(E) Е | begin Еend | while(£)do Е | а:=Е – правила № 5-9

Е → Е or Е | Е хог Е|Е – правила № 10, 11 и 12

Е → Е andE | Е – правила № 13 и 14

Е → Е<Е | Е>Е | £=.£ | Е<>Е | (Е) | not(E) – правила № 15-20

Е → Е-Е | Е+Е | Е – правила № 21, 22 и 23

Е → urn Е|Е – правила № 24 и 25

Е → (_Е) | а | с – правила № 26, 27 и 28

Всего имеем 28 правил. Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

При внимательном рассмотрении видно, что в остовной грамматике неразличимы правила 2, 12, 14, 23 и 25, а также правила 19 и 26. Но если первая группа правил не имеет значения, то во втором случае у распознавателя могут возникнуть проблемы, связанные с тем, что некоторые ошибочные входные цепочки он будет считать допустимыми (например оператор а:=(а or b);, который во входном языке недопустим). Это связано с тем, что круглые скобки определяют приоритет как логических, так и арифметических операций, и хотя они несут одинаковую синтаксическую нагрузку, распознаватель должен их различать, поскольку семантика этих скобок различна. Для этого дополним остовную грамматику еще одним нетерминальным символом B, который будет обозначать логические выражения. Подставив этот символ в соответствующие правила, получим новую остовную грамматику G»({prog,end.,if,else,begin,end,while,do,or,xor,and,not,<,>,=,<>,(,), – ,+,um,a,c,=}, {E,B},P», E) с правилами P»:

E → prog E end. – правило № 1

E → E | E;E | E; – правила № 2-4

E → if(B) EelseE | if(B) E | begin Eend | while(B)do E | a:=E – правила № 5-9

В → В or В | В хог В | В – правила № 10-12

В → В and В | В – правила № 13 и 14

В → Е<Е | Е>Е | Е=Е | Е<>Е | (В) | not(B) – правила № 15-20

Е → Е-Е | Е+Е | Е – правила № 21-23

Е → urn Е | Е – правила № 24 и 25

Е → (Е) | а | с – правила № 26-28

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

Реализация синтаксического распознавателя

Для реализации синтаксического распознавателя воспользуемся программными модулями, созданными при выполнении лабораторной работы № 3.

Модуль SyntSymb (листинг П3.7, приложение 3), который реализует функционирование алгоритма «сдвиг-свертка» для грамматик операторного предшествования, можно использовать, не внося в него никаких изменений, так как он не зависит от входного языка. Требуется перестроить только модуль SyntRulе, внеся в него новые правила грамматики и новую матрицу операторного предшествования. Полученный в результате программный модуль представлен в листинге П3.6 в приложении 3 (обратите внимание на функцию MakeSymbolStr, которая возвращает имена нетерминальных символов для правил остовной грамматики!).

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

 

Внутреннее представление программы и генерация кода

Выбор форм внутреннего представления программы

В качестве формы внутреннего представления программы будут использоваться триады. Преимущества и недостатки триад были рассмотрены ранее (при выполнении лабораторной работы № 4). В данном случае в пользу выбора триад говорят два определяющих фактора:

• для работы с триадами уже имеются необходимые структуры данных (соответствующие программные модули созданы при выполнении лабораторной работы № 4);

• алгоритмы оптимизации, которые предполагается использовать, основаны на внутреннем представлении программы в форме триад.

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

Описание используемого метода порождения результирующего кода

Для порождения результирующего кода будет использоваться рекурсивный алгоритм порождения списка триад на основе дерева синтаксического разбора. Схемы СУ-перевода для такого алгоритма были рассмотрены ранее (при выполнении лабораторной работы № 4).

В данном входном языке мы имеем следующие типы операций:

• логические операции (or, xor, and и not);

• операции сравнения (<, >, = и <>);

• арифметические операции (сложение, вычитание, унарное отрицание);

• оператор присваивания;

• полный условный оператор (if… then … else …) и неполный условный оператор (if… then…);

• оператор цикла с предусловием (while(…)do…);

• операции, не несущие смысловой нагрузки, а служащие только для создания синтаксических конструкций исходной программы (заголовок программы, операторные скобки begin…end, круглые скобки и точка с запятой).

Схемы СУ-перевода для арифметических операций (которые являются линейными операциями), оператора присваивания и условных операторов были построены при выполнении лабораторной работы № 4. Здесь их повторять не будем.

Схему СУ-перевода для оператора цикла с предусловием построим аналогично схемам СУ-перевода для условных операторов (которые были приведены на рис. 4.1 в лабораторной работе № 4).

Генерация кода для цикла с предусловием выполняется в следующем порядке:

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

• Порождается команда условного перехода, которая передает управление в зависимости от результата вычисления логического выражения:

– в начало блока кода № 2, если логическое выражение имеет ненулевое значение;

– в конец оператора, если логическое выражение имеет нулевое значение.

• Порождается блок кода № 2, соответствующий операциям после лексемы do (пятая нижележащая вершина) – для этого должна быть рекурсивно вызвана функция порождения кода для шестой нижележащей вершины.

• Порождается команда безусловного перехода в начало блока кода № 1. Схема СУ-перевода для оператора цикла с предусловием представлена на рис. 5.2.

Рис. 5.2. Схема СУ-перевода для оператора цикла с предусловием.

Таким образом, для реализации оператора цикла достаточно иметь те же типы триад, которые необходимы для реализации условных операторов:

• IF(<операнд1>,<операнд2>) – триада условного перехода;

• JMP(1,<операнд2>) – триада безусловного перехода.

Смысл операндов для этих триад был описан при выполнении лабораторной работы № 4.

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

Однако в данном случае во входном языке логические операции выступают как операции булевой алгебры, которые выполняются только над двумя значениями: «истина» (1) и «ложь» (0). Исходными данными для них служат операции сравнения, результатом которых тоже могут быть только два указанных значения (константы типа «истина» (TRUE) и «ложь» (FALSE) во входном языке отсутствуют, но даже если бы они и были, суть дела это не меняет). При таких условиях возможно иное вычисление логических выражений, поскольку нет необходимости выполнять все операции:

• для операции OR нет необходимости вычислять выражение, если один из операндов TRUE, поскольку вне зависимости от другого операнда результат будет всегда TRUE;

• для операции OR нет необходимости вычислять выражение, если один из операндов FALSE, поскольку вне зависимости от другого операнда результат будет всегда FALSE.

Рассмотрим в качестве примера фрагмент кода для условного оператора:

if (a

При генерации кода для операций сравнения и логических операций как для линейных операций получим фрагмент последовательности триад:

1: < (a, b)

2: < (a, c)

3: < (b, c)

4: and (^2, ^3)

5: or (^1, ^4)

6: if (^5, ^9)

7::= (a, 0)

8: jmp (1, ^10)

9::= (a, 1)

Если же использовать свойства булевой алгебры, то можем получить следующий фрагмент последовательности триад:

1: < (a, b)

2: if01 (^3, ^7)

3: < (a, c)

4: if01 (^9, ^5)

5: < (b, c)

6: if01 (^9, ^7)

7::= (a, 0)

8: jmp (1, ^10)

9::= (a, 1)

Триада условного перехода IF01 здесь имеет следующий смысл: IF01(<операнд1>, <операнд2>) передает управление на триаду, указанную первым операндом, если предыдущая триада имеет значение 0 («Ложь»), иначе – передает управление на триаду, указанную вторым операндом.

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

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

if (a

функция F1 не будет вызвана, если выполняется условие a < b, а это уже принципиально важно.

Еще один пример:

if (a>0 and M[a]<>0) M[a]:=0;

также показывает преимущества второго варианта порождения кода. Если для этого фрагмента построить код по первому варианту, то вычисление выражения M[a] <> 0 может привести к выходу за границы массива M и даже к нарушению работы программы при отрицательных значениях переменной a, хотя в этом нет никакой необходимости – после того как не выполняется условие a>0, проверяющее левую границу массива M, нет надобности обращаться к условию M[a] <> 0. При порождении кода по второму варианту этого не произойдет, и данный оператор будет выполняться корректно.

Для того чтобы порождать код по второму варианту, схема СУ-перевода для логических операций и операций сравнения должна зависеть от вышележащих узлов синтаксического дерева – от вышележащих узлов ей в качестве параметров должны передаваться адреса передачи управления для значений «истина» и «ложь». Будем считать, что рассмотренные далее схемы СУ-перевода получают на вход два аргумента: адрес передачи управления для значения «истина» – А1 и адрес передачи управления для значения «ложь» – А2.

Схема СУ-перевода для операций сравнения будет выглядеть следующим образом:

1. Порождается блок кода для операции сравнения по схеме СУ-перевода для линейной операции.

2. Порождается триада IF01, первый аргумент которой – адрес А2, а второй аргумент – адрес А1.

Схема СУ-перевода для операции AND будет выглядеть следующим образом:

1. Порождается блок кода № 1 для первого операнда. Для этого рекурсивно вызывается функция порождения кода для первой нижележащей вершины, в качестве первого аргумента ей передается адрес блока кода № 2, а в качестве второго аргумента – адрес А2.

2. Порождается блок кода № 2 для второго операнда. Для этого рекурсивно вызывается функция порождения кода для третьей нижележащей вершины, в качестве первого аргумента ей передается адрес А1, а в качестве второго аргумента – адрес А2.

Схема СУ-перевода для операции OR будет выглядеть следующим образом:

1. Порождается блок кода № 1 для первого операнда. Для этого рекурсивно вызывается функция порождения кода для первой нижележащей вершины, в качестве первого аргумента ей передается адрес А1, а в качестве второго аргумента – адрес блока кода № 2.

2. Порождается блок кода № 2 для второго операнда. Для этого рекурсивно вызывается функция порождения кода для третьей нижележащей вершины, в качестве первого аргумента ей передается адрес А1, а в качестве второго аргумента – адрес А2.

Схема СУ-перевода для операции NOT будет выглядеть следующим образом:

Порождается блок кода для единственного операнда. Для этого рекурсивно вызывается функция порождения кода, в качестве первого аргумента ей передается адрес А2, а в качестве второго аргумента – адрес А1 (аргументы меняются местами).

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

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

Для условных операторов генерация кода может выполняться в следующем порядке:

1. Порождается блок кода № 1, вычисляющий логическое выражение, находящееся между лексемами if (первая нижележащая вершина) и then (третья нижележащая вершина). Для этого должна быть рекурсивно вызвана функция порождения кода для второй нижележащей вершины, в качестве первого аргумента ей передается адрес блока кода № 2, а в качестве второго аргумента – адрес блока кода № 3 (для полного условного оператора) или адрес конца оператора (для неполного условного оператора).

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

3. Для полного условного оператора порождается команда безусловного перехода в конец оператора.

4. Для полного условного оператора порождается блок кода № 3, соответствующий операциям после лексемы else (пятая нижележащая вершина) – для этого должна быть рекурсивно вызвана функция порождения кода для шестой нижележащей вершины (оба аргумента нулевые).

Генерация кода для цикла с предусловием выполняется в следующем порядке:

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

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

3. Порождается команда безусловного перехода в начало блока кода № 1.

Современные компиляторы порождают различный код для логических операций:

• для побитовых операций порождается код как для линейных операций;

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

Например, в языке Object Pascal код, порождаемый для операций and, or, xor и not, зависит от типов операндов (являются ли они логическими или целочисленными), а в языках C и C++ логические и побитовые операции даже обозначаются разными знаками операций. При этом в современных компиляторах существует команда, позволяющая разработчику отключить порождение «сокращенного» кода (обычно она называется «Complete Boolean evaluations») – тогда для всех логических выражений порождается полный линейный код.

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

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

Совет.

Желающие могут попробовать свои силы в порождении эффективного кода для логических операций на основе предложенных выше схем СУ-перевода и имеющихся в приложении 3 структур данных и функций. Реализация такого подхода рассматривается как дополнительный бонус для выполняющего курсовую работу студента (по согласованию с преподавателем).

Генерация кода для сокращенного вычисления логических выражений подробно рассмотрена в [2]Программные модули, реализующие таблицы символов, построены таким образом, что в зависимости от условий компиляции они могут либо различать, либо не различать прописные и строчные буквы. Условие компиляции реализовано через макрокоманды компилятора Delphi 5 в функции Upper в модуле TblElem (листинг П3.1, приложение 3). О принципах, на основе которых выполняются макрокоманды и условная компиляция, можно подробно узнать в [7, 13, 23, 25, 28, 32].
.

Реализация генератора триад

Все возможные типы триад перечислены в модуле TrdType (листинг П3.8, приложение 3).

Структуры данных, использованные в лабораторной работе № 4, не зависят от входного языка. Поэтому имеет смысл использовать их для генерации триад в курсовой работе. Эти структуры данных описаны в модуле Triads (листинг П3.10, приложение 3).

Генератор триад также реализован на базе модуля, который был использован для генерации триад в лабораторной работе № 4. В данный модуль были внесены изменения в соответствии с изменившимся синтаксисом входного языка, добавлены новые линейные операции (арифметические операции и операции сравнения), а также добавлена реализация схемы СУ-перевода для оператора цикла (которая была представлена на рис. 5.2).

Для проверки заданных семантических ограничений в генератор триад добавлены следующие проверки:

• при определении имени операнда любой линейной операции проверяется, что имя не совпадает с недопустимым именем «Result»;

• при определении имени операнда операции присваивания проверяется, что имя не совпадает с недопустимыми именами «InpVar» и «Result».

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

Текст полученного программного модуля TrdMake приведен в листинге П3.12, приложение 3.

Генератор ассемблерного кода

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

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

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

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

Например, последовательности операторов:

d:= a + b + c;

с:= d *(a + b);

a:= d *(a + b) + 1;

будет соответствовать последовательность триад:

1: + (a, b)

2: + (^1, c)

3::= (d, ^2)

4: * (d, ^1)

5::= (с, ^4)

6: + (^4, 1)

7::= (a, ^6)

Область действия для каждой триады в этой последовательности показана на рис. 5.3.

Если отбросить триады, область действия которых не распространяется дальше одной триады (как было сказано выше, для них не требуется хранение промежуточных результатов), то по рис. 5.3 видно, что для данной последовательности триад достаточно одной временной переменной, в которую сначала необходимо занести значение триады № 1, а затем – значение триады № 4. Если пользоваться рассмотренным ранее алгоритмом, то потребовалось бы как минимум две временных переменных.

Рис. 5.3. Области действия триад в списке триад.

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

Именно такой алгоритм распределения временных переменных и регистров реализован в функции MakeRegisters в модуле TrdAsm. Эта функция просматривает список триад с конца и распределяет регистры по порядку начиная от первого упоминания каждой триады. Номер закрепленного регистра записывается в информационное поле каждой триады (если это поле равно 0, считается, что нет необходимости хранить промежуточный результат вычисления триады). Минимальная граница области действия триады, в пределах которой регистр не может быть распределен повторно, запоминается в специальном списке регистров (в функции этот список представлен переменной listReg). Количество регистров, упомянутых в нем, и будет равно необходимому количеству регистров для вычисления списка триад.

Генератор ассемблерного кода ориентирован на процессоры типа Intel 80386 и более поздних модификаций в защищенном режиме работы. В этом режиме в процессоре доступно шесть регистров общего назначения по 32 бит каждый [41, 44]:

• еах;

• ebx;

• есх;

• edx;

• esi;

• edi.

Регистр esp используется как указатель стека, а регистр ebp – как базовый указатель стека (хранение временных переменных в стеке с использованием двух регистров описано в разделе, посвященном организации дисплеев памяти процедур и функций в [2, 3, 7]).

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

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

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

Для выполнения всех операций и хранения их результатов в пределах одной триады будем использовать регистр аккумулятора – eax. Кроме того, что это наглядно и удобно, в процессорах серии Intel 80x86 некоторые команды с этим регистром занимают меньше памяти и выполняются быстрее, чем команды с другими регистрами (а в ряде команд этот регистр является единственно возможным) [41, 44].

Порождение ассемблерного кода по списку триад выполняется функцией MakeAsmCode из модуля TrdAsm (листинг П3.13, приложение 3).

Для унарных линейных операций последовательность действий при генерации ассемблерного кода такова:

1. Запоминается имя операнда. Для переменных именем операнда является имя переменной, для константы – значение константы, а для ссылки на другую триаду, кроме предыдущей, – имя регистра или временной переменной, в которой хранится результат вычисления триады (для предыдущей триады имя операнда пустое).

2. Если имя операнда не пустое, то операнд надо загрузить в регистр eax. Для этого порождается команда mov, но если операнд – результат вычисления предыдущей триады (имя операнда пустое), то загружать в eax его не нужно, так как он уже находится там после вычисления триады, и никакая команда на этом шаге не порождается.

3. Порождается команда, соответствующая унарной операции над регистром eax (в данном результирующем языке: not – для логического отрицания; neg – для унарного арифметического минуса).

4. Если одной команды недостаточно, порождается еще одна команда (в данном случае для логического отрицания требуется еще команда and).

5. Если для триады требуется сохранить промежуточный результат, порождается команда mov, которая сохраняет результат из регистра eax в регистр или временную переменную, связанную с триадой.

Для бинарных линейных операций последовательность действий при генерации ассемблерного кода такова:

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

2. Если имя одного из операндов пустое (операнд получен при вычислении предыдущей триады), то нет необходимости загружать его в регистр eax, иначе порождается команда mov, которая загружает первый операнд в регистр eax.

3. Порождается команда, соответствующая бинарной операции над регистром eax. Если имя второго операнда пустое, то первый операнд триады становится вторым операндом команды, иначе – второй операнд триады становится вторым операндом команды.

4. Если одной команды недостаточно, порождается еще одна (в данном результирующем языке это необходимо только для команды вычитания sub в том случае, если операнды менялись местами – чтобы получить верный результат, требуется еще команда neg).

5. Если для триады требуется сохранить промежуточный результат, порождается команда mov, которая сохраняет результат из регистра eax в регистр или временную переменную, связанную с триадой.

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

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

Для триад присваивания значений и для триад безусловного перехода (JMP) порождение команд элементарно просто и не требует пояснений.

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

1: < (a, b)

можно построить по

mov eax, a

cmp eax, b

jl @M1_1

xor eax, eax

jmp @M1_2

@M1_1: xor eax, eax

inc eax

@M1_2:

которая будет обеспечивать запись в регистр аккумулятора (eax) логического результата операции сравнения (0 – «ложь», 1 – «истина»).

Однако, как уже было сказано, большое количество операций передачи управления не способствует эффективности выполнения программы. К тому же рассмотренный выше подход порождает много лишних команд. Как правило, в процессорах есть команды, позволяющие организовать либо прямой обмен между регистром флагов и регистром аккумулятора, либо обмен данными через стек. В процессорах типа Intel 80x86 это команды группы set<*>, где <*> зависит от необходимого флага [41, 44]. Тогда для того же самого примера порядок команд будет иным:

mov eax, a

cmp eax, b

setl al

and eax, 1

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

Еще несколько слов необходимо сказать о триаде условного перехода IF. Для нее ситуация иная, чем для операций сравнения – чтобы выполнить условный переход, надо установить регистр флагов на основе регистра аккумулятора. Для этого можно воспользоваться простейшей командой процессора для сравнения регистра аккумулятора с ним самим, например:

test eax, eax

однако эффективность результирующего кода можно увеличить, если учесть, что триаде IF всегда предшествует либо триада сравнения, либо триада логической операции, а следовательно, при выполнении кода, порожденного для этих триад, флаги уже будут установлены соответствующим образом. Тогда нет необходимости порождать дополнительную команду для установки флагов и для триады IF достаточно построить только команду условного перехода по флагу «ноль» (в процессорах типа Intel 80x86 это команда jz).

Но система команд процессоров типа Intel 80x86 имеет одну особенность: команды условного перехода могут передавать управление не далее, чем на 128 байт вперед или назад от места команды. В момент генерации кода для триады IF, как правило, не известно, будет ли передача управления происходить в пределах 128 байт кода или выйдет за рамки данного ограничения. Чтобы обойти это ограничение, передачу управления можно организовать с помощью двух команд: сначала команда условного перехода по обратному условию «не ноль» передает управление на локальную метку, а потом команда безусловного перехода передает управление на требуемую «дальнюю» метку:

jnz @Fx

jmp @Mx

Fx:…

Здесь @Fx – локальная («обходная») метка, а @Mx – та метка, на которую необходимо передать управление. Именно такой подход реализован в разработанном генераторе ассемблерного кода.

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

a:= 1;

if (a<0) b:=0 else b:=1;

первая часть условного оператора (b:=0) никогда не будет выполнена и в результате выполнения оптимизации это станет очевидным (первый операнд триады IF будет равен 0). Генератор ассемблерного кода порождает соответствующий код: если первый операнд равен 0 – команду безусловного перехода; если первый операнд не равен 0, никаких команд для триады IF вообще не порождается.

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