Построение простейшего дерева вывода
Министерство образования Российской
Федерации
Марийский государственный технический
университет
Факультет информатики и
вычислительной техники
Кафедра ИВС
Лабораторная работа
по дисциплине:
Системное программное обеспечение
Тема:
Построение простейшего дерева вывода
Выполнили: студенты группы ВМ-31
Сорокин О., Петров И.
Проверил: Морохин Д.В.
г. Йошкар-Ола 2012 г.
Цель работы
Изучение основных понятий теории грамматик простого и операторного
предшествования, ознакомление с алгоритмами синтаксического анализа (разбора)
для некоторых классов КС-грамматик, получение практических навыков создания
простейшего синтаксического анализатора для заданной грамматики операторного
предшествования.
Задание
Терминальные символы выделены жирным шрифтом. Вместо символа a
должны подставляться лексемы.
Дана грамматика вида:
S®T<T | T>T | T<=T | T>=T
E®®a*a | a/a | a®®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; Æ} ¸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;..
Вывод
При выполнении лабораторной работы изучили основные понятия теории
грамматик простого и операторного предшествования, ознакомились с алгоритмами
синтаксического анализа для некоторых классов КС-грамматик, получили
практические навыки создания простейшего синтаксического анализатора для
заданной грамматики операторного предшествия.
Написали программу, которая выполняет лексический анализ входного текста
в соответствии с заданием, порождает таблицу лексем и выполняет синтаксический
разбор текста по заданной грамматике с построением дерева разбора. Текст
задаётся в виде текстового файла.