Создание компилятора

2. Различные порождающие правила имеют разные правые части.

Отношения =, < и > называют отношениями предшествования для  символов. Отношение предшествования  единственно для каждой упорядоченной  пары символов. При этом между какими-либо двумя символами может и не быть отношения предшествования - это  значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - например, если S_i > S_j, то не обязательно, что S_j < S_i (поэтому знаки предшествования иногда помечают специальной точкой: =×, <×, ×>)

Метод предшествования  основан на том факте, что отношения  предшествования между двумя  соседними символами распознаваемой строки соответствуют трем следующим вариантам:

• S_i < S_i+1, если символ S_i+1 - крайний левый символ некоторой основы;
• S_i > S_i+1 , если символ S_i - крайний правый символ некоторой основы;
• S_i = S_i+1 , если символы S_i и S_i+1 принадлежат одной основе.

Исходя из этих соотношений  выполняется разбор строки для грамматики предшествования.

 

3.4. Грамматика  операторного предшествования

Грамматикой операторного предшествования называется приведенная  КС-грамматика без l-правил (e-правил), в которой правые части продукций не содержат смежных нетерминальных символов. Для грамматики операторного предшествования отношения предшествования можно задать на множестве терминальных символов (включая символы ^_н и ^_к).

Отношения предшествования  для грамматики операторного предшествования G(VN,VT,P,S) задаются следующим образом:

• a = b, если и только если существует правило U®xaby ÎP или правило U®xaCby, где a,bÎVT, U,CÎVN, x,yÎV^*;
• a < b, если и только если существует правило U®xaCy ÎP и вывод CÞ*bz или вывод CÞ*Dbz, где a,bÎVT, U,C,DÎVN, x,y,zÎV^*;
• a > b, если и только если существует правило U®xCby ÎP и вывод CÞ*za или вывод CÞ*zaD, где a,bÎVT, U,C,DÎVN, x,y,zÎV^*.

В грамматике операторного предшествования различные порождающие  правила имеют разные правые части. Для грамматики операторного предшествования  тоже строится матрица предшествования, но она содержит только терминальные символы грамматики.

Для построения этой матрицы  удобно ввести множества крайних  левых и крайних правых терминальных символов относительно нетерминального  символа U - L_t(U) или R_t(U):

• L_t(U) = {t | $ UÞ*tz или $ UÞ*Ctz }, где tÎVT, U,CÎVN, zÎV^*;
• R_t(U) = {t | $ UÞ*zt или $ UÞ*ztC }, где tÎVT, U,CÎVN, zÎV^*.

Тогда определения отношений  операторного предшествования будут  выглядеть так:

• a = b, если $ правило U®xaby ÎP или правило U®xaCby, где a,bÎVT, U,CÎVN, x,yÎV^*;
• a < b, если $ правило U®xaCy ÎP и bÎL_t(C), где a,bÎVT, U,CÎVN, x,yÎV^*;
• a > b, если $ правило U®xCby ÎP и aÎR_t(C), где a,bÎVT, U,CÎVN, x,yÎV^*.

В данных определениях цепочки  символов x,y,z могут быть и пустыми цепочками.[1,2]

3.5 Построения распознавателя для грамматики операторного предшествования.

Множество правил грамматики имеет  вид:

S ® a := F;   

F ® F+T | T     
T ® T*E | T/E | E     
E ® (F) | -(F) | a

Грамматика является грамматикой  операторного предшествования, так  как она не содержит l-правил и правые части правил не содержат смежных нетерминальных символов. Построим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики.

 

 

Таблица 3.1.

Множества крайних правых и крайних левых символов грамматики (по шагам построения)

Символ	Шаг 1 (начало построения)		Последний шаг (результат)
(U)	L(U)-лево	R(U)-право	L(U)-лево	R(U)-право
E	-(a	)a	-(a	)a
T	ET	E	TE-(a	E)a
F	TF	T	FTE-(a	TE)a
S	a:=	F	a:=	FTE)a

 

Таблица 3.2.

Множества крайних правых и левых терминальных символов грамматики (по шагам построения)

 

Символ	Шаг 1 (начало построения)		Последний шаг (результат)
(U)	Lt(U)	Rt(U)	Lt(U)	Rt(U)
E	-(a	)a	-(a	)a
T	*/	*/	*/-(a	*/)a
F	+	+	+*/-(a	+*/)a
S	a:=	:=	a:=	:=+*/-)a

 

На основе полученных множеств и правил грамматики G построим матрицу операторного предшествования.

Таблица 3.3.

Матрица предшествования грамматики

VT	a	;	:=	+	-	*	/	(	)	^к
a		>.	=.	.>		.>	.>		.>
;	<.									.>
:=	<.	=		<.	<.	<.	<.	<.
+	<.	.>		.>	<.	<.	<.	<.	.>
-								=.
*	<.	.>		.>	<.	.>	.>	<.	.>
/	<.	.>		.>	<.	.>	.>	<.	.>
(	<.			<.	<.	<.	<.	<.	=.
)		.>		.>		.>	.>		.>
^н	<.

 

3.6. Основные  используемые функции

Работа синтаксического  анализатора.

fl:=vx.Count;

     if fl=0 then begin ShowMessage('Ошибка!'); exit;end;

vx.Add('!');

stek.Add('!');

stek.Add(vx.Strings[0]);

vx.Delete(0);

ind:=vx.Count-1;

g1:=vx.Strings[0];

fl:=stek.Count-1;

g2:=stek.Strings[fl];

