Синтаксический анализ языка НОРМА. Разбор описания

Синтаксический анализ языка НОРМА. Разбор описания

_{ÌÎÑÊÎÂÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÈÍÆÅÍÅÐÍÎ-ÔÈÇÈ×ÅÑÊÈÉ ÈÍÑÒÈÒÓÒ}

_{(ÒÅÕÍÈ×ÅÑÊÈÉ ÓÍÈÂÅÐÑÈÒÅÒ)}

_{--------------------------------------------------------}

_{Êàôåäðà 22}

_{Ïîÿñíèòåëüíàÿ çàïèñêà ê}

_{ÊÓÐÑÎÂÎÉ ÐÀÁÎÒÅ}

_{íà òåìó}

_{“Ðàçðàáîòêà ëåêñè÷åñêîãî àíàëèçàòîðà}

_{äëÿ ÿçûêà ïðîãðàììèðîâàíèÿ Íîðìà”}

_{ñòóäåíòêè ãðóïïû Ê7-01}

_{Ïå÷¸íêèíîé Îëüãè Àëåêñàíäðîâíû}

_{Íàó÷íûé ðóêîâîäèòåëü:}

_{Êîìèññèÿ:}

_{Îöåíêà:}

_{Ìîñêâà 1995ã.}

 _{1. ÂÂÅÄÅÍÈÅ}

                _{Â ñîîòâåòñòâèè ñ çàäàíèåì íà ÓÈÐ è ÊÏ â äàííîì ñåìåñòðå ïåðåäî ìíîé áûëè ïîñòàâëåíû ñëåäóþùèå öåëè:}

                _{- îçíàêîìèòüñÿ ñ ÿçûêîì ïðîãðàììèðîâàíèÿ Íîðìà è èçó÷èòü åãî;}

                _{- èçó÷èòü ñòðóêòóðó òðàíñëÿòîðà ñ ÿçûêà ïðîãðàììèðîâàíèÿ Íîðìà;}

                _{- îçíàêîìèòüñÿ ñ ìåòîäàìè ëåêñè÷åñêîãî àíàëèçà;}

                _{- èçó÷èòü ñòðóêòóðó ëåêñè÷åñêîãî àíàëèçàòîðà;}

                _{- ðàçðàáîòàòü ñòðóêòóðó äàííûõ äëÿ ðåàëèçàöèè ëåêñè÷åñêîãî àíàëèçàòîðà;}

                _{- íàïèñàòü ôóíêöèþ, íà âõîä êîòîðîé ïîñòóïàåò ñïèñîê ëåêñåì, à íà âûõîäå - ñïèñîê ñïèñêîâ. Ýëåìåíòîì ýòîãî ñïèñêà ñïèñêîâ ÿâëÿåòñÿ ñïèñîê ëåêñåì, êîòîðûé ïðåäñòàâëÿåò ñîáîé îäíî ïðåäëîæåíèå ïðîãðàììû, íàïèñàííîé íà Íîðìå, îêàí÷èâàþùååñÿ òî÷êîé. Ò.å. ýòà ôóíêöèÿ “ðåæåò” ïîñòóïàþùèé íà âõîä ñïèñîê ëåêñåì ïî òî÷êàì.}

