|
|
Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции
Промежуточные языки трансляции: обратная польская запись, тетрады, триады
Таким образом, были рассмотрены некоторые методы грамматического разбора, которые позволяют проверить синтаксическую корректность входной программы. Также в трансляторах имеются специальные процедуры проверки семантики входного предложения (т.е. его смыслового содержания). Например, проверку наличия в процедуре, которая должна возвращать некоторое значение, оператора return(X), а не просто return нельзя описать грамматикой. Механизма таких процедур проверки мы касаться не будем (обычно стремятся с помощью грамматик описать не только синтаксис, но и семантику языка, например, вводя дополнительные нетерминальные символы). Кроме этого на этапе синтаксического анализа должен быть выполнен перевод программы на некоторый промежуточный язык трансляции.
Перевод исходной программы на промежуточный язык трансляции осуществляется с целью обеспечить, в дальнейшем, возможность перевода программы в объектный вид на язык машинных команд за однократный просмотр программы на промежуточном языке.
Пусть, например, исходная программа содержит оператор:
a = (b + c / d) * (e – f);
который в процессе компиляции должен быть переведен на язык машинных команд. Этот оператор включает в себя следующие операции:
’=’ (присваивание), ’+’, ’/’, ’*’, ’-’.
Однако, с учетом приоритета операций и наличия скобок, эти операции должны выполняться в другой последовательности:
’/’, ’+’, ’-’, ’*’, ’=’.
Требуемая последовательность выполнения операций может быть определена в ходе синтаксического анализа программы. И, чтобы исключить повторный анализ программы в процессе перевода отдельных операций на язык машинных команд, сама программа преобразуется в такой вид, который позволяет генерировать команды в процессе однократного просмотра программы строго в последовательности от начального к конечному символу.
Известны несколько промежуточных языков трансляции: тетрады, триады, косвенные триады и, наиболее распространенная при разработке компиляторов, – обратная польская запись (предложена польским математиком Лукашевичем).
Обратная польская запись представляет собой бесскобочную запись, которая строится по следующим правилам:
операнды в обратной польской записи следуют в том же порядке, как и в обычной (инфиксной) записи;
операторы следуют в том же порядке, как они должны выполняться;
операторы располагаются непосредственно за своими операндами, при этом операндом может являться как операнд инфиксной записи, так и результат какой-либо операции.
Например:
a*(b+c/d) => abcd/+*
(a+b)/(c-d) => ab+cd-/
(ae => ab&
c=-a+b/(c-d) => ca-bcd
/+=
В последнем примере необходимо отметить:
в польской записи следует различать бинарный минус (двуместную операцию) и унарный минус (одноместную операцию, обозначен
). При переводе программы необходимо распознавать вид операции и заносить в польскую запись различные коды для этих операций;
операция = является примером операции, которая не порождает результат.
Следует также отметить, что набор операций в промежуточных языках трансляции отнюдь не совпадает с операциями конкретных языков программирования (, обращение к функции и т.п.).
Другим промежуточным языком трансляции являются тетрады, которые имеют вид: (<операция>, <операнд>, <операнд>, <результат>)
Например, A*B представляется в виде (*, A, B, U), где U – некоторая рабочая переменная, в которую помещается результат.
Если операция имеет один операнд, то поле второго операнда остается пустым. Также пустым может быть и поле результата, если операция не порождает результат.
Недостатком тетрад является большое количество используемых рабочих переменных. Эта проблема отпадает при использовании триад следующего формата: (<операция>, <операнд>, <операнд>)
В триаде нет поля для результата. Если в какой-либо триаде операндом является результат операции из другой триады, то в нее помещается ссылка на эту триаду.
Обратная польская запись наиболее часто используется в качестве промежуточного языка трансляции.
Преимущество польской записи над тетрадами и триадами в возможности использовать операции с переменным количеством операндов.
Основные операции обратной польской записи. Представление операторов ветвления программ в обратной польской записи
Общее количество операций обратной польской записи для алгоритмического языка составляет несколько десятков. Рассмотрим некоторые основные операции:
арифметические операции (+, –, (унарный минус), *, /, % и т.п.);
логические операции и операции сравнения;
операция присваивания;
вычисление адреса элемента массива, имеющая m+1 операнд, где m – размерность массива. Будет обозначаться k], где k – количество операндов (k=m+1);
операция вызова функции, имеющая m+1 операнд, где m – количество параметров функции. Будет обозначаться kФ, где k – количество операндов (k=m+1);
операции перехода: <метка>БП – безусловный переход;
<логическая переменная><метка>УПЛ – переход по лжи (если логическая переменная или результат выражения имеет значение ложь). Место метки в программе отмечается операцией <метка>:.
Примеры перевода в обратную польскую запись выражений и операторов:
a*(-b+c/d)  a b c d / + *
(ac) && d>e a b < b c > || d e > &&
y=-f(a/b,x[i][j]) y f a b / x i j 3] 3Ф =
Перевод в обратную польскую запись условного оператора:
if (L) A; L m1 УПЛ A m1:
if (L) A; else B; L m1 УПЛ A m2 БП m1: B m2:
Например:
if (a
a b x * < m1 УПЛ x y a * = m2 БП m1: x y a / = a b a / = m2:
Операторы цикла.
1. Оператор while для языка С
while (L) A; m1: L m2 УПЛ A m1 БП m2:
Например:
while (a m1: a b < m2 УПЛ a b 2 + = m1 БП m2
2. Оператор for для языка С
for (A; L; B) C; A m1:L m2 УПЛ m3 БП m4: B m1 БП m3: C m4 БП m2:
└─┘└───────────────┘└──────────┘└───-──────┘
A L B C
В качестве примера рассмотрим программу определения значения и номера максимального элемента в массиве положительных чисел с использованием цикла for:
s = 0;
for (i = 0; i < n; i++)
if (s < d[i]) { s = d[i]; j=i; }
В обратной польской записи программа имеет вид:
s 0 =
i 0 = m1: i n < m2 УПЛ m3 БП m4: i i 1 + = m1 БП
m3: s d i 2] < m5 УПЛ s d i 2] = j i = m5: m4 БП m2:
|
|
|
Скачать 0.64 Mb.