ОРГАНИЗАЦИЯ ЛЕКСИЧЕСКОГО АНАЛИЗА

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

Лексический анализ осуществляется лексическим анализатором (lexer), и является первым  процессом интерпретации исходного кода.

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

Так как лексический анализ это первый процесс, то от него зависит дальнейшая работа компилятора, грамотная проектировка и реализация, в значительной степени повысят шанс успешной работы. [1]

Лексический анализ состоит из следующих структурных элементов:

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

1. строковое представление лексемы;
2. номер строки, на которой находится лексема и номер файла из списка файлов (для идентификации ошибок);
3. тип лексемы;

• анализатор.

Абстрактно описать процесс лексического анализа можно следующим образом:

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

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

Задача разбора лексемы крайне проста: сопоставить первый, попавшийся не пробельный символ с имеющимся набором ключевых данных и определить тип [3]. Однако здесь есть один нюанс,  надо соблюдать последовательность сравнений с ключевыми словами и символами:

1. если кавычка, то считывание пользовательской строки;
2. если символ, то:

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

При несоблюдении последовательности возможна неправильная интерпретация символов, и как следствие непредвиденное поведение компилятора.

Использование заранее выделенного и расширяемого пула памяти для лексем вместо new/delete, поможет значительно ускорить процесс создания новых объектов лексем.

Так как лексический анализатор используется парсером (синтаксический анализатор) для получения лексем, то возможно его использовать в нескольких видах:

1. считать все файлы с исходным кодом и создать объекты лексем положив их при этом в стек;
2. считывать лексемы из файлов по требованию синтаксического анализатора, оставляя при этом открытые для чтения файлы в памяти.

Оба способа имеют свои достоинства и недостатки. При использовании первого, возможно еще на этапе считывания лексем обнаружить ошибку, то есть до момента построения АСТ (абстрактного синтаксического дерева), однако потребуется больше памяти для хранения всех лексем. На примере языка s4g, лексема состоит из стокового значения, считанного из файла, и дополнительных 16 байт информации для этого значения [4]. Размер незначительный, если речь идет не о микросистемах.

При втором подходе АСТ будет строиться совместно со считыванием лексем, то есть ошибки лексического анализа будут обнаружены только при построении АСТ, но памяти для хранения лексем потребуется меньше.

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

Также на выбор способа получения и хранения лексем влияет архитектура взаимодействия лексического анализатор и синтаксического. Следует помнить, что при втором подходе, ошибка в одном из уровней должна привести к очистке памяти в другом уровне, что ведет к дополнительному коду, в то время как первый способ приводит лишь к дополнительной памяти.

Также, не маловажным фактором является процесс отладки исходного кода языка на этапе исполнения [2]. Если байт-код имеет ссылки на лексемы (первый способ), которые хранят в себе все необходимое для идентификации этой лексемы в исходном файле, то процесс реализации отладки становится централизованным.

Список литературы:

1. Хабрахабр [Электронный ресурс]  – URL: https://habrahabr.ru (дата обращения: 05.11.2017).
2. Code4Life [Электронный ресурс] // Блог о программировании, проектах и жизни программистов – URL: https://code4life.ru (дата обращения: 13.11.2017)
3. GameDev.ru [Электронный ресурс] // Разработка игр – URL: http://www.gamedev.ru (дата обращения: 20.11.2017)
4. s4g [Электронный ресурс] // Script For Games – URL: https://s4g.su (дата обращения: 24.11.2017)