Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.5.TRANSLATORDLAPROSTYCHWYRAŻEŃ
79
Popierwsze,określonewywołaniarekurencyjnemogązostaćzastąpione
iteracjami.Gdyostatniainstrukcjawykonywanawcieleproceduryjestreku-
rencyjnymwywołaniemtejsamejprocedury,towywołanietakienazywamy
ogonoworekurencyjnym(tailrecursive).Naprzykładwfunkcjirestwywołania
rest()dlasymbolupodglądanego
+
i
-
sąwywołaniamiogonoworekurencyj-
nymi,gdyżwkażdejztychgałęzikoduwywołanierestjestostatniąinstrukcją
wykonywanąwtymwywołaniurest.
Wprzypadkuprocedurybezparametrówrekurencjaogonowamożezostać
zastąpionapoprostuskokiemdopoczątkuprocedury.Koddlarestmożezostać
zatemprzepisanytak,jakwpseudokodziepokazanymnarysunku2.26.Dopóki
symbolpodglądanytoznakpluslubminus,procedurarestdopasowujeznak,
wywołujetermwceludopasowaniacyfryikontynuujeproces.Wprzeciwnym
raziewychodzizpętliwhileinastępujepowrótzproceduryrest.
voidrest(){
while(true){
if(lookahead==!+!){
match(!+!);term();print(!+!);continue;
}
elseif(lookahead==!-!){
match(!-!);term();print(!-!);continue;
}
break;
}
}
RYSUNEK
2026:Eliminowanierekurencjiogonowejwprocedurzerest
zrysunku2.25
Podrugie,gotowyprogramwJaviewymagajeszczejednejzmiany.Potym,
jakrekurencyjnewywołaniarestzrysunku2.25zostałyzastąpioneiteracjami,
jedynepozostałewywołanieproceduryrestznajdujesięwprocedurzeexpr.Obie
procedurymogązostaćzatemzintegrowanewjednąprzezzastąpieniewywołania
rest()ciałemproceduryrest.
2.5.5.Kompletnyprogram
PełnyprogramnaszegotranslatorawjęzykuJavajestwidocznynarysunku
2.27.Pierwszywiersztegokodu,zaczynającysięod
import
,zapewniadostępdo
pakietu
java.io
zawierającegosystemoweprocedurywejściaiwyjścia.Reszta
koduskładasięzdwóchklas
Parser
oraz
Postfix
.Klasa
Parser
zawiera
zmiennąlookaheadorazfunkcjeParser,expr,termimatch.
Wykonywanierozpoczynasięodfunkcji
main
,zdefiniowanejwklasie
Postfix
.
Funkcja
main
tworzywystąpienie
parse
klasy
Parser
iwywołujejegofunkcję
exprwceluanalizywyrażenia.