ГЛАВА 3. Лексические анализаторы. Лексические анализаторы

1 ГЛАВА 3. Лексические анализаторы ГЛАВА 3 Лексические анализаторы Лексические анализаторы (сканеры). Принципы построения сканеров Назначение лексического анализатора Прежде чем перейти к рассмотрению лексических анализаторов, необходимо дать четкое определение того, что же такое лексема. Лексема (лексическая единица языка) это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка. Лексемами языков естественного общения являются слова 1. Лексемами языков программирования являются идентификаторы, константы, ключевые слова языка, знаки операций и разделители. Состав возможных лексем каждого конкретного языка программирования определяется синтаксисом этого языка. Лексический анализатор (или сканер ) это часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы входного языка. На вход лексического анализатора поступает текст исходной программы. Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем. Этот перечень лексем можно представить в виде таблицы, называемой таблицей лексем. Каждой лексеме в таблице лексем соответствует некий уникальный условный код, зависящий от типа лексемы, и дополнительная служебная информация. Кроме того, информация о некоторых типах лексем, найденных в исходной программе, должна помещаться в таблицу идентификаторов (или в одну из таблиц идентификаторов, если компилятор предусматривает различные таблицы идентификаторов для различных типов лексем). ВНИМАНИЕ Не следует путать таблицу лексем и таблицу идентификаторов это две принципиально разные таблицы, обрабатываемые лексическим анализатором. 1 В языках естественного общения лексикой называется словарный запас языка. Лексический состав языка изучается лексикологией и фразеологией, а значение лексем (слов языка) семасиологией. В языках программирования словарный запас, конечно, не столь интересен и специальной наукой не изучается.

2 Лексические анализаторы (сканеры). Принципы построения сканеров 89 Таблица лексем фактически содержит весь текст исходной программы, обработанный лексическим анализатором. В нее входят все возможные типы лексем, кроме того, любая лексема может встречаться в ней любое количество раз. Таблица идентификаторов содержит только определенные типы лексем идентификаторы и константы. В нее не попадают такие лексемы, как ключевые (служебные) слова входного языка, знаки операций и разделители. Кроме того, каждая лексема (идентификатор или константа) может встречаться в таблице идентификаторов только один раз. Также можно отметить, что лексемы в таблице лексем обязательно располагаются в том же порядке, что и в исходной программе (порядок лексем в ней не меняется), а в таблице идентификаторов лексемы располагаются в любом порядке так, чтобы обеспечить удобство поиска (методы организации таблиц идентификаторов рассмотрены в предыдущей главе). В качестве примера можно рассмотреть некоторый фрагмент исходного кода на языке Pascal и соответствующую ему таблицу лексем, представленную в табл. 3.1. begin for I := 1 to N do fg := fg * Таблица 3.1. Лексемы программы Лексема Тип лексемы Значение begin Ключевое слово X1 for Ключевое слово X2 I Идентификатор I : 1 := Знак присваивания S1 1 Целочисленная константа 1 to Ключевое слово X3 N Идентификатор N : 2 do Ключевое слово X4 fg Идентификатор fg : 3 := Знак присваивания S1 fg Идентификатор fg : 3 * Знак арифметической операции A1 0.5 Вещественная константа 0.5 Поле «Значение» в табл. 3.1 подразумевает некое кодовое значение, которое будет помещено в итоговую таблицу лексем в результате работы лексического анализатора. Конечно, значения, которые записаны в примере, являются условными. Конкретные коды выбираются разработчиками при реализации компилятора. Важно отметить также, что устанавливается связка таблицы лексем с таблицей идентификаторов (в примере это отражено некоторым индексом, следующим после идентификатора за знаком «:», а в реальном компиляторе определяется его реализацией). Принципы построения лексических анализаторов С теоретической точки зрения лексический анализатор не является обязательной частью компилятора. Все его функции могут выполняться на этапе синтаксического

