языки и методы трансляции

Part I

Âîïðîñû ê çà÷åòó 1.

Ññûëî÷íûé òèï äàííûõ. Òèïû óêàçàòåëåé. Äåéñòâèÿ íàä óêàçàòåëÿìè.

2.

Ñïèñêè. Êëàññèôèêàöèÿ ñïèñêîâ.

3.

Ðåêóðñèÿ. Ðåêóðñèâíûå ïðîöåäóðû. Ñõåìû ðåêóðñèâíîé ïðîöåäóðû.

4.

Äåðåâüÿ. Îñíîâíûå îïðåäåëåíèÿ. Áèíàðíîå äåðåâî. Àëãîðèòì îáõîäà.

5.

Ñáàëàíñèðîâàííûå äåðåâüÿ. Äèõîòîìè÷åñêèå äåðåâüÿ. Àëãîðèòì ïîñòðîåíèÿ. ÀÂË

6.

- äåðåâüÿ.

ßçûê. Àëôàâèò. Öåïî÷êà. Ãðàììàòèêè ÿçûêà. Êëàññèôèêàöèÿ ãðàììàòèê ïî Õîëìñêîìó.

7.

Ïðåäñòàâëåíèå àâòîìàòíîé ãðàììàòèêè â âèäå ãðàôîâ. Äåòåðìèíèðîâàííûå ôîðìû. Àëãîðèòì ïîñòðîåíèÿ àíàëèçàòîðà.

8.

Ðàñïîçíàâàòåëü

- îñíîâíûå ïîíÿòèÿ è àëãîðèòì ðàáîòû.

9.

Àëãîðèòì ïåðåõîäà îò íå äåòåðìèíèðîâàííîãî àâòîìàòà ê äåòåðìèíèðîâàííîìó.

10.

Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ.

11.

Òåîðåìà îá îáùåì âèäå àâòîìàòíûõ è ÊÑ ÿçûêîâ è èõ ñëåäñòâèÿ.

12.

Îïåðàöèè íàä ÿçûêàìè è òåîðåìà îá îïåðàöèÿõ íàä àâòîìàòíûìè è ÊÑ ÿçûêàìè.

13.

Ìåòîäû àíàëèçà ÊÑ ÿçûêîâ. Ãðàììàòèêè ïðåäøåñòâîâàíèÿ.

14.

ÏÎËÈÇ. Àëãîðèòì Çàìåëüñîíà-Áàóýðà.

15.

Îñíîâíûå ôàçû òðàíñëÿöèè.

×àñòü II

Áèëåòû 1

Ññûëî÷íûé òèï äàííûõ. Òèïû óêàçàòåëåé. Äåéñòâèÿ íàä óêàçàòåëÿìè.

1.1

Ññûëî÷íûé òèï äàííûõ

Èäåíòèôèêàöèÿ îáúåêòà

-

îïðåäåëåíèå ìåñòîíàõîæäåíèÿ îáúåêòà â ïàìÿòè

ÝÂÌ è ïîëó÷åíèå äîñòóïà ê çíà÷åíèþ ñâîéñòâ îáúåêòà. Ñóùåñòâóåò äâà âèäà èäåíòèôèêàöèè:

1

1.

Èìåíîâàíèå

2.

Óêàçàíèå

Ïðè èìåíîâàíèè èìÿ îáúåêòà ñâÿçûâàåòñÿ ñ ýëåìåíòîì õðàíåíèÿ íà ýòàïå êîìïèëÿöèè. Íà ýòàïå âûïîëíåíèÿ ñâÿçü íå ìîæåò áûòü èçìåíåíà. Íàçíà÷åííîå èìÿ âñåãäà äàåò äîñòóï ê îäíîìó è òîìó æå ýëåìåíòó õðàíåíèÿ. Èìåíîâàòüñÿ ìîãó îòäåëüíûå ñâîéñòâà îáúåêòîâ. Òàêîé èäåíòèôèêàòîð íàçûâàåòñÿ êâàëèôèöèðîâàííûì èäåíòèôèêàòîðîì èëè êâàëèäåíòîì. Äèñòàíöèåé íàçûâàåòñÿ äëèíà ïóòè äî íóæíîãî ñâîéñòâà.  ñëó÷àå, åñëè äèñòàíöèÿ äîñòóïà âåëèêà, òî ïðèìåíÿåòñÿ îïåðàòîð ïðèñîåäèíåíèÿ

with. Äëÿ äîñòóïà ê ýëåìåíòàì ìàññèâà èñïîëüçóåòñÿ èíäåêñèðîâàííîå èëè óòî÷íåííîå èìÿ. Âòîðîé òèï èäåíòèôèêàöèè ñâÿçàí ñ èñïîëüçîâàíèåì ññûëî÷íîãî èëè óêàçàòåëüíîãî òèïà. Ññûëî÷íûé òèï îïðåäåëÿåò îñîáûé òèï îáúåêòà, êàæäûé èç êîòîðûõ îïðåäåëÿåò àäðåñ äðóãîãî îáúåêòà â ïàìÿòè ÝÂÌ.  êà÷åñòâå òàêîãî îáúåêòà ìîæåò âûñòóïàòü óêàçàòåëü. Ñóùåñòâóåò ñïåöèàëüíàÿ êîíñòàíòà, êîòîðàÿ îïðåäåëÿåò îñîáîå ïîëîæåíèå óêàçàòåëÿ, ïðè êîòîðîì îí íå óêàçûâàåò íè íà îäèí èç ñóùåñòâóþùèõ îáúåêòîâ.

nil

1.2

Òèïû óêàçàòåëåé

Óêàçàòåëè ïîäðàçäåëÿþò íà òèïèçèðîâàííûå è íå òèïèçèðîâàííûå (ñâîáîäíûå). Íå òèïèçèðîâàííûé óêàçàòåëü óêàçûâàåò íà îáúåêò, äîïóñêàþùèé ïðîèçâîëüíóþ èíòåðïðåòàöèþ. Îí ìîæåò àäðåñîâàòü ëþáóþ ÿ÷åéêó ïàìÿòè, íî íå ïîçâîëÿåò ïîëó÷èòü äîñòóï ê ëþáîìó îáúåêòó. Îí èìååò òèï

Pointer (â C - void*).

Òèïèçèðîâàííûé óêàçàòåëü âñåãäà îïðåäåëÿåòñÿ òàê, ÷òîáû óêàçûâàòü íà îáúåêò òîãî òèïà, ñ êîòîðûì îí ñâÿçàí. Òàêîé óêàçàòåëü ïîçâîëÿåò ïîëó÷èòü äîñòóï ê àòðèáóòàì îáúåêòà.

type myPointer = ^Integer; Ïðèìå÷àíèå: ññûëî÷íûé êîòîðûì îí ñâÿçàí.

1.3

òèï ìîæíî îïðåäåëèòü äî îïðåäåëåíèÿ òèïà, ñ

Äåéñòâèÿ íàä óêàçàòåëÿìè

Ïðèñâàèâàíèå èëè óñòàíîâêà óêàçàòåëÿ Ïðèñâàèâàíèå óêàçàòåëÿ äîëæíî áûòü ñîâìåñòèìûì. Ñîâìåñòèìû ïî ïðèñâàèâàíèþ:

1.

Òèïèçèðîâàííûå óêàçàòåëè îäíîãî è òîãî æå òèïà.

2.

Òèïèçèðîâàííûå óêàçàòåëè è êîíñòàíòû.

3.

Ñâîáîäíûå óêàçàòåëè è êîíñòàíòû.

2

4.

Òèïèçèðîâàííûå óêàçàòåëè ëþáîãî òèïà è ñâîáîäíûå óêàçàòåëè.

Èíèöèàëèçèðîâàòü óêàçàòåëü ìîæíî äâóìÿ ñïîñîáàìè:

1.

Êîíñòàíòîé

2.

Ïóòåì óñòàíîâêè óêàçàòåëÿ íà îáúåêò, àäðåñ êîòîðîãî çàðàíåå èçâåñòåí.

nil.

Ñðàâíåíèå óêàçàòåëåé Óêàçàòåëè ìîæíî ñðàâíèâàòü òîëüêî íà ðàâåíñòâî è íåðàâåíñòâî. Ðàâíûìè ñ÷èòàþòñÿ óêàçàòåëè, óêàçûâàþùèå íà îäèí è òîò æå îáúåêò è óêàçàòåëè, ðàâíûå

nil.

Ðàñêðûòèå ññûëêè (ðàçûìåíîâàíèå óêàçàòåëåé) Äîñòóï ê îáúåêòàì ÷åðåç òèïèçèðîâàííûé óêàçàòåëü îñóùåñòâëÿåòñÿ ñ èñïîëüçîâàíèåì åãî èìåíè è îïåðàòîðà

^.

Êëàññû ïàìÿòè

1.

Ñòàòè÷åñêàÿ

2.

Àâòîìàòè÷åñêàÿ

3.

Äèíàìè÷åñêàÿ

Ñòàòè÷åñêàÿ ïàìÿòü âûäåëÿåòñÿ íà ôàçå òðàíñëÿöèè è íàõîäèòñÿ â íàøåì âëàäåíèè âî âðåìÿ ðàáîòû ïðîãðàììû. Àâòîìàòè÷åñêàÿ âûäåëÿåòñÿ â îáëàñòè ñèñòåìíîãî ñòåêà è èñïîëüçóåòñÿ äëÿ ðàçìåùåíèÿ ôîðìàëüíûõ ïàð è ëîêàëüíûõ ïåðåìåííûõ ïðîöåäóð è ôóíêöèé. Äèíàìè÷åñêàÿ ïàìÿòü âûäåëÿåòñÿ è îñâîáîæäàåòñÿ ïî ÿâíîìó çàïðîñó èç ïðîãðàììó. Ñîîòâåòñòâåííî, âðåìÿ æèçíè îáúåêòà òîæå îïðåäåëÿåò ïðîãðàììèñò. Ðàáîòà ñ äèíàìè÷åñêîé ïàìÿòüþ Äèíàìè÷åñêàÿ ïàìÿòü ðàñïîëàãàåòñÿ â îáëàñòè êó÷è è åå ðàáîòîé çàïðàâëÿåò àäìèíèñòðàòîð êó÷è. Çàïðîñû íà âûäåëåíèå äèíàìè÷åñêîé ïàìÿòè:

procedure GetMem (var P:Pointer;size:integer); procedure New(var P:<òèïèçèðîâàííûé óêàçàòåëü>); Çàïðîñû íà îñâîáîæäåíèå ïàìÿòè: procedure FreeMem(var P:Pointer; size:integer); procedure Dispose(var P: <òèïèçèðîâàííûé óêàçàòåëü>); Îøèáêà ïðè ðàáîòå ñ äèíàìè÷åñêîé ïàìÿòüþ: 1.

Íàêîïëåíèå ìóñîðà

2.

Ìóñîðîì íàçûâàþò áëîêè ïàìÿòè, äîñòóï ê êîòîðûì âî âðåìÿ âûïîëíåíèÿ ïðîãðàììû óòåðÿí, òàê ÷òî èñïîëüçîâàíèå ýòèõ áëîêîâ è âîçâðàò ïàìÿòè â êó÷ó íåâîçìîæåí.

3

2

Ñïèñêè. Êëàññèôèêàöèÿ ñïèñêîâ.

Äèíàìè÷åñêîé ñòðóêòóðîé äàííûõ íàçûâàþò óïîðÿäî÷åííîå ìíîæåñòâî îáúåêòîâ, ñîñòàâ êîòîðûõ ìîæåò èçìåíÿòüñÿ âî âðåìÿ âûïîëíåíèÿ ïðîãðàììû. Îñíîâíûå îïåðàöèè

1.

Äîñòóï ê îáúåêòó

