Главная arrow Контрольные работы arrow Теория языков программирования arrow Программа реализации автомата с магазинной памятью вариант 1
 
 

Программа реализации автомата с магазинной памятью вариант 1

Печать E-mail
(0 голосов)
Автор Administrator   
01:08:2008 г.

Задание 1:
Задана грамматика:

<S>-->a<S>
<S>-->abc<A><B>
<A>-->c
<B>-->a<A>
<B>-->b
<A>-->e, где е - пустая строка.

Множество магазинных слов: <S>, <B>, <A>, a,b,c
Множество символов входной строки: a, b, c, пробел,
Начальное состояние магазина: <S>

Листинг программы:

program MPA3; {Нисходящий детерминированный синтаксический разбор}
uses crt;
type
AutoResult=(No,Accept,Error); {множество результатов синтаксического разбора}
string3 = string[3];
var
y:string;
Stack:array[0..50] of string3; {магазин автомата}
Rez:Boolean; {результат распознования: истина если строка допускается}
sInput: string; {входная и выходная строка автомата}
{---------------------------------------------------------------------------}
function MPAuto3 (sInput: string): Boolean;
var
Result : AutoResult; {результат синтаксического разбора}
i,j,n,k,v : integer;
begin
n:=length(sInput); {длина распознаваемой строки}
{------------Инициализация автомата-------------------------------------}
Stack[0]:='Дно'; Stack[1]:='<S>'; {исходное состояние магазина}
Result:=No;
i:=1; {указатель очередного символа строки}
j:=1; {указатель верхнего символа магазина(стека)}
{------------------------------------------------------------------------}
writeln('Входная строка --> ',sInput);
writeln('-----------------------------------------', n);
writeln('|Стек|**|Вход.символ|');
repeat
{--------------------Cостояние автомата---------------------------------}
for k:=0 to j do write(Stack[k]); write(' '); {вывод содержимого стека}
for k:=i to n do write(sInput[k]); writeln; {вывод входной строки}
{readkey;}
{-----------------------------------------------------------------------}
if Stack[j]='<S>' then v:=1
else if Stack[j]='<A>' then v:=2
else if Stack[j]='<B>' then v:=3
else if Stack[j]='b' then v:=4
else if Stack[j]='c' then v:=5
else if Stack[j]='a' then v:=6 else v:=7;
case v of
1:{<S>} if sInput[i]='a' then
begin
Stack[j]:='<B>';
inc(j);
Stack[j]:='<A>';
inc(j);
Stack[j]:='c';
inc(j);
Stack[j]:='b';
inc(i);
end
else Result:=Error; {отвергнуть}

2:{<A>} if sInput[i]='c'then
begin
dec(j);
inc(i);
end
{вытолкнуть, сдвиг}
else if sInput[i] =' ' then
begin
inc(i);
end {держать, сдвинуть}
else Result:=Error; {отвергнуть}

3:{B} if sInput[i]='a' then
begin Stack[j]:='<A>';
inc(j);
inc(i);
end {заменить <A>,сдвиг}
else if sInput[i]='b'then
begin
dec(j);
inc(i);
end {вытолкнуть, сдвиг}
else Result:=Error; {отвергнуть}
4:{b} if sInput[i]='b'then
begin
dec(j);
inc(i);
end {вытолкнуть, сдвиг}
else Result:=Error; {отвергнуть}
5:{c} if sInput[i]='c'then
begin
dec(j);
inc(i);
end {вытолкнуть, сдвиг}
else Result:=Error; {отвергнуть}
6:{a} if sInput[i]='a'then
begin
dec(j);
inc(i);
end {вытолкнуть, сдвиг}
else Result:=Error; {отвергнуть}
7:{Дно} if sInput[i]='.' then Result:=Accept {допустить}
else Result:=Error; {отвергнуть}
end;
if j<0 then j:=0;
until (Result=Error)or(Result=Accept);{условие окончания распознования}
MPAuto3:=(Result=Accept); {результат распознования строки}
end; {MPAuto3}
{----------------------------------------------------------------}
begin
clrscr;
sInput:='abc cacc.';
Rez:=MPAuto3(sInput);
if Rez then writeln('Допустить') else writeln('Отвергнуть');
read(y);
end.

Результаты работы программы:
Входная строка --> abc cacc.
-----------------------------------------10
|Стек|**|Вход.символ|
Дно<S> abc cacc.
Дно<B><A>cb bc cacc.
Дно<B><A>c c cacc.
Дно<B><A> cacc.
Дно<B><A> cacc.
Дно<B><A> cacc.
Дно<B> acc.
Дно<A><A> cc.
Дно<A> c.
Дно .
Допустить

Задание 2: Входной язык содержит последовательность вызовов процедур, разделенных символом ;(точка с запятой). Вызов процедуры должен состоять из имени процедуры и списка параметров. В качестве параметров могут выступать идентификаторы, шестнадцатеричные числа.

Грамматика: Множество выбора
<S>-переменная<SP> переменная
<SP>-(<Par><E>; (
<E>-,<Par><E> ,
<E>-) )
<Par>-переменная переменная
<Par>-константаh константа

