Файл: Богданов В.С. Системы математического обеспечения цифровых вычислительных машин учеб. пособие.pdf

- н о -

принимает в качестве входной информации,закодированное і.^сд-

стаэление исходной информации на входном языке иг как выходную информацию выдает рабочую программу.

Процесс преобразования программы на входном языке сос­ тоит из следующих этапов:

1)распознавание в закодированном представлении исход­ ной программы различных составляющих входного языка,

2)анализ структуры программы,

3)установление .связи между используемыми идентификато­ рами и их описаниями,

4) преобразование арифметических выражений.

Все методы анализа структуры текста входного языка мож­ но разбить на две группы: прямые и синтаксические. Прямые ме­

тоды основываются на понятии основного символа входного язы­ ка. В синтаксических методах трансляции синтаксической едини­ це программы соответствует прямо некоторая часть транслятора.

использовании магазинной памяти, которая обладает свойством "последнее записанное - первое считаннее", Магазинная память используется как средство сохранения промежуточной информа­ ции до - момента, как будет закончен перевод. Зта храни­ мая информация является некоторым представлением основных

- x i i —

символов входного языка. Основное свойство магазинной памяти используется для анализа скобочной структуры программы. 3 слу­ чае АЛГОЛа это основное свойство— "последнее.записанное

ких выражений.

Процесс трансляции управляется так называемой' матрицей переходов; столбцы и строки этой матрицы переходов соответст­ вуют различным ограничителям АЛГОЛа., Элементы этой матрицы определяют соответствующие действия, которые должен выполнить транслятор.

Оонову других аналогичных трансляторов составляет таб­ лица "следующего оператора" в зависимости от текущего опера­ тора. Эта таблица используется для выбора соответствующего генератора (то есть некоторой программы, которая образует или "генерирует" нужные коды).

3 некоторых трансляторах с каждым ограничителем связа­ но некоторое число, называемое приоритетом. Действия транс­ лятора определяются путем сравнения приоритетов ограничите­ лей.

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

Другуюгруппу составляют синтаксические методы. Они де­ лятся на две подгруппы. В одну входят трансляторы, состоящие из программ, соответствующих синтаксическим единицам, во вто­ рую - трансляторы, которые связывают переводимый текст с скн-

чпсгоаык, состветстчуьцн.. различным синтаксическим единицам,

i-одно вносить поправки в текст на языке и получать соответст­ вующую минимальную программу в кодах без повторной полной трансляции. (Цепной список - это совокупность связанных яче-

памяти, в каждой из которых хранятся информация и адрес следующей ячейки списка).

Транслятор осуществляет перевод программы в три прохода_. Вс Бремя І - г с прохода осуществляется перевод б некоторую оес- ^косочную форму, записанную как цепной список вместе с табли­ цами идентификаторов и констант. Второй проход преобразует этот цепной список в машинные команды, праЕда, еше не привя­ занные к определенному месту в памяти. Третий проход преоб­ разует эта команды в программу, готовую для выполнения.

Далее рассматриваются некоторые основные принципы тран­ сляции арифметических выражений, которые, копію сказать, яв­ ляются основой языков, ориентированных па решение каучнс-те.ѵ- яг чески;: у"ач вычислительного характера.

и з -

s 6. Методы трансляции арифметических выражений

Существующие в настоящее время трансляторы моево разде­

лять на три категории:

а) адгеораические трансляторы, предназначенные для тран­ сляции текстов, записанных на языках типа "автокод". Основ­ ная задача з таких трансляторах - транслирование разданных алгебраических выражений ;

б) операционные трансляторы для языка более сложной структуры, чем автокод. Сни состоят из ояда программ для об- -

работки выражений и опе.'а.озов различных типов. Трансляция,

как правило, осуществляв • я методом сборки;

в) системы интегралы-.ы. трансляции, использутие рекур­

сивное определение структуры операторов и выражений языкое

типа AJiJTCЛ.

Наиболее ранние из описанных методыоазирсв=ились на

многократном просмотре арифметического выражения. При пер­ вом просмотре каждому из операндов, знаков операций и скосок присваивались некоторые номера уровней. Крайний левый элемент

имеет нуль-уровень, который увеличивается на единицу для каж­

дой левов, скоски Сили операнда) и уменьшается на единицу для каждой правой скобки (или знака операции).

- II5 -

(- D * ( E i- F )/ p )

5. ((D ж( ( + F ) //J — H ~rJ

6■( ( / * £ > )- С / ( ( Э х (E + F )/g .

Из этих сегментов формируются триплеты, содержащие номер сег­ мента, знак операции и операнд.

Эти образования имеютвид:

( 1 + , а Ю , + , в) ]

(г, + 0(2, - с у

( з , +,Ф ( У + ,( ;

(4,х,і>)(4,х,3)(4,$);

( , +, 4)(5, Н)(5, +, с);

(& ,x ,2) ( 6y ,s ) .

При определении номера сегмента используется счетчик, который увеличивается в момент просмотра левой скобки. Трип­ леты преобразуется составляюсь, ..тематической программой.

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

Наиболее ранний метод разложения арифметического выра­ жения ка отдельные такты за один просмотр заключается в том, что там, где это возможно, арифметическая операция выполняет­ ся сразу де. Если встречается такой символ, как левая скоб­ ка, то промежуточный результат записывается в память к его модно использовать п о те оораостки подвыражения.

ГТ£ _

- ixü ~

Примет): Еырааекие

а + (3-с)/(/хо)+£

выполняется в такси последовательности

программы выполнения операций выбирается в зависимости от типа встретившихся элементов языка.

Зуаествувт трансляторы, алгоритм работы которых агиводмт к пострсениэ некоторой матрицы (.алгоритмической матрицы?. хаздал строка которой явится з действительности закодирован­ ной трехадресной командой .

Работу транслятора такого типа рассмотрим на примере трансляции выразенпя: '

( С / + D 1) * у г + 2 . 7 6 В + f l 2 + 7 2 ).* K i / z i .

Этому зырзнёниэ после просмотра соответствует матрица: