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

Размещено на http://www.allbest.ru/

Министерство образования Российской Федерации

Марийский государственный технический университет

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

Кафедра ИВС

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

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

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

Тема:

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

Выполнили: студенты группы ВМ-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; _н; } _п { _к+a<a; _н a; } _c {_к+a<a; _нE; 10} _п {_к a<a;

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

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

E<E;10,10,5,10} _с {_к; _н 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

{ TODO -oUser -cConsole 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->T<T|T>T|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.



Вывод

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

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

Размещено на Allbest.ru