Разработка компилятора. Лексический анализатор


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

На начальной стадии разработки скриптового языка программирования s4g, я очень мало уделял внимания лексическому анализатору, его процесс был совмещен с синтаксическим, и мне было крайне не понятно, зачем нужен лексический анализатор?

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

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

Повторим теорию прошлой статьи:

Лексический анализатор (лексер — lexer) — объект выполняющий лексический анализ. Объектом может быть составная часть программы, либо отдельная программа. В большинстве случаев это класс.

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

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

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

Действия и процессы

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

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

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

Зачем парсеру лексемы? Для того чтобы парсер имел представление о ее типе. После прохода лексером выражения:

a = 10

Будет сгенерировано 3 лексемы:

  • тип: идентификатор | символы: «a»
  • тип: знак присваивания | символы: «=»
  • тип: целое число | символы: «10»

В простом случае, это говорит парсеру что нужно создать нод присваивания, левым операндом которого будет является переменная «a» а правым операндом число «10».

Что же будет в случае перемены мест второй и третьей лексем? То есть:

  • тип: идентификатор | символы: «a»
  • тип: целое число | символы: «10»
  • тип: знак присваивания | символы: «=»

Будет ошибка, парсер не поймет что надо делать и должен выдать ошибку. А будет ли это понимать человек? Нет, потому что в итоге получается:

a 10 =

Что это значит? Код записан неверно.

Но описанная ситуация не является ошибочной для лексического анализа.

Какие же ошибки должен выдавать лексер? Здесь все достаточно просто. Если лексер обрабатывает комментарии, то незавершенность комментария будет являться ошибкой. Затем у лексера есть четкий набор символов, которые он распознает, если символ не является распознаваемым, значит ошибка. Форматы записей чисел тоже имеют некий формат, не следование которому генерирует ошибки. И множество других ошибок лексики несоответствия языка.

Как должна быть описана лексема?

Как должна каждый решает сам, я лишь приведу пример как сделано у нас в s4g:

//! лексема
struct s4g_Lexeme
{
	s4g_Lexeme(){}
	s4g_Lexeme(const char *szStr, int numStr, S4G_LEXEME_TYPE type, ID idWord, ID idFile)
	{
		m_sLexeme = szStr; m_numStr = numStr, m_type = type; m_idWord = idWord; m_idFile = idFile;
	}
	String m_sLexeme;		//!< строковое представление лексемы
	int m_numStr;			//!< номер строки на которой находится лексема
	S4G_LEXEME_TYPE m_type;	//!< тип лексемы
	ID m_idWord;			//!< порядковый номер лексемы из массива слов к которому она относится
	ID m_idFile;			//!< порядковый номер файла
};

Типы лексем:

//! типы лексем
enum S4G_LEXEME_TYPE
{
	S4G_LEXEME_TYPE_WORD_USER,				//!< пользовательское слово
	S4G_LEXEME_TYPE_WORD_STRING,			//!< строка
	S4G_LEXEME_TYPE_WORD_FLOAT,				//!< число с плавающей запятой
	S4G_LEXEME_TYPE_WORD_INT,				//!< целое знаковое число
	S4G_LEXEME_TYPE_WORD_UINT,				//!< целое беззнаковое число
	S4G_LEXEME_TYPE_WORD_KEY,				//!< ключевое слово языка
	S4G_LEXEME_TYPE_WORD_PREP,				//!< слово препроцессора
	S4G_LEXEME_TYPE_MARG,					//!< переменное количество аргументов
	S4G_LEXEME_TYPE_SYM_DELIMITER,			//!< символ разделителя
	S4G_LEXEME_TYPE_SYM_ARITHMETIC,			//!< арифметический символ
	S4G_LEXEME_TYPE_SYM_LOGIC,				//!< символ логических операций
	S4G_LEXEME_TYPE_SYM_BIT,				//!< символ битовых операций
	S4G_LEXEME_TYPE_SYM_ASSIGN,				//!< символ присвоения
	S4G_LEXEME_TYPE_SYM_ARITHMETIC_ASSIGN,	//!< арифметический символ и присвоение
	S4G_LEXEME_TYPE_SYM_BIT_ASSIGN,			//!< символ битовой операции и присвоение
	S4G_LEXEME_TYPE_SYM_GROUP_EXPR,			//!< символ группировки выражений
	S4G_LEXEME_TYPE_SYM_GROUP_DATA,			//!< символ группировки данных
	S4G_LEXEME_TYPE_SYM_A2O,				//!< символ обращения к объекту
};

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

Итог

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

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

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

Предполагаемые типы лексем задает грамматика языка (в простом смысле его синтаксис).

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

Поделиться:

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

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

*