2.

Ìîäèôèêàöèÿ äèíàìè÷åñêîé ñòðóêòóðû

3.

Âûäåëåíèå ïîäìíîæåñòâà äèíàìè÷åñêèõ ñòðóêòóð ïî íåêîòîðîìó ïðèçíàêó

4.

Âûäåëåíèå ïîäìíîæåñòâà äèíàìè÷åñêèõ ñòðóêòóð â îïðåäåëåííîì ïîðÿäêå

Äîñòóï ê ýëåìåíòó ñòðóêòóðû îñóùåñòâëÿåòñÿ ñ ïîìîùüþ óêàçàòåëåé. Ëèíåéíî-äèíàìè÷åñêèå ñòðóêòóðû äàííûõ(ñïèñêè)

Ëèíåéíûé ñïèñîê ïðåäñòàâëÿåò ñîáîé ïîñëåäîâàòåëüíîñòü n ≥ 0 óçëîâ X[1],X[2],...,X[n], âàæíåéøåé ñòðóêòóðíîé îñîáåííîñòüþ êîòîðîé ÿâëÿåòñÿ òàêîå ðàñïîëîæåíèå ýëåìåíòîâ ñïèñêà îäíè îòíîñèòåëüíî äðóãîãî, êàê áóäòî îíè íàõîäÿòñÿ íà îäíîé ëèíèè. Èíà÷å ãîâîðÿ, â òàêîé ñòðóêòóðå äîëæíî ñîáëþäàòüñÿ óñëîâèå: åñëè

n > 0 è X[1] ÿâëÿåòñÿ ïåðâûì óçëîì, à X[n] - ïîñëåäíèì, òî k-é óçåë X[k] X[k − 1] è ïðåäøåñòâóåò X [k + 1] äëÿ âñåõ 1 < k < n. X[1] íàçûâàåòñÿ ãîëîâîé ñïèñêà. X[n] íàçûâàåòñÿ õâîñòîì ñïèñêà. Ñ ëèíåéíûìè ñïèñêàìè ìîãóò âûïîëíÿòüñÿ ñëåäóþùèå îïåðàöèè.

ñëåäóåò çà

1.

Ïîëó÷åíèå äîñòóïà ê k-ìó óçëó ñïèñêà äëÿ ïðîâåðêè èëè èçìåíåíèÿ åãî ïîëåé.

2.

Âñòàâêà íîâîãî óçëà ñðàçó ïîñëå èëè äî

k-ãî óçëà.

3.

Óäàëåíèå

4.

Îáúåäèíåíèå â îäíîì ñïèñêå äâóõ èëè áîëåå ëèíåéíûõ ñïèñêîâ.

5.

Ðàçáèåíèå íà äâà èëè áîëåå ëèíåéíûõ ñïèñêîâ.

6.

Ñîçäàíèå êîïèè ëèíåéíîãî ñïèñêà.

7.

Îïðåäåëåíèå êîëè÷åñòâà óçëîâ â ñïèñêå.

8.

Ñîðòèðîâêà óçëîâ â ïîðÿäêå âîçðàñòàíèÿ çíà÷åíèÿ â îïðåäåëåííûõ ïîëÿõ

k-ãî óçëà.

ýòèõ óçëîâ.

9.

Ïîèñê óçëà ñ çàäàííûì çíà÷åíèå â íåêîòîðîì ïîëå.

Êëàññèôèêàöèÿ ñïèñêîâ: Ïî ñïîñîáíîñòè äîáàâëÿòü ýëåìåíòû:

1.

Ñïèñîê ïðîèçâîëüíîãî âèäà: Âêëþ÷åíèå, èñêëþ÷åíèå è äîñòóï ìîæåò áûòü â ëþáîì ìåñòå ñïèñêà.

4

2.

Ñòåê Âêëþ÷åíèå â ãîëîâó, èñêëþ÷åíèå èç ãîëîâû.

3.

Î÷åðåäü Äîáàâëåíèå â õâîñò, âûõîä èç ãîëîâû.

4.

Äåêà Âêëþ÷åíèå â ãîëîâó\õâîñò, èñêëþ÷åíèå èç ãîëîâû\õâîñòà.

Ïî ÷èñëó ñâÿçåé ìåæäó îáúåêòàìè:

1.

Îäíîñâÿçíûå ñïèñêè

2.

Äâóñâÿçíûå ñïèñêè

3.

Ìíîãîñâÿçíûå ñïèñêè

Ó îäíîñâÿçíûõ ñïèñêîâ êàæäûé ýëåìåíò èìååò îäíî èëè áîëåå èíôîðìàöèîííûõ ïîëåé è åäèíñòâåííîå ïîëå ñâÿçè.  íåöèêëè÷åñêèõ ñïèñêàõ ïîëå ñâÿçè ïîñëåäíåãî ýëåìåíòà ðàâíî åñëè ñïèñîê íå ñóùåñòâóåò, òî åãî çíà÷åíèå òîæå

nil.

nil,

íî

Ó öèêëè÷åñêèõ ñïèñêîâ

ïîëå ñâÿçè ïîñëåäíåãî ýëåìåíòà óêàçûâàåò íà ãîëîâó. Ãîëîâîé öèêëè÷åñêîãî ñïèñêà ÿâëÿåòñÿ ñïåöèàëüíûé ýëåìåíò, èíôîðìàöèîííîå ïîëå êîòîðîãî íå èñïîëüçóåòñÿ.  îòëè÷èè îò íåöèêëè÷åñêèõ ñïèñêîâ, ñèòóàöèè ñïèñîê íå ñóùåñòâóåò è ñïèñîê ïóñò ðàçëè÷íû. Ïðåèìóùåñòâà öèêëè÷åñêèõ ñïèñêîâ:

1.

Âêëþ÷åíèå, èñêëþ÷åíèå ýëåìåíòà âûïîëíÿåòñÿ åäèíîîáðàçíî, ò.ê. êàæäûé ýëåìåíò èìååò óêàçàòåëü íà ïðåäûäóùèé è íà ñëåäóþùèé ýëåìåíò.

2.

Îò ëþáîãî ýëåìåíòà ìîæíî äîñòè÷ü ëþáîãî ýëåìåíòà.

3.

Ïðè ïîèñêå íåîáõîäèìî ïðîâåðÿòü óñëîâèå îäíîêðàòíîãî ïðîõîæäåíèÿ ñïèñêà.

Äâóñâÿçíûå ñïèñêè Êàæäûé ýëåìåíò äâóñâÿçíîãî ñïèñêà ñîäåðæèò óêàçàòåëü íà ñëåäóþùèé è ïðåäûäóùèé ýëåìåíòû. Äâóñâÿçíûå öèêëè÷åñêèé ñïèñêè èñïîëüçóþò äîïîëíèòåëüíûé ãîëîâíîé ýëåìåíò. Îñîáåííîñòüþ äâóñâÿçíîãî öèêëè÷åñêîãî ñïèñêà ÿâëÿåòñÿ òî, ÷òî äëÿ ëþáîãî ýëåìåíòà

p:

pˆ.nextˆ.prev = p pˆ.prevˆ.next = p Îðòîãîíàëüíûå ñïèñêè

-

ñïèñêè, êàæäûé ýëåìåíò êîòîðûõ ìîæåò áûòü

âêëþ÷åí îäíîâðåìåííî â íåñêîëüêî ñïèñêîâ. Òàêîé ñïèñîê ïîçâîëÿåò óïîðÿäî÷èòü ñïèñêè ïî ðàçëè÷íûì òðåáîâàíèÿì, ò.å. îðãàíèçîâàòü ðàçëè÷íûå îòíîøåíèÿ ïðåäøåñòâîâàíèÿ. Îíè ìîãóò áûòü îäíîñâÿçíûìè, äâóñâÿçíûìè è öèêëè÷åñêèìè. Ðàçíîðîäíûå ñïèñêè - ñïèñêè, ó êîòîðûõ èíôîðìàöèîííûå ïîëÿ ýëåìåíòîâ ìîãóò áûòü ðàçíûõ òèïîâ äàííûõ.

5

3

Ðåêóðñèÿ. Ðåêóðñèâíûå ïðîöåäóðû. Ñõåìû ðåêóðñèâíîé ïðîöåäóðû.

Ðåêóðñèåé íàçûâàåòñÿ ìåòîä îïðåäåëåíèÿ ìíîæåñòâà èëè ïðîöåññà â òåðìèíàõ ñàìîãî ñåáÿ. Ðåêóðñèâíîå îïðåäåëåíèå ñîäåðæèò äâå ÷àñòè:

1. 2.

Áàçèñíàÿ ÷àñòü, êîòîðàÿ äàåò îïðåäåëåíèå ôèêñèðîâàííîé ãðóïïå îáúåêòîâ. Ðåêóðñèâíàÿ ÷àñòü. Çàïèñûâàåòñÿ òàêèì îáðàçîì, ÷òîáû ïðè öåïî÷êå ïîâòîðíûõ ïðèìåíåíèé îíà ñâîäèëàñü ê áàçèñíîé ÷àñòè.

Èòåðàòèâíàÿ ñõåìà îðãàíèçàöèè âû÷èñëèòåëüíûõ ïðîöåññîâ ðåàëèçóåòñÿ ÷åðåç èòåðàòèâíî âû÷èñëèìûé öèêë

(while).

Âèäû ðåêóðñèâíûõ àëãîðèòìîâ. Íå âñåãäà ðåêóðñèÿ ìîæåò áûòü çàìåíåíà èòåðàöèåé. Ðåêóðñèâíàÿ ïðîöåäóðà

- ïðîöåäóðà, êîòîðàÿ îáðàùàåòñÿ ñàìà ê ñåáå.

Ðåêóðñèþ íàçûâàþò ÿâíîé èëè ïðÿìîé, åñëè ïîäïðîöåäóðà íåïîñðåäñòâåííî ñîäåðæèò îáðàùåíèå ê ýòîé ïðîöåäóðå. Íåÿâíîé, åñëè â ïðîöåññå âûïîëíåíèÿ ïðîöåäóðà îáðàùàåòñÿ ê äðóãîé ïðîöåäóðå, êîòîðàÿ ÷åðåç öåïî÷êó âûçîâîâ îáðàùàåòñÿ ê èñõîäíîé ïðîöåäóðå. Êàæäûé âûçîâ ðåêóðñèâíîé ïðîöåäóðû ÿâëÿåòñÿ íåçàâèñèìîé àêòèâàöèåé, òàê êàê ê ðåêóðñèâíîé ïðîöåäóðå ìîæíî îáðàùàòüñÿ êàê èç ñàìîé ïðîöåäóðû, òàê è èçâíå. Äëÿ îáåñïå÷åíèÿ ïðàâèëüíîñòè íåîáõîäèìî, ÷òîáû âîçâðàò èç íåå ïðîèçâîäèëñÿ â ïîäëåæàùåå ìåñòî âñëåä çà îïåðàòîðîì âûçîâà. Ñîâîêóïíîñòü ôîðìàëüíûõ ïàðàìåòðîâ ëîêàëüíûõ ïåðåìåííûõ îäíîçíà÷íî õàðàêòåðèçóåò àêòèâàöèþ ïðîöåäóðû è íàçûâàåòñÿ ôðåéìîì àêòèâàöèè è âîññòàíîâëåíèÿ. Äëÿ õðàíåíèÿ ôðåéìîâ àêòèâàöèè èñïîëüçóþò ñèñòåìíûé ñòåê. Ñõåìà ðåêóðñèâíîé ïðîöåäóðû.

6



   


  

 



    

 

