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

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

Основное правило состоит в следующем: если выражение является примитивным, т. е. не содержит никакой операции, то запомнить его в ячейке и выдать адрес этой ячейки. В противном случае следует
(a)        Создать список Ц и занести в него главную операцию (имеющую наивысший приоритет).
(b)       Проанализировать выражение слева от главной операции. Если оно примитивно, то занести его в L{, иначе запомнить начальный адрес этого подсписка в Ц.
(с). Повторить шаг (Ь) для выражения справа от главной операции.
(d)       Применять основное правило для всех подсписков, пока
они не будут исчерпаны.
(e)        Выдать адрес списка.

Согласно правилам алгебры, главной операцией в данном случае является V. Она первой заносится в список L1 (шаг а). Слева от этой операции находится составное выражение, поэтому формируется новый список L2, начинающийся с операции *—' (шаг Ь). Слева от операции '—' стоит примитивное выражение X, поэтому она помещается в список (шаг Ь). Далее анализируется запись, находящаяся справа от операции '—' (шаг с), и создается список L3 (шаг d). Подобным же образом обрабатывается выражение, стоящее справа от главной операции V, и создается список L4- (шаг d). Все подсписки завершены, так что теперь нужно задать адрес списка для компиляции выражения (шаг е).

Компиляция такого выражения может основываться на списковой структуре. При этом просмотр ведется с начала дерева и продолжается до тех пор, пока не будет найден последний подсписок L4. Элементарная операция преобразуется в объектный код, и результат запоминается в выделенной компилятором ячейке Т4, которая уже присоединена к списку. В ячейке ветвления ссылка на подсписок заменяется ссылкой на Т4 (рис. 9.35 (а)). Аналогичным образом подсписки L3, и L2, а затем и L1 заменяются ячейкой, содержащей результат элементарной операции, представленной на рисунке подсписком (Ь), (с) и (d). После того как список будет исчерпан, значение арифметического выражения окажется в ячейке Т1, а полученная последовательность объектных кодов (команд) будет вычислять это значение.


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Преобразование арифметических выражений в списковые структуры В качестве примера рассмотрим, как арифметическое выражение преобразуется в ветвящийся список, задающий эквивалентную последовательность элементарных операций для компилятора. Основное правило состоит в следующем: если выражение является примитивным, т. е. не содержит никакой операции, то запомнить его в ячейке и выдать адрес этой ячейки. В противном случае следует (a) Создать список Ц и занести в него главную операцию (имеющую наивысший приоритет). (b) Проанализировать выражение слева от главной операции. Если оно примитивно, то занести его в L{, иначе запомнить начальный адрес этого подсписка в Ц. (с). Повторить шаг (Ь) для выражения справа от главной операции. (d) Применять основное правило для всех подсписков, пока они не будут исчерпаны. (e) Выдать адрес списка. Согласно правилам алгебры, главной операцией в данном случае является V. Она первой заносится в список L1 (шаг а). Слева от этой операции находится составное выражение, поэтому формируется новый список L2, начинающийся с операции *—' (шаг Ь). Слева от операции '—' стоит примитивное выражение X, поэтому она помещается в список (шаг Ь). Далее анализируется запись, находящаяся справа от операции '—' (шаг с), и создается список L3 (шаг d). Подобным же образом обрабатывается выражение, стоящее справа от главной операции V, и создается список L4- (шаг d). Все подсписки завершены, так что теперь нужно задать адрес списка для компиляции выражения (шаг е). Компиляция такого выражения может основываться на списковой структуре. При этом просмотр ведется с начала дерева и продолжается до тех пор, пока не будет найден последний подсписок L4. Элементарная операция преобразуется в объектный код, и результат запоминается в выделенной компилятором ячейке Т4, которая уже присоединена к списку. В ячейке ветвления ссылка на подсписок заменяется ссылкой на Т4 (рис. 9.35 (а)). Аналогичным образом подсписки L3, и L2, а затем и L1 заменяются ячейкой, содержащей результат элементарной операции, представленной на рисунке подсписком (Ь), (с) и (d). После того как список будет исчерпан, значение арифметического выражения окажется в ячейке Т1, а полученная последовательность объектных кодов (команд) будет вычислять это значение.