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

Пусть { L_i | L_i A ^*, i [1,3]}– семейство из трех регулярных языков над входным алфавитом A, где L_i – класс лексем языка Си или его ограничение (подмножество)для всех i [1, 3].

Язык L ₁ – множество идентификаторов языка Си; L ₂ - множество целочисленных констант языка Си в системе счисления с основанием 8; L ₃ – множество «пробельных» лексем, интерпретируемых как непустые слова над алфавитом { s, t }. Символы s и t условно обозначают «пробел» и «знак табуляции» соответственно.

Входной алфавит A представляют 256 символов в 8 – разрядной (байтовой) ASCII-кодировке. Числовой код символа «пробел» - 0x20 и «знака табуляции» - 0x09.

1) Языки L_i индуцируют разбиения P _i алфавита A, i [1,3] :
P₁ = {[_a-zA-Z], [0-9], [^_a-zA-Z]};
P₂ = {[0], [1-7], [lL], [uU], [^01-7 lL uU]},
P₃ = {[\x20\x09], [^\x20\x09]}.
Абстрактные алфавиты, соответствующие разбиениям, следующие:
B ₁ = { a, 9,? }, B ₂ = {0, 7, l, u,? }, B ₃ = { s,? },
Регулярные выражения е_i представляют языки L_i в соответствующих абстрактных алфавитах B_i, i [1,3]:
e ₁ = а(а | 9)^*, e ₂ = 0(0 | 7)^* (λ|u|l|ul|lu), e ₃ = ss ^*.

2) Эквивалентные λ - диаграммы D_i для е _i, i [1,3]:

e ₁ = а (а | 9)^*;

а:

(а | 9):

(а | 9)^*:

e ₁ = а (а | 9)^*:

λ-диаграммa D ₁

а|9

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

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

e ₃ = s s ^*:

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

3) Детерминированные конечные автоматы M_i, допускающие языки
L (D_i), i [1,3]. Символом ‘*’ помечены финальные состояния, символом Æ - состояние “ошибки”.
M ₁

Замыкание	q\a	a		?
[0]= {0}			Æ	Æ
[1]={1, 2, 3} *				Æ
[Æ]=Æ		Æ	Æ	Æ
[{2,3}]={2,3} *				Æ

M ₂

Замыкание	q\a			l	u	?
[0]= {0}			Æ	Æ	Æ	Æ
[1]={1,2,3,6} *						Æ
[Æ] =Æ		Æ	Æ	Æ	Æ	Æ
[2]={2,3, 6} *						Æ
[{4,6}]={4,6} *		Æ	Æ	Æ		Æ
[{5,6}]={5,6} *		Æ	Æ		Æ	Æ
[6]= {6} *		Æ	Æ	Æ	Æ	Æ

M ₃

Замыкание	q\a	s	?
[0]= 0
[1]={1, 2, 3} *			Æ
[Æ] =Æ		Æ	Æ
[{2,3}]={2,3} *			Æ

Языки 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 ₁

Замыкание	q\a				a	l	u	s	?
[0]= {0}		Æ	Æ	Æ				Æ	Æ
[1]={1, 2, 3 } *								Æ	Æ
[Æ] =Æ		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ
[{2,3}]={2,3} *								Æ	Æ

M ₂

Замыкание	q\a				a	l	u	s	?
[0]= {0}			Æ	Æ	Æ	Æ	Æ	Æ	Æ
[1]={1,2,3,6} *				Æ	Æ			Æ	Æ
[Æ] =Æ		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ
[2]={2,3,6} *				Æ	Æ			Æ	Æ
[{4,6}]= {4,6} *		Æ	Æ	Æ	Æ	Æ		Æ	Æ
[{5,6}]= {5,6} *		Æ	Æ	Æ	Æ		Æ	Æ	Æ
[6]= {6} *		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ

M ₃

Замыкание	q\a				a	l	u	s	?
[0]= 0		Æ	Æ	Æ	Æ	Æ	Æ		Æ
[1]={1, 2, 3} *		Æ	Æ	Æ	Æ	Æ	Æ		Æ
[Æ] =Æ		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ
[{2,3}]={2,3} *		Æ	Æ	Æ	Æ	Æ	Æ		Æ

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

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

