Лексический анализатор — это начальный этап выполнения компиляции, на котором символы, образующие исходный текст программы, перегруппировываются в набор отдельных минимальных единиц текста, имеющих смысловую нагрузку и именуемых лексемами.
Теория компиляции
История теории компиляции ведёт свой отчёт от 1957-го года, то есть с момента появления первого компилятора языка Фортран, реализованного Бэкусом и способного сформировать вполне эффективный объектный код. До этого момента формирование компиляторов было достаточно «творческой» процедурой. И только возникновение теории формальных языков и достоверных математических моделей предоставило возможность использовать вместо чисто творческих методик вполне научные. Именно это явилось причиной возникновения сотен разнообразных языков программирования. Кроме того, формализованная теория компиляторов явилась новым стимулом развития математической лингвистики и методов искусственного интеллекта, которые связаны с искусственным и естественным языком.
Основанием теории компиляторов является теория формальных языков, представляющая собой достаточно сложный математический раздел. Естественно, что и реализация объектного кода, и машинно-ориентированная оптимизация, и реализация компоновки очень важны. Тем не менее они являются частностями, которые зависят в первую очередь от фактической структурной организации компьютера, от структуры используемой операционной системы, а основные принципы реализации компиляторов остаются неизменными. Архитектурные построения изменяются практически каждый год, а базовые методики неизменны уже много десятков лет.
Транслятором называется программа, переводящая исходный программный текст в соответствующую объектную программу. В случае, когда объектный язык является автокодом или некоторым машинным языком, транслятор принято называть компилятором. Большинство команд автокода является точным символическим отображением машинных команд, то есть автокод является почти аналогом машинного языка.
Ассемблер представляет собой программу, переводящую исходную программу, сформированную на автокоде или ассемблерном языке (что, практически, то же самое), в исполняемый (то есть объектный) код.
Процесс компиляции
На рисунке ниже показана обобщённая стандартная структура компилятора. В реальности компилятор является целым программным комплексом.
Рисунок 1. Обобщённая стандартная структура компилятора. Автор24 — интернет-биржа студенческих работ
Здесь под исходной программой понимается текстовое отображение программы на языке высокого уровня, который необходимо преобразовать в машинные коды.
Информационные таблицы являются самостоятельными структурами, которые заполняются при выполнении лексического анализа и могут дополняться при осуществлении работы.
Лексический анализатор, то есть сканер, который имеет на выходе лексемный поток, требуется для того, чтобы отсеять всё второстепенное (например, комментарии), отделить лексемы, то есть лексические модули, необходимые для построения машинного языка, и выполнить их преобразование во внутренние или промежуточные формы представления. Этот этап предполагает активную работу с таблицами, в которые записываются информационные данные о идентифицированных лексемах, их значениях, типах и других параметрах. В итоге получается поток лексем, который является эквивалентом исходного теста.
Синтаксический анализатор требуется для выяснения соответствия предложений исходной программы грамматическим правилам выбранного языка. Параллельно с анализом синтаксиса выполняется генерация внутренней формы отображения программы.
Процесс компиляции, как правило, состоит из следующих этапов:
- Этап лексического анализа. На этом этапе выполняется подмена лексем их внутренним отображением (к примеру, подмена операторов, разделителей и идентификационных параметров числовыми значениями).
- Этап синтаксического анализа. Часто на данном этапе могут вводиться добавочные разделители и заменяться уже имеющиеся, чтобы облегчить обработку.
- Этап генерации промежуточных кодов (этап трансляции). Здесь выполняется анализ типа и вида всех идентификационных параметров и иных операндов. Как правило, процесс преобразования исходной программы в промежуточную форму записи выполняется вместе с синтаксическим анализом.
- Этап оптимизации кодов.
- Этап распределения памяти для переменных в формируемой программе.
- Этап генерации объектных кодов и выполнение компоновки сегментов программы.
На каждом из этапов осуществляется взаимодействие с таблицами разного типа.
В общем виде, весь набор этапов может быть представлен так:
Рисунок 2. Работа с таблицами. Автор24 — интернет-биржа студенческих работ
Естественно, структура компилятора зависит от структуры компьютера, вернее, от величины его производительности.
Лексический анализатор
На вход лексического анализатора, то есть сканера, поступает символьная последовательность, являющаяся исходной программой. При его работе отдельные символьные наборы воспринимаются сканером в форме единого объекта. К примеру:
- Набор пробелов подменяется одним пробелом.
- Набор ключевых слов (типа BEGIN, END, INTEGER и другие).
- Последовательность символов, обозначающая константу.
- Последовательность символов, обозначающая имя (идентификатор).
То есть, лексический анализатор выполняет группировку определённых терминальных символов (входных символов) в объединенные синтаксические объекты, именуемые лексемами. Самой простой лексемой является набор типа .
Проблема формирования лексем из входного потока иногда превращается в сложную и зависящую от структурной организации используемого языка задачу.
Известно два главных вида лексических анализаторов:
- Прямые анализаторы.
- Непрямые анализаторы.
Прямой лексический анализатор находит лексему, которая расположена правее текущего указателя, и выполняет сдвиг указателя вправо от текстового участка, определяющего лексему. Непрямой анализатор анализирует, формируют ли знаки, находящиеся правее указателя, лексему данного типа.
