Таблица 3.3

Рис. 3.3

Как и M1, М2 принимает строку из нулей и единиц тогда и только тогда, когда строка начинается с единицы. Однако при распознавании строки с помощью М2 возврат никогда не требуется, так как в процессе чтения определенного входного символа из любого состояния произойдет точно один переход к другому состоянию. Это значит, что при использовании М2 время распознавания строки будет пропорционально ее длине.

Можно доказать, что каждому недетерминированному конечному автомату соответствует детерминированный конечный автомат, принимающий тот же язык. В доказательстве допускается, что состояние в детерминированном автомате соответствует подмножествам состояний недетерминированного автомата. Например, состояние В в М2 соответствует множеству состояний {А, В} в M1, а состояние С в М2 - 0, пустому множеству состояний в M1.

Соответствие лексическому анализу заключается в том, что каждому языку типа 3 соответствует детерминированный конечный автомат, который распознает строки этого языка. Например, строки, генерируемые грамматикой G1 с порождающими правилам

A->1A A->1B A->1 B->0B

B->1B B->0 B->1

где А - начальный символ, распознаются с помощью М1 или М2. Грамматику получают из недетерминированного конечного автомата M1, следующим образом:

1. Начальное состояние автомата становится начальным символом предложения грамматики. 2. Переходам

S(A, 1)=A, §(А, 1)=В, §(В, 0) = B, §(В,1)=В

соответствуют порождающие правила:

A->1A A->1В В->0В B->1B

а тому, что в состоянии А есть переход при чтении 1 к последнему состоянию (В), соответствует

A->1

и аналогично

В->1 B->0

Можно также, наоборот, из грамматики вывести автомат M1. Автомат М2 соответствует грамматике G2 с порождающими правилами

A->1B B->0 A->0C

A->1 B->0B B->1B

B->1

C->0C

C->1C

Рис. 3.4

которая содержит бесполезный нетерминал С, но эквивалентна G1. Грамматику G2 называют «нечистой», так как она включает нетерминал, не генерирующий никаких терминальных символов.

Написание лексического анализатора заключается частично в моделировании различных автоматов для распознавания идентификаторов, чисел, зарезервированных слов и т. д. Конечный автомат для распознавания вещественного числа показан на рис. 3.4. S1 является начальным состоянием, a S4 и S7-последними состояниями; S8 - состояние отказа. Этот автомат - детерминированный, и его можно получить из грамматики типа 3, описанной в начале раздела, в два этапа. Сначала выводится недетерминированный автомат, состояния которого (кроме последнего) соответствуют нетерминалам грамматики, а затем его делают детерминированным.

На основе этого автомата можно написать процедуру для распознавания вещественного числа. Процедура дает значения true или false в зависимости от того, распознается вещественное число или нет.

ргос realno = bool:

begin char in; int i := 1;

while read (in); digit (in) or

sign (in) or in = "." or in = "10" do

i : = case i in

if sign (in) or digit (in) then 2 elif in = then 3 else 8 fi,

if digit (in) then 2 elif in = then 3 else 8 fi,

if digit (in) then 4 else 8 fi,

if digit (in) then 4 elifin = 10 then 5 else 8 fi,

if digit (in) then 7 elif sign (in) then 6 else 8 fi,

if digit (in) then 7 else 8 fi,

if digit (in) then 7 else 8 it, 8 esac od;

backspace (standin); i = 4 or i =7 end

Допускается существование процедуры digit, проверяющей литеру, не является ли она цифрой, и процедуры sign, проверяющей наличие «+» или «-». Процедура заканчивается, когда она доходит до литеры, которая не может содержаться в вещественном числе. Эта последняя литера, считающаяся началом какого-либо другого символа, тогда «не читается».

Если два символа начинаются с одной и той же литеры или строки литер, может оказаться необходимым «соединение» процедур их распознавания.

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

(+-) digit*. digit digit* (10( + -) digit digit*D

На основе регулярного выражения можно написать процедуру для распознавания вещественного числа

ргос realnol=void:

begin char in; read (in); if sign (in) then read (in) f

while digit (in)