В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 20
Текст из файла (страница 20)
Îí îñíîâàí íà îáúåäèíåíèè (ñëèÿíèè) íåêîòîðûõ òàáëèö. Íàçîâ¼ì ÿäðîì ìíîæåñòâà LR(1)ñèòóàöèé ìíîæåñòâî èõ ïåðâûõ êîìïîíåíò (òî åñòü âî ìíîæåñòâå ñèòóàöèé íå ó÷èòûâàþòñÿ àâàíöåïî÷êè). Îáúåäèíèì âñå ìíîæåñòâà ñèòóàöèé ñ îäèíàêîâûìè ÿäðàìè, à âêà÷åñòâå àâàíöåïî÷åê âîçüì¼ì îáúåäèíåíèå àâàíöåïî÷åê.4.6.
Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà131Ôóíêöèè Action è Goto ñòðîÿòñÿ î÷åâèäíûì îáðàçîì. Åñëè ôóíêöèÿ Action òàêèì îáðàçîì ïîñòðîåííîãî àíàëèçàòîðà íå èìååò êîíôëèêòîâ, òî îí íàçûâàåòñÿ LALR(1)àíàëèçàòîðîì (LookAhead LR(1)). Åñëè ãðàììàòèêà ÿâëÿåòñÿ LR(1), òî â òàáëèöàõ LALR(1) àíàëèçàòîðà ìîãóò ïîÿâèòüñÿ êîíôëèêòû òèïû ñâ¼ðòêà-ñâ¼ðòêà (åñëè îäíî èçîáúåäèíÿåìûõ ñîñòîÿíèé èìåëî ñèòóàöèè [A → α, a] è[B → β, b], à äðóãîå [A → α, b] è [B → β, a], òî â LALR(1)ïîÿâÿòñÿ ñèòóàöèè [A → α, {a, b}] è [B → β, {b, a}]). Êîíôëèêòû òèïà ñäâèã-ñâ¼ðòêà ïîÿâèòüñÿ íå ìîãóò, ïîñêîëüêóàâàíöåïî÷êà äëÿ ñäâèãà âî âíèìàíèå íå ïðèíèìàåòñÿ.Ãëàâà 5.Ýëåìåíòû òåîðèèïåðåâîäàÄî ñèõ ïîð ìû ðàññìàòðèâàëè ïðîöåññ ñèíòàêñè÷åñêîãîàíàëèçà òîëüêî êàê ïðîöåññ àíàëèçà äîïóñòèìîñòè âõîäíîéöåïî÷êè.
Îäíàêî, â êîìïèëÿòîðå ñèíòàêñè÷åñêèé àíàëèçñëóæèò îñíîâîé åù¼ îäíîãî âàæíîãî øàãà ïîñòðîåíèÿäåðåâà ñèíòàêñè÷åñêîãî àíàëèçà.  ïðèìåðàõ 4.3 è 4.8 ïðåäûäóùåé ãëàâû â ïðîöåññå ñèíòàêñè÷åñêîãî àíàëèçà â êà÷åñòâå âûõîäà âûäàâàëàñü ïîñëåäîâàòåëüíîñòü ïðèìåí¼ííûõïðàâèë, íà îñíîâå êîòîðîé è ìîæåò áûòü ïîñòðîåíî äåðåâî.Ïîñòðîåíèå äåðåâà ñèíòàêñè÷åñêîãî àíàëèçà ÿâëÿåòñÿ ïðîñòåéøèì ÷àñòíûì ñëó÷àåì ïåðåâîäà ïðîöåññà ïðåîáðàçîâàíèÿ íåêîòîðîé âõîäíîé öåïî÷êè â íåêîòîðóþ âûõîäíóþ.Îïðåäåëåíèå. Ïóñòü T âõîäíîé àëôàâèò, à Π âûõîäíîé àëôàâèò. Ïåðåâîäîì (èëè òðàíñëÿöèåé) ñ ÿçûêà L1 ⊆ T ∗ íà ÿçûê L2 ⊆ Π∗ íàçûâàåòñÿ îòîáðàæåíèåτ : L1 → L2 . Åñëè y = τ (x), òî öåïî÷êà y íàçûâàåòñÿâûõîäîì äëÿ öåïî÷êè x.Ìû ðàññìîòðèì íåñêîëüêî ôîðìàëèçìîâ äëÿ îïðåäåëåíèÿ ïåðåâîäîâ: ïðåîáðàçîâàòåëè ñ ìàãàçèííîé ïàìÿòüþ,ñõåìû ñèíòàêñè÷åñêè óïðàâëÿåìîãî ïåðåâîäà è àòðèáóòíûåãðàììàòèêè.5.1.
Ïðåîáðàçîâàòåëè ñ ìàãàçèííîé ïàìÿòüþ1335.1. Ïðåîáðàçîâàòåëè ñ ìàãàçèííîéïàìÿòüþÐàññìîòðèì âàæíûé êëàññ àáñòðàêòíûõ óñòðîéñòâ, íàçûâàåìûõ ïðåîáðàçîâàòåëÿìè ñ ìàãàçèííîé ïàìÿòüþ. Ýòèïðåîáðàçîâàòåëè ïîëó÷àþòñÿ èç àâòîìàòîâ ñ ìàãàçèííîéïàìÿòüþ, åñëè ê íèì äîáàâèòü âûõîä è ïîçâîëèòü íà êàæäîì øàãå âûäàâàòü âûõîäíóþ öåïî÷êó.Ïðåîáðàçîâàòåëåì ñ ìàãàçèííîé ïàìÿòüþ (ÌÏ-ïðåîáðàçîâàòåëåì) íàçûâàåòñÿ âîñüì¼ðêà P = (Q, T, Γ, Π, D, q0 ,Z0 , F ), ãäå âñå ñèìâîëû èìåþò òîò æå ñìûñë, ÷òî è â îïðåäåëåíèè ÌÏ-àâòîìàòà, çà èñêëþ÷åíèåì òîãî, ÷òî Π êîíå÷íûé âûõîäíîé àëôàâèò, à D îòîáðàæåíèå ìíîæåñòâàQ × (T ∪ {e}) × Γ â ìíîæåñòâî êîíå÷íûõ ïîäìíîæåñòâ ìíîæåñòâà Q × Γ∗ × Π∗ .Îïðåäåëèì êîíôèãóðàöèþ ïðåîáðàçîâàòåëÿ P êàê ÷åòâ¼ðêó (q, x, u, y), ãäå q ∈ Q ñîñòîÿíèå, x ∈ T ∗ öåïî÷êàíà âõîäíîé ëåíòå, u ∈ Γ∗ ñîäåðæèìîå ìàãàçèíà, y ∈ Π∗ öåïî÷êà íà âûõîäíîé ëåíòå, âûäàííàÿ âïëîòü äî íàñòîÿùåãî ìîìåíòà.Åñëè ìíîæåñòâî D(q, a, Z) ñîäåðæèò ýëåìåíò (r, u, z),òî áóäåì ïèñàòü (q, ax, Zw, y) ` (r, x, uw, yz) äëÿ ëþáûõx ∈ T ∗ , w ∈ Γ∗ è y ∈ Π∗ .
Ðåôëåêñèâíî - òðàíçèòèâíîå çàìûêàíèå îòíîøåíèÿ ` áóäåì îáîçíà÷àòü `∗ .Öåïî÷êó y íàçîâ¼ì âûõîäîì äëÿ x, åñëè (q0 , x, Z0 , e) `∗(q, e, u, y) äëÿ íåêîòîðûõ q ∈ F è u ∈ Γ∗ . Ïåðåâîäîì(èëè òðàíñëÿöèåé), îïðåäåëÿåìûì ÌÏ-ïðåîáðàçîâàòåëåìP (îáîçíà÷àåòñÿ τ (P )), íàçîâ¼ì ìíîæåñòâî{(x, y) | (q0 , x, Z0 , e) `∗ (q, e, u, y)äëÿ íåêîòîðûõ q ∈ F è u ∈ Γ∗ }Áóäåì ãîâîðèòü, ÷òî ÌÏ-ïðåîáðàçîâàòåëü P ÿâëÿåòñÿ äåòåðìèíèðîâàííûì (ÄÌÏ-ïðåîáðàçîâàòåëåì), åñëè âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:1) äëÿ âñåõ q ∈ Q, a ∈ T ∪ {e} è Z ∈ Γ ìíîæåñòâîD(q, a, Z) ñîäåðæèò íå áîëåå îäíîãî ýëåìåíòà,2) åñëè D(q, e, Z) 6= ∅, òî D(q, a, Z) = ∅ äëÿ âñåõ a ∈ T .134Ãëàâà 5. Ýëåìåíòû òåîðèè ïåðåâîäàÏðèìåð 5.1.
Ðàññìîòðèì ïåðåâîä τ , îòîáðàæàþùèé êàæäóþ öåïî÷êó x ∈ {a, b}∗ $, â êîòîðîé ÷èñëî âõîæäåíèé ñèìâîëà a ðàâíî ÷èñëó âõîæäåíèé ñèìâîëà b, â öåïî÷êó y = (ab)n ,ãäå n ÷èñëî âõîæäåíèé a èëè b â öåïî÷êó x. Íàïðèìåð,τ (abbaab$) = ababab.Ýòîò ïåðåâîä ìîæåò áûòü ðåàëèçîâàí ÄÌÏ-ïðåîáðàçîâàòåëåì P = ({q0 , qf }, {a, b, $}, {Z, a, b}, {a, b}, D, q0 , Z, {qf }) c ôóíêöèåé ïåðåõîäîâ:D(q0 , X, Z) = {(q0 , XZ, e)}, X ∈ {a, b},D(q0 , $, Z) = {(qf , Z, e)},D(q0 , X, X) = {(q0 , XX, e)}, X ∈ {a, b},D(q0 , X, Y ) = {(q0 , e, ab)}, X ∈ {a, b}, Y ∈ {a, b}, X 6= Y .5.2.
Ñèíòàêñè÷åñêèïåðåâîäóïðàâëÿåìûéÄðóãèì ôîðìàëèçìîì, èñïîëüçóåìûì äëÿ îïðåäåëåíèÿïåðåâîäîâ, ÿâëÿåòñÿ ñõåìà ñèíòàêñè÷åñêè óïðàâëÿåìîãî ïåðåâîäà. Ôàêòè÷åñêè, òàêàÿ ñõåìà ïðåäñòàâëÿåò ñîáîé ÊÑãðàììàòèêó, â êîòîðîé ê êàæäîìó ïðàâèëó äîáàâëåí ýëåìåíò ïåðåâîäà. Âñÿêèé ðàç, êîãäà ïðàâèëî ó÷àñòâóåò â âûâîäå âõîäíîé öåïî÷êè, ñ ïîìîùüþ ýëåìåíòà ïåðåâîäà âû÷èñëÿåòñÿ ÷àñòü âûõîäíîé öåïî÷êè, ñîîòâåòñòâóþùàÿ ÷àñòèâõîäíîé öåïî÷êè, ïîðîæä¼ííîé ýòèì ïðàâèëîì.5.2.1. Ñõåìû ñèíòàêñè÷åñêè óïðàâëÿåìîãîïåðåâîäàÎïðåäåëåíèå. Cõåìîé ñèíòàêñè÷åñêè óïðàâëÿåìîãî ïåðåâîäà (èëè òðàíñëÿöèè, ñîêðàù¼ííî: ÑÓ-ñõåìîé) íàçûâàåòñÿ ïÿò¼ðêà T r = (N, T, Π, R, S), ãäå(1) N êîíå÷íîå ìíîæåñòâî íåòåðìèíàëüíûõ ñèìâîëîâ;(2) T êîíå÷íûé âõîäíîé àëôàâèò;(3) Π êîíå÷íûé âûõîäíîé àëôàâèò;5.2.
Ñèíòàêñè÷åñêè óïðàâëÿåìûé ïåðåâîä135(4) R êîíå÷íîå ìíîæåñòâî ïðàâèë ïåðåâîäà âèäàA → u, vãäå u ∈ (N ∪ T )∗ , v ∈ (N ∪ Π)∗ è âõîæäåíèÿ íåòåðìèíàëîâ â öåïî÷êó v îáðàçóþò ïåðåñòàíîâêó âõîæäåíèé íåòåðìèíàëîâ â öåïî÷êó u, òàê ÷òî êàæäîìó âõîæäåíèþ íåòåðìèíàëà B â öåïî÷êó u ñîîòâåòñòâóåòíåêîòîðîå âõîæäåíèå ýòîãî æå íåòåðìèíàëà â öåïî÷êóv ; åñëè íåòåðìèíàë B âñòðå÷àåòñÿ áîëåå îäíîãî ðàçà,äëÿ óêàçàíèÿ ñîîòâåòñòâèÿ èñïîëüçóþòñÿ âåðõíèå öåëî÷èñëåííûå èíäåêñû;(5) S íà÷àëüíûé ñèìâîë, âûäåëåííûé íåòåðìèíàë èçN.Îïðåäåëèì âûâîäèìóþ ïàðó â ñõåìå T r ñëåäóþùèì îáðàçîì:(1) (S, S) âûâîäèìàÿ ïàðà, â êîòîðîé ñèìâîëû S ñîîòâåòñòâóþò äðóã äðóãó;(2) åñëè (xAy, x0 Ay 0 ) âûâîäèìàÿ ïàðà, â öåïî÷êàõ êîòîðîé âõîæäåíèÿ A ñîîòâåòñòâóþò äðóã äðóãó, èA → u, v ïðàâèëî èç R, òî (xuy, x0 vy 0 ) âûâîäèìàÿ ïàðà. Äëÿ îáîçíà÷åíèÿ òàêîãî âûâîäà îäíîé ïàðû èç äðóãîé áóäåì ïîëüçîâàòüñÿ îáîçíà÷åíèåì ⇒: (xAy, x0 Ay 0 ) ⇒ (xuy, x0 vy 0 ).
Ðåôëåêñèâíîòðàíçèòèâíîå çàìûêàíèå îòíîøåíèå ⇒ îáîçíà÷èì ⇒∗ .Ïåðåâîäîì τ (T r), îïðåäåëÿåìûì ÑÓ-ñõåìîé T r, íàçîâ¼ììíîæåñòâî ïàð{(x, y) | (S, S) ⇒∗ (x, y), x ∈ T ∗ , y ∈ Π∗ }Åñëè ÷åðåç P îáîçíà÷èòü ìíîæåñòâî âõîäíûõ ïðàâèëâûâîäà âñåõ ïðàâèë ïåðåâîäà, òî G = (N, T, P, S) áóäåòâõîäíîé ãðàììàòèêîé äëÿ T r.ÑÓ-ñõåìà T r = (N, T, Π, R, S) íàçûâàåòñÿ ïðîñòîé, åñëèäëÿ êàæäîãî ïðàâèëà A → u, v èç R ñîîòâåòñòâóþùèå äðóãäðóãó âõîæäåíèÿ íåòåðìèíàëîâ âñòðå÷àþòñÿ â u è v â îäíîìè òîì æå ïîðÿäêå.136Ãëàâà 5.
Ýëåìåíòû òåîðèè ïåðåâîäàÏåðåâîä, îïðåäåëÿåìûé ïðîñòîé ÑÓ-ñõåìîé, íàçûâàåòñÿ ïðîñòûì ñèíòàêñè÷åñêè óïðàâëÿåìûì ïåðåâîäîì (ïðîñòûì ÑÓ-ïåðåâîäîì).Ïðèìåð 5.2. Ïåðåâîä àðèôìåòè÷åñêèõ âûðàæåíèé â ÏÎËÈÇ (ïîëüñêóþ èíâåðñíóþ çàïèñü) ìîæíî îñóùåñòâèòü ïðîñòîéÑÓ-ñõåìîé ñ ïðàâèëàìèE →E+TE→TT →T ∗FT →FF → idF → (E)ET +TTF+FidE.Íàéä¼ì âûõîä ñõåìû äëÿ âõîäà id∗(id+id). Íåòðóäíî âèäåòü,÷òî ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü øàãîâ âûâîäà(E, E) ⇒ (T, T ) ⇒ (T ∗ F, T F ∗) ⇒⇒ (F ∗ F, F F ∗) ⇒ (id ∗ F, id F ∗) ⇒ (id ∗ (E), id E∗) ⇒⇒ (id ∗ (E + T ), id E T + ∗) ⇒ (id ∗ (T + T ), id T T + ∗) ⇒⇒ (id ∗ (F + T ), id F T + ∗) ⇒ (id ∗ (id + T ), id id T + ∗) ⇒⇒ (id ∗ (id + F ), id id F + ∗ ) ⇒⇒ (id ∗ (id + id), id id id + ∗),ïåðåâîäÿùàÿ ýòó öåïî÷êó â öåïî÷êó id id id + ∗.Ðàññìîòðèì ñâÿçü ìåæäó ïåðåâîäàìè, îïðåäåëÿåìûìè ÑÓ-ñõåìàìè è îñóùåñòâëÿåìûìè ÌÏ-ïðåîáðàçîâàòåëÿìè [2].Òåîðåìà 5.1.
Ïóñòü P ÌÏ-ïðåîáðàçîâàòåëü. Ñóùåñòâóåò òàêàÿ ïðîñòàÿ ÑÓ-ñõåìà T r, ÷òî τ (T r) =τ (P ).Òåîðåìà 5.2. Ïóñòü T r ïðîñòàÿ ÑÓ-ñõåìà. Ñóùåñòâóåò òàêîé ÌÏ-ïðåîáðàçîâàòåëü P, ÷òî τ (P ) =τ (T r).Òàêèì îáðàçîì, êëàññ ïåðåâîäîâ, îïðåäåëÿåìûõ ìàãàçèííûìè ïðåîáðàçîâàòåëÿìè, ñîâïàäàåò ñ êëàññîì ïðîñòûõÑÓ-ïåðåâîäîâ.5.2. Ñèíòàêñè÷åñêè óïðàâëÿåìûé ïåðåâîä137Ðàññìîòðèì òåïåðü ñâÿçü ìåæäó ÑÓ-ïåðåâîäàìè è äåòåðìèíèðîâàííûìè ÌÏ-ïðåîáðàçîâàòåëÿìè, âûïîëíÿþùèìè íèñõîäÿùèé èëè âîñõîäÿùèé ðàçáîð [2].Òåîðåìà 5.3.
Ïóñòü T r = (N, T, Π, R, S) ïðîñòàÿÑÓ-ñõåìà, âõîäíîé ãðàììàòèêîé êîòîðîé ñëóæèòLL(1)-ãðàììàòèêà. Òîãäà ïåðåâîä {x$, y)|(x, y) ∈ τ (T r)}ìîæíî îñóùåñòâèòü äåòåðìèíèðîâàííûì ÌÏ-ïðåîáðàçîâàòåëåì.Ñóùåñòâóþò ïðîñòûå ÑÓ-ñõåìû, èìåþùèå â êà÷åñòâåâõîäíûõ ãðàììàòèê LR(1)-ãðàììàòèêè è íå ðåàëèçóåìûåíè íà êàêîì ÄÌÏ-ïðåîáðàçîâàòåëå.Ïðèìåð 5.3. Ðàññìîòðèì ïðîñòóþ ÑÓ-ñõåìó ñ ïðàâèëàìèS → Sa,S → Sb,S → e,aSabSbeÂõîäíàÿ ãðàììàòèêà ÿâëÿåòñÿ LR(1)-ãðàììàòèêîé, íî íåñóùåñòâóåò ÄÌÏ-ïðåîáðàçîâàòåëÿ, îïðåäåëÿþùåãî ïåðåâîä{(x$, y)|(x, y) ∈ τ (T r)}.Íàçîâ¼ì ÑÓ-ñõåìó T r = (N, T, Π, R, S) ïîñòôèêñíîé,åñëè êàæäîå ïðàâèëî èç R èìååò âèä A → u, v , ãäå v ∈N ∗ Π∗ .
Èíûìè ñëîâàìè, êàæäûé ýëåìåíò ïåðåâîäà ïðåäñòàâëÿåò ñîáîé öåïî÷êó èç íåòåðìèíàëîâ, çà êîòîðûìè ñëåäóåò öåïî÷êà âûõîäíûõ ñèìâîëîâ.Òåîðåìà 5.4. Ïóñòü T r ïðîñòàÿ ïîñòôèêñíàÿ ÑÓñõåìà, âõîäíàÿ ãðàììàòèêà äëÿ êîòîðîé ÿâëÿåòñÿLR(1). Òîãäà ïåðåâîä{(x$, y)|(x, y) ∈ τ (T r)}ìîæíî îñóùåñòâèòü äåòåðìèíèðîâàííûì ÌÏ-ïðåîáðàçîâàòåëåì.138Ãëàâà 5. Ýëåìåíòû òåîðèè ïåðåâîäà5.2.2. Îáîáù¼ííûå ñõåìû ñèíòàêñè÷åñêèóïðàâëÿåìîãî ïåðåâîäàÐàñøèðèì îïðåäåëåíèå ÑÓ-ñõåìû, ñ òåì ÷òîáû âûïîëíÿòü áîëåå øèðîêèé êëàññ ïåðåâîäîâ.
Âî-ïåðâûõ, ïîçâîëèìèìåòü â êàæäîé âåðøèíå äåðåâà ðàçáîðà íåñêîëüêî ïåðåâîäîâ. Êàê è â îáû÷íîé ÑÓ-ñõåìå, êàæäûé ïåðåâîä çàâèñèòîò ïðÿìûõ ïîòîìêîâ ñîîòâåòñòâóþùåé âåðøèíû äåðåâà. Âîâòîðûõ, ïîçâîëèì ýëåìåíòàì ïåðåâîäà áûòü ïðîèçâîëüíûìèöåïî÷êàìè âûõîäíûõ ñèìâîëîâ è ñèìâîëîâ, ïðåäñòàâëÿþùèõ ïåðåâîäû â ïîòîìêàõ.
Òàêèì îáðàçîì, ñèìâîëû ïåðåâîäà ìîãóò ïîâòîðÿòüñÿ èëè âîîáùå îòñóòñòâîâàòü.Îïðåäåëåíèå. Îáîáù¼ííîé ñõåìîé ñèíòàêñè÷åñêèóïðàâëÿåìîãî ïåðåâîäà (èëè òðàíñëÿöèè, ñîêðàù¼ííî:OÑÓ-ñõåìîé) íàçûâàåòñÿ øåñò¼ðêà T r = (N,T,Π,Γ,R,S),ãäå âñå ñèìâîëû èìåþò òîò æå ñìûñë, ÷òî è äëÿÑÓ-ñõåìû, çà èñêëþ÷åíèåì òîãî, ÷òî(1) Γ êîíå÷íîå ìíîæåñòâî ñèìâîëîâ ïåðåâîäà âèäà Ai ,ãäå A ∈ N è i öåëîå ÷èñëî;(2) R êîíå÷íîå ìíîæåñòâî ïðàâèë ïåðåâîäà âèäàA → u, A1 = v1 , . . . , Am = vm ,óäîâëåòâîðÿþùèõ ñëåäóþùèì óñëîâèÿì:(à) Aj ∈ Γ äëÿ 1 6 j 6 m,(á) êàæäûé ñèìâîë, âõîäÿùèé â v1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
