procedure S(next);
begin
if (next=’a’) then
begin
next:=getnext;
S(next);
if (next<>’b’) then
Virhe;
next:=getnext;
end;
end;
Pääohjelmassa:
Next:=getnext;
S(next);
-Jossain rekursion on päätyttävä!
Rekursio
Säännöllisten kielten sulkeuma määrittelee jonkinlaisen rekursion:
a* = A->aA/e
-ei kovin ilmaisuvoimainen
Kontekstittomilla kieliopeilla voi kuvata paremmin rekursiota:
S->aSb/e
Voidaan toteuttaa aliohjelmalla S, joka kutsuu itseään:
|
procedure S(next); begin if (next=’a’) then begin next:=getnext; S(next); if (next<>’b’) then Virhe; next:=getnext; end; |
|
|
end; Pääohjelmassa: Next:=getnext; S(next); | |