Пред.Страница След.Страница  Раздел Содержание

7.5. Магазин и внутреннее представление функции переходов АТ-преобразователя

Основным компонентом АТ-преобразователя является магазин ( MG ). В процессе работы в нем строится вывод входной программы. При этом инструкции преобразователя записывают в магазин цепочки, состоящие из терминальных и вспомогательных символов, символов действия, атрибутов и ссылок. Каждый такт работы преобразователя заключается в чтении символа, находящегося в вершине магазина и выполнении определенных действий, зависящих от типа прочитанного символа. Для распознавания символов, находящиеся в магазине, необходимо сохранять их тип, поэтому для их представления выберем структуру, состоящую из двух полей: кода типа символа и индекса соответствующей таблицы, определяющего вид символа. Схема такой структуры показана на рисунке 7.3, а значения индикаторов, их кодов и имена соответствующих таблиц приведены в таблице 7.3.

 

 

 

Рис. 7.3 Структура элементов магазина

 

 

Таблица 7.3 Элементы магазина

 

Тип

Код типа

Индекс таблицы

Идентификатор

1

TVR

Число

2

LexTab

Ключевое слово

3

LexTab

Символ

4

Tsym

Вспомогательный

символ

5

Tnterm

Символ действия

6

Tact

Атрибут

7

Tatrib

Ссылка

8

MG

Чтение

9

1/0

 

В качестве базы для программной реализации преобразователя воспользуемся магазином, сохраняющим произвольные объекты и использующим типовой набор методов: pop(),push(), peek(), empty() и full().

Каждый такт работы преобразователя заключается в смене конфигурации. Программа, моделирующая работу преобразователя, в каждом такте по типу входного токена и типу символа, находящемуся в вершине магазина, должна выполнять соответствующую инструкцию, определяемую функцией переходов. Следует отметить, что способ представления функции переходов в памяти компьютера существенно влияет на такие характеристики программы, как быстродействие и требуемый объем памяти. Существует много различных способов представления, однако, в настоящем изложении мы упомянем только те три, которые часто используются на практике. Это представление в виде:

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

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

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

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

 

 

Рис. 7.4. Таблицы для хранения инструкций преобразователя

 

Пред.Страница След.Страница  Раздел Содержание