Задачи и функционирование блока лексического анализа. Объединение сканера и парсера. Распределенные сканеры против централизованных

программа прежде всего разбивается на последовательность строк, или, как принято говорить, лексем (lexeme) . Множество лексем разбивается на непересекающиеся подмножества (лексические классы). Лексемы попадают в один лексический класс , если они неразличимы с точки зрения синтаксического анализатора. Например, во время синтаксического анализа все идентификаторы можно считать одинаковыми.

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

Пример . Рассмотрим оператор языка Pascal const pi = 3.1416; Этот оператор состоит из следующих лексем:

сonst - лексический класс Const_LC
pi - лексический класс Identifier_LC
= - лексический класс Relation_LC
3.1416 - лексический класс Number_LC
; - лексический класс Semicolon_LC

Лексический анализ различных языков программирования

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

От одного языка к другому варьируются правила использования символов языка, в частности, пробелов. В некоторых языках, таких как Алгол 68 и Фортран, пробелы являются значащими только в строковых литералах. Рассмотрим популярный пример, иллюстрирующий потенциальную сложность распознавания лексем в Фортране. В операторе DO 5 I = 1.25 мы не можем определить, что DO не является ключевым словом до тех пор, пока не встретим десятичную точку.

С другой стороны, в операторе DO 5 I = 1,25 мы имеем семь лексем: ключевое слово DO , метку 5 , идентификатор I , оператор = , константу 1 , запятую и константу 25 . Причем, до тех пор пока мы не встретим запятую, мы не можем быть уверены в том, что DO - это

При разборе такого оператора необходимо постоянно переключаться с режима " THEN , ELSE как ключевые слова" на трактовку " THEN , ELSE как идентификаторы", и обратно.

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

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

Задачи и функционирование блока лексического анализа

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

Выходом лексического анализа является поток образов лексем-дескрипторов и таблицы, в которых хранятся значения выделенных в программе лексем.

Дескриптор -- это пара вида: (<тип лексемы>, <указатель>), где <тип лексемы> -- это, как правило, числовой код класса лексемы, который означает, что лексема принадлежит одному из конечного множества классов слов, выделенных в языке программирования;

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

Множество классов лексем (т.е. различных видов слов) в языках программирования может быть различным. Наиболее распространенными классами являются:идентификаторы;

служебные (ключевые) слова;

разделители;

константы.

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

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

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

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

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

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

Идентификация лексемы из конечного класса выполняется путем сравнения ее с эталонным значением. Основная проблема здесь -- минимизация времени поиска эталона. В общем случае может понадобиться полный перебор слов данного класса, в особенности для случая, когда выделенное для опознания слово содержит ошибку. Уменьшить время поиска можно, используя различные методы ускоренного поиска:

метод линейного списка;

метод упорядоченного списка;

метод расстановки и другие.

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

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

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

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

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

10 --- ключевое слово; 20 -- разделитель; 30 -- идентификатор; 40 -- константа.

Вход лексического анализатора имеет вид:

var x,y,z: real;

Внутренние таблицы лексического анализатора имеют вид:

Таблица ключевых слов

Таблица идентификаторов

Таблица констант

	Константа

Выходом лексического анализатора является следующий дескрипторный текст:

(10.1)(30,1) (20,1)

(10,6) (30,2) (20,2) (30,3) (20,2) (30,4) (20,7) (10,5) (20,1) (10,2)

(20,7) (20,8) (40,1) (20,1)

(20,7) (20,8) (30,2) (20,3) (30,3) (20,1)

Однако, основной задачей ЛА является не порождение лексических единиц, а их распознавание. Математической моделью процесса распознавания регулярного языка является вычислительное устройство, которое называется конечным автоматом (КА). Термин «конечный» подчеркивает то, что вычислительное устройство имеет фиксированный и конечный объем памяти и обрабатывает последовательность входных символов, принадлежащих некоторому конечному множеству. Существуют различные типы КА, если функцией выхода КА (результатом работы) является лишь указание на то, допустима или нет входная последовательность символов, такой КА называют конечным распознавателем. Именно этот тип КА в дальнейшем мы и будем рассматривать.