_{2. Îáùàÿ õàðàêòåðèñòèêà ÿçûêà Íîðìà}

                _{2.1 ßçûê ïðîãðàììèðîâàíèÿ Íîðìà.}

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

                _{ßçûê Íîðìà ÿâëÿåòñÿ ñïåöèëèçèðîâàííûì ÿçûêîì è ïðåäíàçíà÷åí äëÿ ñïåöèôèêàöèè ÷èñëåííûõ ìåòîäîâ ðåøåíèÿ çàäà÷ ìàòåìàòè÷åñêîé ôèçèêè. Èçíà÷àëüíî îí áûë îðèåíòèðîâàí íà ðåøåíèå çàäà÷ ìàòåìàòè÷åñêîé ôèçèêè ðàçíîñòíûìè ìåòîäàìè, îäíàêî ìîæåò áûòü èñïîëüçîâàí äëÿ ðåøåíèÿ áîëåå øèðîêîãî êëàññà âû÷èñëèòåëüíûõ çàäà÷.}

                _{Òèïè÷íûé ïðîöåññ ðåøåíèÿ çàäà÷è èç îáëàñòè ìàòåìàòè÷åñêîé ôèçèêè ñîñòîèò èç ñëåäóþùèõ ýòàïîâ.}

                _{1. Ïîñòàíîâêà çàäà÷è. Âûõîäîì ýòîãî ýòàïà ÿâëÿåòñÿ îáû÷íî ñèñòåìà äèôôåðåíöèàëüíûõ óðàâíåíèé, îïèñûâàþùèõ çàäà÷ó.}

                _{2. Âûáîð ïðîñòðàíñòâåííî-âðåìåííîé ñåòêè è äèñêðåòèçàöèÿ óðàâíåíèé ñ ïîìîùüþ îäíîãî èç ðàçíîñòíûõ ìåòîäîâ.}

                _{3. Âûáîð ìåòîäà ðåøåíèÿ äèñêðåòíûõ óðàâíåíèé.  ðåçóëüòàòå ïîëó÷àþòñÿ ôîðìóëû (ñîîòíîøåíèÿ), îïèñûâàþùèéå íåîáõîäèìûå âû÷èñëåíèÿ â óçëàõ ñåòêè.}

                _{4. Ïðîãðàììèðîâàíèå ïîëó÷åííûõ ôîðìóë íà íåêîòîðîì ÿçûêå, êîòîðûé îáåñïå÷èâàåò ðåøåíèå çàäà÷è íà âû÷èñëèòåëüíîé ìàøèíå.}

                _{Ãëàâíàÿ èäåÿ, ïîëîæåííàÿ â îñíîâó ÿçûêà Íîðìà, çàêëþ÷àåòñÿ â òîì, ÷òî ïîëó÷åííûå ïðèêëàäíûì ñïåöèàëèñòîì â ïðîöåññå ðåøåíèÿ ïðèêëàäíîé çàäà÷è ðàñ÷åòíûå ôîðìóëû ïî÷òè íåïîñðåäñòâåííî èñïîëüçóþòñÿ äëÿ ââîäà â âû÷èñëèòåëüíóþ ñèñòåìó è ïðîâåäåíèÿ ñ÷åòà.}

                _{Òàêèì îáðàçîì, ÿçûê Íîðìà äàåò ïðèêëàäíîìó ìàòåìàòèêó âîçìîæíîñòü ñôîðìóëèðîâàòü ñâîþ çàäà÷ó â ïðèâû÷íûõ äëÿ íåãî òåðìèíàõ. Îðãàíèçàöèÿ ïðîöåññà âû÷èñëåíèé ñ ó÷åòîì àðõèòåêòóðû ÝÂÌ (âîçìîæíîñòåé ïàðàëëåëüíîé, âåêòîðíîé îáðàáîòêè è ò. ï.) - çòî çàäà÷à òðàíñëÿòîðà ñ ÿçûêà Íîðìà.}

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

                _{Çàïèñü íà ÿçûêå Íîðìà - ýòî, ïî ñóùåñòâó, ñòðîãàÿ çàïèñü ÷èñëåííûõ ìåòîäîâ ðåøåíèÿ ìàòåìàòè÷åñêîé çàäà÷è, çàïèñü åùå íå àëãîðèòìîâ, à ïðîñòî ðàñ÷åòíûõ ôîðìóë è îñòàëüíîé íåîáõîäèìîé èíôîðìàöèè, êîòîðóþ íåîáõîäèìî çíàòü, ÷òîáû íàïèñàòü ïðîãðàììó äëÿ ÝÂÌ.}

                _{Îòìåòèì, ÷òî â çàïèñè íà Íîðìå íå òðåáóåòñÿ íèêàêîé èíôîðìàöèè î ïîðÿäêå ñ÷åòà, ñïîñîáàõ îðãàíèçàöèè âû÷èñëèòåëüíûõ (öèêëè÷åñêèõ) ïðîöåññîâ. Ïîðÿäîê ïðåäëîæåíèé ÿçûêà ìîæåò áûòü ïðîèçâîëüíûì - èíôîðìàöèîííûå âçàèìîñâÿçè áóäóò âûÿâëåíû è ó÷òåíû ïðè îðãàíèçàöèè ïðîöåññà ñ÷åòà òðàíñëÿòîðîì.}

                _{Âûáîð óðîâíÿ ÿçûêà Íîðìà îïðåäåëÿåò õàðàêòåðíóþ åãî ÷åðòó - â ýòîì ÿçûêå íåò íåîáõîäèìîñòè ââîäèòü òàêèå ïîíÿòèÿ, êàê îïåðàòîð ïðèñâàèâàíèÿ è âîçìîæíîñòü ïåðåïðèñâàèâàíèÿ çíà÷åíèé (òèïà õ:=õ+1) è îïåðàòîðû ïåðåõîäà. Íàëè÷èå òàêèõ ïîíÿòèé â òðàäèöèîííûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ îáúÿñíÿåòñÿ íåîáõîäèìîñòüþ ôîðìóëèðîâêè êîíêðåòíîãî àëãîðèòìà ñ ó÷åòîì âîïðîñîâ ýêîíîìèè è ðàñïðåäåëåíèÿ ïàìÿòè, ïîðÿäêà âûïîëíåíèÿ îïåðàòîðîâ è ò. ï. Ïîáî÷íûé ýôôåêò â ÿçûêå Íîðìà îòñóòñòâóåò ïî îïðåäåëåíèþ.}

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

                _{Íåïðîöåäóðíîñòü ÿçûêà Íîðìà ïîçâîëÿåò ïðåîäîëåòü åùå îäíó òðóäíîñòü, ñâÿçàííóþ ñ ðàñïàðàëëåëèâàíèåì àëãîðèòìà ïðè ñ÷åòå íà ÝÂÌ, äîïóñêàþùèõ ñîâìåùåíèå îïåðàöèé. Èçâåñòíûå ìåòîäû ðàñïàðàëëåëèâàíèÿ ïîñëåäîâàòåëüíûõ àëãîðèòìîâ îñíîâàíû íà âûÿâëåíèè, ïðè íåêîòîðûõ îãðàíè÷åíèÿõ, ÷àñòåé àëãîðèòìà, êîòîðûå ìîæíî âûïîëíÿòü íåçàâèñèìî, â ñîîòâåòñòâèè ñ çàäàííûì êðèòåðèåì ïàðàëëåëèçìà - àñèíõðîííûå âû÷èñëåíèÿ, ñèíõðîííûå è ò. ï. Îäíàêî, âûÿâëåíèå âçàèìîñâÿçåé â óæå ñôîðìèðîâàííîì ïîñëåäîâàòåëüíîì àëãîðèòìå ÿâëÿåòñÿ íååñòåñòâåííîé è òðóäíîé çàäà÷åé, òàê êàê àíàëèçèðóåìàÿ ôîðìóëèðîâêà, êàê ïðàâèëî, íàñûùåíà èçáûòî÷íûìè âçàèìîñâÿçÿìè (òèïà ââåäåíèÿ ðàáî÷èõ ïåðåìåííûõ äëÿ ýêîíîìèè ïàìÿòè, êîíêðåòíûõ ñïîñîáàõ îðãàíèçàöèè öèêëîâ è ò. ï.). Âîîáùå ãîâîðÿ, íè îòêóäà íå ñëåäóåò, ÷òî ïîñëåäîâàòåëüíûé àëãîðèòì íàäî òðàíñëèðîâàòü â ïàðàëëåëüíûé, à íå îïðåäåëÿòü ïàðàëëåëüíûé ñðàçó ïî íåïðîöåäóðíîé çàïèñè.}

                _{Ýòè ñâîéñòâà, è íåêîòîðûå äðóãèå îãðàíè÷åíèÿ, ïîçâîëÿþò ñòðîãî îáîñíîâàòü ðàçðåøèìîñòü ñèíòåçà âûõîäíîé ïðîãðàììû, òàê êàê â äîñòàòî÷íî îáùåé ïîñòàíîâêå ðåøåíèå ýòîé çàäà÷è ïðèâîäèò ê çíà÷èòåëüíûì ìàòåìàòè÷åñêèì òðóäíîñòÿì - îíà ìîæåò îêàçàòüñÿ NP-ïîëíîé ëèáî âîîáùå íåðàçðåøèìîé. Ñ äðóãîé ñòîðîíû, èññëåäîâàíèÿ, ñâÿçàííûå ñ ðàçðàáîòêîé è ïðèìåíåíèåì ÿçûêà Íîðìà ïîêàçûâàþò, ÷òî èìåþùèåñÿ îãðàíè÷åíèÿ ïðèåìëèìû ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ.}

                _{Èñõîäíàÿ ïðîãðàììà, íàïèñàííàÿ íà ÿçûêå ïðîãðàììèðîâàíèÿ Íîðìà, ïðåäñòàâëÿåòñÿ â èñõîäíîì ôàéëå ïî ñëåäóþùèì ïðàâèëàì:}

                _{- òåêñò êàæäîãî èç ðàçäåëîâ Íîðìà-ïðîãðàììû çàïèñûâàåòñÿ â áåñôîðìåííîì ïðåäñòàâëåíèè. Ïðè ïåðåíîñå îïèñàíèÿ èëè îïåðàòîðà íà ñëåäóþùóþ ñòðîêó çàïðåùàåòñÿ ðàçðûâàòü êëþ÷åâûå ñëîâà, èäåíòèôèêàòîðû, êîíñòàíòû, â îñòàëüíîì ïðàâèëà ïåðåíîñà ïðîèçâîëüíûå.}

                _{- êëþ÷åâûå ñëîâà, èäåíòèôèêàòîðû, êîíñòàíòû, îòäåëÿþòñÿ äðóã îò äðóãà ïðîáåëàìè, ñïåöèàëüíûìè ñèìâîëàìè, ñèìâîëàìè êîíöà ñòðîêè. Ïðîáåëû ÿâëÿþòñÿ íåçíà÷àùèìè ñèìâîëàìè: ãðóïïà ïðîáåëîâ òðàêòóåòñÿ êàê îäèí ïðîáåë.}

                _{- ñòðîêà, íà÷èíàþùàÿñÿ ñî çíàêà “!”, ÿâëÿåòñÿ êîììåíòàðèåì. Êîììåíòàðèè âíóòðè îïèñàíèé è âíå ðàçäåëîâ çàïðåùåíû.}

                _{- êîììåíòàðèè ìîãóò èñïîëüçîâàòüñÿ âíóòðè îïåðàòîðà ASSUME â ñëåäóþùèõ ñèòóàöèÿõ: ìåæäó çàãîëîâêîì îïåðàòîðà ASSUME è òåëîì îïåðàòîðà; ìåæäó ñîîòíîøåíèÿìè â òåëå îïåðàòîðà.}

