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

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

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

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

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

Кафедра ИВС

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

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

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

Тема:

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

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

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

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

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

Цель работы

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

Задание

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

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

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

E®®a*a | a/a | a®®T+E | T-E | E

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

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

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

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

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

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

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

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

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

Входная цепочка: 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}

;

label,Y,Z,W,TX,AX;,i,j,k,count,c,n,g,b,bb,aa,ii:integer;:file of char;:real;:text;,del,umn,minus,plus:char;:array[1..30] of string[32];:array[1..20] of integer;_:array[1..20] of string[32];,tmp_:string[60];_tmp:integer;:string[100];:array[1..20] of string[32];:array[1..20] of string[32];:array[1..20] of string[32];_:array[1..20] of string[32];:array[1..30] of char;_:array[1..30] of char;:array[1..20] of integer;

{ TODO -oUser -cConsole Main : Insert code here }

:=0;writeln('‡ ¤ ­ЁҐ:');writeln;('Vipolnit leksicheskii analiz vxodnogo teksta,postroyit tablitsy

leksem');('I vipolnit sintaksicheskii razbor teksta po zadannoi grammatike s

postroeniem dereva ');('а §Ў®а .');

writeln('');('Zadannaya grammatika);writeln('');('S->T<T|T>T|T<=T|T>=T');('T->T+E|T-E|E');;('Vypolnili studenty VM-31 Petrov,Sorokin');('');('!!!!!!!!!!!!!!!!!!!!!WARNING!!!!!!!!!!!!!!!!!!!!!!!!!!!!!');('Vhodnoi fail dolzhen nahoditsya na diske C:\spo3_in.txt');('!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!');;readln;(fin,'C:\spo3_in.txt');reset(fin);i:=1 to 30 do[i]:='';:=0;:=1;:=1;:=1;:=1;:=0;:='';n:=0;not eof(fin) doread(fin,ch);:=s+ch;n:=n+1;: if(((ch>='a')and(ch<='z'))or((ch>='A')and(ch<='Z')))begin if(a=0)then i:=i+1;slovo[i]:=slovo[i]+ch;a:=1;tip[i]:=1;endif(ch='+')begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=3;endif(ch='-')begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=4;endif(ch='*')begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=5;endif(ch='/')begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=6;endif((ch='<')or(ch='>'))begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=7;endif(ch='=')begin slovo[i]:=slovo[i]+ch;a:=0;endif(ch='(')begin:=i+1;tip[i]:=2;(fin,ch);s:=s+ch;n:=n+1;a:=0;[i]:=slovo[i]+ch;:read(fin,ch);s:=s+ch;n:=n+1;((ch>='0')and(ch<='9'))begin slovo[i]:=slovo[i]+ch;goto X;endgoto Y;if(ch=')')begin endbegin j:=1;goto Z;end;;(fin);j:=1 to i do(tip[j]=1)then tip_[j]:='identificator';(tip[j]=2)then tip_[j]:='celoe 10_noe chislo so znakom';(tip[j]=3)then tip_[j]:='znak slozheniya';(tip[j]=4)then tip_[j]:='znak vichitaniya';(tip[j]=5)then tip_[j]:='znak ymnozheniya';(tip[j]=6)then tip_[j]:='znak deleniya';(tip[j]=7)then tip_[j]:='znak neravenstva';;:=0;(fout,'C:\spo3_out.txt');rewrite(fout);(fout,'');writeln(fout,'Tablica lecsem');(fout,'N Lecsema Tip lecsemi');j:=1 to i do(fout,j,' ',slovo[j],' ',tip_[j]);(fout,'');writeln(fout,'Derevo vivoda:');:='';j:=1 to 20 doa_[j]:='';t[j]:='';tt[j]:='';e[j]:='';end;:=1;j:=1 to n do((s[j]='<')or(s[j]='>'))begini:=1 to j-1 do[1]:=t[1]+s[i];[1]:=s[j];i:=j+1 to n do[1]:=tt[1]+s[i];:=1;if(s[j]='=')begin term[2]:='=';delete(t[15],1,1);end;;(c=0)then begin j:=2;goto Z;end;:='T'+term[1]+term[2]+'T -> ';(fout,'S -> ',tmp);

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

g:=1 to length(e[ii]) do((e[ii][g]='*')or(e[ii][g]='/'))begini:=1 to g-1 do_[1]:=a_[1]+e[ii][i];_[1]:=e[ii][g];i:=g+1 to length(e[ii]) do_[2]:=a_[2]+e[ii][i];:=1;break;;;g:=1 to length(tmp) do(tmp[g]='E') thendelete(tmp,g,1);break;end;(bb=0)then begin('a',tmp,g);bb:=0;begin_:='a'+term_[1]+'a';(tmp_,tmp,g);bb:=0;;:=ii+1;g:=1 to length(e[ii]) do((e[ii][g]='*')or(e[ii][g]='/'))begini:=1 to g-1 do_[1]:=a_[1]+e[ii][i];_[1]:=e[ii][g];i:=g+1 to length(e[ii]) do_[2]:=a_[2]+e[ii][i];:=1;break;;;g:=1 to length(tmp) do(tmp[g]='E') thendelete(tmp,g,1);break;end;(bb=0)then begin('a',tmp,g);bb:=0;begin_:='a'+term_[1]+'a';(tmp_,tmp,g);bb:=0;;:=0;ii:=ii+1;;

((length(t[b])>0)or(length(tt[b])>0))b:=b+1;goto TX;end;g:=length(tmp) downto 1 do(tmp[g]='>')then begin delete(tmp,g-1,10);break;end;;(fout,tmp,'-> ',s);

(fout);:if(j=1)writeln('Leksicheskaya oshibka!');(j=2)readln;..

Вывод

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

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