В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 47
Текст из файла (страница 47)
Îïðåäåëèòü, ÿâëÿþòñÿ ëè ñëåäóþùèå ãðàììàòèêèLL(k)-ãðàììàòèêàìè, è óêàçàòü òî÷íîå çíà÷åíèå k :à) S → AbA → Aa | a;á)S → AbA → aA | a;â) S → aAbA → BBB → ab | A | ε;ã) S → aAbA → AaAb | ε;ä) S → aBB → aBB | b.4.4.6. Ïðåîáðàçîâàòü ãðàììàòèêó ê LL(1)-âèäó è ïîñòðîèòü äëÿ íå¼ LL(1)-òàáëèöóà) S → AbA → aA | a;á) S → aBB → aBB | b.C.4. Ñèíòàêñè÷åñêèé àíàëèç3474.4.7. Ñêîëüêî òàêòîâ ñäåëàåò LL(1)-àíàëèçàòîð äëÿãðàììàòèêè G c ïðàâèëàìè:S → aAB A → bC B → SS | ε C → A | εïðè ðàçáîðå öåïî÷êè x = ab?4.4.8.
ßâëÿåòñÿ ëè ãðàììàòèêà S → Sa | bãðàììàòèêîé?LL(2)-4.4.9. ßâëÿåòñÿ ëè ÿçûê, ñîñòîÿùèé èç âñåõ öåëûõ ÷èñåëáåç çíàêà è áåç íåçíà÷àùèõ íóëåé, LL(1)-ÿçûêîì?4.4.10. ßâëÿåòñÿ ëè ÿçûê, ñîñòîÿùèé èç âñåõ öåïî÷åê èç0 è 1, íå ñîäåðæàùèõ ïîäöåïî÷êè 010, LL(1)-ÿçûêîì?4.4.11. ßâëÿåòñÿ ëè ÿçûê, ñîñòîÿùèé èç âñåõ íåïóñòûõöåïî÷åê èç 0 è 1, íå ñîäåðæàùèõ òðåõ 1 ïîäðÿä, LL(1)ÿçûêîì?4.4.12. Ñóùåñòâóåò ëè êîíòåêñòíî-ñâîáîäíàÿ ãðàììàòèêà, LL(1)-òàáëèöà äëÿ êîòîðîé íå ñîäåðæèò ýëåìåíòîâ¾îøèáêà¿?4.4.13. Ñôîðìóëèðóéòå íåîáõîäèìûå è äîñòàòî÷íûåóñëîâèÿ òîãî, ÷òî ÊÑ-ãðàììàòèêà åñòü LL(1)-ãðàììàòèêà.Äîêàæèòå íåîáõîäèìîñòü è äîñòàòî÷íîñòü.C.4.5.
Ðàçáîð ñíèçó-ââåðõñâåðòêàòèïàñäâèã-4.5.1. Ïîñòðîèòü âñå ñîñòîÿíèÿ äëÿ LR(0)-àíàëèçà ãðàììàòèêè G:S → aAb; A → ε; A → aaA.Áóäåò ëè G LR(0)-ãðàììàòèêîé? À LR(1)?4.5.2. ßâëÿåòñÿ ëè ãðàììàòèêà ñ ïðàâèëàìè:S → A | B; B → aB | b | C ; A → AA | a; C → cCLR(0)-ãðàììàòèêîé?4.5.3. Ñêîëüêî ìíîæåñòâ LR(0)-ñèòóàöèé â êàíîíè÷åñêîé ñèñòåìå LR(0)-ñèòóàöèé ãðàììàòèêè G ñ ïðàâèëàìè348à) S → aA | aBá) S → A0 | F 1â) E → (L) | aÏðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãèA → bA | cA → S0 | B1L → EL | E .B → bB | d;B → A1 | F 0F → B0 | S1;4.5.4.
Ñêîëüêî LR(0)-òàáëèö èìååò ãðàììàòèêà ñ ïðàâèëàìè:S → Aa | Bb; B → b; A → ab.4.5.5. Ïîñòðîèòü âñå ñîñòîÿíèÿ LR(1)-àíàëèçà äëÿ ãðàììàòèêè:S → aAb; A → ε | aaA.4.5.6. Ñêîëüêî ìíîæåñòâ LR(1)-ñèòóàöèé â êàíîíè÷åñêîé cèñòåìå LR(1)-ñèòóàöèé ãðàììàòèêè G ñ ïðàâèëàìèà) S → aSb | ab;á) S → aAc | bA → aSc | b.4.5.7. Îïðåäåëèòü, ÿâëÿåòñÿ ëè ãðàììàòèêà c ïðèâåäåííûì íàáîðîì ïðàâèë LR(1)-ãðàììàòèêîé:à) A → aAB | bB → b | ε;á) S → SaSS → a;â) S → Abb | BbaA→aB → a;ã) S → aL | aL → Lb | b.4.5.8.
Ïîñòðîèòü âñå ñîñòîÿíèÿ àíàëèçà (K = 1) äëÿãðàììàòèêèS → S1 ;S1 → S1 S1 ;S1 → a.Áóäåò ëè ýòà ãðàììàòèêà LR(1)?4.5.9. Ïîñòðîèòü âñå ñîñòîÿíèÿ LR(1) àíàëèçà äëÿ ãðàììàòèêè:S → aBc; B → b; B → bBb.Ïðèìåíèâ êðèòåðèé LR(K), îïðåäåëèòü, áóäåò ëè ýòîLR(1)-ãðàììàòèêà.4.5.10. Âûÿñíèòü, ÿâëÿþòñÿ ëè ñëåäóþùèå ãðàììàòèêèLR(k)-ãðàììàòèêàìè. Íàéòè òî÷íîå çíà÷åíèå k è ïîñòðîèòüäåòåðìèíèðîâàííûé ïðàâûé àíàëèçàòîð:à) S → SaSb | ε;á) S → Sa | a;â) S → C | d C → Ac | b D → aD | c;C.4.
Ñèíòàêñè÷åñêèé àíàëèç349ã) S → Ab | Bc A → Aa | ε B → Ba | ε;ä) S → AB A → a B → CD | aE C → ab D → bbE → bba;å) S → AB A → 0A1 | ε B → 1B | 1.4.5.11. ßâëÿåòñÿ ëè íèæåïðèâåäåííàÿ ãðàììàòèêàLR(k), è åñëè äà, òî îïðåäåëèòü ìèíèìàëüíîå k .à) S → aAcA → aScS→bA → b;á) S → S1S1 → S1 S1S1 → a;â) S → aBcB→bB → bBb;ã) S → aAcS→bA → aScA → b;ä) S → aAbA→0A → aaA;å) S → aAbA→εA → aaA.4.5.12. ßâëÿþòñÿ ëè ñëåäóþùèå ãðàììàòèêè LR(k)ãðàììàòèêàìè? Óêàçàòü òî÷íîå çíà÷åíèå k è ïîñòðîèòü ñîîòâåòñòâóþùèé äåòåðìèíèðîâàííûé ïðàâûé àíàëèçàòîð.à) S → AbA → Aa | a;á) S → AbA → aA | a;â) S → aAbA → BBB → ab | A | ε;ã) S → aAbA → AaAb | ε;ä) S → aBB → aBB | b.4.5.13. Äëÿ ãðàììàòèêèS → Ab | Bc A → Aa | ε B → Ba | εíàïèñàòü ýêâèâàëåíòíóþ LR(0)-ãðàììàòèêó.4.5.14. Ñêîëüêî ñâåðòîê è ïåðåíîñîâ ñäåëàåò LR(1)àíàëèçàòîð äëÿ ãðàììàòèêè G = ({S, A}, {a}, P, S) c ïðàâèëàìè S → A A → Aa | a ïðè àíàëèçå öåïî÷êè a100 ?4.5.15.
Ñêîëüêî SLR(1)-òàáëèö èìååò ãðàììàòèêà ñ ïðàâèëàìè:S → Aaa | Bb | C B → aa A → aa C → cAc | cBd.4.5.16. Ñêîëüêî òàêòîâ ñäåëàåò LALR(1)-àíàëèçàòîð äëÿãðàììàòèêè ñ ïðàâèëàìè:S → A | BC B → a A → a; C → AAASïðè ðàçáîðå öåïî÷êè aaaaa?350Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãè4.5.17. Âûïèñàòü öåïî÷êó ìèíèìàëüíîé äëèíû, íà êîòîðîé âèäíû îòëè÷èÿ LARL(1) è LR(1)-àíàëèçàòîðîâ äëÿãðàììàòèêè ñ ïðàâèëàìè:S → Aa | Bb | CB → aaA → aaC → cAc | cBd.4.5.18. Ïóñòü G = (N, T, P, S) LR(1)-ãðàììàòèêà,w ∈ T ∗ .
 êàêèõ ñëó÷àÿõ (â çàâèñèìîñòè îò G è w) LR(1)àíàëèçàòîð ïðè àíàëèçå öåïî÷êè w íå ñäåëàåò íè îäíîãîñäâèãà?4.5.19. Ïóñòü G = (N, T, P, S) LR(1)-ãðàììàòèêà; w ∈/L(G), |w| = n. Ïóñòü k ÷èñëî ñäâèãîâ, äåëàåìûõ LR(1)àíàëèçàòîðîì ïðè àíàëèçå öåïî÷êè w. Ïðèâåñòè íèæíþþè âåðõíþþ îöåíêó äëÿ ÷èñëà k .4.5.20. Ïóñòü G = (N, T, P, S) LR(1)-ãðàììàòèêà,|P | = m > 1; w ∈ L(G), |w| = n. Ïóñòü k ÷èñëî ñâåðòîê, äåëàåìûõ LR(1)-àíàëèçàòîðîì ïðè àíàëèçå öåïî÷êèw.