3 90 Глава 3. Лексические анализаторы разбора, поскольку полностью регламентированы синтаксисом входного языка. Однако существует несколько причин, по которым в состав практически всех компиляторов включают лексический анализ: применение лексического анализатора сокращает объем информации, обрабатываемой на этапе синтаксического разбора; некоторые задачи, требующие использования сложных вычислительных методов на этапе синтаксического анализа, могут быть решены более простыми методами на этапе лексического анализа (например, задача различения унарного минуса и бинарной операции вычитания, обозначаемых одним и тем же знаком ); лексический анализатор отделяет сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходной программы, структура которого может варьироваться в зависимости от архитектуры вычислительной системы, где выполняется компиляция, при такой конструкции компилятора для перехода на другую вычислительную систему достаточно только перестроить относительно простой лексический анализатор; в современных системах программирования лексический анализатор может выполнять обработку текста исходной программы параллельно с его подготовкой пользователем это дает системе программирования принципиально новые возможности, которые позволяют снизить трудоемкость разработки программ (более подробно об этом сказано в главе «Современные системы программирования»). Функции, выполняемые лексическим анализатором, и состав типов лексем, которые он выделяет в тексте исходной программы, могут меняться в зависимости от реализации компилятора. То, какие функции должен выполнять лексический анализатор, а какие оставлять для этапа синтаксического разбора, решают разработчики компилятора. В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих символов (пробелов, символов табуляции и перевода строки), а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, ключевых (служебных) слов входного языка, знаков операций и разделителей. Лексический анализатор имеет дело с такими объектами, как различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык констант и идентификаторов является регулярным то есть может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы. Следовательно, основой для реализации лексических анализаторов служат регулярные грамматики и конечные автоматы. Конечный автомат для каждой входной цепочки языка дает ответ на вопрос о том, принадлежит или нет цепочка языку, заданному автоматом. Однако в общем случае задача лексического анализатора несколько шире, чем просто проверка цепочки символов лексемы на соответствие входному языку. Кроме этого, он должен выполнить следующие действия: определить границы лексем, которые в тексте исходной программы явно не указаны; выполнить действия для сохранения информации об обнаруженной лексеме (или выдать сообщение об ошибке, если лексема неверна).

4 Лексические анализаторы (сканеры). Принципы построения сканеров 91 Эти действия связаны с определенными проблемами. Далее рассмотрено, как эти проблемы решаются в лексических анализаторах. Проблемы построения лексических анализаторов Определение границ лексем Выделение границ лексем является нетривиальной задачей. Ведь в тексте исходной программы лексемы никак не ограничены. Если говорить в терминах лексического анализатора, то определение границ лексем это выделение тех строк в общем потоке входных символов, для которых надо выполнять распознавание. Иллюстрацией случая, когда определение границ лексемы вызывает определенные сложности, может служить пример оператора программы на языке FORTRAN : по фрагменту исходного кода DO 10 I=1 невозможно определить тип оператора языка (а соответственно, и границы лексем). В случае DO 10 I=1.15 это присвоение вещественной переменной DO10I значения константы 1.15 (пробелы в языке FORTRAN игнорируются), а в случае DO 10 I=1,15 это цикл с перечислением от 1 до 15 по целочисленной переменной I до метки 10. Другой иллюстрацией может служить оператор языка C, имеющий вид k=i+++++j;. Существует только одна единственно верная трактовка этого оператора: k = i j; (если явно пояснить ее с помощью скобок, то данная конструкция имеет вид k = (i++) + (++j);). Однако найти ее лексический анализатор может, лишь просмотрев весь оператор до конца и перебрав все варианты, причем неверные варианты могут быть обнаружены только на этапе семантического анализа (например, вариант k = (i++)++ + j; является синтаксически правильным, но семантикой языка C не допускается). Конечно, чтобы эта конструкция была в принципе допустима, входящие в нее операнды k, i и j должны быть описаны и должны допускать выполнение операций языка ++ и +. Поэтому в большинстве компиляторов лексический и синтаксический анализаторы это взаимосвязанные части. Возможны два принципиально различных метода взаимосвязи лексического и синтаксического анализа: последовательный; параллельный 1. При последовательном варианте лексический анализатор просматривает весь текст исходной программы от начала до конца и преобразует его в таблицу лексем. Таблица лексем заполняется сразу полностью, компилятор использует ее для последующих фаз компиляции. Дальнейшую обработку таблицы лексем выполняют следующие фазы компиляции. Если лексический анализатор не смог правильно определить тип лексемы, то считается, что исходная программа содержит ошибку. Работа синтаксического и лексического анализаторов в варианте их последовательного взаимодействия изображена в виде схемы на рис Параллельный метод работы лексического анализатора и синтаксического разбора вовсе не означает, что они должны будут выполняться как параллельные взаимодействующие процессы. Такой вариант возможен, но необязателен.

