Разработка компилятора. Организация лексического анализа


Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Deprecated: Function eregi_replace() is deprecated in /hlds/web/u138079p19/code4life.ru/htdocs/wp-content/plugins/wp-note/wp-note.php on line 43

Notice: Функция get_currentuserinfo с версии 4.5.0 считается устаревшей! Используйте wp_get_current_user(). in /hlds/web/u138079p19/code4life.ru/htdocs/wp-includes/functions.php on line 3840

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

Терминология

Лексический анализ — процесс распознавания исходного кода и деление его на лексемы.

Лексема (lexeme) — последовательность возможных символов, которые могут быть распознаны для дальнейшего разбора.

Токен (token) — синоним лексемы.

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

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

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

Структурные элементы лексического анализа

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

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

Описание процесса лексического анализа

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

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

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

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

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

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

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

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

Оба способа имеют свои достоинства и недостатки:

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

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

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

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

Поделиться:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*