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

В информатике , лексический анализ , Lexing или токенизации это процесс преобразования последовательности символов (например, в компьютерной программе или веб - страницы ) в последовательность лексем ( строки с присвоенным и , таким образом , были определены значения). Программа , которая выполняет лексический анализ можно назвать лексер , токенизатор , ^[1] или сканер , хотя сканер также термин для первой стадии лексера. Лексер обычно сочетается с парсером , который вместе анализируетСинтаксис из языков программирования , веб - страниц , и так далее.

Приложения [ править ]

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

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

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

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

Лексический анализ также является важным ранним этапом обработки естественного языка , когда текст или звуковые волны сегментируются на слова и другие единицы. Это требует множества решений, которые не полностью стандартизированы, а количество производимых системой токенов варьируется для таких строк, как «1/2», «Chair's», «cannot», «and / or», «1/1 /». 2010 »,« 2х4 »,« ..., »и многие другие. Это контрастирует с лексическим анализом для программирования и подобных языков, где точные правила обычно определены и известны.

Лексема [ править ]

Лексема представляет собой последовательность символов в исходной программе , которая соответствует шаблону для маркеров и идентифицируют с помощью лексического анализатора в качестве экземпляра этих маркеров. ^[2]

Некоторые авторы называют это «токеном», взаимозаменяемо используя «токен» для представления токенизируемой строки и структуры данных токена, полученной в результате проведения этой строки в процессе токенизации . ^{[3] [4]}

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

Жетон [ править ]

Лексический маркер или просто маркер является строка с присвоенным и , таким образом , были определены значения. Он структурирован как пара, состоящая из имени токена и необязательного значения токена . Имя токена - это категория лексической единицы. ^[2] Общие имена токенов:

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

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

x = a + b * 2;

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

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

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

Лексическая грамматика [ править ]

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

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

Токенизация [ править ]

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

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

The quick brown fox jumps over the lazy dog

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

Токены могут быть представлены в XML ,

<предложение>  <слово> </ слово>  <слово> быстро </ слово>  <слово> коричневый </ слово>  <слово> лиса </ слово>  <слово> подскакивает </ слово>  <слово> над </ слово >  <слово> </ слово>  <слово> ленивого </ слово>  <слово> собака </ слово> </ предложение>

или как s-выражение ,

( предложение  ( слово  The )  ( слово  quick )  ( word  brown )  ( word  fox )  ( word  jump )  ( word  over )  ( word  the )  ( word  lazy )  ( word  dog ))

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

Токены идентифицируются на основе определенных правил лексического анализатора. Некоторые методы, используемые для идентификации токенов, включают: регулярные выражения , определенные последовательности символов, называемые флагом , определенные разделяющие символы, называемые разделителями , и явное определение словарём. Специальные символы, включая знаки препинания, обычно используются лексерами для идентификации токенов, поскольку они естественным образом используются в письменных языках и языках программирования.

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

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

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

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

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

Сканер [ править ]

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

Оценщик [ править ]

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

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

net_worth_future = (assets – liabilities);

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

ИДЕНТИФИКАТОР net_worth_futureРАВНЫЕОТКРЫВАЮЩАЯ СКОБКАIDENTIFIER активыМИНУСИДЕНТИФИКАТОР обязательствCLOSE_PARENTHESISТОЧКА С ЗАПЯТОЙ

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

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

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

Препятствия [ править ]

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

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

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

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

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

Генератор лексера [ править ]

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

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

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

Структура фразы [ править ]

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

Продолжение строки [ править ]

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

Вставка точки с запятой [ править ]

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

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

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

Off-side правило [ править ]

Правило от стороны (блоки , определенных с помощью отступов) может быть реализовано в лексере, как и в Python , где увеличение отступов результатов в лексере испуская маркер отступа и уменьшение отступов результатов в лексере излучающего маркер DEDENT. ^[9] Эти токены соответствуют открывающей {и закрывающей }фигурным скобкам в языках, в которых фигурные скобки используются для блоков, и означают, что грамматика фраз не зависит от того, используются ли фигурные скобки или отступы. Для этого требуется, чтобы лексер удерживал состояние, а именно текущий уровень отступа, и, таким образом, мог обнаруживать изменения в отступе, когда он изменяется, и, таким образом, лексическая грамматика не является контекстно-независимой : ОТНОСИТЕЛЬНОСТЬ – ОТНОСИТЕЛЬНОСТЬ зависят от контекстной информации предыдущего уровня отступа.

Контекстно-зависимое лексирование [ править ]

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

Однако есть исключения. Простые примеры включают: вставку точки с запятой в Go, что требует просмотра одного токена; конкатенация последовательных строковых литералов в Python ^[9], которая требует удержания одного токена в буфере перед его выдачей (чтобы увидеть, является ли следующий токен другим строковым литералом); и правило off-side в Python, которое требует поддержания количества уровней отступа (действительно, стека каждого уровня отступа). Все эти примеры требуют только лексического контекста, и, хотя они несколько усложняют лексический анализатор, они невидимы для анализатора и более поздних этапов.

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

См. Также [ править ]

• Список генераторов парсеров

Ссылки [ править ]

Источники [ править ]

Внешние ссылки [ править ]

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