Программная модель 32-разрядного микропроцессора фирмы Motorola

Описание интерпретатора


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

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

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

Дескриптор — это пара вида: (<тип лексемы>, <указатель>),

где <тип лексемы> — это, как правило, числовой код класса лексемы, кото­рый означает, что лексема принадлежит одному из конечного множества клас­сов слов, выделенных в языке программирования;

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

Количество классов лексем (т.е. различных видов слов) в языках програм­мирования может быть различным. Наиболее распространенными классами являются:

    - идентификаторы;

- служебные (ключевые) слова;

- разделители;

   - константы.

Все они присутствуют в данной программной модели.



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


Пользователю необходимо учитывать, что метка (если она присутствует) начинается  сначала строки (пробелы – если они есть – во внимание не принимаются), и от операций отделяется символом “:”
Пример:
М: moveq #123,D1;
     add  D1,D2; 
    причём количество пробелов “:”до, после “:”, между операндами, между командой и операндами (и их наличие) может быть произвольным. Обязательной является “,” между приёмником и источником. В конце мнемоники команды в обязательном порядке должна стоять “;”, которая отделяет мнемокод от комментариев пользователя, которые интерпретатором  игнорируются. В противном случае произойдёт выработка исключительной ситуации, о чём появится на экран соответствующее сообщение.
После этого проводится идентификация лексе­мы. Она заключается в сборке лексемы из символов, начиная с выделенного на предыдущем этапе, и проверки правильности записи лексемы данного класса.
Идентификация лексемы из конечного класса выполняется путем сравне­ния ее с эталонным значением. Основная проблема здесь — минимизация вре­мени поиска эталона. В общем случае может понадобиться полный перебор слов данного класса, в особенности для случая, когда выделенное для опозна­ния слово содержит ошибку. Уменьшить время поиска можно, используя раз­личные методы ускоренного поиска:
- метод линейного списка;
- метод упорядоченного списка;
- метод расстановки и другие.
Для идентификации лексем из бесконечных (очень больших) классов ис­пользуются специальные методы сборки лексем с одновременной проверкой правильности написания лексемы. При построении этих алгоритмов широко применяется формальный математический аппарат — теория регулярных язы­ков, грамматик и конечных распознавателей. В данном случае – время поиска не актуально, так как оно и так не высоко из-за  не очень большого количества команд микропроцессора.
При успешной идентификации значение лексемы из бесконечного клас­са помещается в таблицу идентификации лексем данного класса.


При этом необходимо предварительно проверить: не хранится ли там уже значение данной лексемы, т.е. необходимо проводить просмотр элементов табли­цы. Если ее там нет, то значение помещается в таблицу. При этом таблица должна допускать расширение. Опять же для уменьшения времени досту­па к элементам таблицы она должна быть специальным образом органи­зована, при этом должны использоваться специальные методы ускоренного поиска элементов.
После проведения успешной идентификации лексемы формируется ее об­раз — дескриптор, он помещается в выходной поток лексического анализато­ра. В случае неуспешной идентификации формируются сообщения об ошибках в написании слов программы.
В ходе лексического анализа осуществляются и другие виды лексичес­кого контроля, в частности, проверяется парность скобок, допустимость и правильность записи способов адресации.
Выходной поток с лексического анализатора в дальнейшем поступает на вход синтаксического анализатора. Имеется две возможности их связи:
- раздельная связь, при которой выход лексического анализатора формируется полностью и затем передается синтаксическому ана­лизатору;
- нераздельная связь, когда синтаксическому анализатору требуется очередной образ лексемы, он вызывает лексический анализатор, ко­торый генерирует требуемый дескриптор и возвращает управление синтаксическому анализатору.
Второй вариант характерен для однопроходных трансляторов, который и реализуется в данной модели. Таким об­разом, процесс лексического анализа может быть достаточно простым, но в смысле времени компиляции оказывается довольно долгим. Больше половины времени, затрачиваемого компилятором на ком­пиляцию, приходится на этап лексического анализа. Несмотря на это, данный способ позволяет успешно решать задачи, поставленные пользователем перед программой.

Содержание раздела