Текст книги "Системное программное обеспечение. Лабораторный практикум"

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

Для построения синтаксического анализатора будем использовать анализатор на основе грамматик операторного предшествования. Этот анализатор является линейным распознавателем (время анализа линейно зависит от длины входной цепочки), для него существует простой и эффективный алгоритм построения распознавателя на основе матрицы предшествования [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 О, а в множество крайних правых терминальных символов R_t(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 к виду операторного предшествования – читатели могут попробовать в этом свои силы самостоятельно). Если других препятствий нет, то, с точки зрения автора, первый вариант предпочтительнее (лучше изменить синтаксис входного языка и упростить свою работу).[9]9
  Создатели реальных компиляторов, конечно же, лишены первого из предлагаемых вариантов – синтаксис входного языка для них строго определен и не может меняться, поэтому они вынуждены искать преобразования грамматик.


[Закрыть]

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

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

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

• во-вторых, конец логического выражения в условии после ключевых слов 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<b or a<c and b<c) a:=0 else a:=1;

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

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<b or F1(a)<c and b<c) a:=0 else a:=1;

функция 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. Порождается триада IF01, первый аргумент которой – адрес А₂, а второй аргумент – адрес А₁.

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

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

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

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

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

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

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

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

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


[Закрыть]

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

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

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].

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

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

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

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

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

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

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

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

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

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

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