Конечный автомат описывается следующим образом:

А = ,

где V = {а 1 , а 2 ,..., а m } -- входной алфавит (конечное множество символов);

Q = { q 0 , q 1 ,..., q n-1 } -- алфавит состояний (конечное множество символов);

8: Q х V -> Q -- функция переходов;

q 0 Q -- начальное состояние конечного автомата;

F Q -- множество заключительных состояний.

Имеется бесконечная лента, разбитая на ячейки, в каждой из которых может находиться один символ из V. На ленте записана цепочка а V*. Ячейки слева и справа от цепочки не заполнены. Имеется конечное устройство управления (УУ) с читающей головкой, которое может последовательно считывать символы с ленты, передвигаясь вдоль ленты слева направо. При этом УУ может находиться в каком-либо одном состоянии из Q. Начинает свою работу УУ всегда в начальном состоянии q o Q, а завершает в одном из заключительных состояний F. Каждый раз, переходя к новой ячейке на ленте, УУ переходит в соответствии с функцией переходов. Функцию переходов КА можно представить различными способами. Основные из них: совокупность команд; диаграмма состояний; матрица переходов.

Для КС-языков устройствами распознавания языка являются магазинные автоматы (или, иначе, автоматы с магазинной памятью, МП-автоматы).

Автомат имеет конечное множество состояний, конечное множество входных символов и неограниченную снизу вспомогательную ленту (называемую лентой магазинной памяти или магазинной памятью). «Дно» магазина (самый нижний символ) отмечается специальным символом, называемым маркером дна. Магазинная память определяется свойством «первым введен -- последним выведен». При записи символа в магазин, его содержимое сдвигается на одну ячейку «вниз», а на освободившееся место записывается требуемый символ. Обработку входной цепочки МП-автомат начинает в некотором выделенном состоянии при определенном содержимом магазина. Затем автомат выполняет операции, задаваемые его управляющим устройством. При этом выполняется либо завершение обработки, либо переход в новое состояние. Если синтаксический анализатор выполняется переход, то он дает новый верхний символ магазина, новый текущий символ, автомат переходит в новое состояние и цикл работы автомата повторяется. Итогом работы МП-автомата при обработке лексемы является ответ на вопрос: «принадлежит данная лексема данному языку или нет?». В общем виде может быть предложен следующий порядок конструирования ЛА:

Выделить во входном языке множество классов лексем.

Построить для каждого класса лексем грамматику.

Построить модель распознавателя.

Выбрать формат кодов лексем-дескрипторов.

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

Общая информация

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

7. Слово «косарь» - устаревшее. Соответственно, оно не является частью активного словарного запаса современных людей.

Лексический разбор слова «золотая»

Проанализируем слово «золотая», которое входит в следующее предложение: «Пришла к нам золотая осень».

1. Золотая осень - время года, когда все деревья и травы становятся желтыми и напоминают оттенок золота (металла).

2. Слово «золотая» имеет несколько значений, а именно:

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

3. Значение - переносное.

4. Вид переносного значения словосочетания «золотая осень» - метафора (обозначает подобный цвету золота).

5. Синонимами выражения «золотая» являются следующие: желтая, сказочная, восхитительная и пр.

6. Слово «золотая» имеет следующие антонимы: грязная, отвратительная, скверная, плохая.

9. Слово «золотая» - не устаревшее. Соответственно, оно является частью активного словарного запаса современных людей.

Лексический анализ других слов

Приведем еще несколько примеров:

Лексический разбор слова «фантастических» в предложении «Я насмотрелся фантастических фильмов»:

1. Фантастический фильм - измышленный фантазией и в действительности не существующий.

2. Слово «фантастический» имеет несколько значений, а именно: волшебный и причудливый; невероятный и несбыточный; не существующий и являющийся фантазией.

3. Значение - прямое.

4. Синонимами слова являются следующие: невероятный, ошеломляющий, не соответствующий реальности.

5. Имеет следующие антонимы: обычный, банальный.

7. Происхождение - заимствовано из английского языка (fantastic).

