Войти
В информатике, лексический анализ, лексирование или токенизация - это процесс преобразования последовательности символов (например, в компьютерной программе или веб-страница ) в последовательность токенов (строки с присвоенным и, таким образом, идентифицированным значением). Программа, выполняющая лексический анализ, может быть названа лексером, токенизатором или сканером, хотя сканер также является термином для первого этапа лексического анализатора. Лексический анализатор обычно сочетается с парсером , который вместе анализирует синтаксис языков программирования, веб-страниц и т. Д.
Лексер формирует первую фазу внешнего интерфейса компилятора в современной обработке. Обычно анализ выполняется за один проход.
В более старых языках, таких как АЛГОЛ, начальным этапом вместо этого была реконструкция строки, которая выполняла удаление строки и удаление пробелов и комментариев. (и имел парсеры без сканирования, без отдельного лексера). Эти шаги теперь выполняются как часть лексера.
Лексеры и синтаксические анализаторы чаще всего используются для компиляторов, но могут использоваться и для других инструментов компьютерного языка, таких как prettyprinters или линтеры. Лексирование можно разделить на два этапа: сканирование, которое сегментирует входную строку на синтаксические единицы, называемые лексемами, и разделяет их на классы токенов; и оценка, которая преобразует лексемы в обработанные значения.
Лексеры, как правило, довольно просты, большая часть сложности возложена на синтаксический анализатор или семантический анализ фаз, и часто могут быть сгенерированы генератором лексера, в частности lex или производные. Однако лексеры иногда могут включать некоторую сложность, такую как обработка структуры фразы, чтобы упростить ввод и упростить синтаксический анализатор, и могут быть написаны частично или полностью вручную, либо для поддержки дополнительных функций, либо для повышения производительности.
Лексический анализ также является важным ранним этапом в обработке естественного языка, когда текст или звуковые волны сегментируются на слова и другие единицы. Это требует множества решений, которые не полностью стандартизированы, а количество производимых системой токенов варьируется для таких строк, как «1/2», «Chair's», «cannot», «and / or», «1/1 /». 2010 »,« 2х4 »,«..., »и многие другие. Это контрастирует с лексическим анализом для программирования и подобных языков, где точные правила обычно определены и известны.
Лексема - это последовательность символов в исходной программе, которая соответствует шаблону для токена и идентифицируется лексическим анализатором как экземпляр этого токена.
Некоторые авторы называют это «токеном», взаимозаменяемо используя «токен» для представления токенизируемой строки и структуры данных токена, полученной в результате помещения этой строки в процесс токенизации.
словесная лексема в информатике определяется иначе, чем лексема в лингвистике. Лексема в информатике примерно соответствует слову в лингвистике (не путать со словом в компьютерной архитектуре ), хотя в некоторых случаях она может быть больше похожа на морфема.
Лексический токен или просто токен - это строка с присвоенным и, таким образом, идентифицированным значением. Он структурирован как пара, состоящая из имени токена и необязательного значения токена. Имя токена - это категория лексической единицы. Общие имена токенов:
| Имя токена | Примеры значений токена |
|---|---|
| идентификатор | x, цвет, UP |
| ключевое слово | if, в то время как, возвращают |
| разделитель | }, (, ; |
| оператор | +, <, = |
| литерал | истина, 6.02e23, "музыка" |
| комментарий | / * Извлекает данные пользователя * /, // должно быть отрицательным |
Рассмотрим это выражение на языке программирования C :
x = a + b * 2;Лексический анализ этого выражения дает следующую последовательность токенов:
[(идентификатор, x), (оператор, =), (идентификатор, a), (оператор, +), (идентификатор, b), (оператор, *), (литерал, 2), (разделитель,;)]Знаковое имя - это то, что в лингвистике можно назвать частью речи.
Спецификация языка программирования часто включает набор правил, лексическая грамматика, которая определяет лексический синтаксис. Лексический синтаксис - это обычно регулярный язык, с правилами грамматики, состоящими из регулярных выражений ; они определяют набор возможных последовательностей символов (лексем) токена. Лексический анализатор распознает строки, и для каждого типа найденных строк лексическая программа выполняет действие, наиболее просто создавая токен.
Две важные общие лексические категории: пробел и комментарии. Они также определены в грамматике и обрабатываются лексером, но могут быть отброшены (без создания каких-либо токенов) и считаться несущественными, не более чем с разделением двух токенов (как в , если xвместо ifx). Из этого правила есть два важных исключения. Во-первых, в языках off-side rule, которые разделяют блоки с помощью отступов, начальные пробелы имеют значение, поскольку они определяют структуру блока и обычно обрабатываются на уровне лексера; см. структуру фразы ниже. Во-вторых, в некоторых случаях использования лексеров комментарии и пробелы должны быть сохранены - например, prettyprinter также должно выводить комментарии, а некоторые инструменты отладки могут предоставлять программисту сообщения, показывающие исходный исходный код. В 1960-х, особенно для АЛГОЛА, пробелы и комментарии были удалены как часть фазы реконструкции строки (начальная фаза внешнего интерфейса компилятора ), но это Отдельная фаза была удалена, и теперь они обрабатываются лексером.
Токенизация - это процесс разграничения и, возможно, классификации разделов строки входных символов. Полученные токены затем передаются в другую форму обработки. Процесс можно рассматривать как подзадачу синтаксического анализа ввода.
Например, в тексте строка :
Быстрая коричневая лиса перепрыгивает через ленивого псастрока не сегментирована неявно по пробелам, так как естественный язык Динамик подойдет. Необработанный ввод, 43 символа, должен быть явно разделен на 9 токенов с заданным разделителем пробелов (т. Е. Соответствует строке ""или регулярному выражению / \ s {1} /).
Жетоны могут быть представлены в XML,
The quick коричневом fox прыжках поверх ленивый собака
или как s-выражение,
(предложение (слово The) (слово quick) (слово коричневый) (слово лиса) (слово перескакивает) (слово поверх) (слово the) (слово ленивый) (слово собака))
Когда класс лексемы представляет более одной возможной лексемы, лексер часто сохраняет достаточно информации для воспроизведения исходной лексемы, чтобы ее можно было использовать в семантическом анализе. Синтаксический анализатор обычно получает эту информацию из лексического анализатора и сохраняет ее в абстрактном синтаксическом дереве . Это необходимо во избежание потери информации в случае чисел и идентификаторов.
Токены идентифицируются на основе определенных правил лексера. Некоторые методы, используемые для идентификации токенов, включают: регулярные выражения, определенные последовательности символов, называемые флагом, определенные разделяющие символы, называемые разделителями, и явное определение словарём. Специальные символы, включая знаки препинания, обычно используются лексерами для идентификации лексем, поскольку они естественным образом используются в письменных языках и языках программирования.
Токены часто классифицируются по содержанию символа или по контексту в потоке данных. Категории определяются правилами лексера. Категории часто включают элементы грамматики языка, используемого в потоке данных. В языках программирования токены часто классифицируются как идентификаторы, операторы, символы группировки или по типу данных . В письменных языках токены обычно делятся на существительные, глаголы, прилагательные или знаки препинания. Категории используются для пост-обработки токенов либо парсером, либо другими функциями программы.
Лексический анализатор обычно ничего не делает с комбинациями лексем, задача, оставленная парсеру . Например, типичный лексический анализатор распознает круглые скобки как токены, но ничего не делает, чтобы гарантировать, что каждому "(" соответствует ")".
Когда лексический анализатор передает токены анализатору, используемое представление обычно представляет собой нумерованный список представлений чисел. Например, «Идентификатор» представлен с помощью 0, «Оператор присваивания» - с 1, «Оператор сложения» с 2 и т. Д.
Токены часто определяются с помощью регулярных выражений, которые понимаются генератором лексического анализатора, например lex. Лексический анализатор (сгенерированный автоматически с помощью такого инструмента, как lex, или созданный вручную) считывает поток символов, идентифицирует лексемы в потоке и классифицирует их по токенам. Это называется токенизацией. Если лексер находит недопустимый токен, он сообщит об ошибке.
После токенизации выполняется синтаксический анализ. Оттуда интерпретированные данные могут быть загружены в структуры данных для общего использования, интерпретации или компиляции.
Первый этап, сканер, обычно основан на конечном конечный автомат (FSM). Он закодировал в нем информацию о возможных последовательностях символов, которые могут содержаться в любых токенах, которые он обрабатывает (отдельные экземпляры этих последовательностей символов называются лексемами). Например, целочисленная лексема может содержать любую последовательность цифровых цифр символов. Во многих случаях первый непробельный символ может использоваться для определения типа следующего за ним токена, а последующие входные символы затем обрабатываются по одному до тех пор, пока не будет достигнут символ, который не входит в набор символов, приемлемых для этого токена (это называется правилом максимального пережевывания или самого длинного совпадения). В некоторых языках правила создания лексемы более сложные и могут включать возврат по ранее прочитанным символам. Например, в языке C одного символа «L» недостаточно, чтобы отличить идентификатор, начинающийся с «L», и строковый литерал широких символов.
A лексема, однако, представляет собой только строку символов определенного типа (например, строковый литерал, последовательность букв). Чтобы построить лексему, лексическому анализатору нужен второй этап, вычислитель, который перебирает символы лексемы для получения значения. Тип лексемы в сочетании с ее значением - это то, что должным образом составляет токен, который может быть передан синтаксическому анализатору. Некоторые токены, такие как круглые скобки, на самом деле не имеют значений, поэтому функция оценки для них ничего не может вернуть: нужен только тип. Точно так же иногда оценщики могут полностью подавить лексему, скрывая ее от парсера, что полезно для пробелов и комментариев. Оценщики для идентификаторов обычно простые (буквально представляют идентификатор), но могут включать в себя некоторые отмены. Оценщики для целочисленных литералов могут передавать строку (откладывая оценку до фазы семантического анализа) или могут выполнять оценку самостоятельно, что может быть задействовано для различных оснований или чисел с плавающей запятой. Для простого строкового литерала в кавычках оценщику необходимо удалить только кавычки, но оценщик для экранированного строкового литерала включает лексер, который отменяет экранирование управляющих последовательностей.
Например, в исходном коде компьютерной программы строка
net_worth_future = (assets - liabilities);может быть преобразована в следующий поток лексических токенов; пробелы подавляются, а специальные символы не имеют значения:
IDENTIFIER net_worth_future EQUALS OPEN_PARENTHESIS IDENTIFIER assets MINUS IDENTIFIER обязательства CLOSE_PARENTHESIS SEMICOLON
Из-за лицензионных ограничений существующих синтаксических анализаторов может потребоваться написать лексический анализатор рука. Это удобно, если список токенов невелик, но, как правило, лексеры генерируются автоматическими инструментами. Эти инструменты обычно принимают регулярные выражения, которые описывают токены, разрешенные во входном потоке. Каждое регулярное выражение связано с продукционным правилом в лексической грамматике языка программирования, которое оценивает лексемы, соответствующие регулярному выражению. Эти инструменты могут генерировать исходный код, который может быть скомпилирован и выполнен, или построить таблицу переходов между состояниями для конечного автомата (который вставляется в код шаблона для компиляции и выполнения).
Регулярные выражения компактно представляют шаблоны, которым могут следовать символы в лексемах. Например, для языка на основе английский токен IDENTIFIER может быть любым английским алфавитным символом или знаком подчеркивания, за которым следует любое количество экземпляров буквенно-цифровых символов ASCII и / или подчеркиваний. Это может быть компактно представлено строкой [a-zA-Z _] [a-zA-Z_0-9] *. Это означает «любой символ a-z, A-Z или _, за которым следует 0 или более букв a-z, A-Z, _ или 0-9».
Регулярные выражения и генерируемые ими конечные автоматы недостаточно мощны для обработки рекурсивных шаблонов, таких как «n открывающих скобок, за которыми следует инструкция, за которой следует n закрывающих скобок». Они не могут вести счет и проверять, что n одинаково с обеих сторон, если для n не существует конечного набора допустимых значений. Чтобы распознать такие закономерности во всей их общности, требуется полный анализатор. Синтаксический анализатор может поместить круглые скобки в стек, а затем попытаться извлечь их и посмотреть, пуст ли стек в конце (см. Пример в книге Структура и интерпретация компьютерных программ ).
Обычно токенизация происходит на уровне слов. Однако иногда бывает трудно определить, что подразумевается под словом. Часто токенизатор полагается на простую эвристику, например:
В языках, которые используют межсловные пробелы (например, большинство из которых используют латинский алфавит и большинство языков программирования), этот подход довольно прост. Однако даже здесь есть много крайних случаев, таких как сокращения, слова с переносом, смайлики и более крупные конструкции, такие как URI (которые для некоторых целей могут считаться отдельными токенами). Классический пример - «из Нью-Йорка», который наивный токенизатор может сломать в пробелах, даже если лучший разрыв (возможно) - через дефис.
Токенизация особенно трудна для языков, написанных на scriptiocontina, которые не имеют границ слов, таких как древнегреческий, китайский или Тайский. Агглютинативные языки, такие как корейский, также усложняют задачи токенизации.
Некоторые способы решения более сложных проблем включают разработку более сложных эвристик, запросы к таблице общих частных случаев или подгонку токенов к языковой модели, которая идентифицирует словосочетания при последующей обработке шаг.
Лексеры часто генерируются генератором лексических кодов, аналогичным генераторам парсеров, и такие инструменты часто объединяются. Наиболее распространенным является lex в сочетании с генератором синтаксического анализатора yacc или, скорее, некоторые из их многочисленных повторных реализаций, например flex (часто в паре с GNU Bison ). Эти генераторы представляют собой форму предметно-ориентированного языка, принимающего лексическую спецификацию - обычно регулярные выражения с некоторой разметкой - и порождающие лексер.
Эти инструменты обеспечивают очень быструю разработку, что очень важно на ранних этапах разработки, как для получения рабочего лексера, так и потому, что спецификация языка может часто меняться. Кроме того, они часто предоставляют расширенные функции, такие как предварительные и последующие условия, которые трудно запрограммировать вручную. Однако автоматически сгенерированному лексеру может не хватать гибкости и, следовательно, может потребоваться некоторая ручная модификация или полностью написанный вручную лексер.
Производительность лексера вызывает беспокойство, и его оптимизация имеет смысл, особенно на стабильных языках, где лексер запускается очень часто (например, C или HTML). Лексеры, сгенерированные lex / flex, достаточно быстры, но при использовании более настроенных генераторов возможны улучшения в два-три раза. Иногда используются рукописные лексеры, но современные генераторы лексеров создают более быстрые лексеры, чем большинство написанных вручную. В семействе генераторов lex / flex используется табличный подход, который намного менее эффективен, чем подход с прямым кодированием. При втором подходе генератор создает движок, который напрямую переходит к последующим состояниям с помощью операторов goto. Доказано, что такие инструменты, как re2c, производят двигатели в два-три раза быстрее, чем двигатели, производимые гибкими. Как правило, сложно вручную написать анализаторы, которые работают лучше, чем механизмы, созданные этими последними инструментами.
Лексический анализ в основном разбивает входной поток символов на токены, просто группируя символы на части и классифицируя их. Однако лексирование может быть значительно более сложным; Проще говоря, лексеры могут опускать токены или вставлять добавленные токены. Пропуск токенов, особенно пробелов и комментариев, очень распространен, когда они не нужны компилятору. Реже могут быть вставлены добавленные токены. Это делается в основном для группировки токенов в операторы или операторов в блоки, чтобы упростить синтаксический анализатор.
Продолжение строки - это функция некоторых языков, где новая строка обычно является символом конца оператора. Чаще всего завершение строки обратной косой чертой (сразу за которой следует новая строка ) приводит к продолжению строки - следующая строка присоединяется к предыдущей. Обычно это делается в лексере: обратная косая черта и новая строка отбрасываются, а не токенизируется новая строка. Примеры включают bash, другие сценарии оболочки и Python.
Во многих языках точка с запятой используется в качестве символа завершения оператора. Чаще всего это обязательно, но в некоторых языках точка с запятой является необязательной во многих контекстах. В основном это делается на уровне лексического анализатора, где лексический анализатор выводит точку с запятой в поток маркеров, несмотря на то, что она отсутствует во входном потоке символов, и называется вставкой точки с запятой или автоматической вставкой точки с запятой. В этих случаях точки с запятой являются частью формальной грамматики фраз языка, но их нельзя найти во входном тексте, поскольку они могут быть вставлены лексером. Необязательные точки с запятой или другие терминаторы или разделители также иногда обрабатываются на уровне анализатора, особенно в случае замыкающих запятых или точек с запятой.
Вставка точки с запятой - это функция BCPL и его удаленного потомка Go, хотя она отсутствует в B или C. Вставка точки с запятой присутствует в JavaScript, хотя правила несколько сложны и подвергаются большой критике; Чтобы избежать ошибок, некоторые рекомендуют всегда использовать точку с запятой, а другие использовать начальную точку с запятой, называемую защитной точкой с запятой, в начале потенциально неоднозначных операторов.
Вставка точки с запятой (в языках с операторами, завершающимися точкой с запятой) и продолжение строки (в языках с операторами, завершающимися новой строкой) могут рассматриваться как дополнительные: вставка точки с запятой добавляет токен, хотя новые строки обычно не генерируют токены, в то время как продолжение строки предотвращает создание токена, хотя новые строки обычно генерируют токены.
Off-side rule (блоки, определяемые отступом) можно реализовать в лексере, как в Python, где увеличение отступа приводит к тому, что лексер выдает токен INDENT, а уменьшение отступа приводит к тому, что лексер выдает токен DEDENT. Эти лексемы соответствуют открывающей скобке {и закрывающей скобке }в языках, которые используют фигурные скобки для блоков, и означает, что грамматика фразы не зависит от того, используются ли фигурные скобки или отступы. Это требует, чтобы состояние удержания лексера, а именно текущий уровень отступа, таким образом, могло обнаруживать изменения в отступе, когда он изменяется, и, таким образом, лексическая грамматика не является контекстно-свободной : ОТВЕДЕНИЕ – ОТСУТСТВИЕ зависят от контекстной информации предыдущего уровня отступа.
Как правило, лексические грамматики являются контекстно-независимыми или почти таковыми и, следовательно, не требуют оглядки назад или вперед или отслеживания с возвратом, что обеспечивает простую, понятную и эффективную реализацию. Это также обеспечивает простую одностороннюю связь от лексера к анализатору без необходимости передачи какой-либо информации обратно в лексер.
Однако есть исключения. Простые примеры включают: вставку точки с запятой в Go, что требует просмотра одного токена; конкатенация последовательных строковых литералов в Python, которая требует удержания одного токена в буфере перед его выдачей (чтобы увидеть, является ли следующий токен другим строковым литералом); и правило оффсайда в Python, которое требует поддержания количества уровней отступа (действительно, стек каждого уровня отступа). Все эти примеры требуют только лексического контекста, и, хотя они несколько усложняют лексический анализатор, они невидимы для анализатора и более поздних этапов.
Более сложным примером является взлом лексера в C, где класс токена последовательности символов не может быть определен до этапа семантического анализа, поскольку typedef names и имена переменных лексически идентичны, но составляют разные классы токенов. Таким образом, во время взлома лексический анализатор вызывает семантический анализатор (например, таблицу символов) и проверяет, требует ли последовательность имени typedef. В этом случае информация должна поступать обратно не только от парсера, но от семантического анализатора обратно в лексер, что усложняет дизайн.
