10 неделя (1178963)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Ïóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÇàäàíèå 10Çàäà÷à 1:ãðàììàòèêåG,Ïîñòðîèòü äåðåâî âûâîäà, ëåâûå è ïðàâûå ðàçáîðû äëÿ ñëîâàE →E+T(1)E→T(2)T →T ∗F(3)T →F(4)F → (E)(5)F →a(6)ETF(E)TF(E((a))âîïðåäåë¼ííîé âûøå.)E → 1ETE → 2TT → 3T FT → 4FF → 5EF →6Ïîñòðîèì äåðåâî âûâîäà äëÿ ñëîâà ((a)):E ⇒ T ⇒ F ⇒ (E) ⇒ (T ) ⇒ (F ) ⇒((E)) ⇒ ((T )) ⇒ ((F )) ⇒ ((a)).Çàìåòèì, ÷òî âñå ïðàâèëà èìåþò â ïðàâîé÷àñòè ìàêñèìóì îäèí íåòåðìèíàë, çíà÷èòíàø âûâîä ÿâëÿåòñÿ êàê ëåâûì, òàê èïðàâûì.Èìåÿ âûâîä ñëîâà ((a)) â ãðàììàòèêå Gáåç òðóäà ïîëó÷èì åãî ðàçáîð ïðèïîìîùè ãðàììàòèêè Gπ , â êîòîðîéïðàâèëà ïîëó÷åíû èç ïðàâèë Góáèðàíèåì âñåõ òåðìèíàëüíûõ ñèìâîëîâèç ïðàâûõ ÷àñòåé. Òîãäà ïîëó÷èì ëåâûéðàçáîð ïðèìåíåíèåì ïðàâèë Gπ ïîä òåìèæå íîìåðàìè, ÷òî è ïðàâèëà G äëÿ ëåâîãîâûâîäà: E ⇒ 2T ⇒ 24F ⇒ 245E ⇒2452T ⇒ 24524F ⇒ 245245E ⇒2452452T ⇒ 24524524F ⇒ 245245246Êàê ìû îòìåòèëè âûøå, íàø âûâîäÿâëÿåòñÿ òàêæå è ïðàâûì. Òîãäà ïðàâûéðàçáîð â íàøåì ñëó÷àå ÿâëÿåòñÿîáðàòíûì (ðåâåðñíóòûì) ëåâûì, ò.å642542542TFaÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCÇàäà÷à 2:plyus.pavelÏîñòðîèòü äåòåðìèíèðîâàííûé ëåâûé àíàëèçàòîð äëÿ ãðàììàòè-êèS → 0S(1)S → 1S(2)S→ε(3)1.

Ñíà÷àëà âû÷èñëèì ôóíêöèþ F IRST äëÿ âñåõ íåòåðìèíàëîâ. Õîä àëãîðèòìà ïðèâåäåì â òàáëèöå.i Fi (S) Êîììåíòàðèé0εÈíèöèàëèçàöèÿ1 ε, 0, 1 Èç ïðàâèë S → 0S è S → 1S , F0 (0) = 0, F0 (1) = 12 ε, 0, 1 Íè÷åãî íîâîãî íå äîáàâëÿåòñÿ2. Âû÷èñëèì ôóíêöèþ F OLLOW äëÿ åäèíñòâåííîãî íåòåðìèíàëà S .i Fi (S) Êîììåíòàðèé0$Èíèöèàëèçàöèÿ, ò.ê S àêñèîìà1$Îáðàáîòàåì ïðàâèëà S → 0S, S → 1S . Äëÿíèõ β = ε, F IRST (ε) = ε ⇒ äîáàâèì F0 (S)ê F1 (S).3.

Ïðèñòóïèì ê ïîñòðîåíèþ òàáëèöû àíàëèçàòîðà.• S → 0S :F IRST (0S) = F IRST (0) = 0 ⇒ M [S, 0] = S → 0S• S → 1S :F IRST (1S) = F IRST (1) = 1 ⇒ M [S, 1] = S → 1S• S → ε F IRST (ε) = ε ⇒ Äîáàâëÿåì S → ε äëÿ êàæäîãî òåðìèíàëà èçF OLLOW (S) = {$}, ò.ê $ ∈ F OLLOW (S) äîáàâëÿåì S → ε ê M [S, $]S0S → 0S1S → 1S$S→εÇàäà÷à 3∗ :Äîáàâèì â ãðàììàòèêó G ïðàâèëî E → ε. Âû÷èñëèòå çíà÷åíèåF IRST (E)Ïðèâåäåì òàáëèöó ðàáîòû àëãîðèòìà ïî âû÷èñëåíèþ ôóíêöèè F IRST äëÿ âñåõíåòåðìèíàëîâôóíêöèèÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCiplyus.pavelÊîììåíòàðèé (ôîðìóëà â îòíîñèòåëüíî îáùåì âèäå, ò.å â íåéðàñêðûòû âñå óñëîâèÿ ïî âêëþ÷àþùèìñÿ ìíîæåñòâàì äëÿ íàøèõ íåòåðìèíàëîâ ïî âñåì ïðàâèëàì)0ε∅∅Èíèöèàëèçàöèÿ.

