Назначение лексического анализатора
Лексема (лексическая единица языка) – это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка.
Лексемами языков программирования являются идентификаторы, константы, ключевые слова языка, знаки операций и т.п. Состав возможных лексем каждого конкретного языка программирования определяется синтаксисом этого языка.
Лексический анализатор (или сканер) – это часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы входного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
С теоретической точки зрения лексический анализатор не является обязательной частью компилятора. Все его функции могут выполняться на этапе синтаксического разбора, поскольку полностью регламентированы синтаксисом входного языка. Однако существует несколько причин, по которым в состав практически всех компиляторов включают лексический анализ:
· применение лексического анализатора упрощает работу с текстом исходной программы на этапе синтаксического разбора и сокращает объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и выкидывает всю незначащую информацию;
· для выделения в тексте и разбора лексем возможно применять простую, эффективную и теоретически хорошо проработанную технику анализа, в то время как на этапе синтаксического анализа конструкций исходного языка используются достаточно сложные алгоритмы разбора;
· сканер отделяет сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходной программы, структура которого может варьироваться в зависимости от версии входного языка – при такой конструкции компилятора для перехода от одной версии языка к другой достаточно только перестроить относительно простой лексический анализатор.
Функции, выполняемые лексическим анализатором, и состав лексем, которые он выделяет в тексте исходной программы, могут меняться в зависимости от версии компилятора. То, какие функции должен выполнять лексический анализатор и какие типы лексем он должен выделять во входной программе, а какие оставлять для этапа синтаксического разбора, решают разработчики компилятора. В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев, незначащих пробелов, символов табуляции и перевода строки, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, ключевых (служебных) слов входного языка, знаков операций и разделителей.
В простейшем случае фазы лексического и синтаксического анализа могут выполняться компилятором последовательно. Но для многих языков программирования на этапе лексического анализа может быть недостаточно информации для однозначного определения типа и границ очередной лексемы. Иллюстрацией такого случая может служить пример оператора программы на языке С, имеющий вид: k=1+++++j;. Существует только одна-единственно верная трактовка этого оператора: k =i+++++j; (если явно пояснить ее с помощью скобок, то данная конструкция имеет вид: k=(i++)+(++j);). Однако найти ее лексический анализатор может, лишь просмотрев весь оператор до конца и перебрав все варианты, причем неверные варианты могут быть обнаружены только на этапе семантического анализа.
Поэтому в большинстве компиляторов лексический и синтаксический анализаторы – это взаимосвязанные части. Возможны два принципиально различных метода организации взаимосвязи лексического анализа и синтаксического разбора:
· последовательный;
· параллельный.
При последовательном варианте лексический анализатор просматривает весь текст исходной программы от начала до конца и преобразует его в структурированный набор данных. Этот набор данных называют также таблицей лексем. В таблице лексем ключевые слова языка, идентификаторы и константы, как правило, заменяются на специально оговоренные коды, им соответствующие (конкретная кодировка определяется при реализации компилятора). Для идентификаторов и констант, кроме того, устанавливается связь между таблицей лексем и таблицей идентификаторов, которая заполняется параллельно.
В этом варианте лексический анализатор просматривает весь текст исходной программы один раз от начала до конца. Таблица лексем строится полностью вся сразу, и больше к ней компилятор не возвращается. Всю дальнейшую обработку выполняют следующие фазы компиляции.
При параллельном варианте лексический анализ исходного текста выполняется поэтапно так, что синтаксический анализатор, выполнив разбор очередной конструкции языка, обращается к сканеру за следующей лексемой. При этом он может сообщить информацию о том, какую лексему следует ожидать. В процессе разбора при возникновении ошибки может происходить “откат назад”, чтобы попытаться выполнить анализ текста на другой основе. И только после того, как синтаксический анализатор успешно выполнит разбор очередной конструкции языка (обычно такой конструкцией является оператор исходного языка), лексический анализатор помещает найденные лексемы в таблицу лексем и таблицу идентификаторов и продолжает разбор дальше в том же порядке.
Работа синтаксического и лексического анализаторов в варианте их параллельного взаимодействия изображена в виде схемы на рис. 7.
В качестве варианта таблицы лексем можно рассмотреть некоторый фрагмент кода на языке Pascal и соответствующую ему таблицу лексем (табл. 1).
…
begin
for i:=1 to N do
fg := fg * 0.5;
...
Таблица 1
Лексемы программы
Поле “Значение” в табл. 1 подразумевает некое кодовое значение, которое будет помещено в итоговую таблицу лексем в результате работы лексического анализатора. Конечно, значения, которые записаны в примере, являются условными. Конкретные коды определяются при реализации компилятора. Важно отметить также, что для идентификаторов устанавливается связка таблицы лексем с таблицей идентификаторов (в примере это отражено некоторым индексом, следующим после идентификатора за знаком :, а в реальном компиляторе все опять же определяется его реализацией).
Очевидно, что последовательный вариант организации взаимодействия лексического анализа и синтаксического разбора является более эффективным, так как он не требует организации сложных механизмов обмена данными и не нуждается в повторном прочтении уже разобранных лексем. Этот метод является и более простым. Однако не для всех языков программирования возможно организовать такое взаимодействие. Это зависит в основном от синтаксиса языка, заданного его грамматикой. Большинство современных широко распространенных языков программирования, таких, как С и Pascal, тем не менее позволяют построить лексический анализ по более простому, последовательному методу, что дает ряд определенных преимуществ.