2.1. Ìàòåìàòè÷åñêàÿ ìîäåëü
Ïîäðîáíî ìàòåìàòè÷åñêàÿ ìîäåëü, ëåæàùàÿ â îñ-íîâå àíàëèçàòîðà Treevial îïèñàíà â [5]. Çäåñü ìû îãðàíè÷èìñÿ êðàòêèì îïèñàíèåì1.
Îäíèì èç îñíîâíûõ ïîíÿòèé ìîäåëè ÿâëÿåòñÿ ñèíòàêñè÷åñêàÿ ñòðóêòóðà íàïðàâëåííîå äåðåâî ñ ðàçìå÷åííûìè óçëàìè è äóãàìè, â êîòîðîì íå-êîòîðûå äóãè ìîãóò ïîìå÷àòüñÿ ñïåöèàëüíûì ñèì-âîëîì w. Ñ êàæäûì óçëîì äåðåâà ñîîòíîñèòñÿ ëèíãâèñòè÷åñêàÿ õàðàêòåðèñòèêà, ïðåäñòàâëÿåìàÿ íàáîðîì ïàð âèäà <àòðèáóò,çíà÷åíèå>. Íàïðèìåð, ñóùåñòâèòåëüíîå â èìåíèòåëüíîì ïàäåæå îïèñû-âàåòñÿ ñëåäóþùèì îáðàçîì:
(POS = N,CAS = nom)
Êðîìå ëèíãâèñòè÷åñêîé õàðàêòåðèñòèêè, ñ êàæ-äûì óçëîì ñîîòíîñèòñÿ íåêîòîðûé èíòåðâàë ÷èñ-ëîâîé îñè ìåñòî äàííîãî óçëà (ñèíòàêñè÷åñêîé ãðóïïû èëè âàðèàíòà ìîðôîëîãè÷åñêîãî àíàëèçà) â òåêñòå. Òå óçëû, èç êîòîðûõ èñõîäèò w-ñâÿçü, ñîîòâåòñòâóþò ñèíòàêñè÷åñêèì ãðóïïàì, à òå óçëû, èç êîòîðûõ íå èñõîäèò íè îäíîé w-ñâÿçè, ñîîò-âåòñòâóþò âàðèàíòàì ìîðôîëîãè÷åñêîãî àíàëèçà ñëîâ. Ïîääåðåâüÿ, «âèñÿùèå» íà w-ñâÿçÿõ, âîñ-ïðèíèìàþòñÿ êàê âëîæåííûå â óçåë, èç êîòîðîãî èñõîäèò w-ñâÿçü. Âñå èíòåðâàëû, ñîîòíåñåííûå ñ óçëàìè òàêèõ ïîääåðåâüåâ, îáÿçàòåëüíî âëîæåíû â èíòåðâàë, ñîîòíåñåííûé ñ óçëîì, èç êîòîðîãî èñ-õîäèò w-ñâÿçü. Áëàãîäàðÿ ýòîìó ïðàâèëó ñòàíîâèò-ñÿ âîçìîæíûì îòîáðàæàòü ñèíòàêñè÷åñêèå ñòðóê-òóðû ïîäîáíî òîìó, êàê ýòî ñäåëàíî íà ðèñ. 1.
Òàêîé ìåòîä âèçóàëèçàöèè àêòèâíî èñïîëüçóåòñÿ â ñèñòåìå Treeton.
Íà ñèíòàêñè÷åñêóþ ñòðóêòóðó íàêëàäûâàåòñÿ åùå îäíî îãðàíè÷åíèå: èíòåðâàëû, ñîîòíåñåííûå ñ óç-ëàìè, èç êîòîðûõ íå âûõîäèò íè îäíà w-ñâÿçü (òðèâèàëüíûìè óçëàìè), íå ìîãóò ïåðåñåêàòüñÿ äðóã ñ äðóãîì. Ýòî óñëîâèå ñîîòâåòñòâóåò òîìó ôàêòó,
1 Ïî ñðàâíåíèþ ñ [5] ìû ñîçíàòåëüíî ïðèâîäèì çäåñü áî-ëåå óçêóþ ìîäåëü.  íåé íå äîïóñêàþòñÿ ñèíòàêñè÷åñêèå íóëè
óçëû ñèíòàêñè÷åñêîé ñòðóêòóðû, ñ êîòîðûìè íå ñîîòíåñåí èíòåðâàë ÷èñëîâîé îñè. Ýòî ñâÿçàíî ñ òåì, ÷òî òåêóùàÿ âåð-ñèÿ àíàëèçàòîðà Treevial íå ïîääåðæèâàåò ðàáîòó ñ
ñèíòàêñè-÷åñêèìè íóëÿìè.
÷òî â êîíòåêñòå íåêîòîðîé ñèíòàêñè÷åñêîé ñòðóê-òóðû îäíîìó îòðåçêó òåêñòà íå ìîãóò ñîîòâåòñòâî-âàòü äâå ìîðôîëîãè÷åñêèå èíòåðïðåòàöèè.
Ê íàáîðó ñèíòàêñè÷åñêèõ ñòðóêòóð (ìóëüòèñòðóê-òóðå) ìîãóò ïðèìåíÿòüñÿ ñèíòàêñè÷åñêèå ïðàâèëà.
Ñèíòàêñè÷åñêîå ïðàâèëî ýòî äåðåâî, ÷àñòü óç-ëîâ è äóã êîòîðîãî îáúÿâëÿþòñÿ èñõîäíûìè, à
÷àñòü ïðîèçâîäíûìè. Ïðè ïðèìåíåíèè ïðàâèëà îïðåäåëåííûå óçëû è äóãè ìóëüòèñòðóêòóðû ñîïî-ñòàâëÿþòñÿ ñ èñõîäíûìè óçëàìè è äóãàìè ïðàâè-ëà. Åñëè ñîïîñòàâëåíèå âîçìîæíî, òî ïðîèçâîäèò-ñÿ ïîïûòêà äîáàâèòü â ìóëüòèñòðóêòóðó íîâûå óçëû è äóãè, ñîîòâåòñòâóþùèå ïðîèçâîäíûì óçëàì è äóãàì ïðàâèëà. Åñëè ïîñëå ýòîé ïðîöåäóðû ìóëü-òèñòðóêòóðà ïðîäîëæàåò äîïóñêàòü ðàçáèåíèå íà ñèíòàêñè÷åñêèå ñòðóêòóðû, òî ïðàâèëî ñ÷èòàåòñÿ ïðèìåíèìûì. Áîëåå ïîäðîáíî ñèíòàêñè÷åñêèå ïðàâèëà îïèñàíû â [4,5].  ðàìêàõ ýòîãî ðàçäåëà âàæíî çàôèêñèðîâàòü òî, ÷òî ñèíòàêñè÷åñêèå ïðà-âèëà ïðèìåíÿþòñÿ ê íàáîðó ñèíòàêñè÷åñêèõ ñòðóê-òóð (ìóëüòèñòðóêñòðóê-òóðå) è ïðè ýòîì îáðàçóåòñÿ íî-âûé íàáîð èç ìåíüøåãî êîëè÷åñòâà ñèíòàêñè÷åñ-êèõ ñòðóêòóð (íîâàÿ ìóëüòèñòðóêòóðà), ò.ê. ÷àñòü ñèíòàêñè÷åñêèõ ñòðóêòóð èñõîäíîãî íàáîðà «ñêëå-èâàåòñÿ» ìåæäó ñîáîé ñ ïîìîùüþ ïðîèçâîäíûõ äóã ïðàâèëà. Òî, ÷òî ñàìî ïðàâèëî ÿâëÿåòñÿ äåðå-âîì, ïîçâîëÿåò ãàðàíòèðîâàòü, ÷òî â ñëó÷àå, êîãäà âñå ñèíòàêñè÷åñêèå ñòðóêòóðû èñõîäíîãî íàáîðà ïîó÷àñòâóþò â ïðàâèëå (êàêîé-ëèáî óçåë êàæäîé ñòðóêòóðû ñîîòíåñåòñÿ ñ êàêèì-ëèáî óçëîì ïðàâè-ëà), ðåçóëüòèðóþùàÿ ìóëüòèñòðóêòóðà áóäåò ñîñòî-ÿòü èç îäíîé ñèíòàêñè÷åñêîé ñòðóêòóðû. Áóäåì â òàêèõ ñëó÷àÿõ ãîâîðèòü, ÷òî âàðèàíò ïðèìåíåíèÿ ñèíòàêñè÷åñêîãî ïðàâèëà èíòåãðèðóåò íàáîð ñèí-òàêñè÷åñêèõ ñòðóêòóð (ðèñ.2).
Äëÿ èçëîæåíèÿ ïðèíöèïà ðàáîòû àíàëèçàòîðà íàì ïîòðåáóåòñÿ ïîíÿòèå ñèíòàêñè÷åñêîé èíòåð-ïðåòàöèè. Ââåäåì ýòî ïîíÿòèå ïî èíäóêöèè:
1) Âàðèàíò ìîðôîëîãè÷åñêîãî àíàëèçà ÿâëÿåòñÿ ñèíòàêñè÷åñêîé èíòåðïðåòàöèåé (òðèâèàëüíîé).
2) Íàáîð ïîïàðíî íå ïåðåñåêàþùèõñÿ èíòåð-ïðåòàöèé â ñî÷åòàíèè ñ âàðèàíòîì ïðèìåíåíèÿ ñèíòàêñè÷åñêîãî ïðàâèëà, èíòåãðèðóþùèì ýòîò íàáîð, ÿâëÿåòñÿ ñèíòàêñè÷åñêîé èíòåðïðåòàöèåé.
Áóäåì ñ÷èòàòü, ÷òî ñóùåñòâóåò øòðàôíàÿ ôóí-êöèÿ P, ñòàâÿùåå â ñîîòâåòñòâèå êàæäîé ñèíòàê-ñè÷åñêîé èíòåðïðåòàöèè âåêòîð, âñå êîìïîíåíòû êîòîðîãî íåîòðèöàòåëüíûå äåéñòâèòåëüíûå ÷èñ-ëà. Ïðî òî, êàê çàäàåòñÿ ýòà ôóíêöèÿ, ìîæíî ïðî÷åñòü â [4].
Ðèñ. 1. Ïðèìåð ñèíòàêñè÷åñêîé ñòðóêòóðû
Ðèñ. 2. Âàðèàíò ïðèìåíåíèÿ ñèíòàêñè÷åñêîãî ïðàâèëà èíòåãðèðóåò íàáîð ñèíòàêñè÷åñêèõ ñòðóêòóð
2.2. Ñèíòàêñè÷åñêèé ãèïåðãðàô
Äëÿ ñîõðàíåíèÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ àíàëè-çàòîð Treevial èñïîëüçóåò ñïåöèàëüíóþ ñòðóêòóðó, íàçûâàåìóþ ñèíòàêñè÷åñêèì ãèïåðãðàôîì (î ãèïåðã-ðàôàõ â êîìïüþòåðíîé ëèíãâèñòèêå ñì. [8]). Óçëàìè ãèïåðãðàôà ÿâëÿþòñÿ âñå âàðèàíòû ìîðôîëîãè÷åñ-êîãî àíàëèçà ñëîâ âõîäíîãî ïðåäëîæåíèÿ, à òàêæå âñå ñèíòàêñè÷åñêèå ãðóïïû, êîòîðûå ìîãóò âîçíèêàòü â ïðîöåññå àíàëèçà. Ãèïåðäóãàìè ãðàôà ÿâëÿþòñÿ âà-ðèàíòû èñïîëüçîâàíèÿ ñèíòàêñè÷åñêèõ ïðàâèë.
Ñ êàæäûì óçëîì ãðàôà ñîîòíîñÿòñÿ ñèíòàêñè÷åñêèå èíòåðïðåòàöèè, âíóòðè êîòîðûõ èñïîëüçóåòñÿ äàí-íûé óçåë. Ñèíòàêñè÷åñêèé ãèïåðãðàô íàñûùàåòñÿ ïîñòåïåííî.  íà÷àëüíûé ìîìåíò âðåìåíè îí ñîäåð-æèò òîëüêî âàðèàíòû ìîðôîëîãè÷åñêîãî àíàëèçà â êà÷åñòâå óçëîâ è íè îäíîé ãèïåðäóãè.  ïðîöåññå àíà-ëèçà ñïåöèàëüíûå àãåíòû-ãðàôîïîñòðîèòåëè (ñì.
íèæå) äîáàâëÿþò âîçìîæíûå ãèïåðäóãè â ãðàô, èñ-õîäÿ èç ñèñòåìû ñèíòàêñè÷åñêèõ ïðàâèë. Ïðè ýòîì, äëÿ âàðèàíòîâ èñïîëüçîâàíèÿ òåõ ïðàâèë, â êîòîðûõ ïðèñóòñòâóþò ïðîèçâîäíûå óçëû, â ãðàô äîáàâëÿþò-ñÿ íîâûå óçëû, êîòîðûå âïîñëåäñòâèè òîæå ó÷èòûâà-þòñÿ àãåíòàìè-ãðàôîïîñòðîèòåëÿìè. Ñëåäóåò îòìå-òèòü, ÷òî äëÿ òåõ ñèñòåì ïðàâèë, ñ êîòîðûìè ðàáîòà-ëè àâòîðû, ïðîöåäóðà ïîëíîãî ïîñòðîåíèÿ ñèíòàê-ñè÷åñêîãî ãèïåðãðàôà (ðàñ÷åò âñåõ âàðèàíòîâ èñïîëü-çîâàíèÿ ïðàâèë äëÿ âñåõ óçëîâ, âêëþ÷àÿ ïðîèçâîä-íûå, ïðîèçâîäíûå îò ïðîèçâîäíûõ è ò. ï.) çàíèìàëà âðåìÿ, çíà÷èòåëüíî ìåíüøåå, ÷åì âåñü îñòàëüíîé àíàëèç. Åñòü îñíîâàíèÿ ïîëàãàòü, ÷òî äëÿ ÷èñòûõ ãðàììàòèê çàâèñèìîñòåé ýòà ïðîöåäóðà âñåãäà áóäåò áûñòðîé îñíîâíîå âðåìÿ áóäåò çàíèìàòü äàëüíåé-øèé àíàëèç, à äëÿ ÷èñòûõ ãðàììàòèê ñîñòàâëÿþùèõ, íàîáîðîò, îñíîâíîå âðåìÿ áóäåò çàíèìàòü ïðîöåäó-ðà ïîñòðîåíèÿ ãèïåðãïðîöåäó-ðàôà.
2.3. Àëãîðèòì ñèíòàêñè÷åñêîãî àíàëèçà
Îñíîâíóþ èäåþ àëãîðèòìà, èñïîëüçóåìîãî àíàëè-çàòîðîì Treevial, ìîæíî âûðàçèòü ñëåäóþùèì îá-ðàçîì: â ðåçóëüòàòå ïàðàëëåëüíîé ðàáîòû ìíîãèõ ðàçíîôóíêöèîíàëüíûõ ïðîöåññîâ ìíîæàòñÿ, ïî-ñòîÿííî ñîðòèðóþòñÿ ïî êà÷åñòâó è íàíîñÿòñÿ íà
ñèíòàêñè÷åñêèé ãèïåðãðàô ñèíòàêñè÷åñêèå èíòåð-ïðåòàöèè.  òåõ ñëó÷àÿõ, êîãäà îáíàðóæèâàåòñÿ èíòåðïðåòàöèÿ, ïîêðûâàþùàÿ âåñü èñõîäíûé òåêñò, ñîäåðæàùàÿ ìàðêåð çàêîí÷åííîñòè (â òåêóùåé ðåàëèçàöèè òàêèì ìàðêåðîì ÿâëÿåòñÿ ïàðà SYNTTYPE=Clause), ýòà èíòåðïðåòàöèÿ äîáàâëÿ-åòñÿ â ñîðòèðîâàííóþ î÷åðåäü ðåçóëüòàòîâ.
Àíàëèçàòîð Treevial èñïîëüçóåò äëÿ
ñèíòàêñè-÷åñêîãî àíàëèçà ñèñòåìó ñîðòèðîâàííûõ î÷åðåäåé, íàáîð àãåíòîâ (ïàðàëëåëüíûõ ïðîöåññîâ, äåéñòâó-þùèõ íåçàâèñèìî äðóã îò äðóãà) è óæå óïîìèíàâ-øèéñÿ ñèíòàêñè÷åñêèé ãèïåðãðàô.
Àãåíòû äåëÿòñÿ íà ÷åòûðå òèïà:
àãåíòû, ïîäñ÷èòûâàþùèå øòðàôû;
àãåíòû, ïðèìåíÿþùèå ïðàâèëà;
àãåíòû, êîìáèíèðóþùèå èíòåðïðåòàöèè;
àãåíòû-ãðàôîïîñòðîèòåëè.
Êàæäûé èç òèïîâ àãåíòîâ áóäåò îõàðàêòåðèçî-âàí íèæå. Ñëåäóåò ñêàçàòü, ÷òî, íåñìîòðÿ íà ðàç-íîîáðàçèå ôóíêöèé, âñå àãåíòû äåéñòâóþò ïî îä-íîìó ïðèíöèïó: àãåíò îáðàùàåòñÿ ê âõîäíîé î÷åðå-äè (äëÿ êàæäîãî òèïà àãåíòà âõîäíàÿ î÷åðåäü èçâåñò-íà), áåðåò èç íåå îáúåêò, ÷òî-òî ñ íèì äåëàåò, ñîçäà-âàÿ ïðè ýòîì íîâûå îáúåêòû, ïîñëå ÷åãî êëàäåò íî-âûå îáúåêòû â äðóãèå î÷åðåäè è, åñëè òðåáóåòñÿ, äî-ïîëíÿåò ñèíòàêñè÷åñêèé ãèïåðãðàô òîé èëè èíîé èíôîðìàöèåé.
Àíàëèçàòîð èñïîëüçóåò ïÿòü î÷åðåäåé:
î÷åðåäü îöåíåííûõ èíòåðïðåòàöèé;
î÷åðåäü ïàð âèäà <èíòåðïðåòàöèÿ, ïðèìåíåíèå ïðàâèëà>;
î÷åðåäü íåîöåíåííûõ èíòåðïðåòàöèé;
î÷åðåäü óçëîâ ãèïåðãðàôà, êîòîðûå íåîáõîäè-ìî îáñ÷èòàòü;
î÷åðåäü ðåçóëüòàòîâ.
Ïîñêîëüêó î÷åðåäè ñîäåðæàò ðàçëè÷íûå òèïû îáúåêòîâ, ïðèíöèïû ñîðòèðîâêè äëÿ íèõ íåìíîãî ðàçëè÷àþòñÿ, íî âñå ýòè ïðèíöèïû îáúåäèíÿåò îäíî íàèìåíåå øòðàôîâàííûé îáúåêò äîëæåí áûòü ïåðâûì â î÷åðåäè (øòðàôíûå âåêòîðû, ñî-ïîñòàâëÿåìûå ñ èíòåðïðåòàöèÿìè, ñðàâíèâàþòñÿ ìåæäó ñîáîé ïî íîðìå Ýâêëèäà).
Ïðîöåññ ðàáîòû àíàëèçàòîðà ïðåäñòàâëÿåò ñî-áîé ñëåäóþùåå:
•  íà÷àëüíûé ìîìåíò âðåìåíè âñå î÷åðåäè ïóñòû.
•  î÷åðåäü óçëîâ ãèïåðãðàôà, êîòîðûå íåîáõî-äèìî îáñ÷èòàòü, íà÷èíàþò ïîñòóïàòü âàðèàíòû ìîðôîëîãè÷åñêîãî àíàëèçà.
• Àãåíòû-ãðàôîïîñòðîèòåëè íà÷èíàþò çàáèðàòü óçëû èç î÷åðåäè óçëîâ ãèïåðãðàôà è äîáàâëÿòü â íåãî ãèïåðäóãè, èñõîäÿ èç çàäàííîé ñèñòåìû ñèí-òàêñè÷åñêèõ ïðàâèë. Ïðè ýòîì ïîñëå îáñ÷åòà êàæ-äîãî óçëà, ñîîòâåòñòâóþùåãî âàðèàíòó
ìîðôîëîãè-÷åñêîãî àíàëèçà, îíè ñîçäàþò â ýòîì óçëå òðèâè-àëüíóþ èíòåðïðåòàöèþ è äîáàâëÿþò åå â î÷åðåäü îöåíåííûõ èíòåðïðåòàöèé (øòðàôíîé âåêòîð äëÿ âñåõ òðèâèàëüíûõ èíòåðïðåòàöèé ðàâåí 0).
• Àãåíòû, ïðèìåíÿþùèå ïðàâèëà, íà÷èíàþò çà-áèðàòü èç î÷åðåäè îöåíåííûõ èíòåðïðåòàöèé ñèí-òàêñè÷åñêèå èíòåðïðåòàöèè è, ïîëüçóÿñü ãèïåðäó-ãàìè ñèíòàêñè÷åñêîãî ãðàôà, èñêàòü ïîäõîäÿùèå ïðàâèëà äëÿ ïðèìåíåíèÿ. Êàæäóþ ïîòåíöèàëüíî âîçìîæíóþ ïàðó îíè êëàäóò â î÷åðåäü ïàð âèäà
<èí-òåðïðåòàöèÿ, ïðèìåíåíèå ïðàâèëà>. Åñëè ýòè àãåí-òû îáíàðóæèâàþò ñèíòàêñè÷åñêóþ èíòåðïðåòàöèþ, ïîêðûâàþùóþ âåñü èñõîäíûé òåêñò è ñîäåðæàùóþ ìàðêåð çàêîí÷åííîñòè, îíè ïåðåêëàäûâàþò ýòó èí-òåðïðåòàöèþ â î÷åðåäü ðåçóëüòàòîâ.
• Àãåíòû, êîìáèíèðóþùèå èíòåðïðåòàöèè, çà-áèðàþò èç î÷åðåäè ïàðû âèäà <èíòåðïðåòàöèÿ, ïðèìåíåíèå ïðàâèëà> è äëÿ êàæäîé ïàðû èùóò îñòàëüíûå èíòåðïðåòàöèè, êîòîðûå âìåñòå ñ áàçî-âîé ìîãëè áû áûòü èíòåãðèðîâàíû ñ ïîìîùüþ ïðèìåíåíèÿ ïðàâèëà. Âñå òàêèå êîìáèíàöèè ïî îïðåäåëåíèþ ÿâëÿþòñÿ èíòåðïðåòàöèÿìè.  ìî-ìåíò êîìáèíèðîâàíèÿ àãåíòû èñïîëüçóþò èíôîð-ìàöèþ î òîì, êàêèå èíòåðïðåòàöèè íà äàííûé ìîìåíò óæå ñîîòíåñåíû ñ óçëàìè ãèïåðãðàôà, ó÷à-ñòâóþùèìè â ïðèìåíåíèè ïðàâèëà. Ïðèíöèï îï-òèìàëüíîñòè ðàáîòàåò è çäåñü: àãåíòû ñòðåìÿòñÿ ñíà÷àëà êîìáèíèðîâàòü áîëåå õîðîøèå èíòåðïðå-òàöèè. Ïîëó÷àåìûå èíòåðïðåòàöèè ïîìåùàþòñÿ â î÷åðåäü íåîöåíåííûõ èíòåðïðåòàöèé. Ïåðåä òåì, êàê ñîçäàòü íåîöåíåííóþ èíòåðïðåòàöèþ, àãåíòû âçàèìîäåéñòâóþò ñî ñïåöèàëüíûì ðàçäåëÿåìûì îáúåêòîì, áëîêèðóþùèì âîçíèêíîâåíèå îäèíàêî-âûõ èíòåðïðåòàöèé.
• Àãåíòû, ïîäñ÷èòûâàþùèå øòðàôû, çàáèðàþò èç î÷åðåäè íåîöåíåííûõ èíòåðïðåòàöèé ñèíòàê-ñè÷åñêèå èíòåðïðåòàöèè, îöåíèâàþò èõ ñ ïîìî-ùüþ ôóíêöèè P è äîáàâëÿþò â î÷åðåäü îöåíåí-íûõ èíòåðïðåòàöèé è â ñèíòàêñè÷åñêèé ãèïåðã-ðàô (âî âñå óçëû, êîòîðûå ñîäåðæèò äàííàÿ èí-òåðïðåòàöèÿ).  ýòîò ìîìåíò êðóã çàìûêàåòñÿ.
Ðèñ. 3 èëëþñòðèðóåò ôóíêöèîíèðîâàíèå îïèñàí-íîé ñèñòåìû.
Ñëåäóåò îòìåòèòü, ÷òî àíàëèçàòîð ìîæåò ðàáî-òàòü ñ ó÷åòîì îãðàíè÷åíèé íà øòðàôíîé âåêòîð.
Îãðàíè÷åíèÿ çàäàþòñÿ ïåðåä íà÷àëîì àíàëèçà. Îíè ìîãóò áûòü çàäàíû êàê ïîêîìïîíåíòíî (ïðÿìîó-ãîëüíàÿ îáëàñòü), òàê è â âèäå îãðàíè÷åíèÿ íà ýâêëèäîâó íîðìó øòðàôíîãî âåêòîðà (ñôåðè÷åñ-êàÿ îáëàñòü).  ñëó÷àå, êîãäà îãðàíè÷åíèÿ çàäàíû, àãåíòû, ñ÷èòàþùèå øòðàôû, íå ïåðåêëàäûâàþò â î÷åðåäü îöåíåííûõ èíòåðïðåòàöèé òå èíòåðïðåòà-öèè, øòðàôíîé âåêòîð êîòîðûõ íå óäîâëåòâîðÿåò îãðàíè÷åíèÿì.
2.4. Ïðîãðàììíàÿ ðåàëèçàöèÿ
Êàê óæå ãîâîðèëîñü âñÿ ñèñòåìà Treeton íàïèñàíà íà ÿçûêå Java. Ýòîò ÿçûê îêàçàëñÿ îñîáåííî óäîá-íûì äëÿ ðåàëèçàöèè àíàëèçàòîðà Treevial, òàê êàê â íåì ïðåäóñìîòðåíî âñå íåîáõîäèìîå äëÿ ýôôåê-òèâíîãî ìíîãîíèòåâîãî ïðîãðàììèðîâàíèÿ (ñð. [13]).
Êàæäûé àãåíò ðàáîòàåò â îòäåëüíîé íèòè. Âñþäó, ãäå ýòî âîçìîæíî, âçàèìîäåéñòâèå àãåíòîâ ñ ãè-ïåðãðàôîì ïðîèñõîäèò àñèíõðîííî. Âçàèìîäåéñòâèå àãåíòîâ ñ î÷åðåäÿìè ïðîèñõîäèò ñèíõðîííî, ò.ê.
îáúåêòû â î÷åðåäÿõ äîëæíû ïðàâèëüíî ñîðòèðî-âàòüñÿ. Äëÿ ðåàëèçàöèè ñîðòèðîâàííûõ î÷åðåäåé áûë èñïîëüçîâàí äîñòàòî÷íî ýôôåêòèâíûé êëàññ PriorityBlockingQueue èç ïàêåòà java.util.concurrent.
Ñëåäóåò îòìåòèòü, ÷òî ìíîãîíèòåâàÿ àðõèòåêòóðà àíàëèçàòîðà êàæåòñÿ îñîáåííî ïåðñïåêòèâíîé
òå-ïåðü, êîãäà ïðîöåññîðîâ ó ÏÊ ñòàíîâèòñÿ ãîä îò ãîäà âñå áîëüøå.
Ïðîöåäóðà ïîèñêà âîçìîæíîñòåé ïðèìåíåíèÿ ïðàâèë áûëà ñïåöèàëüíûì îáðàçîì îïòèìèçèðî-âàíà. Ïðè çàãðóçêå ñèñòåìû ñèíòàêñè÷åñêèõ ïðà-âèë íàä âñåìè øàáëîíàìè, ïðèñóòñòâóþùèìè â ïðàâèëàõ, ñòðîèòñÿ èíäåêñ, êîòîðûé âïîñëåäñòâèè èñïîëüçóåòñÿ àãåíòàìè-ãðàôîïîñòðîèòåëÿìè äëÿ ýôôåêòèâíîãî ïîèñêà âàðèàíòîâ ïðèìåíåíèÿ ïðà-âèë. öåëÿõ ýêîíîìèè ñèíòàêñè÷åñêèå èíòåðïðåòà-öèè íå õðàíÿòñÿ â ïàìÿòè â âèäå äåðåâüåâ. Êàæ-äàÿ èíòåðïðåòàöèÿ õðàíèòñÿ êàê òðîéêà <áàçîâàÿ èíòåðïðåòàöèÿ, ïðèìåíåíèå ïðàâèëà, ìàññèâ ññûëîê íà îñòàëüíûå èíòåðïðåòàöèè>.  òîò ìîìåíò, êîã-äà òðåáóåòñÿ ïðîèçâåñòè êàêîå-òî àëãîðèòìè÷åñêè íàãðóæåííîå äåéñòâèå íàä èíòåðïðåòàöèåé (íà-ïðèìåð, ïîñ÷èòàòü åå øòðàô), èíòåðïðåòàöèÿ êî-ïèðóåòñÿ â ñïåöèàëüíóþ ñòðóêòóðó, ïîñòðîåííóþ íà õýø-òàáëèöàõ è îïòèìèçèðîâàííóþ äëÿ ýô-ôåêòèâíîé ðàáîòû ñ äåðåâüÿìè.
Ðèñ. 3. Öèêë ñèíòàêñè÷åñêîãî àíàëèçà.  öåíòðå èçîáðàæåí ñèíòàêñè÷åñêèé ãèïåðãðàô. Âîêðóã íåãî, íà÷èíàÿ ñâåðõó, ïî ÷àñîâîé ñòðåëêå ðàñïîëî-æåíû: î÷åðåäü îöåíåííûõ èíòåðïðåòàöèé, î÷åðåäü ðåçóëüòàòîâ, î÷åðåäü ïàð âèäà <èíòåðïðåòàöèÿ,
ïðèìåíåíèå ïðàâèëà>, î÷åðåäü íåîöåíåííûõ èíòåðïðåòàöèé è î÷åðåäü óçëîâ ãèïåðãðàôà.
Ôèãó-ðû ëþäåé îáîçíà÷àþò àãåíòîâ. Êðóæêàìè
îáîçíà-÷åíû óçëû ãèïåðãðàôà. Çàêðàøåííûìè è íåçàêðà-øåííûìè òðåóãîëüíèêàìè îáîçíà÷åíû ñîîòâåò-ñòâåííî îöåíåííûå è íåîöåíåííûå èíòåðïðåòàöèè.
Çàìêíóòûå ïóíêòèðíûå êîíòóðû îáîçíà÷àþò ãèïåðäóãè ñèíòàêñè÷åñêîãî ãðàôà
2.5. Ðàçðûâíîñòü èíòåðïðåòàöèé è çíàêè ïóíêòóàöèè
Ñëåäóåò îòìåòèòü, ÷òî äî ñèõ ïîð íà ðàçðûâíîñòü ñèíòàêñè÷åñêèõ èíòåðïðåòàöèé íå íàêëàäûâàëîñü íèêàêèõ îãðàíè÷åíèé. Âñå âûøåñêàçàííîå áóäåò ðà-áîòàòü äëÿ èíòåðïðåòàöèé, â êîòîðûõ ïðîïóùåíû îòäåëüíûå ñëîâà èëè ãðóïïû ñëîâ. Îäíàêî, äîïó-ùåíèå òàêèõ èíòåðïðåòàöèé ìíîãîêðàòíî óâåëè÷è-âàåò êîìáèíàòîðèêó. Áîëåå òîãî, àâòîðû ãîòîâû ñäå-ëàòü ñëåäóþùåå ïðåäïîëîæåíèå: ìîæíî ñîçäàòü ñè-ñòåìó ïðàâèë, àäåêâàòíî îïèñûâàþùóþ ðóññêèé ÿçûê, ïðè èñïîëüçîâàíèè êîòîðîé ëþáàÿ
ñèíòàêñè-÷åñêàÿ ñòðóêòóðà áóäåò âûâîäèìà áåç èñïîëüçîâà-íèÿ ðàçðûâíûõ èíòåðïðåòàöèé. Ìû ïðèíÿëè ðåøå-íèå çàïðåòèòü ñîçäàðåøå-íèå ðàçðûâíûõ èíòåðïðåòàöèé â õîäå àíàëèçà.  çàùèòó òàêîãî ðåøåíèÿ ïðèâåäåì ïðèìåð, èëëþñòðèðóþùèé òî, êàê ïðîñòûì èçìå-íåíèåì ñèíòàêñè÷åñêîãî ïðàâèëà ìîæíî äîáèòüñÿ òîãî, ÷òî ðàçðûâíûå èíòåðïðåòàöèè â êîíêðåòíîì ñëó÷àå ïåðåñòàþò áûòü íóæíûìè. Ðàññìîòðèì ôðà-çó: «Îí ïåðâûì ïðèõîäèò». Ïðåäïîëîæèì, ÷òî ñèí-òàêñè÷åñêîå ïðàâèëî äëÿ ýòîé êîíñòðóêöèè áóäåò ñëåäóþùèì: åñëè ñóùåñòâèòåëüíîå â èìåíèòåëüíîì ïàäåæå ñîåäèíåíî ñ ãëàãîëîì ñâÿçüþ predic, è ãäå-òî åñòü ïðèëàãàòåëüíîå â òâîðèòåëüíîì ïàäåæå, ñî-ãëàñîâàííîå ñ ñóùåñòâèòåëüíûì ïî ðîäó è ÷èñëó, òî ñîåäèíèòñÿ ïðèëàãàòåëüíîå ñ ãëàãîëîì ñâÿçüþ circI. ×òîáû ïðèìåíèòü òàêîå ïðàâèëî, íåîáõîäèìî ñíà÷àëà ñîåäèíèòü ãëàãîë è ñóùåñòâèòåëüíîå, à äëÿ ýòîãî â ðàññìàòðèâàåìîì ïðèìåðå òðåáóåòñÿ ñîçäà-íèå ðàçðûâíîé èíòåðïðåòàöèè. Ïðåäïîëîæèì òå-ïåðü, ÷òî ïðàâèëî èìååò ñëåäóþùèé âèä: åñëè ãäå-òî åñòü ñóùåñòâèòåëüíîå â èìåíèòåëüíîì ïàäåæå, ãëàãîë è ïðèëàãàòåëüíîå â òâîðèòåëüíîì ïàäåæå, ñî-ãëàñîâàííîå ñ ñóùåñòâèòåëüíûì ïî ðîäó è ÷èñëó, òî ñîåäèíèòñÿ ïðèëàãàòåëüíîå ñ ãëàãîëîì ñâÿçüþ circI, à ñóùåñòâèòåëüíîå ñ ãëàãîëîì ñâÿçüþ predic.
Ïðè òàêîì ïîäõîäå ïðàâèëî ïðèìåíèòñÿ êî âñåìó ïðåäëîæåíèþ ñðàçó, è îáðàçîâàíèÿ ðàçðûâíîé èí-òåðïðåòàöèè íå ïîíàäîáèòñÿ.
Ñëåäóåò óïîìÿíóòü åùå îäèí ïðèíöèï, çàëî-æåííûé â àíàëèçàòîð Treevial: çíàêè ïóíêòóàöèè ðàññìàòðèâàþòñÿ àíàëèçàòîðîì êàê ýëåìåíòû «ìîð-ôîëîãè÷åñêîãî» ïîêðûòèÿ. Ýòî îçíà÷àåò, ÷òî, åñëè íåêàÿ èíòåðïðåòàöèÿ íå èñïîëüçóåò âñåõ çíàêîâ ïðåïèíàíèÿ, âñòðå÷àåìûõ â ïðåäëîæåíèè, òî îíà çàâåäîìî íå ìîæåò ñ÷èòàòüñÿ ïðàâèëüíûì ðåçóëü-òàòîì àíàëèçà. Õîòÿ òàêîé ïîäõîä è òðåáóåò äîñ-òàòî÷íî êðîïîòëèâîãî îïèñàíèÿ ïðàâèë ïóíêòóà-öèè, îí èìååò è ñâîè ïðåèìóùåñòâà. Âî-ïåðâûõ, â ñî÷åòàíèè ñ ïðèíöèïîì íåðàçðûâíîñòè èíòåðïðå-òàöèé îí ñîñòàâëÿåò ìîùíûé îãðàíè÷èâàþùèé ôàêòîð äëÿ ïåðåáîðíîãî ïðîöåññà ÷åðåç çíàê ïðåïèíàíèÿ ìîæåò «ïåðåøàãíóòü» òîëüêî òà èí-òåðïðåòàöèÿ, êîòîðàÿ èñïîëüçóåò åãî âíóòðè ñåáÿ.
Âî-âòîðûõ, óäàåòñÿ åäèíîîáðàçíî îïèñûâàòü ÿâëå-íèÿ íà ñòûêå ïóíêòóàöèè è ñèíòàêñèñà (ñð. ñî÷è-íèòåëüíûé ñîþç è ñî÷èíèòåëüíàÿ çàïÿòàÿ).