_{âíóòðè áëîêà INITIAL...END INITIAL;}

_{âíóòðè òåëà èòåðàöèè.}

                _{- òåêñò ïðîãðàììû ïðåäíàçíà÷åííûé äëÿ òðàíñëÿöèè, çàêàí÷èâàåòñÿ ñòðîêîé ÅÎÐ: èíôîðìàöèÿ, ñëåäóþùàÿ äàëåå òðàíñëÿòîðîì íå îáðàáàòûâàåòñÿ.}

                _{- èíôîðìàöèÿ, ðàñïîëîæåííàÿ â èíòåðâàëå îò “?”, ñòîÿùåãî â ïåðâîé ïîçèöèè, äî çíàêà “?”, ñòîÿùåãî òàêæå â ïåðâîé ïîçèöèè, òðàíñëÿòîðîì íå îáðàáàòûâàåòñÿ. ýòà âîçìîæíîñòü ïîçâîëÿåò âûáèðàòü èç èñõîäíîãî ôàéëà òå ðàçäåëû, êîòîðûå íåîþõîäèìî òðàíñëèðîâàòü.            .
                2.2 Ñòðóêòóðà òðàíñëÿòîðà ñ ÿçûêà Íîðìà.}

                _{Òðàíñëÿòîð ñ ÿçûêà ïðîãðàììèðîâàíèÿ Íîðìà óæå íàïèñàí íà ÿçûêå Ðåôàë. Òåïåðü áûëî ðåøåíî ïåðåâåñòè òðàíñëÿòîð ñ ÿçûêà ïðîãðàììèðîâàíèÿ Íîðìà íà ÿçûê ïðîãðàììèðîâàíèÿ Ñè. ßçûê ïðîãðàììèðîâàíèÿ Ñè áûë âûáðàí ïî ñëåäóþùèì ïðè÷èíàì:}

                _{- ñðåäè ñîâðåìåííûõ ÿçûêîâ ïðîãðàììèðîâàíèÿ ÿçûê Ñè ÿâëÿåòñÿ îäíèì èç íàèáîëåå ðàñïðîñòðàíåííûõ;}

                _{- ÿçûê Ñè óíèâåðñàëåí è íàèáîëåå ýôôåêòèâíî åãî ïðèìåíåíèå â çàäà÷àõ ñèñòåìíîãî ïðîãðàììèðîâàíèÿ - ðàçðàáîòêå òðàíñëÿòîðîâ, îïåðàöèîííûõ ñèñòåì, ýêðàííûõ èíòåðôåéñîâ, èíñòðóìåíòàëüíûõ ñðåäñòâ;}

                _{- ðàçðàáîò÷èêàìè ÿçûêà Íîðìà óæå íàïèñàí èíòåðôåéñ íà ÿçûêå Ñè, ïîçâîëÿþùèé çàêîí÷åííûå ÷àñòè òðàíñëÿòîðà, íàïèñàííûå íà Ðåôàëå, çàìåíÿòü íà çàêîí÷åííûå ÷àñòè òðàíñëÿòîðà, íàïèñàííûå íà Ñè, äëÿ îòëàäêè òðàíñëÿòîðà.}

                _{Òðàíñëÿòîð ñ ÿçûêà ïðîãðàììèðîâàíèÿ èìååò ñëåäóþùóþ ñòðóêòóðó:}

