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

3.1. Конечный автомат

В А-грамматике все порождающие правила имеют вид:

A → aB или A → a,

где A,B – нетерминальные символы, а – терминальный символ.

В процессе порождения, начинающегося с начального нетерминала, цепочка всегда имеет очень простой вид: γA, где γ – терминальная цепочка, A – нетерминал. И только на самом последнем шаге этот единственный нетерминал заменяется терминальным символом. Процесс грамматического разбора должен повторять процесс порождения, его можно реализовать с помощью алгоритма, называемого конечным автоматом (КА).

Конечный автомат задается пятеркой множеств:

{Σ, Q, q₀, F, δ},

где Σ – множество (алфавит) входных символов; Q – множество состояний КА; q₀ – начальное состояние, ;  F – множество заключительных состояний, ; δ – множество правил перехода, каждое правило имеет вид:

(a, q_i) → q_j,

где . Правило перехода задает переход из состояния q_i , когда на входе читается символ a, в состояние q_j.

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

Если множество правил перехода таково, что для каждой пары (a, q_i) имеется не более одного правила, то КА называется детерминированным (ДКА) или однозначно определенным. Если же найдется хотя бы два разных правила перехода с одинаковыми парами (a, q_i), то КА называется недетерминированным (НКА), его работа существенно усложняется, так как придется одновременно отслеживать не одно, а несколько текущих состояний КА.

3.2. Построение детерминированного конечного автомата

Вначале изменим грамматику таким образом, чтобы в конце любой порождаемой ею цепочки был концевой символ _┴, отличающийся от всех символов алфавита языка. Рассмотрим все правила грамматики вида: A → a. Заменим это правило двумя правилами: A → aR, R → _┴ , где R – новый нетерминальный символ.

Нетрудно видеть, что после всех таких замен в грамматике останутся только правила вида A → aB и одно единственное правило R → _┴ , при этом в конце всех порождаемых цепочек появится дополнительный концевой символ _┴ .

Алфавит входных символов КА будет совпадать с алфавитом символов языка грамматики, включая концевой символ _┴, множество состояний КА будет включать все множество нетерминалов (символов грамматики), а также дополнительное заключительное состояние F. Тогда каждое правило грамматики вида A → aB, преобразуется в правило перехода КА: (a, A) → B, а правило грамматики вида R → _┴ преобразуется в правило перехода: (_┴, R) → F.

Построенный КА будет детерминированным (ДКА), если А-грамматика однозначна. В свою очередь, А-грамматика однозначна, если для любой пары (A, a) имеется не более одного правила вида A → aB. В противном случае А-грамматика будет неоднозначной, и будет построен НКА.

Множество правил перехода ДКА удобно записать в виде таблицы, каждая строка в которой соответствует одному состоянию ДКА, а каждый столбец – символу из алфавита входных символов.

Далее везде для сокращения записи группы правил с одним и тем же нетерминалом в левой части будем объединять: левую часть в них будем записывать один раз, а правые части разделять вертикальной чертой. Так, вместо:

A → γ₁, A → γ₂, …, A → γ_n

будем записывать:

A → γ₁| γ₂| … | γ_n .

Пример 1. А-грамматика задана правилами: S → 0A| 1A, A → 0A| 1A| 2. Здесь нетерминал S – начальный. Цепочки языка, порождаемые этой грамматикой, будут состоять из непустых последовательностей нулей и единиц, в конце которых имеется цифра 2.

После изменения грамматика будет содержать правила: S → 0A| 1A, A → 0A| 1A| 2R, R → _┴. Табл. 1 содержит правила перехода ДКА.

Табл. 1

	0	1	2	┴
S	A	A
A	A	A	R
R				F

Если на входе этого КА будет цепочка 01102_┴, то его состояния в процессе работы будут изменяться следующим образом: S, A, A, A, A, R, F. Так как цепочка прочитана вся и ДКА находится в заключительном состоянии, то такая входная цепочка считается распознанной, т.е. она принадлежит языку. При входной цепочке 0110_┴ состояния будут такими: S, A, A, A, A, и возникнет тупик: для состояния A и входного символа _┴ перехода не задано. Это значит, что такая цепочка не принадлежит языку. Входная цепочка 2_┴ также приводит к тупику: на первом же шаге из состояния S при входном символе 2 переход не задан.

Конец примера.