Лексический анализ. Сканер

Теоретические сведения

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

Распределение по таблицам происходит следующим образом.

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

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

Таким образом, алгоритм работы простейшего сканера можно описать так:

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

Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.

Таблица терминальных символов в простейшем случае может иметь следующий вид как показано в таблице 1.

Таблица 1 – Таблица терминальных символов

№ п.п.	Терминальный символ	Комментарий (обозначение)
	PROGRAM	Заголовок программы
	VAR	Описание переменных
	BEGIN	Начало тела программы
	END	Конец тела программы
	INTEGER	Целый тип данных
	FOR	Счетный оператор цикла (для)
	TO	Ключевое слово счетного оператора цикла (до)
	DO	Ключевое слово (выполнить)
	WHILE	Оператор цикла с предусловием (пока)
	DIV	Деление целочисленное
	MOD	Остаток от целочисленного деления
	AND	Логическое И
	OR	Логическое ИЛИ
	:=	Присвоить значение

Сначала заполняется таблица лексем (терминальных символов), затем начинается считывание и обработка входного текста программы пользователя. При работе сканера происходит заполнение таблиц символических имен и литералов.

Данные таблицы могут выглядеть следующим образом:

Таблица 2 – Таблица символических имен

№ п.п.	Идентификатор	Тип	Размер, занимаемый в памяти, байт	Относительный адрес в памяти
	I	INTEGER
	Y	REAL
	X1	REAL
…

Таблица 3 – Таблица литералов

№ п.п.	Литерал	Тип	Размер, занимаемый в памяти, байт	Относительный адрес в памяти
		INTEGER
		INTEGER
…

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

FOR I:=1 TO 100 DO Y:=X1

будет получена строка:

<1,06><2,1><1,14><3,1><1,07><3,2><1,08><2,2><1,14><2,3>,

где в угловых скобках пара чисел задает код таблицы и спецификатор. Можно оформить и в виде таблицы.

Таблица 4 – Таблица выходных символов

№ п.п.
Таблица
Строка

Функционально в сканере могут быть выделены следующие модули:

выделение из входной строки очередного слова;
поиск в таблицах лексем и определение кода лексемы;
формирование и вывод выходной строки.

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

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

В задачи последнего модуля входит занесение в выходную строку кодов лексем.

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

Следующей стадией анализа является синтаксический разбор.

Лексический и синтаксический анализаторы взаимодействуют между собой. Существует два основных способа взаимодействия:

реализуется на основе прямого лексического анализа. От синтаксического анализатора поступает запрос «дать лексему» и указывается тип лексемы;
непрямой лексический анализ. Синтаксический анализатор выдает запрос «дать лексему», тип лексемы не указывается. Нет решающего блока, считаем, что работает группа параллельных автоматов.

Порядок выполнения работ (руководство пользователя)

лабораторная работа №1

Дана некоторая грамматика языка:

1. <prog>::= PROGRAM <prog-name> VAR <dec-list> BEGIN <stmt-list> END.

2. <prog-name>::= id

3. <dec-list>::= <dec> | <dec-list>; <dec>

4. <dec>::= <id-list>: <type>

5. <type>::= INTEGER

6. <id-list>::= id | <id-list>, id

7. <stmt-list>::= <stmt> | <stmt-list>; <stmt>

8. <stmt>::= <assign> | <for>

9. <assign>::= id:= <exp>

10. <exp>::= <term> | <exp> + <term> | <exp> - <term>

11. <term>::= id | int | (<exp>)

12. <for>::= FOR <index-exp> DO <body>

13. <index-exp>::= id:= <exp> TO <exp>

14. <body>::= <stmt> | BEGIN <begin-list> END

Для выполнения работы требуется:

Запустить программу LexAN. На экране появится окно программы (Рисунок 2).

Рисунок 2 – Окно программы LexAN

2. В поле «Текст программы» необходимо набрать программу или загрузить ее из файла *.pas: Файл ► Открыть

3. Заполнить «Таблицу терминальных символов (таблица №1)». Для этого нажмите одну из следующих кнопок, расположенных справа от таблицы:

· «Добавить символ» - добавить терминальный символ. После этого появляется окно «Добавление элементов» показанное на рисунке 3.

В поле «Описание» выбирается необходимый элемент, при этом он тут же показывается в поле «Название». Для добавления элемента в таблицу следует нажать кнопку «Добавить», при этом в таблице терминальных символов добавится новая строка с выбранным символом. Имеется возможность изменить название элемента, если только он не является специальным символом. Для этого в поле «Название» пишется новое название, которое будет использоваться в тексте программы.

Рисунок 3 – Добавление элементов

· «Удалить символ» - удалить терминальный символ. Если возникла необходимость удалить один из элементов таблицы терминальных символов, то для этого необходимо нажать на кнопку «Удалить символ» основного окна программы. После этого появится окно «Удаление элементов», показанное на рисунке 4. Необходимо выбрать удаляемый элемент и нажать кнопку «Удалить».

Рисунок 4 – Удаление элементов

· «Очистить таблицу» - очистить таблицу. В случае, когда необходимо сразу очистить все элементы таблицы терминальных символов следует нажать на кнопку «Очистить таблицу» основного окна программы.

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

Для того, чтобы увеличить\уменьшить кол-во строк в таблице нажмите на UpDown компонент, а затем на кнопку «Применить».

5. В «Таблицу литералов (Таблица №3)» следует занести все литералы, встречающиеся за время программы, в порядке их нахождения, независимо от того встречались ли уже подобные или нет.

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

Нажать на кнопку «Выполнить проверку». При этом в окне «Сообщения» будут показаны найденные ошибки и несоответствия с таблицей выходных кодов лексем или же будет положительный результат: В окне «Сообщения» появится «Проверка удачна. Таблица выходных кодов лексем заполнена верно».

В случае, когда обнаружены ошибки, следует тщательно разобраться с ними, исследовать причины появления, исправить и заново проверить правильность заполнения таблиц.

Отчет по выполненной работе

Для отчета необходимо получить файл листинга программы и распечатать его.

Контрольные вопросы.

1. Что такое лексема, как ее получить из текста программы?

2. Различие межу ключевыми словами и специальными символами.

3. Различие между ключевыми словами и идентификаторами.

4. Какие таблицы существуют в сканере, для чего они нужны?

5. В чем смысл таблицы кодов лексем, ее необходимость?

6. Значимость этапа лексического анализа в компиляторе.

Литература

1. Бек Л. Введение в системное программирование.: Пер. с англ. – М.: Мир, 1998.

2. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. – М.: Мир, 1975.