Задача синтаксического анализа.

На первый взгляд эта задача кажется совсем не похожей на задачу о вычислении. В реальности это практически та же задача.

Дана произвольная символьная последовательность. Выяснить, является ли она правильно построенным выражением.

/*+x1y2 – true

-*+x1y23 – false

Шаблоном текста c₁,…,c_n назовём текст _­­­c₁^|,…,c_n^| , где

‘t’, c_i – терм

c_i^|= ‘f’, c_i – знак операции

‘’, c_i – чужой (посторонний) символ.

Шаблоном атома назовём строку c₁,c₂,c₃. Это либо строка f,t,t, где c₁=f, c₂=t, c₃=t, либо хотя бы один их них равен .

Формальным вычислением назовём переход от шаблона атома c₁,c₂,c₃ к символу ‘t’ в случае ftt, либо к символу ‘’ во втором случае. (?)

Последовательность есть выражение, если его можно преобразовать формальным вычислением к символу ‘t’.

procedure ReadMask(var exp:text;var m:char);

{Определение шаблонов атомов}

begin

if eof(exp) then m:=’’

else

begin

read(exp,c);

if c in [‘+’ , ’-‘ , ’/’ , ’*’] then m:=’f’

else if c in [‘a’..’z’]+[‘0’..’9’] then m:=’t’

else m:=’’;

end;

end;

function CorrectExp(var exp:text):boolean;

begin

reset(exp);

create(stack);

ReadMask(exp,f);

push(stack,f);

b:=(f<>’’) and (f =’t’) and not eof(exp);

ReadMask(exp,x);

push(stack,x);

b:=b and (x<>’’);

while b and not eof(exp) do

begin

pop(stack,x);

pop(stack,f);

ReadMask(exp,y);

while not AtomMask(f,x,y) do{проверяем на атом}

begin

push(stack,f);

push(stack,x);

push(stack,y);

pop(stack,x);

pop(stack,f);

ReadMask(exp,y);

end;

result:=AtomMaskVal(f,x,y);{Вычисляем шаблон}

push(stack,result);

b:=result<>0;

end;

CorrectExp:=(x=’t’) and empty(stack);

end;

Графы-выражения.

(x+1)*(x+1)²+(x+1)*x

Дерево хранит многократно каждое вхождение, но не собственно выражение.

Ациклический граф.

Такие графы соответствуют выражениям

частичного порядка.

Задача вычисления выражения, представленного графом, аналогична случаю дерева.

Подзадача «поиск атома, значения атома» аналогична. Но уничтожить терм теперь можно лишь в случае, когда на него нет других ссылок.

0. способ – хранить обратные ссылки и, в случае удаления, проверять, присутствуют ли они.

1. способ – хранить в каждой вершине счётчик ссылок на эту вершину. При каждом вычислении уменьшать значение счётчика. В случае равенства нулю – удалять вершину.

Упражнение. Завершить задачу о вычислении выражения.

* Преобразовать выражение из представления деревом в представление графом и обратно.