Информационно-безопасные системы. Анализ проблемы: Учебное пособие, страница 28

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

 

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

Синтаксический анализ - это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Синтаксический блок переводит последовательность лексем, построенную лексическим блоком, в другую последовательность, в которой отражается порядок выполнения операций, задуманный программистом. На этом этапе производится разбор структуры программы. Здесь под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике. Входные лексемы пере­водятся синтаксическим блоком в новые единицы, называемые атомами. Например, А*В переводится в атом УМНОЖИТЬ(А,В,R1)

Затем программа может быть переведена во внутреннее представление. Это делает­ся для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразо­вания программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой.

Дерево, построенное синтаксическим анализатором, используется  генератором кода для того, чтобы получить перевод входной программы. Этот перевод может быть программой в машинном языке, но чаще всего он бывает программой в промежуточ­ном языке, таком, как язык ассемблера или "трехадресный код" (последний образуется из простых операторов, каждый из которых включает не более трех идентификаторов; например, А = В, А = В + С, GOTO А). Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамиче­ское программирование, различные синтаксические методы.

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

7.5. Моделирование основных фаз компиляции

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

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

7.5.1. Модель лексического анализатора

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

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

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