7





  !   



 õîäå ðåøåíèÿ î çàâåðøåíèè îïðåäåëÿåòñÿ, ÿâëÿåòñÿ ëè âõîäíûå ïàðàìåòðû òàêèìè, ÷òî äëÿ òàêèõ äàííûõ âîçìîæíî âû÷èñëåíèå âûõîäíûõ ïàðàìåòðîâ â ñîîòâåòñòâèè ñ áàçèñíîé ÷àñòüþ âõîäíûõ ïàðàìåòðîâ.  òåáå ðåêóðñèâíî âû÷èñëèìîãî öèêëà îáÿçàòåëüíî äîëæíû èçìåíÿòüñÿ çíà÷åíèÿ ïåðåìåííûõ, îò êîòîðûõ çàâèñèò çàâåðøåíèå öèêëà. Ïåðâîå îáðàùåíèå ê ðåêóðñèè â ïðîãðàììå àññîöèèðóåòñÿ ñ íîìåðîì

1,

êàæäûé ïîñëåäóþùèé âûçîâ óâåëè÷èâàåò ÷èñëî íà îäèí. Äðóãîé õàðàêòåðèñòèêîé ÿâëÿåòñÿ ãëóáèíà ðåêóðñèè. Ãëóáèíà ðåêóðñèè ÷èñëî ðåêóðñèâíûõ îáðàùåíèé äëÿ âû÷èñëåíèé, íåîáõîäèìûõ ïðè çàäàííûõ àðãóìåíòàõ. Ðåêóðñèâíî ìîæíî îïðåäåëèòü ñëåäóþùèå ñòðóêòóðû äàííûõ: Ñïèñîê èç

n ýëåìåíòîâ.

Íàáîðû. Íàáîð - îðòîãîíàëüíàÿ ñòðóêòóðà èåðàðõè÷åñêè îïðåäåëåííàÿ â èåðàðõè÷åñêîì ñïèñêå, ñîñòîèò èç ýëåìåíòîâ äâóõ òèïîâ:

1.

Àòîì, ñîäåðæàùèé ýëåìåíòàðíóþ ïîðöèþ èíôîðìàöèè.

2.

Íàáîð

3.

Ñòðóêòóðû äëÿ õðàíåíèÿ àðèôìåòè÷åñêèõ âûðàæåíèé.

- ðàçíîðîäíûé ñïèñîê.

 äàííîì ñëó÷àå ðåêóðñèÿ îçíà÷àåò âîçìîæíîñòü âëîæåííîñòè, ò.å. èñïîëüçîâàíèÿ â ê êà÷åñòâå àðãóìåíòà ïîäâûðàæåíèå.

4

Äåðåâüÿ. Îñíîâíûå îïðåäåëåíèÿ. Áèíàðíîå äåðåâî. Àëãîðèòì îáõîäà.

Äåðåâî îáùåãî âèäà - ìíîæåñòâî îáúåêòîâ ñîñòîÿùèõ èç îäíîãî èëè íåñêîëüêèõ óçëîâ, äëÿ êîòîðûõ âûïîëíÿåòñÿ ñëåäóþùåå óñëîâèå:

1. 2.

Èìååòñÿ îäèí ñïåöèàëüíî âûäåëåííûé óçåë, íàçûâàåìûé êîðíåì äåðåâà. Âñå îñòàëüíûå óçëû ðàçáèòû íà íå ïåðåñåêàþùèåñÿ ïîäìíîæåñòâà T1 , T2 , ..., Tn , êàæäîå èç êîòîðûõ ÿâëÿåòñÿ äåðåâîì.

3.

Äåðåâüÿ T1 , T2 , .., Tn - ïîääåðåâüÿ äàííîãî êîðíÿ.

Ñòåïåíüþ óçëà íàçûâàåòñÿ ÷èñëî ïîääåðåâüåâ äàííîãî óçëà. Êîíöåâûì óçëîì (ëèñòîì) äåðåâà íàçûâàåòñÿ óçåë íóëåâîé ñòåïåíè. Óðîâíåì óçëà íàçûâàåòñÿ äëèíà ïóòè âåäóùåãî èç äàííîãî óçëà â êîðåíü äåðåâà. Íåëèíåéíûå ñòðóêòóðû äàííûõ, ê êîòîðûì îòíîñÿò äåðåâüÿ, âûðàæàþòñÿ áîëåå ñëîæíûì îòíîøåíèå ïîðÿäêà, ÷åì ïðåäøåñòâîâàíèå è ñëåäîâàíèå. Èñïîëüçóåòñÿ ïîíÿòèå ïðåäîê è ïîòîìîê. Ñâîéñòâà äåðåâüåâ îáùåãî âèäà:

1.

Êîðåíü äåðåâà íå èìååò ïðåäêîâ.

8

2.

Êàæäûé óçåë, êðîìå êîðíÿ, èìååò îäíîãî ïðåäêà.

3.

Êàæäûé óçåë êðîìå êîðíÿ ñâÿçàí ñ êîðíåì åäèíñòâåííûì ïóòåì. Äåðåâî íàçûâàåòñÿ óïîðÿäî÷åííûì, åñëè äëÿ åãî óçëîâ âàæåí ïîðÿäîê

4.

ñëåäîâàíèÿ ïîääåðåâüåâ. Áèíàðíûì äåðåâîì íàçûâàåòñÿ óïîðÿäî÷åííîå äåðåâî âòîðîé ñòåïåíè. Áèíàðíîå äåðåâî

-

êîíå÷íîå ìíîæåñòâî óçëîâ, êîòîðîå ëèáî ïóñòî, ëèáî

ñîñòîèò èç êîðíÿ è äâóõ íåïåðåñåêàþùèõñÿ áèíàðíûõ äåðåâüåâ, êîòîðûå íàçûâàþòñÿ ëåâûì è ïðàâûì ïîääåðåâüÿìè. Äåðåâüÿ ïðîèçâîëüíîãî âèäà ìîæíî ïðåîáðàçîâàòü â äåðåâüÿ áèíàðíîãî âèäà. Óçëû äåðåâà ñîñòîÿò èç îäíîãî èëè íåñêîëüêèõ ïîëåé è äâóõ ïîëåé ñâÿçè, óêàçûâàþùèõ íà ëåâîå è ïðàâîå ïîääåðåâî. Õðàíåíèå äåðåâüåâ ñ ïîñëåäîâàòåëüíîé îðãàíèçàöèåé ïàìÿòè. Åñëè ðàçìåð äåðåâà èçâåñòåí çàðàíåå, òîãäà êîðåíü äåðåâà õðàíèòñÿ â ÿ÷åéêå ñ íîìåðîì 1 è äëÿ ëþáîãî óçëà, íàõîäÿùåãîñÿ â ÿ÷åéêå i, ëåâûé ïîòîìîê õðàíèòñÿ â ÿ÷åéêå

2i, à ïðàâûé ïîòîìîê â ÿ÷åéêå 2i + 1. - ïðîñòîòà äîñòóïà ê ïðåäêàì è ïîòîìêàì. Îáõîä äåðåâà - ñàìàÿ ðàñïðîñòðàíåííàÿ îïåðàöèÿ, âûïîëíÿåìàÿ íàä äåðåâüÿìè. Ïðè îáõîäå êàæäàÿ âåðøèíà äåðåâà îáðàáàòûâàåòñÿ ðîâíî îäèí ðàç. Ïîëíûé îáõîä äåðåâà ïîðîæäàåò ëèíåéíóþ ïîñëåäîâàòåëüíîñòü óçëîâ äåðåâà. Ïîðÿäîê îáõîäà çàäàåòñÿ àëãîðèòìîì îáõîäà. Íàèáîëåå ðàñïðîñòðàíåííûå àëãîðèòìû îáõîäà: Ïðåèìóùåñòâî

5

1.

Íèñõîäÿùèé (ïðÿìîé): êîðåíü, ëåâî, ïðàâî.

2.

Âîñõîäÿùèé (êîíöåâîé): ëåâî, ïðàâî, êîðåíü.

3.

Ñìåøàííûé (îáðàòíûé)

:

ëåâî, êîðåíü, ïðàâî.

Ñáàëàíñèðîâàííûå äåðåâüÿ. Äèõîòîìè÷åñêèå äåðåâüÿ. Àëãîðèòì ïîñòðîåíèÿ. ÀÂË

- äåðåâüÿ.

Ñáàëàíñèðîâàííûì äåðåâîì íàçûâàþò áèíàðíîå äåðåâî, ó êîòîðîãî êîëè÷åñòâî óçëîâ â ëåâîì è ïðàâîì ïîääåðåâî îòëè÷àåòñÿ íå áîëåå ÷åì íà

1.

Òàêîå äåðåâî èìååò ìèíèìàëüíóþ âûñîòó èç âñåõ äåðåâüåâ èç Âûñîòà ñáàëàíñèðîâàííîãî äåðåâà

Àëãîðèòì ïîñòðîåíèÿ ñáàëàíñèðîâàííîãî äåðåâà èç Åñëè

n óçëîâ.

[log2 n] + 1 n óçëîâ

n > 0:

Áåðåì ïåðâûé ýëåìåíò â êà÷åñòâå êîðíÿ äåðåâà. Ñòðîèì ëåâîå ïîääåðåâî äëÿ äàííîãî êîðíÿ ñ ÷èñëîì óçëîâ nl äàííîìó àëãîðèòìó. Ñòðîèì ïðàâîå ïîääåðåâî ñ ÷èñëîì óçëîâ nr Äèõîòîìè÷åñêèå äåðåâüÿ (äåðåâüÿ ïîèñêà):

9

= n − n div 2 − 1

= n div 2 ïî

Ïðè ïîñòðîåíèè äèõîòîìè÷åñêèõ äåðåâüåâ íà âñå ìíîæåñòâî ýëåìåíòîâ çàäàþò îòíîøåíèå äèõîòîìèè, çàêëþ÷àþùååñÿ â ïîýòàïíîì ðàçáèåíèè ìíîæåñòâà ýëåìåíòîâ íà äâà íå ïåðåñåêàþùèõñÿ ïîäìíîæåñòâà ïî çíà÷åíèþ èíôîðìàöèîííîãî ïîëÿ(íàçûâàåìîãî êëþ÷åâûì ïîëåì). Äåðåâîì ïîèñêà áóäåì íàçûâàòü áèíàðíîå äåðåâî, ïîñòðîåííîå òàêèì îáðàçîì, ÷òî äëÿ ëþáîãî óçëà äåðåâà, èìåþùåãî çíà÷åíèå êëþ÷åâîãî ïîëÿ = T1 âûïîëíÿåòñÿ:

1.

Êëþ÷åâûå ïîëÿ âñåõ ýëåìåíòîâ ëåâîãî ïîääåðåâà

2.

Êëþ÷åâûå ïîëÿ âñåõ ýëåìåíòîâ ïðàâîãî ïîääåðåâà

< T1 > T1

Ïîèñê â äèõîòîìè÷åñêîì äåðåâüåâ çàêëþ÷àåòñÿ â ïîñëåäîâàòåëüíîì ñðàâíåíèè ñ êëþ÷îì òåêóùåãî óçëà è ïåðåõîäîì ê ëåâîìó èëè ïðàâîìó ïîääåðåâó â çàâèñèìîñòè îò ðåçóëüòàòîâ ñðàâíåíèÿ. Ïîèñê íà÷èíàåòñÿ â êîðíå è êîí÷àåòñÿ â íóæíîì ýëåìåíòå ëèáî â

nil.

Ïîèñê â íåñáàëàíñèðîâàííîì äèõîòîìè÷åñêîì äåðåâå âûïîëíÿåòñÿ íå áîëåå, ÷åì çà âûñîòó äåðåâà. Ïðè ïîñòðîåíèè ñáàëàíñèðîâàííûõ äåðåâüåâ ïîèñêà òðåáîâàíèå ê ñáàëàíñèðîâàííîñòè ñíèæàþò. È ñ÷èòàþò ñáàëàíñèðîâàííûì äåðåâî, ó êîòîðîãî âûñîòà ëåâîãî è ïðàâîãî ïîääåðåâà îòëè÷àåòñÿ íå áîëåå, ÷åì íà åäèíèöó. ÀÂË-äåðåâî