Множество магазинных символов: <S> <Sp> <Par> <E> переменная константа ( ) , ; h Дно
Множество символов входной строки: переменная константа ( , ) h;
Начальное состояние автомата: <S>


Листинг программы:
program MPA_Q; {Нисходящий детерминированный синтаксический разбор}
uses crt;
type
AutoResult=(No,Accept,Error); {результаты синтаксического разбора}
{No-начальное состояние, Accept-строка допустима,Error-ошибка }
string3 = string[5]; {тип элемента стека}
{____Запись таблицы лексем: имя, класс, значение-ссылка на таблицу имен___}
rLexeme = record {тип элемента таблицы лексем}
name : string[16]; {идентификатор}
class: string[8]; {класс идентификатора}
value: integer; {значение-ссылка на таблицу имен}
end;
const
nL=10;
{Таблица лексем строки:
proc_name(a1,a2,a3);}
tLexeme:array[1..nL] of rLexeme =
((name:'proc_name' ;class:'ИмяПерем' ;value:0),
(name:'(' ;class:'Раздел' ;value:0),
(name:'a1' ;class:'ИмяПерем' ;value:0),
(name:',' ;class:'Раздел' ;value:0),
(name:'2h' ;class:'Конст' ;value:0),
(name:',' ;class:'Раздел' ;value:0),
(name:'a3' ;class:'ИмяПерем' ;value:0),
(name:')' ;class:'Раздел' ;value:0),
(name:';' ;class:'Раздел' ;value:0),

(name:'#' ;class:'Раздел' ;value:0));
var
Stack:array[0..50] of string3; {магазин автомата}
Rez:Boolean; {результат распознования: истина если строка допускается}
{---------------------------------------------------------------------------}
function MPAuto_Q: Boolean;
var
Result : AutoResult; {результат синтаксического разбора}
i,j,n,k : integer;
begin
{------------Инициализация автомата-------------------------------------}
Stack[0]:='Дно'; Stack[1]:='<S>'; {исходное состояние магазина}
Result:=No;
i:=1; {индекс таблицы лекскм}
j:=1; {указатель верхнего символа магазина(стека)}
{------------------------------------------------------------------------}
writeln('Верх маг.|*|Лексема|*|Номер лекс.|*|Индекс маг.');
repeat
{--------------------Cостояние автомата---------------------------------}
write(' ',Stack[j]); {вывод вершины стека}
gotoXY(14,whereY); write(tLexeme[i].name); {вывод входной лексемы}
gotoXY(26,whereY); write('i=',i,' ','j=',j); writeln;
readkey;
{-----------------------------------------------------------------------}
if Stack[j]='<S>' then if tLexeme[i].class='ИмяПерем'then
begin Stack[j]:='<SP>'; inc(i); end { Заменить, сдвиг}
else Result:=Error { Отвергнуть}
else
if Stack[j]='<SP>'
then
if tLexeme[i].name='('
then begin
Stack[j]:=';'; inc(j);

Stack[j]:='<E>'; inc(j);
Stack[j]:='<Par>'; inc(i);
end { Заменить, сдвиг}
else Result:=Error
else
if Stack[j]='<E>'
then
if tLexeme[i].name=','
then begin
Stack[j]:='<E>'; inc(j);
Stack[j]:='<Par>'; inc(i);
end { Заменить, сдвиг}
else
if tLexeme[i].name=')'

then begin dec(j); inc(i);
end
else Result:=Error { Отвергнуть}
else if Stack[j]='<Par>'
then
if tLexeme[i].class='ИмяПерем'

then begin dec(j); inc(i);
end { Заменить, сдвиг}
else
if tLexeme[i].class='Конст'

then begin dec(j); inc(i);
end
else Result:=Error

else if Stack[j]=';' then if tLexeme[i].name=';'
then begin dec(j); inc(i) end {7: Вытокнуть, сдвиг}
else Result:=Error {отвергнуть}
else if Stack[j]='Дно' then if tLexeme[i].name='#'
then Result:=Accept {допустить}
else Result:=Error; {отвергнуть}
if j<0 then j:=0;
until (Result=Error)or(Result=Accept);{or(i>nL);{условие окончания распознования}
MPAuto_Q:=(Result=Accept); {результат распознования последовательности лексем}
end; {MPAuto_Q}
{----------------------------------------------------------------}
begin
clrscr;
Rez:=MPAuto_Q;
if Rez then writeln('Допустить') else writeln('Отвергнуть');
readkey;
end.

Результаты работы программы:
Верх маг.|*|Лексема|*|Номер лекс.|*|Индекс маг.
<S> proc_name i=1 j=1
<SP> ( i=2 j=1
<Par> a1 i=3 j=3
<E> , i=4 j=2
<Par> 2h i=5 j=3
<E> , i=6 j=2
<Par> a3 i=7 j=3
<E> ) i=8 j=2
; ; i=9 j=1
Дно # i=10 j=0
Допустить



 
 
 
 
 

dedal t2 380 hunter