Пример проектирования лексического анализатора

M₂

M₃

Языки L_i – не пусты, поскольку не пусты множества заключительных состоянийавтоматовM_i для всехi [1,3] , и -свободны,так как начальные состояния не являются заключительными;

4) Общий алфавит B = {0, 7, 9, a, l, u, s, ?}. Соответствующее разбиениеалфавита A -
P = {[0], [1-7], [89], [_a-km-tv-zA-KM-TV-Z], [lL], [uU], [\x20\x09],
[^0-9_a-zA-Z\x20\x09]}.

Элементы алфавитов связаны следующими соотношениями:

элементы B₁ = {a, 9, ?} –
a = а | l | u,

9 = 0 | 7 | 9,

? = s | ?;

элементы B₂ = {0, 7, l, u, ?} –
0 = 0,

7 = 7,

l = l,

u = u,

? = 9 | a | s | ?;

элементы B₃ = {s, ?} –

s = s,
t = t,
? = 0 | 7 | 9 | а | l | u | ?.

Применяя соотношения как правила подстановки к исходным выражениям, получаем регулярные выражения над общим алфавитом B:

e₁ = (а | l | u)(а | l | u | 0 | 7 | 9)^* ,

e₂ = 0(0 | 7)^* (|u|l|ul|lu),

e₃ = ss^*.
Чтобы получить регулярные выражения, определяющие языки в исходном алфавите A, необходимо заменить вхождения символов алфавита B в регулярные выражения на выражения, представляющие соответствующие классы разбиения P. Например, в языке C# выражения имеют следующие представления в формате строковых констант (литералов):
e₁ - @”([_a-km-tv-zA-KM-TV-Z] | [lL] | [uU])”+
@”( [_a-km-tv-zA-KM-TV-Z] | [lL] | [uU] | [0] | [1-7] | [89])^*” ;
e₂ - @”[0]([0] | [1-7])^* ( [uU] | [lL] | [uU] [lL] | [lL] [uU])?”;

e₃ - @” [\x20\x09] [\x20\x09]^*”.

Диаграммы D_i в алфавитах B_iтакже просто преобразуются в соответствующие диаграммы над общим алфавитомB:достаточно каждую
a-дугу заменить параллельнымиb-дугами.Например, в диаграммеD₁ каждая дуга (i, a, j) заменяется на (i, а | l | u, j), дуга (i, 9, j) – на (i, 0 | 7 | 9, j) и (i, ?, j) – на (i, s | t |?, j).

Приведенные к общему алфавиту B -диаграммы D_i, i [1,3]:

e₁ = (а | l | u)(а| l | u | 0 | 7 | 9)^* ;

e₂ = 0(0 | 7)^* (|u|l|ul|lu):

-диаграммa D₂

e₃ = ss^* :

-диаграммa D₃

Детерминированные конечные автоматы M_i , приведенные к общему алфавиту B, i [1,3] .
M₁

M₂

M₃

Языки L_i над общим алфавитом B так же не пусты, поскольку не пусты множества заключительных состоянийавтоматовM_i для всехi [1,3] , и -свободны,так как начальные состояния не являются заключительными.

Декартово произведениедвух детерминированных конечных автоматов -aвтомат M_1,2= M₁x M₂, допускающий объединение исходных языков: L₁ L₂.
M_1,2

5) Декартово произведениетрех детерминированных конечных автоматов -aвтомат M= M₁x M₂x M₃, допускающий объединение исходных языков: L₁ L₂ L₃.

M

ПустьM =(Q, B , g, q₀, F), где F= F₁ F₂ F₃ , F₁ = {3, 8},
F₂= {1, 5, 6, 7, 10}, F₃ = {4, 8}. Соответствующие автоматы
(Q, B , g, q₀, F_i) допускают языки L_i , i [1,3] .

Cемейство подмножеств {F₁, F_2, F₃} состоит из попарно не пересекающихся множеств, следовательно семейство языков {L₁, L_2, L₃} состоит из трех попарно не пересекающихся регулярных языков;

Автомат M¢ , построенный методом «слияния диаграмм переходов» автоматов M_1,2 и M₃. Автоматы M и M¢ изоморфны, поскольку их диаграммы переходов изоморфны.
M¢

7) Классификация состояний и переходов.
По построению все состояния достижимы из начального состояния q₀.

Множество «тупиковых» или состояний, сигнализирующих о лексической ошибке, - Error ={q| g*(q, x) ÏF}.

В автомате M= M₁x M₂x M₃ множество Error = {2}, так как из q₂ не достижимо ни одно финальное состояние q Î F.

Множество активных состояний -Active = Q\ Error.
Множество активных переходов -
ActiveTransition = {(q, a)| q ÎActive и g(q, a) ÎActive,a Î B }.
Множество переходов, определяющих условие распознавания лексемы класса L_i , - EndL_i = {(q, a)| q Î F_i и g(q, a) ÎError,a Î B }.

Символ a такой, что (q, a) Î EndL_i определяет правый контекст лексемы x Î L_i.Слово x переводит автомат из начального состояния в финальное состояниеqÎF_i, причем q=g*(q₀, x).

Переходы множества ErrorL = {(q, a)| q ÎActive \ F и g(q, a) ÎError,a Î B } определяют условия обнаружения лексической ошибки.
Если (q, a) ÎErrorL, тогда слово x такое, что q=g*(q₀, x) переводит автомат из начального состояния вактивное не финальное состояние q, определяет допустимый собственный префикс некоторой лексемы, но

слово xa – не допустимый префикс, так как не существует слова y Î B*, что xaу Î L.

Очевидно, ActiveTransition,EndL₁ ,EndL₂, EndL₃ ,ErrorL,-попарно не пересекающиеся множества переходов.