Все внутренние формы представления программ в трансляторе содержат элементы 2 видов:
-операторы
-операнды
Операторы задают выполняемые действия, и в простейшем случае могут рассматриваться как знаки выполняемых операций.
Операнды – это переменные, константы, промежуточные данные, формируемые транслятором, переменные с индексом и другие данные над которыми выполняются соответствующие операторы.
В результате семантического анализа формируется программа, эквивалентная исходной программе и представленная во внутренней форме, удобной для дальнейшей оптимизации.
1. Семантическое дерево, 2 польская запись, 3 список тетрад.
1. Семантическое дерево (СД) – модифицированное дерево грамматического разбора из которого исключили вершины соответствующие нетерминальным символам. Листья СД соответствуют операндам, а вершины операторам. Расположение операторов по уровням дерева определяет порядок их выполнения.
СД удобно использовать для описания выражений и операторов их использующих.
Пример:
E→E+T / T
T→T*M / M
M→(E) | a | b| c
a+b*c
Дерево разбора:
При построении СД скобки не требуются т.к. порядок выполнения операций определяется структурой дерева. Таким образом если дерево разбора показывает порядок вывода цепи языка из начальных символов (синтаксис предложения), то СД отражает только порядок выполнения операторов над заданными операндами (семантика предложения).
2. Польская запись.
Просто и однозначно указывает порядок выполнения операторов.
Основные свойства:
1. не требует скобок;
2. оператор располагается непосредственно за своими операндами;
3. операторы следуют в том порядке, в котором они должны быть выполнены;
4. операнды следуют в том же порядке, что и в исходной записи.
Пример: 1) a+b – инфиксная форма записи; ab+ – польская запись (постфиксная).
2) a+b*c – инфиксная форма записи, abc*+ – польская запись.
Формально построение польской записи описывается следующим грамматическим правилом:
<операнд>::=<константа>|<идентификатор>|
<операнд><операнд><оператор>
<оператор>::=+ | – | * | / | …
Если должны быть учтены операторы с одним операндом, то грамматическое правило должно быть расширено с учётом введения таких операторов (добавляется бинарный и унарный оператор).
Замечание. Если оператор расположен перед своим операндом, то получается префиксная форма записи: +a*bc.
Указанная форма записи может быть получена по СД. Для этого используют рекурсивную процедуру обхода СД в заданном порядке. Для получения постфиксной формы дерево обходят снизу в порядке LRT. Для получения префиксной формы дерево обходят сверху в прядке TLR.
3. Списки тетрад. Удобной формой представления бинарных операций являются тетрады вида:
(<оператор>, <операнд1>, <операнд2>, <результат>)
A+B*C–D
(*, B, C, T1)
(+, A, T1, T2)
(–, T2, D, T3)
T1, T2, T3 –временные переменные формируемые транслятором.
Важным свойством списка тетрад является то, что тетрады располагаются строго в соответствии с порядком в котором должны быть выполнены операторы при реализации программы. При этом оператор с одним операндом может быть представлен в виде тетрад. Некоторые элементы тетрад остаются пустыми: «–A» – изменение знака (–, A, , T1), «A:=B» – (:=, B, , A).
Аналогично вводят тетрады описывающие переходы программ.
(JML, <метка>, , )
(JM, <адрес>, , )
(<оператор>, <адрес>, <условие>, )
Пример: (JMP, <адрес>, R, ) – переход на адрес если R>0;
В случае тетрад под адресом понимается номер тетрад заданной в списке.
Фрагмент программы в тетрадной форме:
1: (–, I, J, T1)
2: (JMP, <6>, T1, )
3: (+, K, 1, T2)
4: (:=, T2, , K)
5: (JMP, <7>, , )
6: (JML, M1, , )
7: (*, B, K, T3)
8: (:=, T3, , A)
Исходники:
|
Главная
Каталог файлов