_Ðèñ.1

_{òåêñò ëåêñè÷åñêèé      ñèíòàêñè÷åñêèé       îïð. ïîðÿäêà          êîäîãåíåðàöèÿ  FORTRAN}

           _{àíàëèç                    àíàëèç         âû÷èñë. è ðàñïàð.}

                     _{ìåíåäæåð ïàìÿòè                   òàáëèöû}

                _{Íà âõîä ëåêñè÷åñêîãî àíàëèçàòîðà ïîñòóïàåò òåêñò èñõîäíîé ïðîãðàììû, íàïèñàííîé íà ÿçûêå ïðîãðàììèðîâàíèÿ Íîðìà. Íà âûõîäå - îòñîðòèðîâàííûé ïî îïèñàíèÿì, îïåðàòîðàì è èòåðàöèÿì ñïèñîê ñïèñêîâ. Ýëåìåíòîì ýòîãî ñïèñêà ñïèñêîâ ÿâëÿåòñÿ ñïèñîê ëåêñåì, êîòîðûé ïðåäñòàâëÿåò ñîáîé îäíî ïðåäëîæåíèå ïðîãðàììû, íàïèñàííîé íà Íîðìå, îêàí÷èâàþùååñÿ òî÷êîé.}

                _{Äàëåå ýòîò ñïèñîê ñïèñêîâ ïîñòóïàåò íà âõîä ñèíòàêñè÷åñêîãî àíàëèçàòîðà. Íà âûõîäå ñèíòàêñè÷åñêèé àíàëèçàòîð âûäàåò òàáëèöû îïèñàíèé, òàáëèöû îïåðàòîðîâ.}

                _{Ýòè òàáëèöû ïîñòóïàþò íà âõîä ñëåäóþùåãî ýòàïà, ãäå ïðîèñõîäèò îïðåäåëåíèå ïîðÿäêà âû÷èñëåíèé è ðàçäåëåíèå íà ïàðàëëåëüíûå âåòâè âû÷èñëåíèé, íåçàâèñÿùèå äðóã îò äðóãà. Íà âûõîäå ïîëó÷àåì âíóòðåííèå êîäû.}

                _{Âíóòðåííèå êîäû ïîñòóïàþò íà âõîä êîäîãåíåðàöèè. Âûõîäîì êîäîãåíåðàöèè ÿâëÿåòñÿ ïðîãðàììà íà ÿçûêå Ôîðòðàí.}

                _{Òàêæå èìååòñÿ Ìåíåäæåð ïàìÿòè, ïîçâîëÿþùèé ðàáîòàòü ñ ïàìÿòüþ.  Âçàèìîäåéñòâèå ñ Ìåíåäæåðîì ïàìÿòè ïðîèñõîäèò íà âñåõ ÷åòûðåõ ýòàïàõ. Âçàèìîäåéñòâèå ñ òàáëèöàìè òàêæå ïðîèñõîäèò íà âñåõ ÷åòûðåõ ýòàïàõ.}

                _{2.3 Çíàêîìñòâî ñ ìåòîäàìè ëåêñè÷åñêîãî àíàëèçà.}

                _{ ðåçóëüòàòå âûïîëíåíèÿ ýòîãî çàäàíèÿ ÿ óçíàëà, ÷òî â ëåêñè÷åñêîì àíàëèçå ïðèìåíÿþòñÿ è èñïîëüçóþòñÿ ñëåäóþùèå ìåòîäû:}

                _{- êîíå÷íûå àâòîìàòû è À-ãðàììàòèêè, îïèñûâàþùèå êîíå÷íûå àâòîìàòû;}

                _{2.4 Ñòðóêòóðà ëåêñè÷åñêîãî àíàëèçàòîðà.}

                _{Íà âõîä ëåêñè÷åñêîãî àíàëèçàòîðà ïîñòóïàåò òåêñò èñõîäíîé ïðîãðàììû, íàïèñàííîé íà ÿçûêå Íîðìà. Ïðîãðàììà, íàïèñàííàÿ íà ÿçûêå Íîðìà, òðàíñëèðóåòñÿ ïî ðàçäåëàì. Ñíà÷àëà òðàíñëèðóåòñÿ îäèí ðàçäåë, ïîñëå òîãî, êàê îí áóäåò îòòðàíñëèðîâàí, íà÷íåòñÿ òðàíñëÿöèÿ ñëåäóþùåãî ðàçäåëà.}

                _{Íà ïåðâîì øàãå ïðîèñõîäèò ÷òåíèå èñõîäíîãî òåêñòà ïðîãðàììû íà Íîðìå è ðàçáèåíèå åãî íà ëåêñåìû. Ðåçóëüòàòîì ýòîãî øàãà ÿâëÿåòñÿ ñïèñîê ëåêñåì.}

                _{Ëþáîé ýëåìåíò-ðàçäåëà (îïèñàíèå, îïåðàòîð, èòåðàöèÿ) çàêàí÷èâàåòñÿ òî÷êîé. Ïîýòîìó íà ñëåäóþùåì øàãå ïðîèñõîäèò “ðåçàíèå” ñïèñêà ëåêñåì ïî òî÷êàì.  ðåçóëüòàòå ýòîé ïðîöåäóðû ïîëó÷àåì ñïèñîê ñïèñêîâ. Ýëåìåíòîì ýòîãî ñïèñêà ñïèñêîâ ÿâëÿåòñÿ ñïèñîê ëåêñåì, êîòîðûé ïðåäñòàâëÿåò ñîáîé îäíî ïðåäëîæåíèå ïðîãðàììû, íàïèñàííîé íà Íîðìå, îêàí÷èâàþùååñÿ òî÷êîé.}

                _{Íà ñëåäóþùåì øàãå ïðîèñõîäèò ñîðòèðîâêà ñïèñêà ñïèñêîâ ïî îïèñàíèÿì, îïåðàòîðàì è èòåðàöèÿì.  ðåçóëüòàòå ïîëó÷àåì ñïèñîê ñïèñêîâ, â êîòîðîì ñíà÷àëà èäóò âñå îïèñàíèÿ ðàçäåëà, çàòåì âñå îïåðàòîðû ðàçäåëà, è â çàêëþ÷åíèè, âñå èòåðàöèè ðàçäåëà.}

                _{Ïîñëå ýòîãî îòñîðòèðîâàííûé ñïèñîê ñïèñêîâ ïîäàåòñÿ íà âõîä ñèíòàêñè÷åñêîãî àíàëèçàòîðà.}

                _{2.5 Ðàçðàáîòêà ñòðóêòóð äàííûõ äëÿ ðåàëèçàöèè ëåêñè÷åñêîãî àíàëèçàòîðà}

                _{Äëÿ ðåàëèçàöèè ëåêñè÷åñêîãî àíàëèçàòîðà â ìîåé ÷àñòè ðàáîòû áûëè ðàçðàáîòàíû ñëåäóþùèå ñòðóêòóðû äàííûõ:}

                _{1) ñïèñîê ëåêñåì ïðåäñòàâëåí ñëåäóþùåé ñòðóêòóðîé:}

                _{struct spis} 

                                _{{ int p1,p2;}

                                _{struct spis *next;} rec1;}

                _{ãäå ð1 è ð2 - ïîëÿ òèïà öåëîå, êîòîðûå îçíà÷àþò íîìåð òàáëèöû è íîìåð â òàáëèöå ñîîòâåòñòâåííî;  ýòèì íîìåðàì ÷åðåç òàáëèöû óñòàíàâëèâàåòñÿ â ñîîòâåòñòâèå êîíêðåòíàÿ ëåêñåìà, áóäü òî èäåíòèôèêàòîð, êëþ÷åâîå ñëîâî, êîíñòàíòà, çíàê îïåðàöèè èëè ðàçäåëèòåëü;}

                _{next - ÿâëÿåòñÿ óêàçàòåëåì íà ñëåäóþùèé ýëåìåíò ñïèñêà ëåêñåì;}

                _{Äàííàÿ ñòðóêòóðà ïðåäñòàâëåíà ããðàôè÷åñêè íà ðèñ.2}