-

ñáàëàíñèðîâàííîå ïî ñûñîòå äâîè÷íîå äåðåâî ïîèñêà: äëÿ

êàæäîé åãî âåðøèíû âûñîòà åå äâóõ ïîääåðåâüåâ ðàçëè÷àåòñÿ íå áîëåå ÷åì íà

1. ÀÂË-äåðåâüÿ íàçâàíû ïî ïåðâûì áóêâàì ôàìèëèé èõ èçîáðåòàòåëåé, Ã.Ì.

Àäåëüñîíà-Âåëüñêîãî è Å.Ì. Ëàíäèñà, êîòîðûå âïåðâûå ïðåäëîæèëè èñïîëüçîâàòü ýòó ñòðóêòóðó äàííûõ â

6

1962 ãîäó.

ßçûê. Àëôàâèò. Öåïî÷êà. Ãðàììàòèêè ÿçûêà. Êëàññèôèêàöèÿ ãðàììàòèê ïî Õîëìñêîìó.

Àëôàâèò

- êîíå÷íîå íå ïóñòîå ìíîæåñòâî ñèìâîëîâ, èñïîëüçóåìûõ â ÿçûêå. A={0, 1} A={1..9, +, −, ∗, /, 0} A={a..z} A={0 A0 ..0 Z 0 ,0 a0 ..0 z0 } Àëôàâèò áóäåì îáîçíà÷àòü áîëüøèìè áóêâàìè, à èñïîëüçóåìûå ñèìâîëû - ìàëûìè áóêâàìè. Öåïî÷êîé áóäåì íàçûâàòü ëþáóþ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ â àëôàâèòå. Îáîçíà÷àòü èõ áóäåì ãðå÷åñêèìè áóêâàìè. Îòäåëüíî îáîçíà÷èì ïóñòóþ öåïî÷êó è íàçîâåì åå Äëèíó öåïî÷êè, îáîçíà÷àåìóþ

|a|,

ε.

áóäåì íàçûâàòü êîëè÷åñòâî ñèìâîëîâ

â öåïî÷êå. ßçûêîì

A.

L

â àëôàâèòå

A

áóäåì íàçûâàòü ìíîæåñòâî öåïî÷åê â àëôàâèòå

A∗ - ìíîæåñòâî âñåõ öåïî÷åê â ýòîì àëôàâèòå.

10

Îïèñàòü ÿçûê ïóòåì ïåðå÷èñëåíèÿ âñåõ åãî öåïî÷åê âîçìîæíî òîëüêî êîãäà ìíîæåñòâî öåïî÷åê êîíå÷íî.  áîëüøèíñòâå æå ñëó÷àåâ ìíîæåñòâî íå ÿâëÿåòñÿ êîíå÷íûì èëè íåæåëàòåëüíî çàäàâàòü ìàêñèìàëüíîå ÷èñëî öåïî÷åê. Ïîýòîìó ÷òîáû îïèñàíèå ÿçûêà áûëî êîíå÷íûì èñïîëüçóþò äðóãèå ìåòîäû îïèñàíèÿ ÿçûêà, ïîçâîëÿþùèå îïèñûâàòü áåñêîíå÷íûå ÿçûêè êîíå÷íûìè ñðåäñòâàìè. Îäíèì èç òàêèõ ñïîñîáîâ ÿâëÿåòñÿ èñïîëüçîâàíèå ãðàììàòèêè èëè ïîðîæäàþùåé ñèñòåìû. Ãðàììàòèêîé

G áóäåì íàçûâàòü ÷åòâåðêó îáúåêòîâ: G = hS,Vn ,VT , Ri,ãäå: Vn -ìíîæåñòâî íå òåðìèíàëüíûõ ñèìâîëîâ ãðàììàòèêè. VT -ìíîæåñòâî òåðìèíàëüíûõ ñèìâîëîâ ãðàììàòèêè. R-ìíîæåñòâî ïðàâèë ãðàììàòèêè. Ìíîæåñòâî VT ñîâïàäàåò ñ ìíîæåñòâîì ñèìâîëîâ àëôàâèòà. VN -ìíîæåñòâî ñèìâîëîâ, ó÷àñòâóþùèõ â ïîðîæäåíèè öåïî÷åê ÿâíî, íî íå ó÷àñòâóþùèõ â îïèñàíèè ÿçûêà. Ñèìâîë S - ñèìâîë ñ êîòîðîãî íà÷èíàåòñÿ ïîðîæäåíèå öåïî÷êè ÿçûêà, S ∈ VN . Ìíîæåñòâî R îáû÷íî çàïèñûâàåò ñëåäóþùèì îáðàçîì. S→0 S→1 S → 0A S → 1A A → 1A A → 0A A→ε Çàïèñü â ïðàâèëüíîé ôîðìå, ïðèâåäåííîé âûøå, íå âñåãäà óäîáíà, ïîýòîìó ÷àñòî ââîäÿò ñëåäóþùèå ñèìâîëû: 0 |0 -àëüòåðíàòèâà. S → 0|1|0A|1A 0 [0 ,0 ]0 -ôàêóëüòàòèâíûé ýëåìåíò S → 0[A]|1[A] 0 {0 ,0 }0 -ìíîæåñòâî ýëåìåíòîâ - ýëåìåíòû âûáîðà ...{0|1|2}... Ýòè îáîçíà÷åíèÿ áûëè ââåäåíû Áýêóñîì è Íàóðîì äëÿ îïèñàíèÿ Àëãîë60. Íîòàöèÿ ñ èñïîëüçîâàíèå ýòèõ ýëåìåíòîâ íîñèò íàçâàíèå íîòàöèè ÁýêóñàÍàóðà. Ñ èñïîëüçîâàíèå ãðàììàòèêè ïðåäïîëàãàåòñÿ ïîðîæäåíèå öåïî÷åê, äëÿ ÷åãî çàïèñûâàåòñÿ íà÷àëüíûé ñèìâîë ãðàììàòèêè, çàòåì íà÷àëüíûé ñèìâîë ãðàììàòèêè çàìåíÿåòñÿ íà öåïî÷êó ñèìâîëîâ â ñîîòâåòñòâèè ñ ëþáûì ïðàâèëîì ãðàììàòèêè â ëåâîé ÷àñòè êîòîðîãî íàõîäèòñÿ íîðìàëüíûé ñèìâîë. Ïðîöåññ áóäåò ïðîäîëæàòüñÿ äî òåõ ïîð, ïîêà íå áóäåò ïîëó÷åíà öåïî÷êà, ñîñòîÿùàÿ òîëüêî èç òåðìèíàëüíûõ ñèìâîëîâ. Ïðè ïîðîæäåíèè èñïîëüçóþò ñëåäóþùèå îáîçíà÷åíèÿ.

⇒- ïîðîæäàåò, íåïîñðåäñòâåííî ïîðîæäàåò. 11

⇒+ -ïîðîæäàåò çà îäèí èëè áîëåå øàãîâ. (α ⇒∗ β ) ⇔ (α ⇒+ β ) ∨ (α = β ) Åñëè â ãðàììàòèêå èìååòñÿ ïðàâèëî u → ...u...,òî îíà íàçûâàåòñÿ ðåêóðñèâíîé, ïðè ýòîì ãðàììàòèêà âèäà u → u... íàçûâàåòñÿ ëåâîðåêóðñèâíîé, à âèäà u → ...u-ïðàâî-ðåêóðñèâíîé. Ñëåäóåò îòìåòèòü, ÷òî ãðàììàòèêà, ïîðîæäàþùàÿ áåñêîíå÷íûé ÿçûê äîëæíà áûòü ðåêóðñèâíîé. Ñåíòåíöèàëüíîé ôîðìîé áóäåì íàçûâàòü öåïî÷êó, âûâîäèìóþ èç íà÷àëüíîãî ñèìâîëà ãðàììàòèêè. Êëàññèôèêàöèÿ ãðàììàòèê ïî Õîëìñêîìó. Ãðàììàòèêà òèïà 3- àâòîìàòíàÿ ãðàììàòèêà. Ýòî ãðàììàòèêà, âñå ïðàâèëà êîòîðîé èìåþò âèä A → aB A → a, ãäå A, B ∈ VN , a ∈ VT . Ïðàâèëà âèäà A → a-çàêëþ÷èòåëüíûå(òåðìèíàëüíûå) ïðàâèëà. Ïðèìå÷àíèå: â íåêîòîðûõ êíèãàõ âñòðå÷àåòñÿ ïðàâèëî àâòîìàòíîé ãðàììàòèêè â âèäå: A → Ba. Òèï 2 - áåñêîíòåêñòíàÿ, êîíòåêñòíî-ñâîáîäíàÿ ãðàììàòèêà, ÊÑ - ãðàììàòèêà. Ïðàâèëà èìåþò âèä

∪

A → α , A ∈ VN , α ∈ (VT Vn )∗ Òèï 1 - êîíòåêñòíî-çàâèñèìàÿ ãðàììàòèêà, ÊÇ - ãðàììàòèêà ϕ Aψ → ϕγψ A ∈ VN ∪ ϕ , ψ ∈ (V V )∗ ∪N ∗ T γ ∈ (VN VT ) Òèï 0 - ðåêóðñèâíî - ïåðå÷èñëèìàÿ ãðàììàòèêà α →β α , β -ëþáûå. Âñå ÿçûêè òèïà I ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì ÿçûêîâ I −1, çà èñêëþ÷åíèåì ÿçûêîâ, ïîðîæäåííîé ÊÑ - ãðàììàòèêîé. ßçûê ïîðîæäåííûé ãðàììàòèêîé òèïà i áóäåì íàçûâàòü ÿçûêîì òèïà i. ßçûêè òèïà 0 î÷åíü ñëîæíû äëÿ àíàëèçà è äëÿ íèõ íå ñóùåñòâóåò àëãîðèòìîâ, ïîçâîëÿþùèõ îïðåäåëèòü ïðèíàäëåæíîñòü öåïî÷êè ÿçûêó çà êîíå÷íîå ÷èñëî øàãîâ. â ñâÿçè ñ ýòèì ðàññìàòðèâàòü òàêèå ÿçûêè ìû íå áóäåì. Âñå îñòàëüíûå ÿçûêè, êîòîðûå áóäåì íàçûâàòü êîíòåêñòíûìè, ðàçðåøèìû, ò.å. äëÿ íèõ ñóùåñòâóþò àëãîðèòìû, îïðåäåëÿþùèå ïðèíàäëåæíîñòü ÿçûêó çà êîíå÷íîå ÷èñëî øàãîâ. Ñóùåñòâóåò òåîðåìà, ãëàñÿùàÿ: Âñå êîíòåêñòíûå ÿçûêè ðàçðåøèìû. Òåõíèêà ïîñòðîåíèÿ àâòîìàòíûõ è êîíòåêñòíî ñâîáîäíûõ ãðàììàòèê. Çàäà÷à: îïèñàòü ÿçûê â âèäå ãðàììàòèêè.

Çàäàíû öåïî÷êè ÿçûêîâ è

òðåáóåòñÿ íàïèñàòü ýòè öåïî÷êè ñ ïîìîùüþ ïîðîæäàþùåé ãðàììàòèêè.

12

Äëÿ ïîñòðîåíèÿ ãðàììàòèêè ðàçáèâàåì öåïî÷êó íà íå òåðìèíàëüíûå

1.