F0 (S) = {ε} ò.ê åñòü ïðàâèëî E → ε1ε, +∅(, aF1 (E) = F0 (E) ∪ ((F0 (ε)/{ε} ∪ {ε}) ∪ (F0 (E)/{ε} ∪ {ε}) ∪ F0 (T )):Èç ïðàâèëà E → ε ñëåäóåò äîáàâëåíèå (F0 (ε)/{ε} ∪ {ε}), èçE → E + T ñëåäóåò äîáàâëåíèå (F0 (E)/{ε} ∪ {ε}) ∪ F0 (T )F1 (T ) = F0 (T ) ∪ (F0 (T )/ε ∪ F0 (F )):Èç ïðàâèëà T → T ∗F ñëåäóåò äîáàâëåíèå (F0 (T )/ε, à èç T → Fñëåäóåò äîáàâêà F0 (F )F1 (F ) = F0 (F ) ∪ (F0 (0 (0 ) ∪ F0 (a)):Èç ïðàâèëà F → (E) íàäî äîáàâèòü F0 (0 (0 ), à èç-çà F → añëåäóåò äîáàâêà F0 (a)2ε, +(, a(, aF2 (E) = F1 (E) ∪ ((F1 (ε)/{ε} ∪ {ε}) ∪ (F1 (E)/{ε} ∪ {ε}) ∪ F1 (T ));F2 (T ) = F1 (T ) ∪ (F1 (T )/ε ∪ F1 (F )); F2 (F ) = F1 (F ) ∪ (F1 (0 (0 ) ∪F1 (a))3 ε, +, (, a(, a(, aF3 (E) = F2 (E) ∪ ((F2 (ε)/{ε} ∪ {ε}) ∪ (F2 (E)/{ε} ∪ {ε}) ∪ F2 (T ));F3 (T ) = F2 (T ) ∪ (F2 (T )/ε ∪ F2 (F )); F3 (F ) = F2 (F ) ∪ (F2 (0 (0 ) ∪F2 (a))4 ε, +, (, a(, a(, aF4 (E) = F3 (E) ∪ ((F3 (ε)/{ε} ∪ {ε}) ∪ (F3 (E)/{ε} ∪ {ε}) ∪ F3 (T ));F4 (T ) = F3 (T ) ∪ (F3 (T )/ε ∪ F3 (F )); F4 (F ) = F3 (F ) ∪ (F3 (0 (0 ) ∪F3 (a))Òàêèì îáðàçîì, F IRST (E) = F4 (E) = {ε, +, (, a}FI (E)FI (T )Çàäà÷à 4:ÿâëÿåòñÿFI (F )Äîêàæèòå, ÷òî ãðàììàòèêà íå ÿâëÿåòñÿLL(2)-ãðàììàòèêîé.Âû÷èñëèòå ôóíêöèèF IRST2LL(1)-ãðàììàòèêîé, íîè F OLLOW2 äëÿ âñåõíåòåðìèíàëîâ.S → aAaa|bAbaA → b|εÑïåðâà âû÷èñëèì çíà÷åíèÿ ôóíêöèé F IRST, F OLLOW, F IRST2 , F OLLOW2 äëÿâñåõ íåòåðìèíàëîâ.

Õîä ðàáîò àëãîðèòìîâ ïðèâåäåì â òàáëèöàõ, ñîîòâåòñòâóþùèå èòîãîâûå çíà÷åíèÿ ôóíêöèé íàõîäÿòñÿ íà ïîñëåäíèõ ñòðîêàõ.i012i012FI (S)∅a, ba, bFi (A)εε, bε, bÐèñ. 1: F IRSTFI (S) Fi (A)$∅$aa, ba$aa, bai012FI (S)$$$Fi (A)∅a, ba, bÐèñ. 2: F OLLOWi012FI (S)∅ab, aa, bbab, aa, bbFi (A)b, εb, εb, εÐèñ.

3: F IRST2Ðèñ. 4: F OLLOW2Çàìåòèì, ÷òî ãðàììàòèêà G íå ÿâëÿåòñÿ LL(1) ãðàììàòèêîé. Ïðåäïîëîæèì ïðîòèâíîå è ðàññìîòðèì ïàðó ïðàâèë A → ε|b. Ò.ê ε ∈ F IRST (ε), òî F IRST (b)∩F OLLOW (A) =Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavel∅ èç óñëîâèÿ LL(1) ãðàììàòèêè, íî F IRST (b) ∩ F OLLOW (A) = {b}, ïîëó÷èëè ïðîòèâîð÷åèå ⇒ G íå ÿâëÿåòñÿ LL(1).Äîêàæåì, ÷òî îíà ÿâëÿåòñÿ LL(2) ïî òåîðåìå 4.6 ñî ñòðàíèöû 106 ó÷åáíèêà Ñåðåáðÿêîâà.

Ðàññìîòðèì ïðàâèëà S → aAaa|bAba. Çàìåòèì, ÷òî ∀α F IRST2 (aAaaα) ∩F IRST2 (bAbaα) = ∅, à çíà÷èò îíî ïóñòî è ïðè âñåõ òàêèõ ωSα, ÷òî S ⇒∗l ωAα.Ðàññìîòðèì ïðàâèëà A → ε|b. Ðàññìîòðèì âîçìîæíûå ñåíòåíöèàëüíûå ôîðìû, âûâîäèìûå èç S ñ ó÷àñòèåì A: ýòî aAaa èëè bAba (äðóãèõ íåò, ò.ê A ïîëó÷àåòñÿ òîëüêî èçS ïðàâèëàìè S → aAaa|bAba, A íîâûõ âõîæäåíèé A íå ïîðîæäàåò).

Òîãäà â óñëîâèèòåîðåìû α = aa èëè α = ba, ò.ê âûâîäèìû ëèøü S ⇒∗l aAaa èëè S ⇒∗l bAba. Äëÿ α = aaF IRST2 (εaa) ∩ F IRST2 (baa) = ∅, êàê è äëÿ α = ba F IRST2 (εba) ∩ F IRST2 (bba) = ∅Çíà÷èò, ãðàììàòèêà G ÿâëÿåòñÿ LL(2) ïî ýòîé òåîðåìå.Çàäà÷à 5∗ :L = a∗ ∪ an bn íå ÿâëÿåòñÿ LL-ÿçûêîì.Ïðåäïîëîæèì ïðîòèâíîå, ïóñòü L - LL ÿçûê, ò.å äëÿ íåãî ñóùåñòâóåò LL(k) ãðàììàòèêà.Äîêàæèòå, ÷òî ÿçûêËþáàÿ ÊÑ - ãðàììàòèêà, ïîðîæäàþùàÿ ÿçûê L äîëæíà èìåòü âåòâëåíèå, èç îäíîéâåòâè (íåòåðìèíàëà) äîëæíî ïîðîæäàòüñÿ a∗ , èç äðóãîé (äðóãîãî íåòåðìèíàëà) - an bn .Óñëîâíî, ýòó ãðàììàòèêó ìîæíî çàïèñàòü â âèäå G: S → A|B, A → aAb|ε, B → aB|ε.Ãëàâíîå, ÷òî áóäåò íåòåðìèíàë, èç êîòîðîãî èäåò ðàçâåòâëåíèå, áóäåì íàçûâàòü åãî S(â íàøåì ñëó÷àå âåòâÿùèéñÿ íåòåðìèíàë - S ).Ò.ê íàøà ãðàììàòèêà G ÿâëÿåòñÿ LL(k) äëÿ íåêîòîðîãî k , òî äëÿ íåå ñïðàâåäëèâà òåîðåìà, èñïîëüçîâàííàÿ â ïðåäûäóùåé çàäà÷å.Ðàññìîòðèì ïðàâèëà S → A|B .

Èç óñëîâèÿ òåîðåìû, ïåðåñå÷åíèå F IRSTk (Aα) ∩F IRSTk (Bα) ïóñòî ïðè âñåõ òàêèõ ωAα, ÷òî S ⇒∗l ωAα. Äëÿ ïðîèçâîëüíîãî k èç òåîðåìû ðàññìîòðèì ñëîâî ak bk , âûâîäÿùååñÿ èç ãðàììàòèêè, â ÷àñòíîñòè èç íåòåðìèíàëàA, ⇒ ak ∈ F IRSTk (A). Òàêæå ðàññìîòðèì ak , âûâîäÿùååñÿ èç ãðàììàòèêè, â ÷àñòíîñòèèç íåòåðìèíàëà B⇒ ak ∈ F IRSTk (B).Ïîëó÷èëè, ÷òî ak ∈ F IRSTk (A), ak ∈ F IRSTk (B) ⇒ F IRSTk (Aα) ∩ F IRSTk (Bα) íåïóñòî, òàê êàê ñîäåðæèò êàê ìèíèìóì ak . Ïîëó÷èëè ïðîòèâîðå÷èå, çíà÷èò ëþáàÿ ãðàììàòèêà, çàäàþùàÿ ÿçûê L íå ÿâëÿåòñÿ LL(k) ãðàììàòèêîé íè äëÿ êàêîãî k ⇒ L - íåLL ÿçûê.Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ Ïðîãðàììèðîâàíèÿ.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов курсовой работы