Ïðèâåñòè íèæíþþ îöåíêó äëÿ ÷èñëà k .4.5.21. Ïóñòü G = (N, T, P, S) LR(1)-ãðàììàòèêà,|P | = m > 1; w ∈/ L(G), |w| = n. Ïóñòü k ÷èñëî ñâåðòîê, äåëàåìûõ LR(1)-àíàëèçàòîðîì ïðè àíàëèçå öåïî÷êèw. Ïðèâåñòè íèæíþþ îöåíêó äëÿ ÷èñëà k .4.5.22. Ñóùåñòâóåò ëè LR(1)-ãðàììàòèêà, äëÿ êîòîðîéôóíêöèÿ äåéñòâèé LR(1)-òàáëèöû íå ñîäåðæèò ýëåìåíòîâ¾îøèáêà¿?4.5.23. Äàíà ÊÑ-ãðàììàòèêà G = (N, T, P, S).
Íàéòèâåðõíþþ îöåíêó ÷èñëà LR(1)-ñèòóàöèé äëÿ G.4.5.24. Äàíà LR(1)-ãðàììàòèêà áåç ε-ïðàâèë G è öåïî÷êà w ∈ L(G).  äåðåâå ðàçáîðà w − n1 ëèñòüåâ è n2 âíóòðåííèõ âåðøèí. Ñêîëüêî ñäâèãîâ è ñâåðòîê ñäåëàåò LR(1)àíàëèçàòîð äëÿ G ïðè àíàëèçå öåïî÷êè w?C.5. Ýëåìåíòû òåîðèè ïåðåâîäà351C.5. Ýëåìåíòû òåîðèè ïåðåâîäàC.5.3. Àòðèáóòíûå ãðàììàòèêè5.3.1. Äîïîëíèòü ãðàììàòèêó S → 0S11, S → 1S00,S → ε äî àòðèáóòíîé òàê, ÷òîáû âû÷èñëÿëàñü ìàêñèìàëüíàÿ äëèíà íåïðåðûâíîé ïîñëåäîâàòåëüíîñòè åäèíèö â ïîðîæäåííîì ñëîâå.5.3.2. Äîïîëíèòü ãðàììàòèêó S → AA, A → 0A,A → 1A, A → ε äî àòðèáóòíîé òàê, ÷òîáû âû÷èñëÿëàñüìàêñèìàëüíàÿ äëèíà íåïðåðûâíîé ïîñëåäîâàòåëüíîñòè èç1 â ïîðîæäåííîì ñëîâå.5.3.3. Äîïîëíèòü ãðàììàòèêó S → AA, A → A0,A → A1, A → ε äî àòðèáóòíîé òàê, ÷òîáû âû÷èñëÿëîñü÷èñëî ñî÷åòàíèé 01 â ïîðîæäåííîì ñëîâå.5.3.4.  ãðàììàòèêå [öåëîå] → dC, C → dC | ε òåðìèíàë d èìååò àòðèáóò 0 èëè 1.
Îïðåäåëèòü àòðèáóòû òàê,÷òîáû íåòåðìèíàë [öåëîå] èìåë àòðèáóò, ðàâíûé âîñüìåðè÷íîìó çíà÷åíèþ âûâîäèìîãî ÷èñëà.5.3.5. Ïîñòðîèòü àòðèáóòíûå ãðàììàòèêè äëÿ ñëåäóþùèõ ïåðåâîäîâ:à) {(x, x) | x ∈ {a, b}∗ };á) {(x, xR ) | x ∈ {a, b}∗ };â) {(x, xx) | x ∈ {a, b}∗ };ã) {(an bn , an bn cn ) | n > 1}.5.3.6. Ïðèâåñòè ïðèìåð àòðèáóòíîé ãðàììàòèêè ñ íåêîððåêòíî çàäàííûìè ñåìàíòè÷åñêèìè ïðàâèëàìè5.3.7.
Ïðèâåñòè ïðèìåð àòðèáóòíîé ãðàììàòèêè, âû÷èñëåíèå àòðèáóòîâ äëÿ êîòîðîé íåëüçÿ âûïîëíèòü ïàðàëëåëüíî ñ LL(1)-àíàëèçîì.5.3.8. Ïðèâåñòè ïðèìåð àòðèáóòíîé ãðàììàòèêè, âû÷èñëåíèå àòðèáóòîâ äëÿ êîòîðîé íåëüçÿ âûïîëíèòü ïàðàëëåëüíî ñ LR(1)-àíàëèçîì.352Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãèC.9. Ãåíåðàöèÿ êîäàC.9.1. Òðàíñëÿöèÿ àðèôìåòè÷åñêèõ âûðàæåíèé9.1.1. Äëÿ ñëåäóþùèõ àðèôìåòè÷åñêèõ âûðàæåíèé ñ ïîìîùüþ àëãîðèòìà Ñåòè-Óëüìàíà ñãåíåðèðîâàòü ïðîãðàììóè èçîáðàçèòü àòðèáóòèðîâàííîå äåðåâî:à) A∗ B + C ∗ (D + E)∗ F ;á) A∗ (B + C)∗ (D + E)∗ F ;â) A + B + C ∗ D + E ∗ F ;ã) A + B ∗ C ∗ D∗ E + F ;ä) A + B ∗ (C ∗ D + E ∗ F ).C.9.2.
Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèé9.2.1. Äëÿ ñëåäóþùèõ ëîãè÷åñêèõ âûðàæåíèé ñãåíåðèðîâàòü êîä íà êîìàíäàõ ïåðåõîäà è èçîáðàçèòü àòðèáóòèðîâàííîå äåðåâîà) A and not (B or C) or (D and E);á) A and B and C or not (D or E);â) A and (B or not (C and D) and E);ã) not (A and B or C or D) and E ;ä) A and B or C or D and not E .C.9.3. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà ìåòîäàìè ñèíòàêñè÷åñêîãî àíàëèçà9.3.1. Äëÿ ñëåäóþùèõ îïåðàòîðîâ ïðèñâàèâàíèÿ ñãåíåðèðîâàòü îïòèìàëüíûé êîä ìåòîäîì ñîïîñòàâëåíèÿîáðàçöîâ:à) a = b[i] + j ;á) a = b[i+5];â) a = b[i] + c[2];ã) a = b[i+2+j];ä) a = b[2+c[1]];å) a = b[i+j];æ) a = b[i+2] + 3;ç) a = j + b[i+3];è) a = b[i+j+1];ê) a = b[i+j] + 1.Ëèòåðàòóðà1. Àäåëüñîí-Âåëüñêèé Ã.Ì., Ëàíäèñ Å.Ì.
Îäèí àëãîðèòìîðãàíèçàöèè èíôîðìàöèè // ÄÀÍ ÑÑÑÐ. 1962. Ò. 146.N 2. Ñ. 263266.2. Àõî À., Óëüìàí Ä. Òåîðèÿ ñèíòàêñè÷åñêîãî àíàëèçà,ïåðåâîäà è êîìïèëÿöèè, â 2-õ ò. Ì.: Ìèð, 1978.3. Àõî À., Ñåòè Ð., Óëüìàí Äæ. Êîìïèëÿòîðû. Ïðèíöèïû, òåõíîëîãèè, èíñòðóìåíòû. Ì. - ÑÏá. - Êèåâ: Âèëüÿìñ, 2001.4. Áåçäóøíûé À.Í., Ëþòûé Â.Ã., Ñåðåáðÿêîâ Â.À. Ðàçðàáîòêà êîìïèëÿòîðîâ â ñèñòåìå ÑÓÏÅÐ.Ì.: ÂÖ ÀÍÑÑÑÐ, 1991.5.
Ãðèñ Ä. Êîíñòðóèðîâàíèå êîìïèëÿòîðîâ äëÿ öèôðîâûõ âû÷èñëèòåëüíûõ ìàøèí. Ì.: Ìèð, 1975.6. Êíóò Ä. Èñêóññòâî ïðîãðàììèðîâàíèÿ äëÿ ÝÂÌ. Ò.1. Îñíîâíûå àëãîðèòìû. Ì.: Ìèð, 1976.7. Êíóò Ä. Ñåìàíòèêà êîíòåêñòíî-ñâîáîäíûõ ÿçûêîâ //Ñåìàíòèêà ÿçûêîâ ïðîãðàììèðîâàíèÿ. Ì.: Ìèð, 1980.8. Êóðî÷êèí Â.Ì., Ñòîëÿðîâ Ë.Í., Ñóøêîâ Á.Ã., Ôë¼ðîâÞ.À. Òåîðèÿ è ðåàëèçàöèÿ ÿçûêîâ ïðîãðàììèðîâàíèÿ.Êóðñ ëåêöèé. ÌÔÒÈ, 1973 (1-å èçä.) è 1978 ã. (2-å èçä.)9. Êóðî÷êèí Â.Ì. Àëãîðèòì ðàñïðåäåëåíèÿ ðåãèñòðîâ äëÿâûðàæåíèé çà îäèí îáõîä äåðåâà âûâîäà. 2 Âñåñ.
êîíô.354Ëèòåðàòóðà¾Àâòîìàòèçàöèÿ ïðîèçâîäñòâà ÏÏÏ è òðàíñëÿòîðîâ¿. 1983. Ñ. 104105.10. Ëàâðîâ Ñ.Ñ., Ãîí÷àðîâà Ë.È. Àâòîìàòè÷åñêàÿ îáðàáîòêà äàííûõ. Õðàíåíèå èíôîðìàöèè â ïàìÿòè ÝÂÌ. Ì.:Íàóêà, 1971.11. Ìàðòûíåíêî Á.Ê. ßçûêè è òðàíñëÿöèè. ÑÏá.: ÑÏá.ÃÓ, 2004. Ñì. òàêæå êîíñïåêò ýòèõ ëåêöèé â Ñåòè:http://www.math.spbu.ru/user/mbk/TUTORY/LT.html12. Íàäåæèí Ä.Þ., Ñåðåáðÿêîâ Â.À., Õîäóêèí Â.Ì. Ïðîìåæóòî÷íûé ÿçûê Ëèäåð (ïðåäâàðèòåëüíîå ñîîáùåíèå)// Îáðàáîòêà ñèìâîëüíîé èíôîðìàöèè. Ì.: ÂÖ ÀÍÑÑÑÐ, 1987. Ñ. 5063.13. Õîïêðîôò Ä., Ìîòâàíè Ð., Óëüìàí Ä. Ââåäåíèå â òåîðèþ àâòîìàòîâ, ÿçûêîâ è âû÷èñëåíèé, èçä. 2-å. Ì.: Âèëüÿìñ, 2002.
Ñ. 527.14. Aho A.U., Ganapathi M., Tjiang S.W. Code generationusing tree matching and dynamic programing // ACMTrans. Progr. Languages and Systems. 1989. V.11. N 4.15. Bezdushny A., Serebriakov V. The use of the parsingmethod for optimal code generation and commonsubexpression elimination // Techn. et Sci. Inform. 1993.V. 12.
N. 1. P. 6992.16. Emmelman H., Schroer F.W., Landweher R. BEG agenerator for efficient back-ends // ACM SIGPLAN. 1989.V. 11. N 4. P. 227237.17. Fraser C.W., Hanson D.R. A Retargetable compiler forANSI C // SIGPLAN Notices. 1991. V. 26.18. Graham S.L., Harrison M.A., Ruzzo W.L. An improvedcontext-free recognizer // ACM Trans. Program.Languages and Systems. 1980. N. 2.19. Harrison M.A. Introduction to formal language theory.Reading, Mass.: Addison-Wesley, 1978.Êðàòêèå ñâåäåíèÿ îá àâòîðàõ355Data on authors of the manual ¾The Theory &Realization of Programming Languages¿Vladimir A.
Serebryakov - DSc (Physics, Mathematics), Chief of the Department of Software Systems, ComputingCenter, Russian Academy of Sciences (RAS), Professor atMIPT and Moscow State University.Gives lectures on ¾Computer Design¿ and ¾Theory andRealization of Programming Languages¿.Area of Research: programming languages, compilers andinterpreters, distributed systems.Maxim P.Galochkin - research scientist of theDepartment of Software Systems, Computing Center of RAS,lecturer at Moscow State University.Gives classes on ¾Computer Design¿.Area of Research: programming languages, compilers andinterpreters, distributed systems.Dmitry R.Gonchar - research scientist of the branch¾CAD of Real-time Systems¿, Computing Center, Russian Ac.of Sci., Assistant Professor at MIPT.Gives lectures on ¾Theory of Formal Languages¿and seminars on ¾Theory & Realization of ProgrammingLanguages¿, ¾Relational Data Bases and SQL language¿.Area of Research: automatic design of real-timecomputational systems, schedule theory.Meran G.Fourougian - Ph D (Physics, Mathematics),Head of the branch ¾CAD of Real-time Systems¿, ComputingCenter, Russian Ac.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