8. Данное выражение является общеупотребительным. Оно может применяться в любых стилях речи.

Лексический разбор слова «доброте» в предложении: «По доброте душевной он отдал всю свою одежду»:

1. По доброте - душевное качество, выражающееся в заботливом и нежном отношении к кому-либо.

2. Слово «доброта» имеет только одно значение.

3. Значение - прямое.

4. Синонимами слова являются следующие: хороший, благодушный, добродушный, человеколюбивый.

5. Имеет следующие антонимы: злой, жестокий.

7. Происхождение - исконно русское.

8. Данное выражение является общеупотребительным. Оно может применяться в любых стилях речи.

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

10. Применяется в следующих фразеологизмах: по доброте душевной, слепая доброта и пр.

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

Такой подход имеет свое место, но, как вы уже видели, существуют множество вещей, которые вы можете сделать даже никогда не обращавшись к этому вопросу, и, фактически, сканер, который мы здесь закончим, не очень будет напоминать то, что эти тексты описывают. Причина? Теория компиляторов и, следовательно, программы следующие из нее, должны работать с большинством общих правил синтаксического анализа. Мы же не делаем этого. В реальном мире возможно определить синтаксис языка таким образом, что будет достаточно довольно простого сканера. И как всегда KISS – наш девиз.

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

Зачем необходимо разделение? Ответ имеет и теоретическую и практическую основы.

В 1956 Ноам Хомский определил «Иерархию Хомского» для грамматик. Вот они:

Тип 0. Неограниченные (например Английский язык)

Тип 1. Контекстно-зависимые

Тип 2. Контекстно-свободные

Тип 3. Регулярные.

Некоторые характеристики типичных языков программирования (особенно старых, таких как Фортран) относят их к Типу 1, но большая часть всех современных языков программирования может быть описана с использованием только двух последних типов и с ними мы и будем здесь работать.

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

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

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

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

Имеется другая, более практическая причина для отделения сканера от синтаксического анализатора. Мы хотим думать о входном исходном файле как потоке символов, которые мы обрабатываем справа налево без возвратов. На практике это невозможно. Почти каждый язык имеет некоторые ключевые слова типа IF, WHILE и END. Как я упомянул ранее, в действительности мы не можем знать является ли данная строка ключевым словом до тех пор пока мы не достигнем ее конца, что определено пробелом или другим разделителем. Так что мы должны хранить строку достаточно долго для того, чтобы выяснить имеем мы ключевое слово или нет. Это ограниченная форма перебора с возвратом.

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

lex - стандартный генератор в Unix
Flex - альтернативный вариант классической "lex" утилиты
JLex - генератор на Java
gplex - генератор лексических анализаторов для С#
OOLEX - объектно-ориентированный генератор анализаторов
alex - генератор лексических анализаторов для Haskell
leex - генератор для Erlang

Литература

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

Wikimedia Foundation . 2010 .

Краснохолмский район Тверской области
Восточный факультет Санкт-Петербургского государственного университета

Смотреть что такое "Лексический анализ" в других словарях:

Лексический анализ - проверка правильности лексем. Лексический анализ программы выполняется при ее трансляции. См. также: Трансляторы Финансовый словарь Финам … Финансовый словарь

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

Синтаксический анализ - В информатике, синтаксический анализ (парсинг) это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно… … Википедия

Грамматический анализ - В информатике, синтаксический анализ (парсинг) это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора. Обычно применяется совместно с лексическим … Википедия

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

смысловой анализ текста - 1. Изучение ключевых лексических средств и словесно художественное структурирование текста в целом. 2. Изучение языковой доминанты текста (стилистической или эстетической). 3. Поуровневое изучение текста, при котором лексический уровень является… … Словарь лингвистических терминов Т.В. Жеребило

смысловой анализ текста - 1. Изучение ключевых лексических средств и словесно художественное структурирование текста в целом. 2. Изучение языковой доминанты текста (стилистической или эстетической). 3. Поуровневое изучение текста, при котором лексический уровень… … Методы исследования и анализа текста. Словарь-справочник

Lexical scan - Лексический анализ … Краткий толковый словарь по полиграфии

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