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

Запрос «Лексема (информатика)» перенаправляется сюда; см. также другие значения.

В информатике лексический анализ — процесс аналитического разбора входной последовательности символов (например, такой как исходный код на одном из языков программирования) с целью получения на выходе последовательности символов, называемых «токенами» (подобно группировке букв в словах). Группа символов входной последовательности, идентифицируемая на выходе процесса как токен, называется лексемой. В процессе лексического анализа производится распознавание и выделение лексем из входной последовательности символов.

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

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

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

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

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

Пример

Для примера, исходный код следующей строки программы

 net_worth_future = (assets - liabilities);

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

ИМЯ "net_worth_future" 
ПРИСВАИВАНИЕ 
ОТКРЫВАЮЩАЯ_СКОБКА 
ИМЯ "assets" 
МИНУС 
ИМЯ "liabilities" 
ЗАКРЫВАЮЩАЯ_СКОБКА 
ТОЧКА_С_ЗАПЯТОЙ

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

Лексический анализатор (англ. lexical analyzer или коротко lexer) — это программа или часть программы, выполняющая лексический анализ. Лексический анализатор обычно работает в две стадии: сканирование и оценка.

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

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

Токен с типом и соответственно подготовленным значением передаётся на вход синтаксического анализатора.

Генераторы лексических анализаторов

• lex — стандартный генератор в Unix
• Flex — альтернативный вариант классической утилиты lex
• JLex — генератор на Java
• ANTLR

См. также

• Синтаксический анализ
• Компилятор
• Транслятор

Литература

• Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4.
• Робин Хантер. Основные концепции компиляторов = The Essence of Compilers. — М.: «Вильямс», 2002. — С. 256. — ISBN 5-8459-0360-2.

Отрывок, характеризующий Лексический анализ

– Не хочу больше. Тимохин тут? – спросил он. Тимохин подполз к нему по лавке.
– Я здесь, ваше сиятельство.
– Как рана?
– Моя то с? Ничего. Вот вы то? – Князь Андрей опять задумался, как будто припоминая что то.
– Нельзя ли достать книгу? – сказал он.
– Какую книгу?
– Евангелие! У меня нет.
Доктор обещался достать и стал расспрашивать князя о том, что он чувствует. Князь Андрей неохотно, но разумно отвечал на все вопросы доктора и потом сказал, что ему надо бы подложить валик, а то неловко и очень больно. Доктор и камердинер подняли шинель, которою он был накрыт, и, морщась от тяжкого запаха гнилого мяса, распространявшегося от раны, стали рассматривать это страшное место. Доктор чем то очень остался недоволен, что то иначе переделал, перевернул раненого так, что тот опять застонал и от боли во время поворачивания опять потерял сознание и стал бредить. Он все говорил о том, чтобы ему достали поскорее эту книгу и подложили бы ее туда.
– И что это вам стоит! – говорил он. – У меня ее нет, – достаньте, пожалуйста, подложите на минуточку, – говорил он жалким голосом.
Доктор вышел в сени, чтобы умыть руки.
– Ах, бессовестные, право, – говорил доктор камердинеру, лившему ему воду на руки. – Только на минуту не досмотрел. Ведь вы его прямо на рану положили. Ведь это такая боль, что я удивляюсь, как он терпит.
– Мы, кажется, подложили, господи Иисусе Христе, – говорил камердинер.
В первый раз князь Андрей понял, где он был и что с ним было, и вспомнил то, что он был ранен и как в ту минуту, когда коляска остановилась в Мытищах, он попросился в избу. Спутавшись опять от боли, он опомнился другой раз в избе, когда пил чай, и тут опять, повторив в своем воспоминании все, что с ним было, он живее всего представил себе ту минуту на перевязочном пункте, когда, при виде страданий нелюбимого им человека, ему пришли эти новые, сулившие ему счастие мысли. И мысли эти, хотя и неясно и неопределенно, теперь опять овладели его душой. Он вспомнил, что у него было теперь новое счастье и что это счастье имело что то такое общее с Евангелием. Потому то он попросил Евангелие. Но дурное положение, которое дали его ране, новое переворачиванье опять смешали его мысли, и он в третий раз очнулся к жизни уже в совершенной тишине ночи. Все спали вокруг него. Сверчок кричал через сени, на улице кто то кричал и пел, тараканы шелестели по столу и образам, в осенняя толстая муха билась у него по изголовью и около сальной свечи, нагоревшей большим грибом и стоявшей подле него.
Душа его была не в нормальном состоянии. Здоровый человек обыкновенно мыслит, ощущает и вспоминает одновременно о бесчисленном количестве предметов, но имеет власть и силу, избрав один ряд мыслей или явлений, на этом ряде явлений остановить все свое внимание. Здоровый человек в минуту глубочайшего размышления отрывается, чтобы сказать учтивое слово вошедшему человеку, и опять возвращается к своим мыслям. Душа же князя Андрея была не в нормальном состоянии в этом отношении. Все силы его души были деятельнее, яснее, чем когда нибудь, но они действовали вне его воли. Самые разнообразные мысли и представления одновременно владели им. Иногда мысль его вдруг начинала работать, и с такой силой, ясностью и глубиною, с какою никогда она не была в силах действовать в здоровом состоянии; но вдруг, посредине своей работы, она обрывалась, заменялась каким нибудь неожиданным представлением, и не было сил возвратиться к ней.
«Да, мне открылась новое счастье, неотъемлемое от человека, – думал он, лежа в полутемной тихой избе и глядя вперед лихорадочно раскрытыми, остановившимися глазами. Счастье, находящееся вне материальных сил, вне материальных внешних влияний на человека, счастье одной души, счастье любви! Понять его может всякий человек, но сознать и предписать его мот только один бог. Но как же бог предписал этот закон? Почему сын?.. И вдруг ход мыслей этих оборвался, и князь Андрей услыхал (не зная, в бреду или в действительности он слышит это), услыхал какой то тихий, шепчущий голос, неумолкаемо в такт твердивший: „И пити пити питии“ потом „и ти тии“ опять „и пити пити питии“ опять „и ти ти“. Вместе с этим, под звук этой шепчущей музыки, князь Андрей чувствовал, что над лицом его, над самой серединой воздвигалось какое то странное воздушное здание из тонких иголок или лучинок. Он чувствовал (хотя это и тяжело ему было), что ему надо было старательна держать равновесие, для того чтобы воздвигавшееся здание это не завалилось; но оно все таки заваливалось и опять медленно воздвигалось при звуках равномерно шепчущей музыки. „Тянется! тянется! растягивается и все тянется“, – говорил себе князь Андрей. Вместе с прислушаньем к шепоту и с ощущением этого тянущегося и воздвигающегося здания из иголок князь Андрей видел урывками и красный, окруженный кругом свет свечки и слышал шуршанъе тараканов и шуршанье мухи, бившейся на подушку и на лицо его. И всякий раз, как муха прикасалась к егв лицу, она производила жгучее ощущение; но вместе с тем его удивляло то, что, ударяясь в самую область воздвигавшегося на лице его здания, муха не разрушала его. Но, кроме этого, было еще одно важное. Это было белое у двери, это была статуя сфинкса, которая тоже давила его.