Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TYaP_posobie.doc
Скачиваний:
9
Добавлен:
01.04.2025
Размер:
951 Кб
Скачать
☆

Принципы построения лексических анализаторов

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

Распознаватель идентификаторов.

б

б

ц

Распознаватель вещественных констант с фиксированной и плавающей точкой

ц

ц . ц + ц

Е - ц

. ц

Распознаватель операций отношения

>

< =

=

> =

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

Определение границ лексем

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

1. Использование в качестве границы лексемы незначащих символов – пробелов, табуляций и т.д. Это требует установки незначащего символа после каждой лексемы, но в языках программирования допускается непосредственное следование лексем без промежуточных символов, например: a:=15+b .

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

3. Использование принципа выбора лексемы наибольшей длины: очередной символ исходного текста добавляется в лексему всегда, когда он может быть туда добавлен. Как только символ не может быть добавлен в лексему, то считается, что он является границей лексемы и началом следующей лексемы (если он не является незначащим символом или знаком комментария). Такой принцип не всегда позволяет правильно определить границы лексем, например, строка языка С k=i+++++j; будет разбита на лексемы следующим образом: k = i ++ ++ + j ; - и это разбиение не верное. Существует другой, верный вариант разбиения этой строки на лексемы: k = i ++ + ++ j ; . Для обработки этой ситуации возможно применение непрямого лексического анализатора, который после первого обнаружения лексемы ++ не будет распознавать такую же лексему (такая последовательность лексем не допускается синтаксисом языка С ), но разумнее отвергнуть рассматриваемую строку и обязать пользователя явно указать границы лексем с помощью пробелов.

Внесём в распознаватель типов лексем изменения, позволяющие обнаруживать границы лексем используя принцмп выбора лексемы наибольшей длины. Если в графе распознавателя есть вершина – допускающее состояние, из которой выходит хотя бы одна дуга, то введём новую вершину, проведём в неё дуги из рассматриваемых допускающих состояний, по которым осуществляется переход, если по текущему входному символу невозможен переход в состояние, отличное от состояния ошибки. Введённая вершина будет соответствовать допускающему состоянию. Введённую вершину-состояние отметим символом ‘*’, который говорит о том, что обработка следующей лексемы начинается с символа, по которому выполнен переход в это состояние.

Ниже представлен результат изменения распознавателей. Здесь начальные состояния объединены в одно с целью получения детерминированного распознавателя. Для пропуска незначащих символов (обозначим ‘_’) введём “петлю” около начального состояния. При достижении концевого маркера ‘┤’ выполняется переход из начального состояния в допускающее. Концевой маркер является лексемой типа “концевой маркер” и служит признаком окончания обработки исходного текста.

б

иначе

ц

б

_ ц

ц . ц + ц

Е - ц *

. ц иначе

< иначе

=

>

=

┤

> =

иначе

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]