img160

160

11. Metody dtzewowe

procedury:

remember(out), decide(list,tab) - opisano w p. 10 2,

findnode(place,label) - procedura znajduje kolejny wierzchołek drzewa, który powinien być obecnie analizowany (zgodnie z przedstawioną zasadą analizy) - parametr place daje miejsce (adres) tego wierzchołka, a label - jego etykietę,

transfunc(label, place, nonterminal, out) - realizacja funkcji przejścia, tzn. procedura na bazie parametrów wejściowych: label (wybierającego właściwą funkcję przejścia - Siabei) i place (wskazującego argument funkcji 6/ab'i - czyli nAi,..., r_r(o)J4_r(₀), gdy label^Ai... r_r(_a)A_r(_a)) jest poddrzewem rozpoczynającym się w wierzchołku wskazanym przez place), daje: symbol do jakiego dokonujemy redukcji - nonterminal oraz numer produkcji - out (znakowo); w przypadku gdy takie przejście nie istnieje -pod out podstawiany jest znak e,

replace(place, nonterminal) - procedura zastępuje napis label (riAi... ^Tf(a)A_r(_a)) wskazany przez parametr place napisem nonterminal.

procedurę TreeRec (var rec);

begin

repeat

findnode(place,label); transfunc(label,place,nonterminal,out); replace(place, nonterminal); remember(out);

until (nonterminal in finalstates) or (out = 'e');

if out = V then rec := 'err'

else rec := decide(list,tab);

end;

Algorytm ten został skonstruowany na bazie automatu drzewowego przedstawionego w tym rozdziale i stanowi jego wierne odwzorowanie. Innym rozwiązaniem, mniej zgodnym z tradycją teorii języków formalnych, za to bardziej naturalnym dla struktury drzewowej, byłby algorytm reku-rencyjny. W tym celu sekwencję wywoływania procedur transfunc, replace oraz remember należałoby zgrupować w osobnej procedurze, np. analy-sis(label, place, nonterminal, out). Następnie pętlę repeat należałoby zastąpić rekurencyjnym wywołaniem procedury analysis po wcześniejszym ustaleniu jej parametrów wejściowych przez procedurę findnode.