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

Основные понятия теории грамматик простого и операторного предшествования, алгоритмы синтаксического разбора предложения для классов КС-грамматик; разработка дерева вывода для грамматики входного языка в форме Бэкуса-Наура с указанием шагов построения.
Краткое сожержание материала:

Размещено на

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

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

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

Кафедра ИВС

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

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

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

Тема:

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

Выполнили: студенты группы ВМ-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...