Лексические анализаторы (сканеры). Принципы построения сканеров

Введение

Актуальность работы. Важным этапом создания компилятора является построение лексического анализатора (сканера), с помощью которого во входном потоке символов языка осуществляется поиск ее отдельных структурных единиц - лексем.
Лексический анализ является первой фазой работы компилятора, во время которой осуществляется подготовка для выполнения анализа синтаксиса текста. Для этого определяются типы всех найденных лексем, которые отвечают определенным структурам языка, - токенам.
Таким образом, сканер будто «ограждает» синтаксический анализатор от непосредственной работы с лексемами, чем значительно упрощает его роботу и повышает быстродействие и эффективность компилятора в целом [1].
Целью работы является определение общих принципов проектирования сканеров.
Объект исследования: лексические анализаторы (сканеры).
Предмет исследования: принципы построения сканеров.
Для осуществления поставленной цели необходимо решить следующие задачи:
- рассмотреть принципы работы лексических анализаторов;
- проанализировать лексические анализаторы;
- выявить анализатор для эффективного программирования.


1. Основные принципы работы лексических анализаторов
Можна сформулировать основные принципы работы лексических анализаторов:
1. Считывание потока символов из текста входной программы.
2. Удаление из текста «лишних» символов, которые не входят в состав токенов, - пробел, символы табуляции и новой строки, и тому подобное.
3. Группирование полученных символов у лексемы, которая включает определение границ каждой лексемы.
4. Выявление и сообщение об ошибке, если лексема неправильна.
5. Формирование и заполнение таблиц лексем и идентификаторов для их следующей передачи синтаксическому анализатору [2].
Отметим основные отличия между таблицей лексем и идентификаторов, а именно:
1.) Таблица лексем включает все их возможные типы. Таблица идентификаторов содержит только определенные типы лексем - идентификаторы и константы.
2.) Любая лексема, в таблице лексем, может встречаться неограниченное количество раз. В таблице идентификаторов каждая лексема (идентификатор или константа) определена только один раз.
3.) Обязательно в таблице лексем они размещаются в том же порядке, что и во входной программе, а в таблице идентификаторов - расположены в порядке, который обеспечивает их удобный поиск.
Рассмотрим процесс лексического анализа и формирования таблиц на примере.
Пример. При лексическом анализе фрагмента входного кода на языке Java :
if (flag) return 1;
- полученные следующие таблицы: таблица лексем, без учета пробельных символов (таблица 4), таблица идентификаторов (таблица 3) и таблица литералов (таблица 2).
Также приведенная часть таблицы терминальных символов языка программирования Java (таблица 1), которая применялась во время лексического анализа приведенного выражения, в ней хранится информация об основных конструкциях языка (ключевые слова, разделители, знаки операций и тому подобное).
В заданном выражении к терминальным символам относятся: if, (, ) return, ; а также пробел.
Таблица 1 - Таблица терминальных символов
№ символа
Символ
Тип
1
;
Разделитель
2
...
Разделитель
3
(
Разделитель
4
)
Разделитель
5
if
Ключевое слово
6
return
Ключевое слово

Таблица констант включает записи следующей структуры : номер константы в таблице констант; строчное представление константы; тип (целый, действительный, логический, символьный, строчный); точность представления константы в памяти (в виде числа байтов, отведенных для хранения).
К константам входного выражения запишем лексему 1 (тип int).
Таблица 2 - Таблица констант
№
Имя
Тип
Значение
1
«1»
int
00000001
Идентификаторы, которые складывают соответствующую таблицу, имеют атрибуты: номер, имя (переменной, массива, функции и тому подобное), тип (действительный, целый, логический, строчный, символьный) и адрес в памяти.
Выделим идентификаторы заданной последовательности символов - flag (тип boolean).
Таблица 3 - Таблица идентификаторов переменных
№
Вид (имя)
Тип
Адрес
1
flag
boolean
Ø(пока что не распределена)
Исходной таблицей лексического анализатора является таблица лексем, которые одновременно являются входными для синтаксического анализа. Код лексемы состоит из признака типа лексемы и номеру лексемы в таблице лексем. Обозначение типов лексем: I - для лексем- идентификаторов, С - для лексем-констант, Т - для лексем - терминальных символов языка.
Таблица 4 - Таблица лексем
№
Лексема
Тип лексемы
Код
Ссылка
1
if
Служебное слово
Т5
Адрес в таблице терминалов
3
(
Служебный символ
Т3
Адрес в таблице терминалов
4
flag
Идентификатор
11
Адрес в таблице идентификаторов
5
)
Служебный символ
Т4
Адрес в таблице терминалов
6
return
Служебный символ
Т6
Адрес в таблице идентификаторов
7
1
Литерал
С1
Адрес в таблице литералов
8
5
Служебный символ
Т1
Адрес в таблице терминалов

2. Лексический анализ
На данном этапе во входной программе выделяются лексемы и формируются таблице разных классов лексем. Типичные классы лексем - это идентификаторы, константы, ключевые слова языка программирования. В результате работы лексического анализатора программа превращается в последовательность лексем.
Для выделения лексем используются грамматики, которые описывают отдельные классы лексем. Согласно этим грамматикам во входной последовательности букв, которые использованы для написания входной программы, находят под последовательности, которые выводятся в той или другой грамматике. Оказывается, что на этапе лексического анализа можно ограничиться регулярными грамматиками.
Рассмотрим пример выделения вещественных чисел, которые описываются регулярным выражением
( + - )d*.dd* (e ( + - )dd* ),
где d - цифра