ñèìâîëû. Íîâûå êîìïîíåíòû ðàçáèâàåì íà ïîäêîìïîíåíòû è ò.ä. ïîêà íå äîéäåì

2.

äî òåðìèíàëüíûõ ñèìâîëîâ. Ïðè ïîñòðîåíèè àâòîìàòíîé ãðàììàòèêè ðàññìîòðèì âñå èñõîäÿùèå öåïî÷êè, âûïèñûâàÿ âñå òåðìèíàëüíûå ñèìâîëû, êîòîðûå ìîæíî âñòðåòèòü íà äàííîé öåïî÷êå è ââåäåì íåòåðìèíàëüíûå ñèìâîëû, îáîçíà÷àþùèå êîíåö öåïî÷êè. Çàïèñü âûâîäà â âèäå öåïî÷êè íå î÷åíü íàãëÿäíà, òàê ÷òî åé ñëåäóåò ïðåäïî÷åñòü çàïèñü â âèäå äåðåâà. Âûâåäåííàÿ öåïî÷êà ìîæåò áûòü ïîëó÷åíà ïóòåì ëåâîãî îáõîäà äåðåâà. Ñëåäóåò îòìåòèòü, ÷òî ó äåðåâà âûâîäà íå îïðåäåëåí òî÷íûé ïîðÿäîê âûâîäà. Âûâîäû, êîòîðûì ñîîòâåòñòâóåò îäíî è òî æå äåðåâî âûâîäà áóäåì ñ÷èòàòü ýêâèâàëåíòíûìè. Öåïî÷êà, äëÿ êîòîðîé ñóùåñòâóåò áîëåå îäíîãî äåðåâà âûâîäà íàçûâàåòñÿ íåîäíîçíà÷íîé. Ãðàììàòèêà íàçûâàåòñÿ íåîäíîçíà÷íîé, åñëè â íåé âîçìîæíî ïîðîæäåíèå íåîäíîçíà÷íîé öåïî÷êè.

7

Ïðåäñòàâëåíèå àâòîìàòíîé ãðàììàòèêè â âèäå ãðàôîâ. Äåòåðìèíèðîâàííûå ôîðìû. Àëãîðèòì ïîñòðîåíèÿ àíàëèçàòîðà.

Ãðàììàòèêó óäîáíî ïðåäñòàâëÿòü â âèäå ãðàôîâ. Âåðøèíà ãðàôà ñîñòîÿíèÿ ñîîòâåòñòâóåò íåòåðìèíàëüíûì ñèìâîëàì ãðàììàòèêè. Èç âåðøèíû A ïðîâîäèòñÿ äóãà â B åñëè â èñõîäíîé ãðàììàòèêå åñòü ïðàâèëî âèäà

A → aB.

Ãðàììàòèêó

ìîäèôèöèðóþò, äîáàâëÿÿ ê èñõîäíîé ãðàììàòèêè íåêîòîðûå ïðàâèëà.

VN

∪

{F} è çàìåíÿÿ âñå ïðàâèëà âèäà A → a íà A → aF.

0

VN =

Äåòåðìèíèðîâàííàÿ, íåäåòåðìèíèðîâàííàÿ è âïîëíå äåòåðìèíèðîâàííàÿ ãðàììàòèêà. Ãðàììàòèêà a íàçûâàåòñÿ äåòåðìèíèðîâàííîé åñëè äëÿ ëþáîãî òåðìèíàëà A ñóùåñòâóåò íå áîëåå îäíîãî ïðàâèëà A → aB.  ïðîòèâíîì ñëó÷àå àâòîìàòíàÿ ãðàììàòèêà íàçûâàåòñÿ íåäåòåðìèíèðîâàííîé. Ãðàììàòèêà íåòåðìèíàëà

A → aB. Òåîðåìà:

A

A

íàçûâàåòñÿ âïîëíå äåòåðìèíèðîâàííîé, åñëè äëÿ ëþáîãî

è äëÿ ëþáîãî òåðìèíàëà

a

ñóùåñòâóåò ðîâíî îäíî ïðàâèëî

âèäà

Äëÿ ëþáîé ãðàììàòèêè ñóùåñòâóåò ýêâèâàëåíòíàÿ äåòåðìèíèðîâàííàÿ ãðàììàòèêà. Àëãîðèòì íàõîæäåíèÿ äåòåðìèíèðîâàííîé ãðàììàòèêè. Íà ïðàêòèêå ïðè àíàëèçå öåïî÷åê ÷àñòî ââîäÿò òåðìèíàëüíûé (çàêëþ÷èòåëüíûé) ñèìâîë. Ïðè ýòîì çàêëþ÷èòåëüíóþ âåðøèíó F çàìåíÿþò íà çàêëþ÷èòåëüíóþ âåðøèíó

0

F.

13

Òàêæå äëÿ ïðèâåäåíèÿ ãðàììàòèêè îò äåòåðìèíèðîâàííîé êî âïîëíå äåòåðìèíèðîâàííîé

ε . Äàëåå äëÿ âñåõ A → aε .

ôîðìå ÷àñòî ââîäÿò îøèáî÷íóþ âåðøèíó è îáîçíà÷àþò åå íåòåðìèíàëüíûõ ñèìâîëîâ ñòðîÿò äëÿ ëþáûõ À ïåðåõîä Ñèíòàêñè÷åñêèé àíàëèç àâòîìàòíûõ ÿçûêîâ.

Ñõåìà àëãîðèòìà è ïðîãðàììà, àíàëèçèðóþùàÿ ïðèíàäëåæíîñòü öåïî÷êè a ê ñîîòâåòñòâóþùåìó ÿçûêó ñòðîèòñÿ ïî ñîîòâåòñòâóþùèì àâòîìàòàì. Êàæäàÿ âåðøèíà ãðàôà êðîìå çàêëþ÷èòåëüíîé è îøèáî÷íîé ñîîòâåòñòâóåò âûáîðó öåïî÷êè. Êàæäîìó ðåáðó ãðàôà ñîîòâåòñòâóåò áëîê àíàëèçà ñèìâîëà ñ ïîñëåäóþùèì ïåðåõîäîì â ñëåäóþùóþ âåðøèíó. Àëãîðèòì ïîñòðîåíèÿ.

1.

ñîñòàâëÿåòñÿ àâòîìàòíàÿ ãðàììàòèêà.

2.

Åñëè ãðàììàòèêà íå äåòåðìèíèðîâàííàÿ, òî ïðèâåñòè ê äåòåðìèíèðîâàííîé ôîðìå.

3.

Ïî ïîëó÷åííîé ãðàììàòèêå ñòðîèòñÿ ãðàô ñîñòîÿíèé.

4.

Ïî ïîëó÷åííîìó ãðàôó ïèøåòñÿ ïðîãðàììà.

5.

Îñóùåñòâëÿåòñÿ äîáàâëåíèå â ïðîãðàììó ñåìàíòè÷åñêèõ ïðîöåäóð.

8

Ðàñïîçíàâàòåëü - îñíîâíûå ïîíÿòèÿ è àëãîðèòì ðàáîòû.

Åùå îäèí ñïîñîá çàäàíèÿ ÿçûêîâ - èñïîëüçîâàíèå ðàñïîçíàâàòåëÿ èëè àâòîìàòà. Îí ñîñòîèò èç ÷åòûðåõ ÷àñòåé.

1.

Âõîäíàÿ ëåíòà

2.

Ãîëîâêà ÷òåíèÿ

3.

Óñòðîéñòâî óïðàâëåíèÿ

4.

Âíåøíÿÿ ïàìÿòü

Âõîäíàÿ ëåíòà

-

ëèíåéíàÿ ïîñëåäîâàòåëüíîñòü ÿ÷ååê, ñîäåðæàùàÿ ñèìâîëû

àëôàâèòà. Íà ïðàâîì èëè ëåâîì êðàþ ìîãóò ñòîÿòü îñîáûå ñèìâîëû. Ìîæåò ñäâèãàòüñÿ çà

1 øàã âïðàâî\âëåâî\íèêóäà.

Ðàñïîçíàâàòåëü, êîòîðûé íèêîãäà íå ïåðåäâèãàåò ãîëîâêó âëåâî, íàçûâàåòñÿ îäíîñòîðîííèì. ×àùå âñåãî ãîëîâêà òîëüêî ÷èòàåò ñèìâîëû âõîäíîé ëåíòû, íî âñòðå÷àþòñÿ è ðàñïîçíàâàòåëè

- ïðåîáðàçîâàòåëè, íàïðèìåð ìàøèíà Òüþðèíãà.

Âíåøíÿÿ ïàìÿòü - õðàíèëèùå èíôîðìàöèè íåêîòîðîãî òèïà, àëôàâèò êîòîðîé êîíå÷åí. Çàäàåòñÿ äâóìÿ ôóíêöèÿìè: ÔÄÏ

- ôóíêöèÿ äîñòóïà ê ïàìÿòè. - ôóíêöèÿ ïðåîáðàçîâàíèÿ ïàìÿòè. ÔÄÏ - îòîáðàæåíèÿ ìíîæåñòâà èíôîðìàöèîííûõ ñèìâîëîâ. ÔÏÏ

14

ÔÏÏ

- îòîáðàæàåò ñîñòîÿíèå ïàìÿòè â íîâîå ñîñòîÿíèå ïàìÿòè.

Óñòðîéñòâî óïðàâëåíèÿ - ìíîæåñòâî ñîñòîÿíèé, â ñîâîêóïíîñòè ñ îòîáðàæåíèåì, êîòîðàÿ îïèñûâàåò, êàê ìåíÿþòñÿ òåêóùèå ñîñòîÿíèÿ â çàâèñèìîñòè îò âõîäíîãî ñèìâîëà è èíôîðìàöèè, è0âëåêàåìîé èç âíåøíåé ïàìÿòè. Ðàñïîçíàâàòåëü ðàáîòàåò, ïðîäåëûâàÿ ïîñëåäîâàòåëüíîñòü øàãîâ:

1.

Ãîëîâêà âïðàâî\âëåâî\íåïîäâèæíà.

2.

 ïàìÿòü ïîìåùàåòñÿ íåêîòîðàÿ èíôîðìàöèÿ.

3.

Èçìåíÿåòñÿ ñîñòîÿíèå óïðàâëÿþùåãî óñòðîéñòâà.

Êîíôèãóðàöèÿ ðàñïîçíàâàòåëÿ

- ñîâîêóïíîñòü ïàðàìåòðîâ, îïèñûâàþùèõ

1.

Ñîñòîÿíèå óñòðîéñòâà

2.

Ñîäåðæèìîå âõîäíîé ëåíòû âìåñòå ñ ïîëîæåíèåì â ãîëîâêå.

3.

Ñîäåðæèìîå ïàìÿòè

Íåäåòåðìèíèðîâàííûì íàçûâàþò ðàñïîçíàâàòåëü, äëÿ êîòîðîãî ñóùåñòâóåò ìíîæåñòâî øàãîâ, êîòîðîå îí ìîæåò ñäåëàòü èñõîäÿ èç òåêóùåé êîíôèãóðàöèè. Ñðåäè ñîñòîÿíèé ðàñïîçíàâàòåëÿ âûäåëàþò ïîäìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé è ïîäìíîæåñòâî êîíå÷íûõ ñîñòîÿíèé. Ðàñïîçíàâàòåëü äîïóñêàåò âõîäíóþ öåïî÷êó

α,

åñëè íà÷èíàÿ ñ îäíîé èç

