ЛР4 Лексический анализ, тестирование созданного компилятора

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

Содержание

• Основные сведения
• Работа сканера
• Построение графа распознавания лексических единиц.
• ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
• ИСПОЛЬЗОВАНИЕ «УЧЕБНОГО КОМПИЛЯТОРА» В Л/Р №4
• СОДЕРЖАНИЕ ОТЧЕТА
• КОНТРОЛЬНЫЕ ВОПРОСЫ
• ЛИТЕРАТУРА

Начало методички:

Основные сведения

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

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

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

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

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

Работа сканера

Сканер читает литеры первоначальной исходной программы и строит слова, или иначе символы, исходной программы (идентификаторы, служебные слова, целые числа, одно- или двулитерные разделители, такие как *, +, :=, <= ). Символы называются лексемами или лексическими единицами (ЛЕ).

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