Построение простейшего дерева вывода

Министерство образования Российской Федерации Марийский государственный технический университет

Факультет информатики и вычислительной техники

Кафедра ИВС

Лабораторная работа

по дисциплине:

Системное программное обеспечение

Тема:

Построение простейшего дерева вывода

Выполнили: студенты группы ВМ-31

Сорокин О., Петров И.

Проверил: Морохин Д. В.

г. Йошкар-Ола 2012 г.

Цель работы

Изучение основных понятий теории грамматик простого и операторного предшествования, ознакомление с алгоритмами синтаксического анализа (разбора) для некоторых классов КС-грамматик, получение практических навыков создания простейшего синтаксического анализатора для заданной грамматики операторного предшествования.

Задание

Терминальные символы выделены жирным шрифтом. Вместо символа a должны подставляться лексемы.

Дана грамматика вида:

S®T<T | T>T | T<=T | T>=T

E®a*a | a/a | a

T®T+E | T-E | E

Допустимые лексемы входного языка: идентификаторы, целые десятичные числа со знаком.

Описание грамматики входного языка в форме Бэкуса-Наура

Грамматика для распознавания идентификаторов:

Грамматика для распознавания целых десятичных чисел со знаком:

Грамматика для лексического анализатора получается объединением этих 2-х грамматик.

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

Символ	Шаг 1	Последний шаг
(U)	L(U)	R(U)	L(U)	R(U)
S	T	T	TEa	TEa
T	TE	E	TEa	Ea
E	a	a	a	a

Множества крайних правых и крайних левых терминальных символов

Символ	Шаг 1	Шаг 2
(U)	Lt (U)	Rt (U)	Lt (U)	Rt (U)
S	< > <= >=	< > <= >=	< > <= >= ±a	< > <= >=±a
T	+;	+;	±a	±a
E	a	a	a	a

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

Символ	<	>		;	*		<=	>=	a	к
<			=	=					=
>			=	=					=
			>	>					<	>
;			>	>					<	>
*									=
									=
<=			=	=					=
>=			=	=					=
a					=	=				>
н			<	<					<

Пример выполнения разбора предложения

Входная цепочка: a+a

