Алгоритм Дейкстри.

Алгоритм Дейкстри. Введення приорітету операцій

Операційя	Приорітет
(	0
)	1
+-	2
*/	3

Проглядають вхідний потік з ліва на право і операнди переписують в результуючий рядок, а знаки операцій заносять в стек на основі наступних правил:

1. Якщо стек порожній то операція з вхідного рядка переписується в стек

2. Операція виштовхує зі стека всі операції з більшим або рівним приорітетом у вхідний рядок

3. Якщо зустрічається права дужка, вона пишеться в стек

4. Права дужка виштовхує всі операції зі стека до найближчої лівої дужки і знищують одна одну.

Асемблерний код або машинні команди.

Машинні команди зручні тим, що при їх використанні внутрішнє представлення програми повністю відповідає об’єктному коду і складні перетворення не потрібні. Команди асемблера являють собою тільки форму запису машинних команд, а тому в якості форми внутрішнього представлення програми практично нічим не відрізняються від них.

Але використання команд асемблера або машинних команд для внутрішнього представлення програми вимагає додаткових структур для відображення взаємозв’язку операцій. В цьому випадку внутрішнє представлення програми буде залежати від архітектури обчислювальної системи, на яку орієнтований результуючий код. Значить, при орієнтації компілятора на інший результуючий код необхідно перебудовувати як саме внутрішнє представлення програми, так і методи його обробки.

Але – машинні команди, це мова, на якому повинна бути записана результуюча програма. Тому компілятор так або інакше повинен працювати з ними. Крім того, тільки опрацьовуючи машинні команди, можна досягнути найбільш ефективної результуючої програми. Тому, довільний компілятор працює з представленням результуючої програми в формі машинних команд, але обробка виконується, як правило, на останніх етапах генерації коду.

Розбір арифметичного виразу. Алгоритм Рутисхаузера.

Алгоритм Рутисхаузера является одним из наиболее ранних алгоритмов разбора выражений. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявный приоритет операций при этом не учитывается. Например: D:=((C-(B*L))+K)

Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему правилу:

• если это открывающаяся скобка или переменная, то значение увеличивается на 1;

• если знак операции или закрывающаяся скобка, то уменьшается на 1.

Для выражения (А+(В*С)) присваивание значений уровня будет происходить следующим образом :

N симв.	1	2	3	4	5	6	7	8	9
Символы строки	(	A	+	(	B	*	C	)	)
Номера уровней	1	2	1	2	3	2	3	2	1

Алгоритм складывается из следующих шагов:

• выполнить расстановку уровней;

• выполнить поиск элементов строки с максимальным значением уровня;

• выделить тройку — два операнда с максимальным значением уровня и операцию, которая заключена между ними;

• результат вычисления тройки обозначить вспомогательной переменной;

• из исходной строки удалить выделенную тройку вместе с ее скобками, а на ее место поместить вспомогательную переменную, обозначающую результат, со значением уровня на единицу меньше, чем у выделенной тройки;

• выполнять п.п.2 — 5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.