Формулы Бэкуса-Наура

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

Санкт–Петербургский Государственный

Электротехнический Университет

Кафедра МО ЭВМ

Дисциплина: Программирование

Отчет по лабораторной работе №1

Выполнил:

студент группы 3341, Худяков Я.Д.

Проверил:

Преподаватель Самойленко В. П.

Санкт-Петербург

2003

1) Задание

Построить синтаксический анализатор для понятия простое вырадение.

простое_выражение::=простой_идентификатор | (простое_выражение знак_операции простое_выражение)

простой_идентификатор::=буква

знак_операции::=- | + | *

2) Постановка задачи

В рекурсивном определении последовательности символов, называемой простое_выражение, присутствуют 2 части. Часть простой_идентификатор, еоторый является буквой, и взаимно рекурсивная часть (простое_выражение знак_операции простое_выражение). Знак_операции есть один зи знаков -, +, *. Примеры последовательностей, порождаемых этим определением:

(a+a), ((a+a)-b), ((a+(a*a))-b), (a*(a+(a-b)))

Синтаксическим анализатором назовём программу, которая по заданной(входной) части определяет, является ли она простым выражением или нет.

Реализована программа с помощью трёх основных булевских функций: prost_ident, которая проверяет переданное выражение на то, является ли оно простым идентификатором, функция znak, проверяющая выражение на его принадлежность к множеству знаков и основная функция prost_vyr, которая проверяет выражение на его принадлежность к множеству простых выражений.

3) Текст программы

{Программа синтаксического анализатора простого выражения (задание 13)}

{Выполнено студентом гр 3341 Худяковым Ярославом}

{входные выражения в файле analiz.in}

{выходные данные в файле analiz.out}

{если выражение простое, то в соответствующей строке выходного файла стоит true и false в противном случае}

uses crt;

var

cursgm:char;

brake,len,i:integer;

f1,f2:text;

znach:boolean;

str:string;

procedure scan;

begin

if i<=len then

begin

cursgm:=str[i];

i:=i+1;

end else exit;

end; {scan}

function prost_ident:boolean;

begin

if ((ord(cursgm)>=65) and (ord(cursgm)<=90)) or ((ord(cursgm)>=97) and (ord(cursgm)<=122))

then scan else prost_ident:=false;

end; {prost_ident}

function znak:boolean;

begin

if (cursgm='-') or (cursgm='+') or (cursgm='*') then scan else znak:=false;

end; {znak}

function prost_vyr:boolean;

begin

if (cursgm<>'(') then

begin

znach:=prost_ident;

if (brake=0) then znach:=false;

brake:=1;

end else

begin

brake:=1;

scan;

znach:=prost_vyr;

if znach then znach:=znak;

if znach then znach:=prost_vyr;

if (cursgm<>')') then znach:=false;

cursgm:=' ';

scan;

end;

if (znach=false) then prost_vyr:=false;

end; {prost_vyr}

Begin

clrscr;

assign(f1,'analiz.in'); reset(f1);

assign(f2,'analiz.out'); rewrite(f2);

{driver}

while not eof(f1) do

begin

i:=1;

readln(f1,str);

brake:=0;

len:=Length(str);

scan;

if len=1 then brake:=1;

writeln(f2,prost_vyr);

writeln(i);

end;

{/driver}

close(f1);

close(f2);

End.

4) Тестирование

Входные данные	Выходные данные
(a+(g+(a+N))) a a+b) (a+(a+G)) a*b a(t (a+a*a) ((a+a)+b) (a+(a+b)) (a+(c+g) a+a)	TRUE TRUE FALSE TRUE FALSE FALSE FALSE TRUE TRUE TRUE FALSE