5 92 Глава 3. Лексические анализаторы Рис Последовательное взаимодействие лексического и синтаксического анализаторов При параллельном варианте лексический анализ текста исходной программы выполняется поэтапно по шагам. Лексический анализатор выделяет очередную лексему в исходном коде и передает ее синтаксическому анализатору. Синтаксический анализатор может подтвердить правильность найденной лексемы и обратиться к лексическому анализатору за следующей лексемой либо же отвергнуть найденную лексему. Во втором случае он может проинформировать лексический анализатор о том, что надо вернуться назад к уже просмотренному ранее фрагменту исходного кода и сообщить ему дополнительную информацию о том, лексему какого типа следует ожидать. Взаимодействуя между собой таким образом, лексический и синтаксический анализаторы могут перебрать несколько возможных вариантов лексем, и, если ни один из них не подойдет, будет считаться, что исходная программа содержит ошибку. Только после того, как синтаксический анализатор успешно выполнит разбор очередной конструкции исходного языка, лексический анализатор помещает найденные лексемы в таблицу лексем и в таблицу идентификаторов и продолжает разбор дальше в том же порядке. Работа синтаксического и лексического анализаторов в варианте их параллельного взаимодействия изображена в виде схемы на рис Рис Параллельное взаимодействие лексического и синтаксического анализаторов Последовательная работа лексического и синтаксического анализаторов, представленная на рис. 3.1, является более простым вариантом их взаимодействия. Она проще в реализации и обеспечивает более высокую скорость работы компилятора, чем их параллельное взаимодействие, показанное на рис Поэтому разработчики компиляторов стремятся организовать взаимодействие лексического и синтаксического анализаторов именно таким образом. Для большинства языков программирования границы лексем распознаются по заданным терминальным символам. Эти символы пробелы, знаки операций, символы комментариев, а также разделители (запятые, точки с запятой и т. п.). Набор

