Построение простейшего дерева вывода
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Министерство образования Российской Федерации
Марийский государственный технический университет
Факультет информатики и вычислительной техники
Кафедра ИВС
Лабораторная работа
по дисциплине:
Системное программное обеспечение
Тема:
Построение простейшего дерева вывода
Выполнили: студенты группы ВМ-31
Сорокин О., Петров И.
Проверил: Морохин Д.В.
г. Йошкар-Ола 2012 г.
Цель работы
Изучение основных понятий теории грамматик простого и операторного предшествования, ознакомление с алгоритмами синтаксического анализа (разбора) для некоторых классов КС-грамматик, получение практических навыков создания простейшего синтаксического анализатора для заданной грамматики операторного предшествования.
Задание
Терминальные символы выделены жирным шрифтом. Вместо символа a должны подставляться лексемы.
Дана грамматика вида:
ST=T
Ea*a | a/a | aT+E | T-E | E
Допустимые лексемы входного языка: идентификаторы, целые десятичные числа со знаком.
Описание грамматики входного языка в форме Бэкуса-Наура
Грамматика для распознавания идентификаторов:
Грамматика для распознавания целых десятичных чисел со знаком:
Грамматика для лексического анализатора получается объединением этих 2-х грамматик.
Множества крайних правых и крайних левых символов с указанием шагов построения
СимволШаг 1Последний шаг(U)L(U)R(U)L(U)R(U)STTTEaTEaTTEETEaEaEaaaa
Множества крайних правых и крайних левых терминальных символов
СимволШаг 1Шаг 2(U)Lt(U)Rt(U)Lt(U)Rt(U)S=+-aT+-+-+-a+-aEaaaa
Матрица предшествования для грамматики
Символ^н<<<
Пример выполнения разбора предложения
Входная цепочка: 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 );(а Ўа .);
T=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,