Л.Е. Карпов - Системы программирования (1114903), страница 10
Текст из файла (страница 10)
В частности,••••имена локальных объектов блоков дополняются именами блоков (функций,процедур), в которых они описаны,имена внутренних (в терминах языка Си++ – статических) переменных ифункций модулей программы дополняются именами самих этих модулей,имена процедур и функций, принадлежащих классам в объектноориентированных языках (Си++) или вложенных в другие процедуры ифункции в процедурных языках дополняются именами этих классов илипроцедур,имена методов в описаниях классов дополняются именами, строящимися взависимости от числа и типов их формальных параметров, это же относитсяи к именам перегруженных функций Си++.Особой заботой компиляторов являются имена внешних (глобальных) объектов,которые остаются видимыми в объектной программе и могут обрабатываться другимикомпонентами систем программирования, например, редакторами связей.
Для такихимен в конкретных системах программирования могут существовать собственныесоглашения именования. Такие имена должны быть уникальными на уровне библиотек,в которые они могут попадать после завершения компиляции.363.3.3. Внутреннее представление программДополнительную сложность задаче компиляции придает тот факт, что из-засерьезных различий между входным и выходным языками провести непосредственноепреобразование из одного языка в другой не всегда представляется возможным. Дажесинтаксический анализ исходного текста приходится делать поэтапно, разбивая его налексическую и собственно синтаксическую часть. Это позволяет использовать накаждом этапе свои грамматические правила разбора, существенно упрощая реализациюраспознавателей, применяемых на этих этапах.
Именно поэтому часто в компиляторахна некоторых стадиях обработки программ возникает некоторое промежуточноевнутреннее представление компилируемой программы, которое лишь на завершающейстадии преобразуется в представление программы на выходном языке компилятора.К основным свойствам языков внутреннего представления программ можноотнести такие:•••языки внутреннего представления позволяют фиксировать синтаксическуюструктуру исходной программы;текст на языках внутреннего представления можно автоматическигенерировать во время синтаксического анализа;конструкции языков внутреннего представления должны относительнопросто транслироваться в объектный код, либо достаточно эффективноинтерпретироваться.Легче всего синтаксическому анализатору организовать внутреннее (а для себя –выходное) представление в виде дерева синтаксического разбора.
Однако дереворазбора содержит огромное количество избыточной информации: в нем присутствуютдаже нетерминальные символы, не несущие никакой полезной информации. Чтодолжно присутствовать во внутреннем представлении – это операторы и операндыисходной программы, записанные в более удобной для последующей обработки форме.Удобство это заключается, прежде всего, в том, чтобы было легко отличить оператор отоперанда, в каком бы порядке они друг за другом ни следовали.
В основе каждого извидов внутреннего представления программ лежит некоторый метод представлениясинтаксического дерева. В реальных компиляторах применяются следующиеобщепринятые способы внутреннего представления программ:•••••••связные списочные структуры, представляющие синтаксическое дерево;многоадресный код с явно именуемыми результатами (тетрады – оператор,операнд, операнд, результат);многоадресный код с неявно именуемыми результатами (триады – оператор,операнд-результат, операнд), иногда этот способ представлениямодифицируется и используется последовательность косвенных триад (самитриады хранятся в отдельной таблице, формируемая программа представляетсобой последовательность ссылок на таблицу);инфиксная запись (операции записываются между своими операндами, как вобычной записи арифметических выражений);префиксная запись (операции записываются перед своими операндами, как взаписи вызова процедуры или функции с параметрами);постфиксная запись (операции записываются после своих операндов);язык ассемблера целевой или абстрактной машины.37В одном компиляторе может использоваться любая из этих форм, обычновыбираются несколько разных видов внутреннего представления программ для разныхстадий компиляции.
Если от компилятора не требуется проведения серьезнойоптимизации программ, выбирается схема, в которой синтаксический разбор,семантический анализ и генерация объектной программы совмещены в одном проходекомпилятора. В такой схеме внутреннее представление программы существует толькона концептуальном уровне, выражаясь только в последовательности шаговпреобразований.Связные списочные структуры. Списки – это структуры представленияпрограмм, которые можно наиболее просто и эффективно строить на этапесинтаксического анализа. Обычно списки используются для представлениясинтаксических деревьев – таких структур, вершинами которых являются операции, алистьями – операнды.
Как правило, листья связаны с записями в таблицахидентификаторов и констант. Структура синтаксических деревьев наиболее точноотражает синтаксис языка программирования, на котором была написана исходнаяпрограмма. Обычно перед построением синтаксических деревьев в грамматиках языкаизбавляются от цепных правил вида A → B, где A и B –нетерминальные символы.В тех случаях, когда синтаксическому дереву соответствует последовательностьопераций, порождающая в результате команды объектной программы, такое деревоназывают деревом операций. Дерево операций строится непосредственно иавтоматически из дерева вывода, порождаемого синтаксическим анализатором.
Дляэтого из него удаляются цепочки нетерминальных символов, а также узлы, не несущиесемантической нагрузки при генерации объектной программы (например, скобки,меняющие порядок операций):=–AПредставлениеарифметическоговыражения языка Си++A = B * C + D – B * 10в виде дерева операций(один из возможныхвариантов)+*B*CDB10Грамматика исходного языка не имеет никакого влияния на то, какой узел вдереве будет операцией, а какой операндом. Влияние на это имеет не синтаксис, асемантика языка программирования.38Деревом операций обычно пользуются на внутренних стадиях компиляции,предшествующих генерации объектной программы. Оно отражает общую структурупрограммы и связь операций между собой.
Имея представление программы в видедерева, удобно проводить преобразования, связанные с перестановкой фрагментовпрограммы и переупорядочением операций. Многие оптимизирующие компиляторывыбирают именно древовидные структуры для внутреннего представления программ.Недостатком деревьев является сложность их преобразования в линейнуюпоследовательность команд объектной программы.Многоадресный код с явно именуемым результатом (тетрады).
Тетрадыпредставляют собой запись операций в форме четырех составляющих: операции, двухоперандов и результата операции:<операция>(<операнд1>,<операнд2>,<результат>)Тетрады составляют линейную последовательность команд, как в следующейзаписи арифметического выражения A=B*C+D–B*10 в виде последовательноститетрад:1 *2 +3 *4 5 =BT1BT2T4CD10T3?T1T2T3T4AПри вычислении выражения, записанного в форме тетрад, они вычисляютсяпоследовательно одна за другой, без каких-либо приоритетов. Если какой-то изоперандов (или оба) в тетраде отсутствует (как в унарной операции), он заменяетсяпризнаком пустого операнда.
Результат тетрады никогда опущен быть не может.Порядок вычисления тетрад может быть изменен только явно с помощью специальныхтетрад, вызывающих переходы по последовательности тетрад вперед или назад.Тетрады записываются в линейной последовательности, поэтому их легкопреобразовать в последовательность команд объектной программы, либо в языкассемблера, но в отличие от языка ассемблера, тетрады не зависят от архитектурывычислительной системы, для которой ведется компиляция, и являются машиннонезависимым представлением программ.
Некоторые сложности при работе с тетрадамимогут возникать потому, что у вычислительных машин редко встречаютсятрехадресные системы команд.Многоадресный код с неявно именуемым результатом (триады). Триадыпредставляют собой запись операций в форме из трех составляющих: операции и двухоперандов:<операция>(<операнд1>,<операнд2>)Особенностью триад является то, что один или оба операнда в триаде могутбыть ссылками на другую триаду в том случае, если в качестве операнда даннойтриады выступает результат выполнения другой триады, например, так в виде триадможно записать арифметическое выражение A=B*C+D–B*10:123*+*B^1BCD103945=^2A^3^4Ссылка на триады в реальных компиляторах обычно реализуется настоящимуказателем, что делает триады списочной структурой и облегчает процессыпреобразования триад.
Тем самым, назвать триады полностью линейной структуройнельзя. В то же время триады можно рассматривать и как линейнуюпоследовательность, если результаты вычислений операций триад хранить во временновыделяемой памяти. Такое свойство триад приводит к необходимости использования вкомпиляторах специальных алгоритмов распределения памяти для храненияпромежуточных результатов, поскольку в отличие от тетрад, какие-либо явныевременные переменные в триадах не используются.Триады требуют меньше памяти для представления программ и имеют в этомпреимущество перед тетрадами, к тому же триады ближе к двухадресным машиннымкомандам, чем тетрады, поэтому их легче преобразовывать к окончательному видуобъектной программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