_Ðèñ.2

                _{2) ñïèñîê ñïèñêîâ ïðåäñòàâëåí ñëåäóþùåé ñòðóêòóðîé:}

                _{struct spspis}

                                _{{int p1,p2;} 

                                _{struct spis *next;}

                                _{struct spspis *link;} rec2;}

                _{ãäå ð1 è ð2 - ïîëÿ òèïà öåëîå, êîòîðûå îçíà÷àþò íîìåð òàáëèöû è íîìåð â òàáëèöå ñîîòâåòñòâåííî; ýòèì íîìåðàì ÷åðåç òàáëèöû óñòàíàâëèâàåòñÿ â ñîîòâåòñòâèå êîíêðåòíàÿ ëåêñåìà, áóäü òî èäåíòèôèêàòîð, êëþ÷åâîå ñëîâî, êîíñòàíòà, çíàê îïåðàöèè èëè ðàçäåëèòåëü;}

                _{next - ÿâëÿåòñÿ óêàçàòåëåì íà ñòóêòóðó ñïèñîê ëåêñåì;}

                _{link - ÿâëÿåòñÿ óêàçàòåëåì íà ñëåäóþùèé ýëåìåíò ñïèñêà ñïèñêîâ.}

                _{Ýëåìåíòîì ýòîãî ñïèñêà ñïèñêîâ ÿâëÿåòñÿ ñïèñîê ëåêñåì, êîòîðûé ïðåäñòàâëÿåò ñîáîé îäíî ïðåäëîæåíèå ïðîãðàììû, íàïèñàííîé íà Íîðìå, îêàí÷èâàþùååñÿ òî÷êîé, à ñïèñîê ñïèñêîâ ïðåäñòàâëÿåò ñîáîé ñîîòâåòñòâåííî ñïèñîê ïðåäëîæåíèé. Äàííàÿ ñòðóêòóðà ïðåäñòàâëåíà ãðàôè÷åñêè íà ðèñ.3}