íà÷àëüíûõ êîíôèãóðàöèÿ ðàñïîçíàâàòåëü ìîæåò ïðîäåëàòü ïîñëåäîâàòåëüíîñòü øàãîâ, çàêàí÷èâàþùóþñÿ êîíå÷íîé êîíôèãóðàöèåé.  çàêëþ÷èòåëüíîì êîíôèãóðàöèè ðàñïîçíàâàòåëü íàõîäèòñÿ â îäíîì èç çàêëþ÷èòåëüíûõ ñîñòîÿíèé è ãîëîâêà îáîçðåâàåò êðàéíèé ïðàâûé ñèìâîë âîäíîé ëåíòû èëè ñîøëà ñ ëåíòû è ñîäåðæèìîå ïàìÿòè óäîâëåòâîðÿåò íåêîòîðûì çàäàííûì óñëîâèÿì. ßçûê, äîïóñêàåìûé ðàñïîçíàâàòåëåì - ìíîæåñòâî âõîäíûõ öåïî÷åê, êîòîðûå îí äîïóñêàåò. ßçûê îïðåäåëÿåìûé ðàñïîçíàâàòåëåì àâòîìàòà òîãäà è òîëüêî òîãäà, êîãäà îí îïðåäåëÿåòñÿ îäíîñòîðîííèì äåòåðìèíèðîâàííûì àâòîìàòîì

(ïðèìåð - ìàøèíà Òüþðèíãà).

9

Àëãîðèòì ïåðåõîäà îò íå äåòåðìèíèðîâàííîãî àâòîìàòà ê äåòåðìèíèðîâàííîìó.

Êîíå÷íûì àâòîìàòîì áóäåì íàçûâàòü îäíîñòîðîííèé ðàñïîçíàâàòåëü, ãäå ãîëîâêà äâèæåòñÿ òîëüêî âïðàâî è îòñóòñòâóåò âíåøíÿÿ ïàìÿòü. Êîíå÷íûé àâòîìàò

M îïðåäåëÿåòñÿ ïÿòåðêîé îáúåêòîâ M = hQ, F, δ , N, Σi, ãäå Q - ìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé F - ìíîæåñòâî êîíå÷íûõ ñîñòîÿíèé δ - ôóíêöèÿ îòîáðàæåíèÿ N - ìíîæåñòâî ñîñòîÿíèé àâòîìàòà

15

Σ - àëôàâèò δ : N ×Σ → N ↓ Σ\N A B C a B b C c C Ø Ø 1 C - çàêëþ÷èòåëüíîå ñîñòîÿíèå, A - çàêëþ÷èòåëüíîå ñîñòîÿíèå. Åñëè àâòîìàò íåäåòåðìèíèðîâàííûé, òî âõîäíûõ ñîñòîÿíèé ìîæåò áûòü íåñêîëüêî. Íåäåòåðìèíèðîâàííûé êîå÷íûé àâòîìàò - àâòîìàò, ó êîòîðîãî çíà÷åíèÿ ôóíêöèè ïåðåõîäîâ - íå îòäåëüíîå ñîñòîÿíèå, à ìíîæåñòâî ñîñòîÿíèé.  îáùåì ñëó÷àå ó íåäåòåðìèíèðîâàííîãî àâòîìàòà íà÷àëüíûõ ñîñòîÿíèé ìîæåò áûòü íåñêîëüêî. Àëãîðèòì ïîëó÷åíèÿ èç ÍÄÀ ÄÀ.

Ïóñòü Mí - íåäåòåðìèíèðîâàííûõ àâòîìàò ñ ôóíêöèåé ïåðåõîäîâ δí . Áóäåì ñòðîèòü äåòåðìèíèðîâàííûé àâòîìàò

1.

Mä âìåñòå ñ ôóíêöèåé ïåðåõîäîâ δä .

Ïîìå÷àåì ïåðâûé ñòîëáåö òàáëèöû ïåðåõîäà ÄÀ ìíîæåñòâîì íà÷àëüíûõ ñîñòîÿíèé ÍÄÀ.

2.

Ïî äàííîìó ìíîæåñòâó ñîñòîÿíèé X ïîìå÷àåì ñòîëáåö òàáëèöû ïåðåõîäà ÄÀ, äëÿ êîòîðîãî ïåðåõîäà åùå íå âû÷èñëåíî îïðåäåëÿåì òå ñîñòîÿíèÿ ÍÄÀ, êîòîðûå ìîãóò áûòü äîñòèãíóòû èç X ñ ïîìîùüþ êàæäîãî ñèìâîëà àëôàâèòà

a

è ïîìåùàåì ìíîæåñòâî ñîñòîÿíèé

Y

â ñîîòâåòñòâóþùèå

ÿ÷åéêè ÄÀ.

y = δä (x, a) = {u|u ∈ δí (v, a) , v ∈ X} 3.

Äëÿ êàæäîãî ìíîæåñòâà Y, ïîðîæäåííîãî íà øàãå 2, ïðîâåðèòü, èìååòñÿ ëè â ÄÀ ñòîëáåö, ïîìå÷åííûé ýòèì.

Åñëè íå èìååòñÿ, òî ñîçäàòü íîâûé ñòîëáåö è ïîìåòèòü åãî Y ∗

4.

Åñëè â òàáëèöå ÄÀ åñòü ñòîëáöû äëÿ êîòîðûõ ïåðåõîä åùå íå âûïîëíåí ïðèìåíÿåì ê íåìó øàã

5.

2 â ïðîòèâíîì ñëó÷àå ïåðåõîäèì ê øàãó 5.

Ïîìå÷àåò ñòîëáåö ÄÀ êàê äîïóñêàþùåå ñîñòîÿíèå åñëè â íåì åñòü õîòÿ áû îäíî äîïóñêàþùåå ñîñòîÿíèå.

10

Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ.

11

Òåîðåìà îá îáùåì âèäå àâòîìàòíûõ è ÊÑ ÿçûêîâ è èõ ñëåäñòâèÿ.

Òåîðåìà îá îáùåì âèäå öåïî÷åê àâòîìàòíûõ ÿçûêîâ.

16

Ïóñòü L - àâòîìàòíûé ϕ ∈L |ϕ | ≥ p. ϕ = α Bγ , |B| > 0 α Bi γ ∈ L

ÿçûê. Òîãäà ñóùåñòâóåò

p > 0,

÷òî äëÿ êàæäîãî

Äàííàÿ òåîðåìà ãîâîðèò î òîì, ÷òî åñëè äàí àâòîìàòíûé ÿçûê è äîñòàòî÷íî äëèííàÿ öåïî÷êà â íåì, òî â äàííîé öåïî÷êå ìîæíî íàéòè íåïóñòóþ ïîäöåïî÷êó, êîòîðóþ ìîæíî ïîâòîðèòü ñêîëüêî óãîäíî ðàç è âñå ïîëó÷åííûå öåïî÷êè áóäóò ïðèíàäëåæàòü òîìó æå ñàìîìó ÿçûêó. Òåîðåìà èñïîëüçóåòñÿ äëÿ òîãî, ÷òîáû äîêàçàòü, ÷òî íå âñå öåïî÷êè ìîãóò áûòü ïîñòðîåíû ñ ïîìîùüþ àâòîìàòíûõ ãðàììàòèê. 1 ñëåäñòâèå: ÿçûê, ñîäåðæàùèé öåïî÷êó âèäà xn yn íå ÿâëÿåòñÿ àâòîìàòíûì ÿçûêîì.

2 ñëåäñòâèå: ÿçûê àðèôìåòè÷åñêîãî âûðàæåíèÿ â îáùåì ñëó÷àå íå ÿâëÿåòñÿ àâòîìàòíûì. Òåîðåìà îá îáùåì âèäå ÊÑ ÿçûêîâ.

L - ÊÑ ÿçûê ⇒ ∃p > 0 : ϕ ∈ L; |ϕ | ≥ p 1: xn yn zn íå ìîãóò áûòü ïîðîæäåíû ÊÑ ÿçûêàìè. Ñëåäñòâèå 2: ÿçûêè ïðîãðàììèðîâàíèÿ â îáùåì ñëó÷àå íå ÿâëÿþòñÿ ÊÑ ÿçûêàìè. Íà ïðàêòèêå âñå ÿçûêè ñ÷èòàþòñÿ ÊÑ. Äîïîëíèòåëüíûé êîíòðîëü çà ïðîâåðêîé ïîëàãàåòñÿ íà ñåìàíòè÷åñêèå ïîäïðîãðàììû. Ïóñòü

Ñëåäñòâèå

12

Îïåðàöèè íàä ÿçûêàìè è òåîðåìà îá îïåðàöèÿõ íàä àâòîìàòíûìè è ÊÑ ÿçûêàìè.

1.

ßçûê L íàçûâàåòñÿ îáúåäèíåíèåì ÿçûêîâ L1 , L2 , åñëè îí ñîñòîèò èç öåïî÷åê L = {α |α ∈ L1 ∨ α ∈ L2 }.

2.

Ïåðåñå÷åíèå

3.

Ðàçíîñòü

4.

Äîïîëíåíèå

5.

Êîíêàòåíàöèÿ

6.

ßçûê L íàçûâàåòñÿ èòåðàöèåé ÿçûêà L1 , åñëè L0 = {ε } Ln = L Ln−1 ∪1 1 n ∗ L = ∪n≥0 L L+ = n>0 Ln

7.

ßçûê L íàçûâàåòñÿ îáðàùåíèåì ÿçûêà { } L = L1R , L = α R |α ∈ L1

L = L1 ∧ L2 ⇔ L = {α |α ∈ L1 ∧ α ∈ L2 }

