Лексическая токенизация — это преобразование текста в (семантически или синтаксически) значимые лексические токены, принадлежащие категориям, определенным программой «лексер». В случае естественного языка эти категории включают существительные, глаголы, прилагательные, знаки препинания и т. д. В случае языка программирования категории включают идентификаторы, операторы, группирующие символы и типы данных . Лексическая токенизация связана с типом токенизации, используемым в больших языковых моделях (LLM), но с двумя отличиями. Во-первых, лексическая токенизация обычно основана на лексической грамматике , тогда как токенизаторы LLM обычно основаны на вероятности . Во-вторых, токенизаторы LLM выполняют второй шаг, который преобразует токены в числовые значения.
Программа на основе правил, выполняющая лексическую токенизацию, называется токенизатором [1] или сканером , хотя сканер также является термином для первой стадии лексера. Лексер образует первую фазу внешнего интерфейса компилятора при обработке. Анализ обычно происходит за один проход. Лексеры и парсеры чаще всего используются для компиляторов, но могут использоваться для других инструментов компьютерного языка, таких как prettyprinters или linters . Лексинг можно разделить на два этапа: сканирование , которое сегментирует входную строку на синтаксические единицы, называемые лексемами , и категоризирует их в классы токенов, и оценку , которая преобразует лексемы в обработанные значения.
Лексеры, как правило, довольно просты, большая часть сложности отложена на фазы синтаксического анализа или семантического анализа , и часто могут быть сгенерированы генератором лексеров, в частности лексами или производными. Однако лексеры иногда могут включать некоторую сложность, такую как обработка структуры фразы, чтобы сделать ввод проще и упростить парсер, и могут быть написаны частично или полностью вручную, либо для поддержки большего количества функций, либо для производительности.
То, что называется «лексемой» в обработке естественного языка на основе правил , не равно тому, что называется лексемой в лингвистике. То, что называется «лексемой» в обработке естественного языка на основе правил, может быть равно лингвистическому эквиваленту только в аналитических языках , таких как английский, но не в высокосинтетических языках , таких как фузионные языки . То, что называется лексемой в обработке естественного языка на основе правил, больше похоже на то, что называется словом в лингвистике (не путать со словом в компьютерной архитектуре ), хотя в некоторых случаях оно может быть больше похоже на морфему .
Лексический токен — это строка с назначенным и, таким образом, идентифицированным значением, в отличие от вероятностного токена, используемого в больших языковых моделях . Лексический токен состоит из имени токена и необязательного значения токена . Имя токена — это категория лексической единицы, основанной на правилах. [2]
Рассмотрим это выражение на языке программирования 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-х годах, особенно для ALGOL , пробелы и комментарии были устранены как часть фазы реконструкции строки (начальная фаза интерфейса компилятора ), но эта отдельная фаза была устранена, и теперь они обрабатываются лексером.
Первый этап, сканер , обычно основан на конечном автомате (FSM). Он закодировал в себе информацию о возможных последовательностях символов, которые могут содержаться в любом из токенов, которые он обрабатывает (отдельные экземпляры этих последовательностей символов называются лексемами). Например, целочисленная лексема может содержать любую последовательность числовых цифровых символов. Во многих случаях первый непробельный символ может использоваться для определения вида следующего токена, а последующие входные символы затем обрабатываются по одному за раз, пока не будет достигнут символ, который не входит в набор символов, приемлемых для этого токена (это называется правилом максимального пережевывания или самого длинного соответствия ). В некоторых языках правила создания лексем более сложны и могут включать возврат по ранее прочитанным символам. Например, в C одного символа 'L' недостаточно, чтобы отличить идентификатор, начинающийся с 'L', от строкового литерала с широкими символами.
Однако лексема — это всего лишь строка символов, о которой известно, что она принадлежит к определенному виду (например, строковый литерал, последовательность букв). Чтобы построить токен, лексическому анализатору требуется вторая ступень, оценщик , который проходит по символам лексемы, чтобы получить значение . Тип лексемы в сочетании с ее значением — это то, что собственно составляет токен, который может быть передан синтаксическому анализатору. Некоторые токены, такие как скобки, на самом деле не имеют значений, и поэтому функция оценщика для них может ничего не возвращать: нужен только тип. Аналогично, иногда оценщики могут полностью подавить лексему, скрыв ее от синтаксического анализатора, что полезно для пробелов и комментариев. Оценщики для идентификаторов обычно просты (буквально представляют идентификатор), но могут включать в себя некоторую расстроповку . Оценщики для целочисленных литералов могут передавать строку (откладывая оценку до фазы семантического анализа) или могут выполнять оценку самостоятельно, что может быть задействовано для различных оснований или чисел с плавающей точкой. Для простого строкового литерала в кавычках оценщику нужно удалить только кавычки, но оценщик для экранированного строкового литерала включает лексер, который расэкранирует escape-последовательности.
Например, в исходном коде компьютерной программы строка
net_worth_future = (assets – liabilities);может быть преобразован в следующий поток лексических токенов; пробелы подавляются, а специальные символы не имеют значения:
ИДЕНТИФИКАТОР чистая_стоимость_будущееРАВНЫЕОТКРЫТЫЕ_СКОБКИИДЕНТИФИКАТОР активыМИНУСИДЕНТИФИКАТОР обязательстваЗАКРЫТЬ_СКОБКИТОЧКА С ЗАПЯТОЙ
Лексеры могут быть написаны вручную. Это практично, если список токенов невелик, но лексеры, сгенерированные автоматизированным инструментарием как часть цепочки инструментов компилятор-компилятор, более практичны для большего числа потенциальных токенов. Эти инструменты обычно принимают регулярные выражения, которые описывают токены, разрешенные во входном потоке. Каждое регулярное выражение связано с производственным правилом в лексической грамматике языка программирования, которое оценивает лексемы, соответствующие регулярному выражению. Эти инструменты могут генерировать исходный код, который может быть скомпилирован и выполнен, или создавать таблицу переходов состояний для конечного автомата (который подключается к шаблонному коду для компиляции и выполнения).
Регулярные выражения компактно представляют шаблоны, которым могут следовать символы в лексемах. Например, для языка на основе английского языка токен IDENTIFIER может быть любым английским буквенным символом или символом подчеркивания, за которым следует любое количество вхождений буквенно-цифровых символов ASCII и/или символов подчеркивания. Это может быть компактно представлено строкой [a-zA-Z_][a-zA-Z_0-9]*. Это означает «любой символ az, AZ или _, за которым следует 0 или более символов az, AZ, _ или 0-9».
Регулярные выражения и генерируемые ими конечные автоматы недостаточно мощны для обработки рекурсивных шаблонов, таких как " n открывающихся скобок, за которыми следует оператор, за которым следует n закрывающихся скобок". Они не способны вести подсчет и проверять, что n одинаково с обеих сторон, если только не существует конечного набора допустимых значений для n . Для распознавания таких шаблонов в их полной общности требуется полный синтаксический анализатор. Синтаксический анализатор может помещать скобки в стек, а затем пытаться вытащить их и смотреть, пуст ли стек в конце (см. пример [3] в книге "Структура и интерпретация компьютерных программ" ).
Обычно лексическая токенизация происходит на уровне слов. Однако иногда бывает сложно определить, что подразумевается под «словом». Часто токенизатор полагается на простые эвристики, например:
В языках, использующих межсловные пробелы (например, в большинстве языков, использующих латинский алфавит, и в большинстве языков программирования), этот подход довольно прост. Однако даже здесь есть много пограничных случаев, таких как сокращения , слова с дефисом , смайлики и более крупные конструкции, такие как URI (которые для некоторых целей могут считаться отдельными токенами). Классический пример — «New York-based», который наивный токенизатор может разбить на пробеле, хотя лучший разрыв (возможно) — на дефисе.
Токенизация особенно сложна для языков, написанных в scriptio continua , которые не имеют границ слов, таких как древнегреческий , китайский , [4] или тайский . Агглютинативные языки , такие как корейский, также усложняют задачи токенизации.
Некоторые способы решения более сложных проблем включают разработку более сложных эвристик, запрос таблицы общих особых случаев или подгонку токенов под языковую модель , которая идентифицирует словосочетания на более позднем этапе обработки.
Лексеры часто генерируются генератором лексеров , аналогичным генераторам парсеров , и такие инструменты часто объединяются. Наиболее устоявшимся является lex , в паре с генератором парсеров yacc , или, скорее, некоторые из их многочисленных реализаций, таких как flex (часто в паре с GNU Bison ). Эти генераторы являются формой языка , специфичного для предметной области, принимающего лексическую спецификацию — обычно регулярные выражения с некоторой разметкой — и выдающего лексер.
Эти инструменты обеспечивают очень быструю разработку, что очень важно на ранних этапах разработки, как для получения работающего лексера, так и потому, что спецификация языка может часто меняться. Кроме того, они часто предоставляют расширенные функции, такие как пред- и постусловия, которые трудно программировать вручную. Однако автоматически сгенерированный лексер может не обладать гибкостью, и поэтому может потребоваться некоторая ручная модификация или полностью написанный вручную лексер.
Производительность лексера вызывает беспокойство, и оптимизация имеет смысл, особенно в стабильных языках, где лексер запускается очень часто (например, C или HTML). Лексеры, сгенерированные lex/flex, достаточно быстры, но возможны улучшения в два-три раза с использованием более настроенных генераторов. Иногда используются рукописные лексеры, но современные генераторы лексеров производят более быстрые лексеры, чем большинство вручную закодированных. Семейство генераторов lex/flex использует табличный подход, который гораздо менее эффективен, чем подход с прямым кодированием. [ сомнительно – обсудить ] При последнем подходе генератор создает движок, который напрямую переходит к последующим состояниям с помощью операторов goto. Такие инструменты, как re2c [5], доказали свою способность создавать движки, которые в два-три раза быстрее, чем движки, созданные flex. [ необходима цитата ] В целом сложно вручную написать анализаторы, которые работают лучше, чем движки, созданные этими последними инструментами.
Лексический анализ в основном сегментирует входной поток символов на токены, просто группируя символы в части и категоризируя их. Однако лексирование может быть значительно более сложным; проще говоря, лексеры могут опускать токены или вставлять добавленные токены. Пропуск токенов, особенно пробелов и комментариев, очень распространен, когда они не нужны компилятору. Реже могут быть вставлены добавленные токены. Это делается в основном для группировки токенов в операторы или операторов в блоки для упрощения синтаксического анализатора.
Продолжение строки — это функция некоторых языков, где новая строка обычно является терминатором оператора. Чаще всего завершение строки обратной косой чертой (сразу за которой следует новая строка ) приводит к тому, что строка продолжается — следующая строка присоединяется к предыдущей. Обычно это делается в лексере: обратная косая черта и новая строка отбрасываются, а не новая строка токенизируется. Примерами служат bash , [6] другие скрипты оболочки и Python. [7]
Во многих языках точка с запятой используется в качестве терминатора оператора. Чаще всего это обязательно, но в некоторых языках точка с запятой необязательна во многих контекстах. Это в основном делается на уровне лексера, где лексер выводит точку с запятой в поток токенов, несмотря на то, что она отсутствует во входном потоке символов, и называется вставкой точки с запятой или автоматической вставкой точки с запятой . В этих случаях точки с запятой являются частью формальной фразовой грамматики языка, но могут отсутствовать во входном тексте, поскольку их может вставить лексер. Необязательные точки с запятой или другие терминаторы или разделители также иногда обрабатываются на уровне синтаксического анализатора, особенно в случае конечных запятых или точек с запятой.
Вставка точки с запятой является функцией BCPL и его дальнего потомка Go , [8] хотя она отсутствует в B или C. [9] Вставка точки с запятой присутствует в JavaScript , хотя правила довольно сложны и часто подвергаются критике; чтобы избежать ошибок, некоторые рекомендуют всегда использовать точку с запятой, в то время как другие используют начальные точки с запятой, называемые защитными точками с запятой , в начале потенциально неоднозначных утверждений.
Вставку точки с запятой (в языках с операторами, завершаемыми точкой с запятой) и продолжение строки (в языках с операторами, завершаемыми символом новой строки) можно рассматривать как взаимодополняющие: вставка точки с запятой добавляет токен, хотя переводы строк обычно не генерируют токены, в то время как продолжение строки предотвращает генерацию токена, хотя переводы строк обычно генерируют токены.
Правило «off-side » (блоки, определяемые отступом) может быть реализовано в лексере, как в Python , где увеличение отступа приводит к тому, что лексер выдает токен INDENT, а уменьшение отступа приводит к тому, что лексер выдает один или несколько токенов DEDENT. [10] Эти токены соответствуют открывающей фигурной скобке {и закрывающей фигурной скобке }в языках, которые используют фигурные скобки для блоков, и означают, что грамматика фразы не зависит от того, используются ли фигурные скобки или отступы. Это требует, чтобы лексер удерживал состояние, а именно стек уровней отступа, и, таким образом, мог обнаруживать изменения в отступе при его изменении, и, таким образом, лексическая грамматика не является контекстно-свободной : INDENT–DEDENT зависят от контекстной информации предыдущих уровней отступа.
Обычно лексические грамматики являются контекстно-свободными или почти таковыми, и поэтому не требуют оглядывания назад или вперед, или возврата назад, что позволяет простую, чистую и эффективную реализацию. Это также позволяет простую одностороннюю связь от лексера к парсеру, без необходимости какой-либо информации, поступающей обратно в лексер.
Однако есть исключения. Простые примеры включают вставку точки с запятой в Go, которая требует просмотра одного токена назад; конкатенацию последовательных строковых литералов в Python [7] , которая требует удержания одного токена в буфере перед его выдачей (чтобы увидеть, является ли следующий токен другим строковым литералом); и правило «вне стороны» в Python, которое требует поддержания счетчика уровней отступа (на самом деле, стека каждого уровня отступа). Все эти примеры требуют только лексического контекста, и хотя они несколько усложняют лексер, они невидимы для парсера и более поздних фаз.
Более сложным примером является хак лексера в C, где класс токена последовательности символов не может быть определен до фазы семантического анализа, поскольку имена typedef и имена переменных лексически идентичны, но составляют разные классы токенов. Таким образом, в хаке лексер вызывает семантический анализатор (например, таблицу символов) и проверяет, требует ли последовательность имени typedef. В этом случае информация должна поступать не только из парсера, но и из семантического анализатора обратно в лексер, что усложняет проектирование.