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