Лексический анализ

«Лексер» перенаправляется сюда. Чтобы узнать о людях с этим именем, см. Лексер (фамилия) .

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

Программы, основанные на правилах

Программа, основанная на правилах и выполняющая лексическую токенизацию, называется tokenizer . или сканер , хотя сканер также является термином для первой стадии лексера. Лексер формирует первую фазу внешнего интерфейса компилятора обработки . Анализ обычно происходит за один проход. Лексеры и парсеры чаще всего используются для компиляторов, но могут использоваться и для других инструментов компьютерного языка, таких как Prettyprinters или линтеров . Лексирование можно разделить на два этапа: сканирование , при котором входная строка сегментируется на синтаксические единицы, называемые лексемами , и классифицируется по классам токенов, и оценка , которая преобразует лексемы в обработанные значения.

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

Значение слова «лексема»

См. Также: Граница слова (лингвистика) и Граница слова (вычисления).

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

Лексический токен и лексическая токенизация

Не путать с Большой языковой моделью § Вероятностная токенизация , или токенизация (безопасность данных) .

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

Примеры общих токенов

Имя токена	Объяснение	Примеры значений токенов
идентификатор	Имена присвоены программистом.	x, color, UP
ключевое слово	Зарезервированные слова языка.	if, while, return
разделитель/пунктуатор	Знаки пунктуации и парные разделители.	}, (, ;
оператор	Символы, которые оперируют аргументами и дают результаты.	+, <, =
буквальный	Числовые, логические, текстовые и ссылочные литералы.	true, 6.02e23, "music"
комментарий	Линия или блокировка комментариев. Обычно отбрасывают.	/* Retrieves user data */, // must be negative
пробелы	Группы непечатаемых символов. Обычно отбрасывают.	–

Рассмотрим это выражение на языке программирования C :

x = a + b * 2;

Лексический анализ этого выражения дает следующую последовательность токенов:

[(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]

Имя-токен – это то, что в лингвистике можно назвать частью речи .

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

Например, в текстовой строке :

The quick brown fox jumps over the lazy dog

строка не сегментируется неявно по пробелам, как это естественного языка сделал бы носитель . Необработанные входные данные, 43 символа, должны быть явно разделены на 9 токенов с заданным разделителем пробелов (т. е. в соответствии со строкой " " или регулярное выражение /\s{1}/).

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

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

Когда лексер передает токены в анализатор, используемое представление обычно представляет собой перечислимый тип , который представляет собой список числовых представлений. Например, «Идентификатор» может быть представлен цифрой 0, «Оператор присваивания» — цифрой 1, «Оператор сложения» — цифрой 2 и т. д.

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

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

Лексическая грамматика

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

Двумя важными общими лексическими категориями являются пробелы и комментарии . Они также определяются в грамматике и обрабатываются лексером, но могут быть отброшены (не создавая никаких токенов) и считаться несущественными , разделяя максимум два токена (как в if x вместо ifx). Из этого правила есть два важных исключения. Во-первых, в языках внешних правил , которые разделяют блоки с помощью отступов, начальные пробелы имеют важное значение, поскольку они определяют структуру блока и обычно обрабатываются на уровне лексера; см. структуру фразы ниже. Во-вторых, в некоторых случаях использования лексеров комментарии и пробелы должны сохраняться — например, Prettyprinter также должен выводить комментарии, а некоторые инструменты отладки могут предоставлять программисту сообщения, показывающие исходный исходный код. В 1960-х годах, особенно в АЛГОЛе , пробелы и комментарии были устранены как часть фазы реконструкции строки (начальная фаза внешнего интерфейса компилятора ), но эта отдельная фаза была исключена, и теперь они обрабатываются лексером.

Подробности

Сканер

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

оценщик

Однако лексема — это всего лишь строка символов, о которых известно, что они относятся к определенному типу (например, строковый литерал, последовательность букв). Для создания токена лексическому анализатору необходим второй этап — оценщик , который перебирает символы лексемы для получения значения . Тип лексемы в сочетании с ее значением представляет собой токен, который может быть передан анализатору. Некоторые токены, такие как круглые скобки, на самом деле не имеют значений, поэтому функция оценки для них не может ничего возвращать: нужен только тип. Точно так же иногда оценщики могут полностью скрыть лексему, скрывая ее от анализатора, что полезно для пробелов и комментариев. Оценщики идентификаторов обычно просты (буквально представляют идентификатор), но могут включать в себя некоторые unstropping . Оценщики целочисленных литералов могут передать строку (отложив оценку до фазы семантического анализа) или могут выполнить оценку самостоятельно, которая может использоваться для разных базисных чисел или чисел с плавающей запятой. Для простого строкового литерала в кавычках оценщику необходимо удалить только кавычки, а для Экранированный строковый литерал включает в себя лексер, который восстанавливает escape-последовательности.

Например, в исходном коде компьютерной программы строка

net_worth_future = (assets – liabilities);

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

IDENTIFIER net_worth_future
EQUALS
OPEN_PARENTHESIS
IDENTIFIER assets
MINUS
IDENTIFIER liabilities
CLOSE_PARENTHESIS
SEMICOLON

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

Регулярные выражения компактно представляют шаблоны, которым могут следовать символы в лексемах. Например, для языка, основанного на английском языке , маркером IDENTIFIER может быть любой буквенный символ английского языка или знак подчеркивания, за которым следует любое количество экземпляров буквенно-цифровых символов ASCII и/или символов подчеркивания. Это можно компактно представить строкой [a-zA-Z_][a-zA-Z_0-9]*. Это означает «любой символ az, AZ или _, за которым следует 0 или более символов az, AZ, _ или 0–9».

Регулярные выражения и генерируемые ими конечные автоматы недостаточно мощны для обработки рекурсивных шаблонов, таких как « n открывающих круглых скобок, за которыми следует оператор, за которым следуют n закрывающих скобок». Они не могут вести подсчет и проверять, что n одинаково с обеих сторон, если только для n не существует конечного набора допустимых значений . Чтобы распознать такие шаблоны во всей их полноте, требуется полноценный синтаксический анализатор. Парсер может поместить круглые скобки в стек, а затем попытаться вытащить их и посмотреть, пуст ли стек в конце (см. пример в книге «Структура и интерпретация компьютерных программ» ).

Препятствия

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

• Знаки пунктуации и пробелы могут включаться или не включаться в результирующий список токенов.
• Все смежные строки буквенных символов являются частью одного токена; аналогично и с числами.
• Токены разделяются пробелами , такими как пробел или разрыв строки, или знаками пунктуации.

В языках, в которых используются пробелы между словами (например, в большинстве языков, использующих латинский алфавит, и в большинстве языков программирования), этот подход довольно прост. Однако даже здесь существует множество крайних случаев, таких как сокращения , через дефис слова , смайлы и более крупные конструкции, такие как URI (которые для некоторых целей могут считаться отдельными токенами). Классический пример — «Находится в Нью-Йорке», который наивный токенизатор может разбить на пробел, даже если лучший разрыв (возможно) на дефисе.

Токенизация особенно сложна для языков, написанных в scriptio continua , которые не имеют границ между словами, таких как древнегреческий , китайский , или тайский . Агглютинативные языки , такие как корейский, также усложняют задачи токенизации.

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

Лексерный генератор

См. также: Генератор парсера.

Лексеры часто генерируются генератором лексеров , аналогичным генераторам синтаксических анализаторов , и такие инструменты часто объединяются. Наиболее известным является lex в паре с генератором синтаксического анализатора yacc , или, скорее, некоторые из их многочисленных реализаций, например flex (часто в паре с GNU Bison ). Эти генераторы представляют собой форму предметно-ориентированного языка , принимающего лексическую спецификацию (обычно регулярные выражения с некоторой разметкой) и создающего лексер.

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

Производительность лексера вызывает беспокойство, и оптимизация имеет смысл, особенно в стабильных языках, где лексер запускается очень часто (например, C или HTML). Лексеры, сгенерированные lex/flex, достаточно быстры, но возможно улучшение в два-три раза при использовании более настроенных генераторов. Иногда используются рукописные лексеры, но современные генераторы лексеров производят более быстрые лексеры, чем большинство написанных вручную. Семейство генераторов lex/flex использует табличный подход, который гораздо менее эффективен, чем подход с прямым кодированием. При последнем подходе генератор создает механизм, который напрямую переходит к последующим состояниям с помощью операторов перехода. Такие инструменты, как re2c доказали, что производят двигатели, которые работают в два-три раза быстрее, чем двигатели гибкого производства. Как правило, сложно написать вручную анализаторы, которые будут работать лучше, чем механизмы, созданные этими последними инструментами.

Структура фразы

Лексический анализ в основном сегментирует входной поток символов на токены, просто группируя символы на части и классифицируя их. Однако лексика может быть значительно более сложной; Проще говоря, лексеры могут опускать токены или вставлять добавленные токены. Пропуск токенов, особенно пробелов и комментариев, очень распространен, когда они не нужны компилятору. Реже могут быть вставлены дополнительные токены. Это делается в основном для группировки токенов в операторы или операторов в блоки, чтобы упростить синтаксический анализатор.

Продолжение линии

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

Вставка точки с запятой

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

Вставка точки с запятой — особенность BCPL и его дальнего потомка Go . хотя он отсутствует в B или C. Вставка точки с запятой присутствует в JavaScript , хотя правила несколько сложны и подвергаются большой критике; Чтобы избежать ошибок, некоторые рекомендуют всегда использовать точки с запятой, в то время как другие используют начальные точки с запятой, называемые защитными точками с запятой , в начале потенциально неоднозначных операторов.

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

Правило офсайда

Дополнительная информация: Правило офсайда.

Правило off-side (блоки, определенные с помощью отступов) может быть реализовано в лексере, как в Python , где увеличение отступов приводит к тому, что лексер выдает токен INDENT, а уменьшение отступов приводит к тому, что лексер выдает один или несколько токенов DEDENT. Эти токены соответствуют открывающей скобке. { и закрывающая скобка } в языках, в которых для блоков используются фигурные скобки, и означает, что грамматика фраз не зависит от того, используются ли фигурные скобки или отступы. Для этого требуется, чтобы лексер удерживал состояние, а именно стек уровней отступов, и, таким образом, мог обнаруживать изменения в отступах при его изменении, и, таким образом, лексическая грамматика не является контекстно-свободной : ОТМЕН – ОТМЕНА зависят от контекстной информации предыдущих уровней отступов.

Контекстно-зависимая лексика

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

Однако есть исключения. Простые примеры включают вставку точки с запятой в Go, которая требует просмотра одного токена; объединение последовательных строковых литералов в Python, который требует хранения одного токена в буфере перед его отправкой (чтобы проверить, является ли следующий токен другим строковым литералом); и правило оффсайда в Python, которое требует поддержания подсчета уровней отступа (фактически, стека каждого уровня отступа). Все эти примеры требуют только лексического контекста, и хотя они несколько усложняют лексер, они невидимы для синтаксического анализатора и последующих этапов.

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

См. также

• Лексикализация
• Лексическая семантика
• Список генераторов парсеров

Ссылки

Источники

• Компиляция с помощью C# и Java , Пэт Терри, 2005 г., ISBN   032126360X
• Алгоритмы + Структуры данных = Программы , Никлаус Вирт, 1975, ISBN   0-13-022418-9
• «Строительство компилятора» , Никлаус Вирт, 1996 г., ISBN   0-201-40353-6
• Себеста, RW (2006). Концепции языков программирования (Седьмое издание), стр. 177. Бостон: Пирсон/Аддисон-Уэсли.

Внешние ссылки

• Ян, В.; Цай, Чей-Воэй; Чан, Цзянь-Цай (2002). «О применимости правила наибольшего совпадения в лексическом анализе» . Компьютерные языки, системы и структуры . 28 (3): 273–288. дои : 10.1016/S0096-0551(02)00014-0 . НСК 86-2213-Е-009-021 и НСК 86-2213-Е-009-079.
• Трим, Крейг (23 января 2013 г.). «Искусство токенизации» . Разработчик работает . ИБМ. Архивировано из оригинала 30 мая 2019 г.
• Задача сегментации упоминаний слов , анализ