6 Лексические анализаторы (сканеры). Принципы построения сканеров 93 таких терминальных символов зависит от синтаксиса входного языка. Важно отметить, что знаки операций и разделители сами также являются лексемами. Но для многих языков программирования на этапе лексического анализа может быть недостаточно информации для однозначного определения типа и границ очередной лексемы. Однако даже и тогда разработчики компиляторов стремятся избежать параллельной работы лексического и синтаксического анализаторов. В ряде случаев помогает принцип выбора из всех возможных лексем лексемы наибольшей длины: очередной символ из входного потока добавляется в лексему всегда, когда он может быть туда добавлен. Когда символ не может быть добавлен в лексему, то считается, что он является границей лексемы и началом следующей лексемы. Такой принцип не всегда позволяет правильно определить границы лексем в том случае, когда они не разделены пустыми символами. Например, приведенная выше строка языка C k = i+++++j; будет разбита на лексемы следующим образом: k = i j; и это разбиение неверное. Лексический анализатор, разбирая строку из 5 знаков + дважды выбрал лексему наибольшей возможной длины знак операции инкремента (увеличения значения переменной на 1) ++, хотя это неправильно. Компилятор должен будет выдать пользователю сообщение об ошибке, при том что правильный вариант распознавания этой строки существует. Разработчики компиляторов сознательно идут на то, что отсекают некоторые правильные, но не вполне читаемые варианты исходных программ. Попытки усложнить лексический распознаватель неизбежно приведут к необходимости организации его параллельной работы с синтаксическим разбором. Это снизит эффективность работы всего компилятора. Возникшие накладные расходы никак не оправдываются достигаемым эффектом распознаванием строк с сомнительными лексемами. Достаточно обязать пользователя явно указать с помощью пробелов (или других незначащих символов) границы лексем, что значительно проще 1. Не для всех входных языков такой подход возможен. Например, для рассмотренного выше примера с языка FORTRAN невозможно применить указанный метод разница между оператором цикла и оператором присваивания слишком существенна. В таком случае приходится организовывать параллельную работу лексического и синтаксического анализаторов 2. Большинство современных широко распространенных языков программирования, таких как C, C++, Java и Object Pascal, тем не менее позволяют построить лексический анализ по более простому, последовательному, методу. Выполнение действий, связанных с лексемами Выполнение действий в процессе распознавания лексем представляет для лексического анализатора гораздо меньшую проблему, чем определение границ лексем. Фактически конечный автомат, который лежит в основе лексического анализатора, 1 Желающие могут воспользоваться любым доступным компилятором C и проверить, насколько он способен разобрать приведенный здесь пример. 2 Приведенные здесь два оператора на языке FORTRAN, различающиеся только на один символ «.» (точка) или «,» (запятая), представляют собой проблему не столько для компилятора, сколько для программиста, поскольку позволяют допустить очень неприятную и трудно обнаруживаемую ошибку [6].

7 94 Глава 3. Лексические анализаторы должен иметь не только входной язык, но и выходной. Он должен не только уметь распознать правильную лексему на входе, но и породить связанную с ней последовательность символов на выходе. В такой конфигурации конечный автомат преобразуется в конечный преобразователь [3, 4 т.1, 5, 29, 34]. Для лексического анализатора действия по обнаружению лексемы могут трактоваться несколько шире, чем только порождение цепочки символов выходного языка. Он должен уметь выполнять такие действия, как запись найденной лексемы в таблицу лексем, поиск и запись лексемы в таблице идентификаторов. Набор выполняемых действий определяется реализацией компилятора. Обычно эти действия выполняются сразу же при обнаружении конца распознаваемой лексемы. В конечном автомате, лежащем в основе лексического анализатора, эти действия можно отобразить довольно просто достаточно иметь возможность с каждым переходом на графе автомата (или в функции переходов автомата) связать выполнение некоторой произвольной функции f(q,a), где q текущее состояние автомата, a текущий входной символ. Функция f(q,a) может выполнять любые действия, доступные лексическому анализатору: помещать новую лексему в таблицу лексем; проверять наличие найденной лексемы в таблице идентификаторов; добавлять новую лексему в таблицу идентификаторов; выдавать сообщения пользователю о найденных ошибках и предупреждения об обнаруженных неточностях в программе; прерывать процесс компиляции. Возможны и другие действия, предусмотренные реализацией компилятора. Такую функцию f(q,a), если она есть, обычно записывают на графе переходов конечного автомата под дугами, соединяющими состояния автомата. Функция f(q,a) может быть пустой (не выполнять никаких действий), тогда соответствующая запись отсутствует. Регулярные языки и грамматики Чтобы перейти к примерам реализации лексических анализаторов, необходимо более подробно рассмотреть регулярные языки и грамматики, лежащие в их основе. Регулярные и автоматные грамматики Регулярные грамматики К регулярным относятся два типа грамматик: леволинейные и праволинейные. Леволинейные грамматики G(VT,VN,P,S), V = VN VT могут иметь правила двух видов: A Bγ или A γ, где A,B VN, γ VT*. В свою очередь, праволинейные грамматики G(VT,VN,P,S), V = VN VT могут иметь правила также двух видов: A γb или A γ, где A,B VN, γ VT*. Доказано, что эти два класса грамматик эквивалентны. Разница между леволинейными и праволинейными грамматиками заключается в основном в том, в каком по-