img179

179

12.2. Parsing dla gramatyki grafowej klasy ETL(l)

conid(G, H, i) - boolowska funkcja sprawdzająca, czy wierzchołki indeksowane przez i grafów G oraz H są kontekstowo identyczne;

pconid(G, H,i, D, rec) - procedura dołącza do zbioru D opis potencjalnie kontekstowej identyczności, jeśli wierzchołki indeksowane przez i grafów G oraz H są potencjalnie kontekstowo identyczne, w przeciwnym przypadku rec err';

check(£>, H,i,rec) - jeśli istnieje opis potencjalnie kontekstowej identyczności (q, k,e) € D taki, że q = i, to procedura usuwa (q, k, e) ze zbioru D w przypadku zgodności opisu z sytuacją w grafie H, a w przypadku niezgodności rec := 'err'.

Zmienne: rec, list, tab, procedura remember oraz funkcja decide zostały zdefiniowane w rozdziale 11.

procedurę ETLRec (var rec);

begin

H := Z;

for i := 1 to m do

if rec 5^ ’err’ then begin

if n'(i) jest wierzchołkiem nieterminalnym then begin

choose(n'(i), n(i), k); if k = 0 then rec := 'err' else {żądana produkcja istnieje} begin

production(H,i,k);

remember(k)

end;

end;

if not conid(G, H, i) then pconid(G, H, i, D, rec);

check(D, H, i, rec); end;

if rec / ’err’ then rec := decide(list,tab);

end;

Zakończymy ten rozdział kilkoma uwagami co do przedstawionych metod: w obu przypadkach algorytm analizy syntaktycznej ma złożoność