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

Определение 2.2.1. Порождающая грамматика G = <N, Т, Р, S>, правила которой имеют вид: А  аВ или С  b, где А, В, С  N; a, b  Т называется регулярной (автоматной).

Язык L(G), порождаемый автоматной грамматикой, называется автомат­ным (регулярным) языком или языком с конечным числом состояний.

Пример 2.2.1.  Идентификатором является пос­ледовательность, состоящая из букв и цифр, и первым символом идентифика­тора может быть только буква. Класс идентификаторов описывается следующей порождающей регулярной грамматикой      G = <N, Т, Р, S>, в которой

N = {I, K}, T = {б, ц}, S = {I},

P = {1.I б

2.I бк

3.K бк

4.K цк

5.K б

6.K ц}

Здесь б, ц — обобщенные терминальные символы для обозначения букв и цифр соответственно.

Процесс порождения идентификатора «ббцбц» описывается следующей последовательностью подстановок:

   2           3            4              3                6

I  бК  ббК  ббцК  ббцбК  ббцбц

Необходимо отметить, что данная грамматика не единственная, которая опи­сывает язык идентификаторов.

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

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