repeat

Begin

     g1:=vx.Strings[0];

     fl:=stek.Count-1;

     repeat

     if stek.Strings[fl]<>'E' then g2:=stek.Strings[fl]

                              else fl:=fl-1;

     until(g2<>'E');

     j:=1;i1:=0;

     repeat

        if term[j][2]=g1 then i1:=StrToInt(term[j][1])

                         else j:=j+1;

     until(i1<>0);

     j:=1;i2:=0;

     repeat

        if term[j][2]=g2 then i2:=StrToInt(term[j][1])

                         else j:=j+1;

 

     until(i2<>0);

     g3:=matrix[i2][i1];

     if (g3='=')or(g3='<') then

begin stek.Add(g1);vx.Delete(0); end

else

if g3='>' then

begin

if fl=stek.Count-1 then

begin

dl:=1;

i:=1;

pr:=g2;

M1:

g4:=stek.Strings[fl-i];

if g4<>'E' then begin

j:=1;i4:=0;

repeat

if term[j][2]=g4 then i4:=StrToInt(term[j][1])

else j:=j+1;

until(i4<>0);

g5:=matrix[i4][i2];

if g5='='then

begin

dl:=dl+1;pr:=g4+pr;i:=i+1;i2:=i4;

goto M1;

end

else begin goto M2; end;

end

else

 

begin

if stek.Strings[fl-i-1]<>'E' then

begin

j:=1;i4:=0;

repeat

if term[j][2]=stek.Strings[fl-i-1] then i4:=StrToInt(term[j][1])

else j:=j+1;

until(i4<>0);

g5:=matrix[i4][i2];

if g5='='then

begin

dl:=dl+1;pr:=g4+pr; i:=i+1;goto M1;

end

else begin goto M2; end;

end;

end;

end

else

begin

dl:=1;

i:=1;

pr:=g2;

g4:=stek.Strings[fl-i];

g6:=stek.Strings[fl+i];

if (g4='E')and(g6='E') then begin pr:='E'+g2+'E';dl:=3;end

else begin ShowMessage('Ошибка ('+g2+')!');exit; end;

end;

M2:

for j:=1 to dl do stek.Delete(stek.Count-1);

 

j:=1;zn:=0;

repeat

if prav_1[j][2]=pr then zn:=StrToInt(prav_1[j][1])

else j:=j+1;

until(zn<>0);

stek.Add('E');

d.Add(IntToStr(zn));

CepofV[u]:=zn;

u:=u+1;

end

else begin ShowMessage('Ошибка!');exit; end;

fl:=stek.Count-1;

g1:=vx.Strings[0];

g2:=stek.Strings[fl-1];

end;

until (g1='!')and(g2='!');

vx.Clear;

str:='';

i4:=d.Count-1;

for i:=0 to i4 do str:=str+d.Strings[i]+' ';

memo9.Text:=str;

n:=d.Count;

with TreeView1 do

begin

Items.Clear;

Items.Add(Nil,'E');

vetv:=0;

j:=0;

for k:=n downto 1 do begin

 

m:=Items.Count;

if k<n then

for i:=m-1 downto 0 do if (Items[i].Text=notterm[CepofV[k]])and(Items[i].HasChildren=False) then begin vetv:=i;break;  end;

for i:=1 to 4 do

if Canon[CepofV[k],i]<>'' then Items.AddChild(Items[vetv],Canon[CepofV[k],i]);

end;

FullExpand

end;

vx.Destroy;

stek.Destroy;

d.Destroy;

end;

3.7. Результат работы синтаксического анализатора

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

Экранная   форма   работы   синтаксического   анализатора   представлена на рис. 3.1.

Рис. 3.1. Экранная форма  работы синтаксического анализатора

По последовательности сработавших правил «свертки» строится цепочка вывода и дерево вывода.

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

Экранная форма при  обнаружении синтаксической ошибки представлена на рис. 3.2.

Рис. 3.2. Экранная форма при обнаружении синтаксической ошибки

 

В случае обнаружения  ошибки программа выдает сообщение  об ошибке, работа синтаксического  анализатора останавливается.

 

Заключение

В результате выполнения курсовой работы для заданного входного языка были построены отдельные фазы компиляции.

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

Было установлено, что из заданных методов более эффективным является метод рехеширования  с  использованием  случайных  чисел,  так   как при сравнении его с методом упорядоченного списка именно он дал лучшие результаты при поиске идентификатора.

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

В третьей части курсовой работы разработан синтаксический анализатор, построенный на основе КС-грамматики операторного предшествования, который на    основе   таблицы   лексем   выполняет   синтаксический   разбор    текста с построением дерева вывода и перечислением всех сработавших правил «свертки». При обнаружении в исходном тексте ошибки выдается сообщение об ошибке, а работа синтаксического анализатора прекращается. Анализ типа обнаруженной ошибки не производится.

 

Список литературы

1. Системное программное обеспечение: Учебник для вузов/ А.Ю.    Молчанов -СПб.: Питер, 2003.-396 с.

2. Системное программное обеспечение. Лабораторный практикум/ А.Ю. Молчанов - СПб.: Питер, 2005.- 284 с.

3. Афанасьев А.Н. Формальные языки и грамматики: Учебное пособие. - Ульяновск: УлГТУ, 1997. - 84с.

4. Ахо А., Сети Р., Ульман Д. Компиляторы:   принципы,   технологии   и инструменты.: Пер. с англ. - М.: Изд. дом «Вильяме», 2001. - 768с.