{ _к a+a

_н; } _п { _к+a_н a; } _c {_к+a_нE; 10} _п {_к a

_нE+; 10} _п {_к

_н E+a;10} _с {_кн E+Е;10,10} _с {_кн

E;10,10,5} _п {_к a; _н E<;10,10,5} _п {_к; _н E_c {_к; _н

E_с {_к; _н E; 10,10,5,10,1}

операторный грамматика дерево вывод

Дерево вывода:

Текст программы

program Project1;

{$APPTYPE CONSOLE}

uses

SysUtils;

label

X, Y, Z, W, TX, AX;

var

a, i, j, k, count, c, n, g, b, bb, aa, ii: integer;

fin:file of char;

m:real;

fout:text;

ch, del, umn, minus, plus: char;

slovo:array[1.30] of string[32];

tip:array[1.20] of integer;

tip_:array[1.20] of string[32];

tmp, tmp_:string[60];

dl_tmp:integer;

s:string[100];

t:array[1.20] of string[32];

tt:array[1.20] of string[32];

e:array[1.20] of string[32];

a_:array[1.20] of string[32];

term:array[1.30] of char;

term_:array[1.30] of char;

nn:array[1.20] of integer;

begin

{ TODOoUsercConsole Main: Insert code here }

a:=0;writeln ('‡ ¤ ­ЁҐ:');writeln;

writeln ('Vipolnit leksicheskii analiz vxodnogo teksta, postroyit tablitsy

leksem');

writeln ('I vipolnit sintaksicheskii razbor teksta po zadannoi grammatike s

postroeniem dereva ');

writeln ('а §Ў®а .');

writeln ('');

writeln ('Zadannaya grammatika);writeln ('');

writeln ('S->TT|T<=T|T>=T');

writeln ('T->T+E|T-E|E');

writeln;

writeln ('Vypolnili studenty VM-31 Petrov, Sorokin');

writeln ('');

writeln ('!!!WARNING!!!');

writeln ('Vhodnoi fail dolzhen nahoditsya na diske C: spo3_in.txt');

writeln ('!!!');

writeln;readln;

assign (fin,'C:spo3_in.txt');reset (fin);

for i:=1 to 30 do

slovo[i]: ='';

j:=0;

i:=1;

c:=1;

a:=1;

ii:=1;

count:=0;

s:='';n:=0;

while not eof (fin) do

begin read (fin, ch);

s:=s+ch;n:=n+1;

Y: if (((ch>='a')and (ch<='z'))or ((ch>='A')and (ch<='Z')))

then begin if (a=0)then i:=i+1;slovo[i]: =slovo[i]+ch;a:=1;tip[i]:=1;end

else if (ch='+')

then begin i:=i+1;slovo[i]: =slovo[i]+ch;a:=0;tip[i]:=3;end

else if (ch='-')

then begin i:=i+1;slovo[i]: =slovo[i]+ch;a:=0;tip[i]:=4;end

else if (ch='*')

then begin i:=i+1;slovo[i]: =slovo[i]+ch;a:=0;tip[i]:=5;end

else if (ch='/')

then begin i:=i+1;slovo[i]: =slovo[i]+ch;a:=0;tip[i]:=6;end

else if ((ch='<')or (ch='>'))

then begin i:=i+1;slovo[i]: =slovo[i]+ch;a:=0;tip[i]:=7;end

else if (ch='=')

then begin slovo[i]: =slovo[i]+ch;a:=0;end

else if (ch='(')

then begin

i:=i+1;tip[i]: =2;

read (fin, ch);s:=s+ch;n:=n+1;a:=0;

slovo[i]:=slovo[i]+ch;

X:read (fin, ch);s:=s+ch;n:=n+1;

if ((ch>='0')and (ch<='9'))

then begin slovo[i]: =slovo[i]+ch;goto X;end

else goto Y;

end

else if (ch=')')

then begin end

else begin j:=1;goto Z;end;

end;

close (fin);

for j:=1 to i do

begin

if (tip[j]=1)then tip_[j]: ='identificator';

if (tip[j]=2)then tip_[j]: ='celoe 10_noe chislo so znakom';

if (tip[j]=3)then tip_[j]: ='znak slozheniya';

if (tip[j]=4)then tip_[j]: ='znak vichitaniya';

if (tip[j]=5)then tip_[j]: ='znak ymnozheniya';

if (tip[j]=6)then tip_[j]: ='znak deleniya';

if (tip[j]=7)then tip_[j]: ='znak neravenstva';

end;

c:=0;

assign (fout,'C:spo3_out.txt');rewrite (fout);

writeln (fout,'');writeln (fout,'Tablica lecsem');

writeln (fout,'N Lecsema Tip lecsemi');

for j:=1 to i do

writeln (fout, j,' ', slovo[j],' ', tip_[j]);

writeln (fout,'');writeln (fout,'Derevo vivoda:');

tmp:='';

for j:=1 to 20 do

begin a_[j]: ='';t[j]:='';tt[j]:='';e[j]:='';end;

aa:=1;

for j:=1 to n do

begin

if ((s[j]='<')or (s[j]='>'))

then begin

for i:=1 to j-1 do

t[1]: =t[1]+s[i];

term[1]:=s[j];

for i:=j+1 to n do

tt[1]: =tt[1]+s[i];

c:=1;

end

else if (s[j]='=')

then begin term[2]: ='=';delete (t[15], 1,1);end;

end;

if (c=0)then begin j:=2;goto Z;end;

tmp:='T'+term[1]+term[2]+'T -> ';

write (fout,'S -> ', tmp);

b:=1;a:=1;bb:=0;aa:=3;

TX:

nn[b]: =length (t[b]);

if (nn[b]>0)then

begin

for i:=nn[b] downto 1 do

begin

if ((t[b][i]='+')or (t[b][i]='-'))

then begin

if (t[b][i-1]<>'(')then

begin

for g:=i+1 to nn[b] do

e[a]: =e[a]+t[b][g];

term[aa]:=t[b][i];

for g:=1 to i-1 do

t[b+1]: =t[b+1]+t[b][g];

bb:=1;break;

end;end;

end;

if (bb=0)then begin e[a]: =t[b];delete (tmp, 1,1);tmp:='E'+tmp;bb:=0;end

else begin delete (tmp, 1,1);tmp:='T'+term[aa]+'E'+tmp;bb:=0;end;

a:=a+1;

end;

nn[b]: =length (tt[b]);

if (nn[b]>0)then

begin

for i:=nn[b] downto 1 do

begin

if ((tt[b][i]='+')or (tt[b][i]='-'))

then begin

if (tt[b][i-1]<>'(')then

begin

for g:=i+1 to nn[b] do

e[a]: =e[a]+tt[b][g];

aa:=aa+1;

term[aa]:=tt[b][i];

for g:=1 to i-1 do

tt[b+1]: =tt[b+1]+tt[b][g];

bb:=1;break;

end;end;

end;

dl_tmp:=length (tmp);

for g:=dl_tmp downto 1 do

if (tmp[g]='T')then

begin k:=g;break;end;

delete (tmp, k,1);

if (bb=0)then begin insert ('E', tmp, k);e[a]: =tt[b];write (fout, tmp);bb:=0;end

else begin

tmp_:='T'+term[aa]+'E';insert (tmp_, tmp, k);write (fout, tmp);bb:=0;end;

a:=a+1;

end;

begin

for g:=1 to length (e[ii]) do

begin

if ((e[ii][g]='*')or (e[ii][g]='/'))

then begin

for i:=1 to g-1 do

a_[1]: =a_[1]+e[ii][i];

term_[1]:=e[ii][g];

for i:=g+1 to length (e[ii]) do

a_[2]: =a_[2]+e[ii][i];

bb:=1;break;

end;

end;

for g:=1 to length (tmp) do

if (tmp[g]='E') then

begin delete (tmp, g,1);break;end;

if (bb=0)then begin

insert ('a', tmp, g);bb:=0;

end

else begin

tmp_:='a'+term_[1]+'a';

insert (tmp_, tmp, g);bb:=0;

end;

ii:=ii+1;

for g:=1 to length (e[ii]) do

begin

if ((e[ii][g]='*')or (e[ii][g]='/'))

then begin

for i:=1 to g-1 do

a_[1]: =a_[1]+e[ii][i];

term_[1]:=e[ii][g];

for i:=g+1 to length (e[ii]) do

a_[2]: =a_[2]+e[ii][i];

bb:=1;break;

end;

end;

for g:=1 to length (tmp) do

if (tmp[g]='E') then

begin delete (tmp, g,1);break;end;

if (bb=0)then begin

insert ('a', tmp, g);bb:=0;

end

else begin

tmp_:='a'+term_[1]+'a';

insert (tmp_, tmp, g);bb:=0;

end;

c:=0;ii:=ii+1;

end;

if ((length (t[b])>0)or (length (tt[b])>0))

then

begin b:=b+1;goto TX;end;

for g:=length (tmp) downto 1 do

begin

if (tmp[g]='>')then begin delete (tmp, g-1,10);break;end;

end;

write (fout, tmp,'-> ', s);

close (fout);

Z:if (j=1)

then writeln ('Leksicheskaya oshibka!');

if (j=2)

then readln;

end.

end.

Вывод

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

Написали программу, которая выполняет лексический анализ входного текста в соответствии с заданием, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст задаётся в виде текстового файла.