.
Данное выражение показывает, что вещественное число состоит из нескольких компонент, расположенных в поданном порядке:
1) возможный знак;
2) последовательность цифр, которая может быть и пустой;
3) десятичная точка;
4) непраздная последовательность цифр;
5) возможный порядок, который состоит из а) символа е, б) возможного знака, в) непраздной последовательности цифр.
Приведенному регулярному выражению отвечает грамматика из продукциями
1. S  +R -R dR .P
2. R  dR .P
3. P  dF d
4. F  dF eA d
5. A  +N -N dN d
6. N  dN d
Для того, чтобы написать программу, которая выделяет действительные константы, построим сначала автомат, который представляет язык вещественных чисел. Означает функцию переходов так, как это делалось при доказательстве теоремы 6.3, одержимо автомат, показанный на рис.5.


Рисунок 5 - Недетерминированный автомат, который принимает вещественные числа.
На поданном рисунку около ребер показаны соответствующие входные буквы, и τ = T. Состояние π не показано, чтобы не усложнять рисунок. Его учет при написании программы не вызывает трудностей. Полученный автомат недетерминированный. Для того, чтобы перейти к эквивалентному детерминированному автомату, надо выполнить превращение такое, как при доказательстве теоремы. В данном случае получаем детерминированный автомат после объединения состояний F и T, а также N и T (рис.6).
Рисунок 6 - Детерминированный автомат.
Полученный граф автомату можно рассматривать как блок-схему алгоритма выделения вещественного числа. Каждый шаг этого алгоритма отвечает переходу автомату из одного состояния в другой, когда на вход приходит соответствующий символ входного алфавита.
Формирование таблиц
На этапе лексического анализа идентификаторы и константы, имеющие произвольную длину, заменяются кодами фиксированной длины. Ключевые слова также заменяются некоторым стандартным представлениям. Например, слова языка программирования могут заменяться целыми числами, идентификаторы - буквой "i" и следующим за ней целым числом, константы - буквой "с" с последующим числом и т.д. Поскольку эти цели числа ограничены разрядностью вычислительной машины, очевидно, что количество идентификаторов и констант в программе не должна превышать некоторого числа. Каждый раз, когда в программе при последовательном чтении появляется некоторое идентификатор, говорят, что имеет место его реализация. Реализация идентификатора при определении типа соответствующей переменной называется определяющей. Другие реализации называются прикладными.
При обработке входящей программы лексическим анализатором каждая реализация идентификатора заменяется соответствующим кодом. Это означает, что лексический анализатор должен создавать таблицу идентификаторов, определяет соответствие между кодом и идентификатором. При обработке определяющей реализации идентификатору проверяется, не содержится уже этот идентификатор в таблице. Если нет, таблица пополняется, иначе диагностируется ошибка. Обработка прикладной реализации включает поиск идентификатора в таблице для определения его типа.



121
122


Рисунок 7 - Списковая структура таблицы идентификаторов.
Для хранения таблицы идентификаторов в памяти машины нужная структура данных, что позволяет включение идентификаторов произвольной длины. Очевидное решение - применение списка, каждый элемент которого отвечает букве идентификатора. Например, таблица идентификаторов может иметь структуру, условно изображенную на рис.7.
На рисунке стрелки отвечают связкам за указателями, а перечеркнутый квадрат - нулевому указателю.
Для описания такой таблицы в языке Object Pascal можно использовать записи
type
ptr = ^sym;
sym = record
lit : char;
ref : ptr
end;
tabid = array[1 .. n] of ptr;
В такой таблице кодом идентификатору является индекс массива tabid, а значение идентификатору хранится в виде списка. Большое количество указателей в этой структуре приводит к лишним расходам памяти. Но, если язык программирования, которым пишется компилятор, имеет строчные переменные, то указатели не нужны. Уменьшить расходы памяти для хранения таблицы идентификаторов можно также за счет использования (если позволяет язык программирования) гибкого массива. Гибкий массив - это массив, длину которого можно изменять во время прогонки.
Аналогичная таблица нужна и для констант. Некоторые компиляторы проверяют длину констант и вычисляют их в процессе лексического анализа. Однако, допустимая длина константы зависит от объектной машины. Поэтому преимущество можно отдать такому решению, когда на этапе лексического анализа в таблице хранятся константы произвольной длины.
В отличие от идентификаторов код константы состоит из двух частей: номеру Х соответствующего индекса таблицы констант и типа Т константы, то есть имеет вид ХТ. Такой код передается как на стадию синтаксического анализа, так и генерации кода, где только и оказывается зависимость от машины.
Лексический анализатор, кроме формирования лексем, может включать в входную программу дополнительную информацию и извлекать из нее некоторые строки букв. Примером дополнительной информации есть номера строк программы, используемые при диагностике ошибок. Информации, изымаемого принадлежат комментарии. Кроме того, некоторые алгоритмические языки позволяют включать в текст программы специальные указания, например, на использование при компиляции оптимизации по времени выполнения или на применение определенного способа исправления ошибок