Вектор	q\a				a	l	u	s	?
(0,0)			Æ	Æ				Æ	Æ
(2,1) 2				Æ	Æ			Æ	Æ
(2,2)= Æ		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ
(1,2) 1								Æ	Æ
(2,3) 2				Æ	Æ			Æ	Æ
(2,4) 2		Æ	Æ	Æ	Æ	Æ		Æ	Æ
(2,5) 2		Æ	Æ	Æ	Æ		Æ	Æ	Æ
(3,2) 1								Æ	Æ
(2,6) 2		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ

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

Вектор	q\a				a	l	u	s	?
(0,0,0)			Æ	Æ					Æ
(2,1,2) 2				Æ	Æ			Æ	Æ
(2,2,2)= Æ		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ
(1,2,2) 1								Æ	Æ
(2,2,1) 3
(2,3,2) 2
(2,4,2) 2
(2,5,2) 2
(3,2,2) 1
(2,2,3) 3
(2,6,2) 2

Пусть 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 ₂_, L ₃} состоит из трех попарно не пересекающихся регулярных языков;

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

F	q\a				a	l	u	s	?
			Æ	Æ				9	Æ
				Æ	Æ			Æ	Æ
Æ		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ
								Æ	Æ
				Æ	Æ			Æ	Æ
		Æ	Æ	Æ	Æ	Æ		Æ	Æ
		Æ	Æ	Æ	Æ		Æ	Æ	Æ
								Æ	Æ
		Æ	Æ	Æ	Æ	Æ	Æ	Æ	Æ
		Æ	Æ	Æ	Æ	Æ	Æ		Æ
		Æ	Æ	Æ	Æ	Æ	Æ		Æ

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, - попарно не пересекающиеся множества переходов.

Семантические процедуры

Определить (классифицировать) множество P «действий» (семантических процедур)значитопределить функцию выхода
f: Q ´ B¢ → P,где B ¢= B È { #}.Если f (q, a)= p Î P, тогда p – действие, выполняемое лексическим анализатором в состоянии q Î Q привходном символе a Î B ¢.Формально символ # Ï B служитпризнаком конца входного потока .
Фактически результатом проектирования является разработка модели детерминированного конечного преобразователя M =(Q, B ¢, P, f, g)простого типа.

Пусть P = { pActiveTransition, p EndL₁, …, p EndL _n, p ErrorL}. Определим очевидным образом функцию выхода:

f (q, a)= p ActiveTransition, если (q, a)ÎActiveTransition;

если(q, a)Î EndL _i, то (q, #)Î EndL _i, и
f (q, a)= p EndL _i, если(q, a)Î EndL _i, i Î [1, n ];

если(q, a)Î ErrorL, то(q, #)Î ErrorL, и

f (q, a)= p ErrorL, если(q, a)Î ErrorL.

Тогда программная реализация (интерпретация) преобразователя
M =(Q, B ¢, P, f, g) определяет основные действия (функции) лексического анализатора при сканировании входного потока символов алфавита B ¢.

Ниже на псевдоязыке приводится в обобщенной форме одна из возможных программных интерпретаций.

Интерпретация символов выходного алфавита P.

p ActiveTransition:

s = s + a; //добавить входной символ, расширить префикс некоторой //лексемы

// q ₁ = <q>

q = g[q,b]; // b = [a] – класс входного символа а ¹ #

// q ₂ = <q> и (q ₁, b, q ₂) in ActiveTransition `

return;

p EndL _i, i Î [1, n ]:

//(q, b) in EndL _i, i Î [1, n ]

//<s> = x – лексема, b = [a] и <a> = a – правый контекст

tokenStream.WriteLine(“<L”, i, “>”, s);

if (b == [#])

{

//выход

return;

}

else

{

inputStream.UnGetC(a); // вернуть символ <a> = a во входной поток
q = 0; // переключить автомат в начальное состояние

s=””; // очистить буфер для накопления символов очередной лексемы

return;

}

p ErrorL:

s = s + a;

tokenStream.WriteLine(“<ErrorL>”, s); //s= xa

if (b == [#])

{

//выход

return;

}

else

{

//skip входной символ а, доставивший лексическую ошибку
q = 0;

s=””;

return;

}