Лексический анализ. Регулярные грамматики и выражения, конечные автоматы.

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

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

Лексический анализатор – это часть транслятора, получающая на вход исходный текст программы и выделяет в нем лексемы. Лексический анализатор работает с объектами, подобными идентификаторам или константам. ЛА является достаточно простым процессом и похож на то, как человек читает текст программы. Благодаря этому, символы языка (лексемы) почти всегда можно представить с помощью РГ или РВ. На основе РГ или РВ нетрудно построить необходимое устройство распознавания. Инструменты для их создания доступны и легки в использовании. Помимо распознавания лексем лексический анализатор также может выполнять удаление комментариев, введение номеров строк, вычисление констант и др.

Абстрактное устройство распознавания (распознаватель) состоит из 3 частей: Входная лента бесконечной длины, Устройство управления Вспомогательная память.

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

Доступ - f , Преобразование - g

В информатике, регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского. Регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.

Регулярная грамматика может быть задана набором правил как левая или правая регулярная грамматика.

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

1. A → a

2. A → aB

3. A → ε

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

1. A → a

2. A → Ba

3. A → ε

где

· заглавные буквы (A, B) обозначают нетерминалы из множества N

· строчные буквы (a, b) обозначают терминалы из множества Σ

· ε - пустая строка, т.е. строка длины 0

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