_Ðèñ.3

                _{2.6  Ôóíêöèÿ “ðåçàíèÿ” ñïèñêà ëåêñåì ïî òî÷êàì.}

                _{ äàííîì çàäàíèè òðåáîâàëîñü íàïèñàòü ôóíêöèþ, íà âõîä êîòîðîé ïîñòóïàåò ñïèñîê ëåêñåì, à íà âûõîäå ïîëó÷àåòñÿ ñïèñîê ñïèñêîâ. Ýëåìåíòîì ýòîãî ñïèñêà ñïèñêîâ ÿâëÿåòñÿ ñïèñîê ëåêñåì, êîòîðûé ïðåäñòàâëÿåò ñîáîé îäíî ïðåäëîæåíèå ïðîãðàììû, íàïèñàííîé íà Íîðìå, îêàí÷èâàþùååñÿ òî÷êîé. Ò.å. ýòà ôóíêöèÿ “ðåæåò” ïîñòóïàþùèé íà âõîä ñïèñîê ëåêñåì ïî òî÷êàì, à íà âûõîäå âûäàåò ñïèñîê ïðåäëîæåíèé, êàæäîå èç êîòîðûõ çàêàí÷èâàåòñÿ òî÷êîé è ïðåäñòàâëÿåòñÿ ñïèñêîì ëåêñåì.}

                _{Íèæå ïðèâåäåíû àëãîðèòì â âèäå áëîê ñõåìû è ñàìà ôóíêöèÿ.}