/ L2 } L = L1 \ L2 ⇔ L = {α |a ∈ L1 ∧ α ∈ L = L¯1 ⇔ L = {α |α ∈ / L1 } L = L1 L2 ⇔ L = {α |α = β γ , β ∈ L1 , γ ∈ L2 }

17

L1 ,

åñëè îí ñîñòîèò èç öåïî÷åê

8.

Ïîäñòàíîâêà ÿçûêà âñòðå÷àåòñÿ ñèìâîë

L2 â L1 âìåñòî a - âî âñåõ öåïî÷êàõ ÿçûêà L1 , a, îí çàìåíåí íà âñå âîçìîæíûå öåïî÷êè L2 .

ãäå

ÊÑ ÿçûêè çàìêíóòû îòíîñèòåëüíî îáúåäèíåíèÿ, êîíêàòåíàöèè, èòåðàöèè, ïîäñòàíîâêè è îáðàùåíèÿ. Àâòîìàòíûå ÿçûêè çàìêíóòû îòíîñèòåëüíî îáúåäèíåíèÿ, êîíêàòåíàöèè, èòåðàöèè, îáðàùåíèÿ, ïîäñòàíîâêè, ïåðåñå÷åíèÿ, äîïîëíåíèÿ è ðàçíîñòè.  ðåçóëüòàòå îïåðàöèé íàä ÿçûêàìè ïîëó÷àåòñÿ íîâîå ìíîæåñòâî öåïî÷åê. Ïðè ðåàëèçàöèè íà ÝÂÌ ïðîãðàììû ñèíòàêñè÷åñêîãî àíàëèçà ëó÷øå âñåãî ïðåäñòàâëÿòü â âèäå ëîãè÷ñêèõ ôóíêöèé, äàþùèõ ïîëíûé îòâåò, åñëè öåïî÷êà ïðèíàäëåæèò ÿçûêó è îòðèöàòåëüíûé îòâåò â ïðîòèâíîì ñëó÷àå. Ïðè òàêîì ïîñòðîåíèè èòåðàöèÿ - âûçîâ ïðîöåäóðû âíóòðè öèêëà, êîíêàòåíàöèÿ - ïîñëåäîâàòåëüíûé âûçîâ ïîäïðîãðàìì, îáúåäèííèå - àëüòåðíàòèâíûé âûçîâ ïðîöåäóðû, ïîäñòàíîâêà- çàìåíà àíàëèçà òåðìèíàëüíîãî ñèìâîëà íà ïðîöåäóðó åãî ñèíòàêñè÷åñêîãî ðàçáîðà.

13

Ìåòîäû àíàëèçà ÊÑ ÿçûêîâ. Ãðàììàòèêè ïðåäøåñòâîâàíèÿ.

13.1

Ñèíòàêñè÷åñêèé àíàëèç êîíòåêñíî-ñâîáîäíûõ ÿçûêîâ

Ìåòîäû ïîñòðîåíèÿ àíàëèçàòîðîâ äëÿ ÊÑ ãðàììàòèêè ðàçäåëÿþòñÿ íà äâå ãðóïïû: 1. Íèñõîäÿùèå ìåòîäû 2. Âîñõîäÿùèå ìåòîäû Ýòè òåðìèíû ñîîòâåòñòâóþò ñïîñîáó ïîñòðîåíèÿ ñèíòàêñè÷åñêèõ äåðåâüåâ âûâîäà. Íèñõîäÿùèå ìåòîäû âûïîëíÿþò àíàëèç ñ íà÷àëüíîãî âûïîëíåíèÿ íåòåðìèíàëà èëè îò êîðíÿ äåðåâà ê êîíöåâûì âåðøèíàì ïûòàÿñü ïîñòðîèòü äåðåâî âíèç (åñëè äåðåâî ïîñòðîèòü óäàëîñü, òî öåïî÷êà ïðèíàäëåæèò äàííîé ãðàììàòèêå, â ïðîòèâíîì ñëó÷àå íå ïðèíàäëåæèò).  îáùåì ñëó÷àå ìåòîäû ýòîé ãðóïïû îñíîâàíû íà ïåðåáîðå âñåõ âîçìîæíûõ âàðèàíòîâ ÿçûêà. Ïîýòîìó áîëåå ÷àñòî èñïîëüçóþòñÿ ìåòîäû âîñõîäÿùèå. Àëãîðèòìû âîñõîäÿùåãî ðàçáîðà íà÷èíàþòñÿ ñ ëèñòüåâ äåðåâà âûâîäà è ïûòàþòñÿ ïîñòðîèòü äåðåâî ðàçáîðà âîñõîäÿ îò ëèñòüåâ ê êîðíþ. Ñðåäè âîñõîäÿùèõ àëãîðèòìîâ íàèáîëüøåå ðàñïðîñòðàíåíèå ïîëó÷èëè àëãîðèòìû, èñïîëüçóþùèå îòíîøåíèå ïðåäøåñòâîâàíèÿ. Ñîãëàñíî ýòèì ìåòîäàì ìåæäó ñèìâîëàìè, êîòîðûå ìîãóò âñòðåòèòüñÿ â öåïî÷êå, îïðåäåëÿþòñÿ îòíîøåíèÿ: 1. Îòíîøåíèå ðàâåíñòâà

= ˙

2. Îòíîøåíèå ìåíüøå (ðàíüøå) 3. Îòíîøåíèå áîëüøå (ïîçæå)

˙ ≤

˙ ≥ 18

Îòíîøåíèå ðàâåíñòâà îïðåäåëÿåòñÿ, åñëè ñèìâîëû

h1 è h2

ñòîÿò â îäíîì

ðÿäó. Îòíîøåíèå ìåíüøå îïðåäåëÿåòñÿ, åñëè ñèìâîëû h1 óæå âûâåäåíî, à h2 áóäåò ñòîÿòü íåïîñðåäñòâåííî ñïðàâà îò h1 ïðè ïðèåíåíèè íåêîòîðîãî ïðàâèëà íà ñëåäóþùåì øàãå âûâîäà. Îòíîøåíèå áîëüøå îïðåäåëåíî êîãäà íåïîðåäñòâåííî ñëåâà îò

h2

h2 óæå âûâåäåíî, à íà ñëåäóþùåì øàãå âûâîäà.

h1 áóäåò

ñòîÿòü

Îñíîâîé äëÿ ñâåðòêè ïðè èñàîëüçîâàíèè ðàñìàòðèâàåñûõ ìåòîäîâ ÿâëÿþòñÿ ñèìâîëû, ðàñïîëîæåííûå ìåæäó îòíîøåíèÿìè ïðåøåñòâîâàíèÿ

13.2

<, >.

Ãðàììàòèêè ïðåäøåñòâîâàíèÿ

Íàèáîëåå ýôôåêòèâíûå ìåòîäû ñâåðòêè ìîæíî ïðèìåíèòü äëÿ óçêîãî êëàññà ÊÑ ãðàììàòèê, êîòîðûå íàçûâàþòñÿ ãðàììàòèêàìè ïðåäøåñòâîâàíèÿ. Ãðàììàòèêè ïðåäøåñòâîâàíèÿ - óçêèé êëàññ ÊÑ ãðàììàòèê, äëÿ êîòîðûõ âûïîëíÿþòñÿ äâà ïðàâèëà: 1. Ìåæäó ëþáûìè äâóìÿ ñèìâîëàìè ñóùåñòâóåò íå áîëåå îäíîãî îòíîøåíèÿ ïðåäøåñòâîâàíèÿ. 2. Íå ñóùåñòâóåò äâóõ ïðàâèë, ñîäåðæàùèõ îäèíàêîâûå ïðàâûå ÷àñòè. Ñóùåñòâóåò ðÿä âèäîâ ãðàììàòèê ïðåäøåñòâîâàíèÿ, ðàçëè÷àþùèõñÿ ïðàâèëàìè îïðåäåëåíèÿ. 1. Ãðàììàòèêà ïðåäøåñòâîâàíèÿ Âèðòà, îòíîøåíèÿ ïðåäøåñòâîâàíèÿ îïðåäåëåíû ìåæäó ëþáûìè ñèìâîëàìè ( òåðìèíàëüíûìè è íåòåðìèíàëüíûìè) 2. Ãðàììàòèêà ïðåäøåñòâîâàíèÿ Ôëîéäà, îòíîøåíèÿ ïðåäøåñòâîâàíèÿ ââåäåíû òîëüêî ìåæäó òåðìèíàëüíûìè ñèìâîëàìè. Êðîìå òîãî, â ãðàììàòèêå Ôëîéäà íå äîïóñêàåòñÿ äâà ñòîÿùèõ ðÿäîì íåòåðìèíàëüíûõ ñèìâîëîâ. Ïðè èñïîëüçîâàíèè ãðàììàòèê ïðåäøåñòâîâàíèÿ òàáëèöû, ñîäåðæàùèå îòíîøåíèÿ ïðåäøåñòâîâàíèÿ ìîãóò áûòü î÷åíü áîëüøèìè, òàê êàê ÷èñëî íåòåðìèíàëüíûõ è òåðìèíàëüíûõ ñèìâîëîâà âåëèêî. Äëÿ ðåøåíèÿ ýòîé ïðîáëåìû áûëî ïðåäëîæåíî èñïîëüçîâàòü ÷èñëîâûå ôóíêöèè ïðåäøåñòâîâàíèÿ ñ íå÷èñëîâûìè àðãóìåíòàìè, äëÿ êîòîðûõ âûïîëíÿåòñÿ:

f (h1 ) = g (h2 ) ⇔ h1 =h ˙ 2 ˙ 2 f (h1 ) < g (h2 ) ⇔ h1 g (h2 ) ⇔ h1 >h

14 14.1

ÏÎËÈÇ. Àëãîðèòì Çàìåëüñîíà-Áàóýðà. ÏÎËÈÇ

ÏÎËÈÇ

- ïîëüñêàÿ èíâåðñíàÿ çàïèñü. 19

1.

È èäåíòèôèêàòîðû, è êîíñòàíòû èäóò â òîì æå ïîðÿäêå, ÷òî è â èíôèêñíîé çàïèñè.

2.

Îïåðàòîðû ñëåäóþò â òîì æå ïîðÿäêå, ïî êîòîðîìó îíè äîëæíû âû÷èñëÿòüñÿ.

3.

Îïåðàòîðû ðàñïîëàãàþòñÿ íåïîñðåäñòâåííî çà ñâîèìè îïåðàíäàìè.

Àëãîðèòì Çàìåëüñîíà-Áàóýðà ïåðâîäà àðèôìåòè÷åñêîãî âûðàæåíèÿ â ÏÎËÈÇ Äëÿ êàæäîãî ðàçäåëèòåëÿ(ñêîáêè, îïåðàòîðû) ââîäÿò äâà ïðèîðèòåòà: ñðàâíèòåëüíûé è ìàãàçèííûé. Ñèìâîë

Pc Pì

( 9 0

) 0 -

+,7 7

*,/ 8 8

if,:=,while 9 0

then,do 1 0

else 2 2

;,end 1 -

or 3 3

and 4 4

not 5 5

îï. ñðàâíåíèÿ

Èñõîäíîå âûðàæåíèå ðàññìàòðèâàåòñÿ îäèí ðàç ñëåâà íàïðàâî. Èäåíòèôèêàòîðû è êîíñòàíòû ïåðåïèñûâàþòñÿ â âûõîäíóþ ñòðîêó. Ïðè îáíàðóæåíèè ðàçäåëèòåëÿ åãî ñðàâíèòåëüíûé ïðèîðèòåò ñðàâíèâàåòñÿ ñ ìàãàçèííûì ïðèîðèòåòîì ðàçäåëèòåëÿ, êîòîðûé ñòîèò íà âåðøèíå ñòåêà. Åñëè îí áîëüøå, èëè ñòåê ïóñòîé, òî ðàçäåëèòåëü ïîìåùàåòñÿ â ñòåê. Èíà÷å ðàçäåëèòåëü èçâëåêàåòñÿ èç ñòåêà è çàïèñûâàåòñÿ â âûõîäíóþ ñòðîêó ÏÎËÈÇ, ïîñëå ÷åãî øàã

2 âûïîëíÿåòñÿ äëÿ òîãî æå âõîäíîãî ñèìâîëà.

Çàêðûâàþùàÿñÿ ñêîáêà - èç ñòåêà èçâëåêàåòñÿ âñå âïëîòü äî ïåðâîé îòêðûâàþùåé ñêîáêè è çàïèñûâàåòñÿ â ñòðîêó ÏÎËÈÇ. Îòêðûâàþùàÿ ñêîáêà èçâëåêàåòñÿ, íî íå çàïèñûâàåòñÿ. Ïîñëå èçúÿòèÿ ñêîáêè ïåðåõîäèì ê ñëåäóþùåìó ñèìâîëó. Ïðè äîñòèæåíèè êîíöà ñòðîêè ñîäåðæèìîå ñòåêà ïåðåïèñûâàåòñÿ â ÏÎËÈÇ. Èíòåðïðåòàöèÿ. Ñ ïîìîùüþ ñòåêà âûðàæåíèå ìîæåò áûòü âû÷èñëåíî çà îäèí ïðîñìîòð ñëåâà íàïðàâî, ïðè ýòîì åñëè ñêàíèðóåìûé ñèìâîë èäåíòèôèêàòîð èëè êîíñòàíòà, ñîîòâåòñòâóþùåå çíà÷åíèå çàíîñèòñÿ â ñòåê. Åñëè ñêàíèðóåìûé ñèìâîë - óíàðíûé îïåðàòîð, òî îí ïðèìåíÿåòñÿ ê âåðõíåìó îïåðàòîðó â ñòåêå, êîòîðûé çàìåíÿåòñÿ íà ðåçóëüòàò. Åñëè áèíàðíûé îïåðàòîð(çà èñêëþ÷åíèÿìè, ïðèâåäåííûìè íèæå), òî îí ïðèìåíÿåòñÿ ê äâóì âåðõíèì çíà÷åíèÿì â ñòåêå è â íåãî äîáàâëÿåòñÿ ðåçóëüòàò. Åñëè âñòðåòèëñÿ áèíàðíûé îïåðàòîð ïðèñâàèâàíèÿ, îáà àðãóìåíòà èçâëåêàþòñÿ èç ñòåêà, çíà÷åíèå, êîòîðîå äîëæíî áûòü ïðèñâîåíî, ñîõðàíÿåòñÿ ïî àäðåñó, óêàçàííîìó â ïåðâîì àðãóìåíòå, â ñòåê íè÷åãî íå çàíîñèòñÿ. Áèíàðíûé îïåðàòîð óñëîâíîãî ïåðåõîäà óäàëÿåò äâà àðãóìåíòà èç ñòåêà è íå ôîðìèðóåò ðåçóëüòàò. Åñëè çíà÷åíèå èñòèííî, òî ñêàíèðóåòñÿ ñëåäóþùèé çà ÓÏË ñèìâîë, èíà÷å ïðîèñõîäèò ïåðåõîä ê ñèìâîëó, íîìåð êîòîðîãî ñîäåðæèò âòîðîé àðãóìåíò. Îïåðàòîð áåçóñëîâíîãî ïåðåõîäà èçâëåêàåò èç ñòåêà íîìåð ïîçèöèè è ïåðåõîäèò ïî àäðåñó.

14.2

Ãåíåðàöèÿ êîìàíä ïî ÏÎËÈÇó

Ïðè ãåíåðàöèè êîìàíä òàêæå èñïîëüçóåòñÿ ñòåê â êîòîðîì âìåñòî çíà÷åíèé ñîõðàíÿþòñÿ àäðåñà ïðîìåæóòî÷íûõ ïåðìåííûõ è îïåðàíäîâ.

20

6 6

Îñíîâà äëÿ ôîðìèðîâàíèÿ êîìàíä ñîñòàâëÿåò êîäû ðåïðîäóêöèè, ò.å. íàáîð ìàøèííûõ êîìàíä, ñîîòâåòñòâóþùèõ êàæîìó îòäåëüíî âçÿòîìó îïåðàòîðó ÏÎËÈÇà. Ñòðîêà ÏÎËÈÇà ïðîñìàòðèâàåòñÿ îäèí ðàç ñëåâà íàïðàâî è ïðè âñòå÷å ñ îïåðàíäàìè èõ èìåíà çàíîñÿòñÿ â ñòåê. Ïðè âñòðå÷å ñ îïåðàòîðîì èç òàáëèöû âûáèðàþòñÿ ñîîòâåòñòâóþùèå åìó êîä ðåïðîäóêöèè è â íåå ïîäñòàâëÿþòñÿ èìåíà ïåðåìåííûõ, èçâëå÷åííûå èç ñòåêà. Åñëè êîìàíäà ôîðìèðóåò ðåçóëüòàò, òî èìÿ ðåçóëüòàòà çàìåùàåò îïåðàíäû, ïðîñìàòðèâàåìûå èç ñòåêà. Ñôîðìèðîâàííàÿ ïðîäóêöèÿ ïîìåùàåòñÿ â âûõîäíîé ôàéë.

14.3

Òåòðàäû è òðèàäû

Òåòðàäîé (÷åòâåðêîé) áóäåì íàçûâàòü çàïèñü áèíàðíîé îïåðàöèè â âèäå: <îïåðàöèÿ> <îïåðàíä 1> <îïåðàíä 2> <ðåçóëüòàò> Îïòèìàëüíûì ÿâëÿåòñÿ ïðåäñòàâëåíèÿ âíóòðåííåé ôîðìû â âèäå òðèàäû. Ñïîñîá íå òðåáóåò áîëüøîãî êîëè÷åñòâà ïàìÿòè äëÿ âíóòðåííèõ ïåðåìåííûõ. Ïîëå ðåçóëüòàò ó íèõ îòñòóòñòâóåò è åñëè âïîñëåäñòâèè íåîáõîäèìî èñïîëüçîâàíèå ðåçóëüòàòà êàêîé-ëèáî îïåðàöèè, òî íà ýòó îïåðàöèþ ñòàâèòñÿ ññûëêà. Òðèàäû çàíèìàþò ìåíüøå ìåñòà, ÷åì òåòðàäû, íî ïðè ðàáîòå ñ íèìè íåîáõîäèìû âûÿñíÿòü, ðåçóëüòàòû êàêèõ îïåðàöèé íóæíû â äàëüíåéøåì è õðàíèòü îïèñàíèå ýòèõ îïåðàöèé. Äîñòîèíñòâà òðèàä ïî ñðàâíåíèþ ñ ïîëèçîì î÷åâèäíû: îíè ïðåäñòàâëÿþò ïîñëåäîâàòåëüíîñòü â âèäå îäíîñâÿçíîãî\äâóñâÿçíîãî ñïèñêà, ýëåìåíòû êîòîðîãî ìîæíî ëåãêî ïåðåñòàâëÿòü äëÿ ìàøèííî çàâèñèìîé îïòèìèçàöèè.

15

Îñíîâíûå ôàçû òðàíñëÿöèè.

Òðàíñëÿòîðîì áóäåì íàçûâàòü ïðîãðàììó ïåðåâîäà òåêñòà ïðîãðàììû ñ èñõîäíîãî ÿçûêà íà öåëåâîé. Òðàíñëÿòîðû áûâàþò äâóõ âèäîâ:

1.

Êîìïèëÿòîðû

2.

Èíòåðïðåòàòîðû

Êîìïèëÿòîðû öåëèêîì ïåðåâîäÿò ïðîãðàììó â îáúåêòíûé êîä, êîòîðûé ìîæåò áûòü ïðåîáðàçîâàí â èñïîëíÿåìûé ôàéë. Èíòåðïðåòàòîð èñïîëüçóåò êàæäóþ êîìàíäó ïî îòäåëüíîñòè. Ìàòåìàòè÷åñêàÿ ëèíãâèñòèêà - íàóêà, êîòîðàÿ çàíèìàåòñÿ ôîðìàëüíûìè ìåòîäàìè ïîñòðîåíèÿ ÿçûêîâ.

21

Ðàçäåëà ìàòåìàòè÷åñêîé ëèíãâèñòèêè, èçó÷àþùåé ñïîñîáû îïèñàíèÿ ÿçûêîâ, ïîñòðîåíèÿ àëãîðèòìîâ òðàíñëÿöèè, íàçûâàåòñÿ òåîðèåé ôîðìàëüíûõ ãðàììàòèê. Ñèíòàêñèñ - ñâîä ïðàâèë, îïðåäåëÿþùèõ ïðàâèëüíîñòü ïîñòðîåíèÿ öåïî÷åê ÿçûêà. Ñåìàíòèêà

- îïðåäåëÿåò ñìûñëîâóþ ïðàâèëüíîñòü.

Îñíîâíûå ôàçû êîìïèëÿöèè ïðîãðàììû:

1.

Ëåêñè÷åñêèé àíàëèç

- ñêàíèðîâàíèå.

Ïðåîáðàçóåò êîä ïðîãðàììû â öåïî÷êó ëåêñåì.

2.

Ñèíòàêñè÷åñêèé àíàëèç

- ïðîâåðÿåò, óäîâëåòâîðÿåò ëè öåïî÷êà ëåêñåì

òðåáîâàíèÿì, íàëîæåííûì íà ÿçûê ïðîãðàììèðîâàíèÿ. Ñâîäèò ïðîãðàììó ê åäèíñòâåííîìó ïåðâîíà÷àëüíîìó ñèìâîëó. Âûïîëíÿåòñÿ ñ ïîìîùüþ ïðîãðàììû, ïîñòðîåííîé ïî çàäàííîé ãðàììàòèêå ÿçûêà (ðàçáîð, ñèíòàêñè÷åñêèé ðàçáîð, ïàðñèíã).

3.

Ñåìàíòè÷åñêèé àíàëèç. ßâëÿåòñÿ ñèíòàêñè÷åñêè óïðàâëÿåìûì ïðîöåññîì è çàêëþ÷àåòñÿ â îïðåäåëåíèè ñìûñëîâîãî çíà÷åíèÿ êîíñòðóêöèè. Ýòàïû:

(a)

Ñèíòàêñè÷åñêèé àíàëèçàòîð ðàñïîçíàåò êîíñòðóêöèþ ÿçûêà.

(b)

Âûçûâàåòñÿ ñîîòâåòñòâóþùàÿ ñåìàíòè÷åñêàÿ ïîäïðîãðàììà.

(c)

Ýòà ïðîãðàììà ôîðìèðóåò âíóòðåííþþ ôîðìó ïðîãðàììû (ÂÔÏ).  êà÷åñòâå ÂÔÏ ìîæíî èñïîëüçîâàòü ÏÎËÈÇ, ïåòðàäó èëè òåòðàäó.

Ïåòðàäà:

(a)

Îïåðàöèÿ

(b)

Ïåðâûé îïåðàíä

(c)

Âòîðîé îïåðàíä

(d)

Ðåçóëüòàò

4.

Ìàøèííî-íåçàâèñèìàÿ îïòèìèçàöèÿ.

5.

Ðàñïðåäåëåíèå ïàìÿòè.

6.

Ãåíåðàöèÿ êîäà.

7.

Ìàøèííî-çàâèñèìàÿ îïòèìèçàöèÿ.

8.

Ñáîðêà ïðîãðàììû.

Ðåçóëüòàò: îáúåêòíûé ìîäóëü. Ýòàïû

5-8

ÿâëÿþòñÿ ìàøèííî-çàâèñèìûìè,

îñòàëüíûå

- ìàøèííî íåçàâèñèìûìè. Êîíòåêñò êîìïèëÿòîðà. Äëÿ ñîçäàíèÿ êîíå÷íîãî èñïîëíÿåìîãî ôàéëà òðåáóåòñÿ òàêæå äðóãèå

ïðîãðàììû, òàêèå êàê ïðåïðîöåññîð çàãðóç÷èê è ðåäàêòîðû ñâÿçè.

22

Èñõîäíûé êîä ïðîãðàììû ìîæåò áûòü ðàçäåëåí íà ìîäóëè, â íåé ìîãóò ñîäåðæàòüñÿ äèðåêòèâû óñëîâèé êîìïèëÿòîðà, íàñòðîéêè êîìïèëÿòîðà. Ñáîð åäèíîé èñõîäíîé ïðîãðàììû âûïîëíÿåò ïðåïðîöåññîð. Íà âûõîäå êîìïèëÿòîðà ñîçäàåòñÿ öåëåâàÿ ïðîãðàììà, ïðåäñòàâëÿþùàÿ ñîáîé ïåðåìåùàåìûé îáúåêòíûé êîä, êîòîðûé çàòåì ñâÿçûâàåòñÿ â èñïîëíÿåìûé ôàéë âìåñòå ñ çàãðóç÷èêîì. Äëÿ ñâÿçûâàíèÿ ìîæåò òðåáîâàòüñÿ êðîìå èñõîäíîãî ôàéëà îáúåêòíûé ôàéëû áèáëèîòåê, èñïîëüçóåìûõ â ýòîé ïðîãðàììå.  òàêèõ îáúåêòíûõ ôàéëàõ ñîäåðæàòñÿ:

•

Ñèìâîëüíûå îáîçíà÷åíèÿ ôóíêöèé, ïðåäíàçíà÷åííûõ äëÿ èñïîëüçîâàíèÿ â äðóãèõ îáúåêòíûõ ôàéëàõ.

•

Ñèìâîëû îïðåäåëåííûå â äðóãèõ îáúåêòíûõ ôàéëàõ è èñïîëüçóåìûå â äðóãîé ïðîãðàììå.

•

Âíóòðåííèå ñèìâîëû ïîçâîëÿþùèå ïåðåìåùàòü êîä îáúåêòíîãî ôàéëà ïî ëþáîìó àäðåñó.

23