Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.4.ANALIZASKŁADNIOWA
73
2.4.5.Lewostronnarekurencja
Istniejemożliwość,abyparserdziałającymetodązejśćrekurencyjnychwpadł
wnieskończonąpętlę.Problempojawiasięprzynlewostronnierekurencyjnych”
produkcjach,takichjak
expr→expr+term
gdzieskrajnylewysymbolwcieleprodukcjijesttakisamjaknieterminalwjej
nagłówku.Załóżmy,żeproceduradlaexprzdecydujeozastosowaniutejpro-
dukcji.Ciałozaczynasięodexpr,zatemproceduradlaexprjestwywoływana
rekurencyjnie.Ponieważsymbolpodglądanyzmieniasiętylkowtedy,gdydopaso-
wanyzostanieterminalwcieleprodukcji,nienastępujeżadnazmianawdanych
wejściowychmiędzyrekurencyjnymiwywołaniamiexpr.Wrezultaciedrugie
wywołanieexprwykonujedokładnietosamocopierwsze,awięcporaztrzeci
wywołujeexpritakdalejwnieskończoność.
Produkcjęlewostronnierekurencyjnąmożnawyeliminować,przepisująckło-
potliwąprodukcję.RozważmynieterminalnysymbolAzdwiemaprodukcjami
A→AO|;
gdzie
O
i
;
sąsekwencjamisymboliterminalnychinieterminalnych,które
niezaczynająsięodA.Naprzykładw
expr→expr+term|term
nieterminalA=exprciągO=+term,aciąg;=term.
Nieterminalnysymbol
A
ijegoprodukcję
A→AO
nazywamylewostronnie
rekurencyjnymi,gdyżprodukcja
A→AO
zawieratensamsymbolA,któryjest
nagłówkiemprocedury,jakoskrajnylewysymbolpoprawejstronie
4
.Powtarzane
stosowanietejprodukcjibudujesekwencjęciągów
O
naprawood
A
,jakna
rysunku2.20(a).Gdy
A
zostanieostateczniezastąpioneprzez
;
,otrzymamy
;
,
poktórymnastępujesekwencjazerolubwięcejwystąpieńO.
(a)
A
β
A
A
lll
lll
A
α
A
β
R
R
lll
lll
(b)
α
R
R
6
RYSUNEK
2020:
Lewo-iprawostronnierekurencyjnesposobygenerowaniaciągu
4
Wogólności,wlewostronnierekurencyjnejgramatyce,zamiastjawnejprodukcji
A→Aα
,
znieterminalnegosymboluAmożnawyprowadzićAαprzezpośrednieprodukcje.