_{#include<stdio.h>      /*ïîäêëþ÷åíèå ôàéëà stdio.h*/}

_{#include<alloc.h>      /* ïîäêëþ÷åíèå ôàéëà alloc.h */}

_{#include<process.h>   /* ïîäêëþ÷åíèå ôàéëà sprocess.h */}

_{struct spis                           /*îáúÿâëåíèå ñòðóêòóðû ñïèñêà, êàæäûé ýëåìåíò */}

                _{{ int p1,p2;               /*êîòîðîãî èìååò äâà ïîëÿ òèïà öåëîå, (ð1-íîìåð*/}

                _{struct spis *next;} rec1;/*òàáëèöû, ð2-íîìåð â òàáëèöå) è ïîëå-óêàçàòåëü*/}

                                       _{/*íà ñëåäóþùèé ýëåìåíò ñïèñêà*/}

_{struct spspis                        /* îáúÿâëåíèå ñòðóêòóðû ñïèñêà ñïèñêîâ, êàæäûé */}

                _{{int p1,p2;               /*ýëåìåíò êîòîðîãî èìååò äâà ïîëÿ òèïà öåëîå,*/}

                                      _{ð1-íîìåð òàáëèöû,ð2- íîìåð â òàáëèöå*/}

                _{struct spspis *link;    /* óêàçàòåëü íà ñëåäóþùèé ýëåìåíò ñïèñêà ñïèñêîâ*/}

                _{struct spis *next;} rec2;/*óêàçàòåëü íà ñòðóêòóðó ñïèñîê*/}

_{struct spis *f,*q,*r;              /* óêàçàòåëü íà ñòðóêòóðó ñïèñîê */}

_{struct spspis *t1,*t;             /* óêàçàòåëü íà ñòðóêòóðó ñïèñîê ñïèñêîâ*/}

_{struct spspis *tochka(p)   /*îáúÿâëåíèå ôóíêöèè, âîçðàùàþùåé óêàçàòåëü íà                                                                    ñïèñîê ñïèñêîâ*/}

_{struct spis *p;          /*àðãóìåíòîì ôóíêöèè ÿâëÿåòñÿ óêàçàòåëü íà ñïèñîê*/}

_{

_{f=p;    /*ïðñâàèâàíèå ðàáð÷åé ïåðåìåííîé çíà÷åíèÿ àðãóìåíòà ôóíêöèè*/}

_{t=malloc(sizeof( rec2));/*ñîçäàíèå 1-îãî ýëåìåíòà ñïèñêà ñïèñêîâ*/}

_{t1=t;  /* ïðñâàèâàíèå ðàáî÷åé ïåðåìåííîé óêàçàòåëÿ íà ñïèñîê ñïèñêîâ*/}

_{while(f!=NULL) /*òåëî äàííîãî îïåðàòîðà áóäåò âûïîëíÿòüñÿ äî òåõ ïîð, ïîêà íå                               äîñòîãíåì êîíöà ñïèñêà ëåêñåì*/}

_{{              t1->p1=f->p1;/*ïðèñâàèâàíèå çíà÷åíèé ïîëÿì ýëåìåíòà ñïèñêà ñïèñêîâ*/}

                _{t1->p2=f->p2;}

                _f=f->next;

                _{if (f!=NULL)}

                _{{  t1->next=malloc(sizeof(rec1));/*ñîçäàíèå 1-îãî ýëåìåíòà ñïèñêà â ñïèñêå                                                                                                ñïèñêîâ*/}

                      _{q=t1->next;/* ïðèñâàèâàíèå ðàáî÷åé            ïåðåìåííîé óêàçàòåëÿ íà                                                       ýëåìåíò ñïèñêà*/}

                      _{do  /*ñîçäàíèå ñàìîãî ñïèñêà ëåêñåì â ñïèñêå ñïèñêîâ*/}

                      _{

                                _{q->p1=f->p1;/*ïðèñâàèâàíèå çíà÷åíèé ïîëÿì ýëåìåíòà ñïèñêà*/}

                                _q->p2=f->p2;

                                _{if ((q->p1!=1) && (q->p2!=1))/*åñëè äàííàÿ ëåêñåìà íå ÿâëÿåòñÿ                                                                                           òî÷êîé*/}

                                _{{ q->next=malloc(sizeof(rec1));//*òî ñîçäàåì íîâûé ýëåìåíò ñïèñêà */}

                                _q=q->next;

                                _}

                                _{else { t1->link=malloc(sizeof(rec2));/*èíà÷å, ñîçäàåì íîâûé ýëåìåíò                                                                                                          ñïèñêà ñïèñêîâ*/}

                                    _t1=t1->link;

                                _};

                _f=f->next;

                _}

                _{while(((q->p1!=1) && (q->p2!=1)) || (f!=NULL)) ;/*òåëî äàííîãî îïåðàòîðà âûïîëäíÿåòñÿ äî òåõ ïîð,ïîêà ëèáî íå áóäåò ïðî÷èòàíà òî÷êà, ëèáî íå áóäåò äîñòèãíóò êîíåö ñïèñêà ëåêñåì,íà êîòîðûé óêàçûâàåò àðãóìåíò ôóíêöèè*/}

                _}

_}

_{return(t);/*ôóíêöèÿ âîçâðàùàåò óêàçàòåëü íà ñïèñîê ñïèñêîâ*/}

_}

_íà÷àëî

_f:=p

_{t:=new rec2}

_t:=t1

                                                      _{f<>NULL          íåò}

          _äà

_t1.p1:=f.p1

_t1.p2:=f.p2

_f:=f.next

                                                     _{f<>NULL             íåò}

_{t1.next:=new rec1}

_q:=t1.next

_q.p1:=f.p1

_q.p2:=f.p2

_{(q.p1<>1)&(q.p2<>1)}

         _{q.next:=new rec1                                                    t1.link:=new rec2}

         _{q:=q.next                                                                  t1:=t1.link}

_f:=f.next

_{((q.p1<>1)&(q.p2<>1))or(f<>NULL)}

         _äà                       

                                                    _íåò

_return(t)

_êîíåö

                _{3. ÇÀÊËÞ×ÅÍÈÅ}

                _{Â ðåçóëüòàòå ïðîäåëàííîé ðàáîòû ìíîþ áûëè äîñòèãíóòû ñëåäóþþùèå öåëè:}

                _{- îçíàêîìèëàñü è èçó÷èëà íåïðîöåäóðíûé ÿçûê ïðîãðàììèðîâàíèÿ Íîðìà, ïðåäíàçíà÷åííûé äëÿ çàïèñè ÷èñëåííûõ ìåòîäîâ ðåøåíèÿ çàäà÷ ìàòåìàòè÷åñêîé ôèçèêè ðàçíîñòíûìè ìåòîäàìè;}

                _{- èçó÷èëà ñòðóêòóðó òðàíñëÿòîðà ñ ÿçûêà ïðîãðàììèðîâàíèÿ Íîðìà;}

                _{- îçíàêîìèëàñü ñ ìåòîäàìè ëåêñè÷åñêîãî àíàëèçà;}

                _{- èçó÷èëà ñòðóêòóðó ëåêñè÷åñêîãî àíàëèçàòîðà;}

                _{- ðàçðàáîòàëà ñòðóêòóðó äàííûõ ñâîåé ÷àñòè çàäàíèÿ äëÿ ðåàëèçàöèè       ëåêñè÷åñêîãî àíàëèçàòîðà;}

                _{-íàïèñàëà ôóíêöèþ, íà âõîä êîòîðîé ïîñòóïàåò ñïèñîê ëåêñåì, à íà âûõîäå ïîëó÷àåì ñïèñîê ñïèñêîâ. Ýëåìåíòîì ýòîãî ñïèñêà ñïèñêîâ ÿâëÿåòñÿ ñïèñîê ëåêñåì, êîòîðûé ïðåäñòàâëÿåò ñîáîé îäíî ïðåäëîæåíèå ïðîãðàììû, íàïèñàííîé íà Íîðìå, îêàí÷èâàþùååñÿ òî÷êîé. Ò.å. ýòà ôóíêöèÿ “ðåæåò” ïîñòóïàþùèé íà âõîä ñïèñîê ëåêñåì ïî òî÷êàì, à íà âûõîäå ïîëó÷àåì ñïèñîê ïðåäëîæåíèé, êàæäîå èç êîòîðûõ çàêàí÷èâàåòñÿ òî÷êîé è ïðåäñòàâëÿåòñÿ ñïèñêîì ëåêñåì.}

                _{Ïðîãðàììà íàõîäèòñÿ  íà ñòàäèè ðàçðàáîòêè.  Çàâåðøåíèå ðàáîòû ïëàíèðóåòñÿ â ñëåäóþùåì ñåìåñòðå. Çàäàíèå íà ÓÈР è ÊÏ âûïîëíèëà ïîëíîñòüþ.}

_{Ñïèñîê ëèòåðàòóðû:}

                _{À.Í. Àíäðèàíîâ, Ê.Í. Åôèìêèí, È.Á. Çàäûõàéëî, Í.Â. Ïîääåðþãèíà “ßçûê Íîðìà”}

                _{À.Í. Àíäðèàíîâ, Ê.Í. Åôèìêèí, È.Á. Çàäûõàéëî “Íåïðîöåäóðíûé ÿçûê Íîðìà è ìåòîäû åãî ðåàëèçàöèè”}

                _{À.Á. Áóãåðÿ “Ðåàëèçàöèÿ ìàòåìàòè÷åñêèõ ôóíêöèé ÿçûêà Íîðìà äëÿ ðàñïðåäåëåííûõ âûñèñëèòåëüíûõ ñèñòåì”}

_{Ïðèëîæåíèå 1.}

_{#include<stdio.h>}

_{#include<alloc.h>}

_{#include<process.h>}

_{struct spis}

      _{{ int p1,p2;}

                _{struct spis *next;} rec1;}

_{struct spspis}

      _{{int p1,p2;}

       _{struct spspis *link;}

       _{struct spis *next;} rec2;}

_{struct spis *f,*q,*r;}

_{struct spspis *t1,*t;}

_{extern struct spspis *(tochka(struct spis*));}

_{struct spspis *tochka(p)}

_{struct spis *p;}

_{

_f=p;

_{t=malloc(sizeof( rec2));}

_t1=t;

_{while(f!=NULL)}

_{{  t1->p1=f->p1;}

   _{t1->p2=f->p2;}

   _f=f->next;

   _{if (f!=NULL)}

   _{{  t1->next=malloc(sizeof(rec1));}

      _do

      _{{q->p1=f->p1;}

                _q->p2=f->p2;

                _{if ((q->p1!=1) && (q->p2!=1))}

                   _{{ q->next=malloc(sizeof(rec1));}

                     _{q=q->next;   }}

                _{else { t1->link=malloc(sizeof(rec2));}

                       _{t1=t1->link;};}

                _f=f->next;}

                _{while(((q->p1!=1) && (q->p2!=1)) || (f!=NULL)) ;}

    _}

_}

  _return(t);}

_{main() {}

_{tochka(r);return(0);}

_}