- •Введение
- •Формальные грамматики. Выводы Основные понятия
- •Способы задания языков
- •Операции над языками
- •Формальные грамматики. Выводы
- •Преобразования кс-грамматик Основные понятия
- •Устранение лишних символов
- •Исключение лишних правил
- •Исключение -правил
- •Устранение цепных правил
- •Выделение нетерминала
- •Левая факторизация
- •Устранение левой рекурсии
- •Устранение правой рекурсии
- •Нормальная форма Хомского
- •Нормальная форма Грейбах
- •Операторная кс-грамматика
- •Регулярные языки и конечные распознаватели Правосторонние грамматики
- •Левосторонние грамматики
- •Связь правосторонних и левосторонних грамматик
- •Преобразование кс-грамматики произвольного вида в правостороннюю
- •Конечные распознаватели. Основные понятия
- •Преобразование недетерминированных конечных распознавателей с -переходами в детерминированные
- •Эквивалентность состояний конечных детерминированных распознавателей
- •Эквивалентность конечных детерминированных распознавателей
- •Минимизация конечных детерминированных распознавателей
- •Регулярные множества и регулярные выражения
- •Регулярные выражения и конечные распознаватели
- •Получение регулярного выражения из конечного распознавателя
- •Построение конечного распознавателя по регулярному выражению
- •Конечные распознаватели и регулярные грамматики
- •Получение грамматики из конечного распознавателя
- •Построение конечных распознавателей по регулярным грамматикам
- •Ещё один способ взаимного преобразования право- и левосторонних грамматик
- •Программная реализация конечных детерминированных распознавателей
- •Лексический анализ
- •Принципы построения лексических анализаторов
- •Определение границ лексем
- •Выполнение действий, связанных с лексемами
- •Выделение ключевых слов
- •Программная реализация лексических анализаторов
- •Глава 3. Синтаксический анализ
- •3.1. Автомат с магазинной памятью
- •3.2. Таблично-управляемый предсказывающий разбор
- •3.2.1. Алгоритм разбора сверху-вниз
- •3.2.2. Множества first и follow
- •3.2.3. Конструирование таблиц предсказывающего анализатора
- •3.2.4. Ll(1)-грамматики
- •3.2.7. Рекурсивный спуск
- •3.3. Разбор снизу-вверх типа сдвиг-свертка
- •3.3.1. Основа
- •3.3.2. Lr(k)-анализаторы
- •3.3.4. Конфликты разбора типа сдвиг-свертка
Принципы построения лексических анализаторов
Лексический анализатор выделяет лексемы языка в исходном тексте и определяет тип выделенной лексемы. Лексемы определённого типа представляют собой множество цепочек, т.е. формальный язык. Характерной особенностью языков, представляющих собой лексемы определённого типа, является принадлежность их классу регулярных языков, поэтому каждый тип лексем может быть описан регулярным выражением или регулярной грамматикой и может быть построен конечный детерминированный распознаватель языка (лексем). Ниже представлены возможные распознаватели некоторых типов лексем.
Распознаватель идентификаторов.
б
б
ц
Распознаватель вещественных констант с фиксированной и плавающей точкой
ц
ц . ц +
ц
Е - ц
. ц
Распознаватель операций отношения
>
< =
=
> =
Распознаватель всех типов лексем представляет собой объединение распознавателей каждого типа, который можно рассматривать как недетерминированный распознаватель с множеством начальных состояний, содержащим начальные состояния распознавателей каждого типа лексем. Недетерминированный распознаватель может быть преобразован в детерминированный. Особенностью приведённых выше распознавателей является то, что множества символов, по которым осуществляется переход из начальных состояний в состояния, отличные от состояния ошибки, попарно не пересекаются, поэтому преобразование недетерминированного распознавателя в детерминированный, в данном случае, заключается только в объединении начальных состояний.
Определение границ лексем
Отличительной особенностью лексического анализатора от конечного распознавателя является то, что при выделении лексемы в исходном тексте явно не указаны границы лексемы и лексический анализатор должен их каким-то образом обнаруживать. Определение границы лексемы является нетривиальной задачей и зависит от особенностей исходного языка. Решение задачи определения границ лексем должно учитываться при разработке языка. Рассмотрим некоторые варианты решения этой задачи.
1. Использование в качестве границы лексемы незначащих символов – пробелов, табуляций и т.д. Это требует установки незначащего символа после каждой лексемы, но в языках программирования допускается непосредственное следование лексем без промежуточных символов, например: a:=15+b .
2. Использование в качестве границы лексемы незначащих символов и символов-разделителей. В этом случае некоторые символы, определяющие границу лексемы, сами могут быть лексемами или началом лексемы и важно не пропустить их при обработке текста.
3. Использование принципа выбора лексемы наибольшей длины: очередной символ исходного текста добавляется в лексему всегда, когда он может быть туда добавлен. Как только символ не может быть добавлен в лексему, то считается, что он является границей лексемы и началом следующей лексемы (если он не является незначащим символом или знаком комментария). Такой принцип не всегда позволяет правильно определить границы лексем, например, строка языка С k=i+++++j; будет разбита на лексемы следующим образом: k = i ++ ++ + j ; - и это разбиение не верное. Существует другой, верный вариант разбиения этой строки на лексемы: k = i ++ + ++ j ; . Для обработки этой ситуации возможно применение непрямого лексического анализатора, который после первого обнаружения лексемы ++ не будет распознавать такую же лексему (такая последовательность лексем не допускается синтаксисом языка С ), но разумнее отвергнуть рассматриваемую строку и обязать пользователя явно указать границы лексем с помощью пробелов.
Внесём в распознаватель типов лексем изменения, позволяющие обнаруживать границы лексем используя принцмп выбора лексемы наибольшей длины. Если в графе распознавателя есть вершина – допускающее состояние, из которой выходит хотя бы одна дуга, то введём новую вершину, проведём в неё дуги из рассматриваемых допускающих состояний, по которым осуществляется переход, если по текущему входному символу невозможен переход в состояние, отличное от состояния ошибки. Введённая вершина будет соответствовать допускающему состоянию. Введённую вершину-состояние отметим символом ‘*’, который говорит о том, что обработка следующей лексемы начинается с символа, по которому выполнен переход в это состояние.
Ниже представлен результат изменения распознавателей. Здесь начальные состояния объединены в одно с целью получения детерминированного распознавателя. Для пропуска незначащих символов (обозначим ‘_’) введём “петлю” около начального состояния. При достижении концевого маркера ‘┤’ выполняется переход из начального состояния в допускающее. Концевой маркер является лексемой типа “концевой маркер” и служит признаком окончания обработки исходного текста.
б
иначе
ц
б
_ ц
ц . ц + ц
Е -
ц *
. ц иначе
< иначе
=
>
=
┤
> =
иначе
