В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 11
Текст из файла (страница 11)
Íî òîãäà äëÿ ëþáîãî i > 0 àâòîìàò ìîæåò ïðîäåëàòü ïîñëåäîâàòåëüíîñòü òàêòîâ (q0 , xyz) `∗ (q1 , y i z) `+(q1 , y i−1 z) ...`+ (q1 , yz)`+ (q1 , z)`∗ (q2 , e)Òàêèì îáðàçîì, xy i z ∈ L äëÿ âñåõ i > 1. Ñëó÷àé i = 0òî åñòü xy ∈ L òàêæå î÷åâèäåí.Ñ ïîìîùüþ ëåììû î ðàçðàñòàíèè ìîæíî ïîêàçàòü, ÷òîíå ÿâëÿåòñÿ ðåãóëÿðíûì ìíîæåñòâîì ÿçûê L={0n 1n |n > 1}.Äîïóñòèì, ÷òî L ðåãóëÿðåí. Òîãäà äëÿ äîñòàòî÷íî áîëüøîãî n 0n 1n ìîæíî ïðåäñòàâèòü â âèäå xyz , ïðè÷¼ì y 6= eè xy i z ∈ L äëÿ âñåõ i > 0.
Åñëè y ∈ 0+ èëè y ∈ 1+ , òîxz = xy 0 z ∈/ L. Åñëè y ∈ 0+ 1+ , òî xyyz ∈/ L. Ïîëó÷èëè ïðîòèâîðå÷èå. Ñëåäîâàòåëüíî, L íå ìîæåò áûòü ðåãóëÿðíûììíîæåñòâîì.3.5. Ïðîãðàììèðîâàíèå ëåêñè÷åñêîãî àíàëèçàÊàê óæå îòìå÷àëîñü ðàíåå, ëåêñè÷åñêèé àíàëèçàòîð(ËÀ) ìîæåò áûòü îôîðìëåí êàê ïîäïðîãðàììà. Ïðè îáðàùåíèè ê ËÀ, âûðàáàòûâàþòñÿ êàê ìèíèìóì äâà ðåçóëüòàòà:òèï âûáðàííîé ëåêñåìû è å¼ çíà÷åíèå (åñëè îíî åñòü).Åñëè ËÀ ñàì ôîðìèðóåò òàáëèöû îáúåêòîâ, îí âûäà¼ò òèï ëåêñåìû è óêàçàòåëü íà ñîîòâåòñòâóþùèé âõîä âòàáëèöå îáúåêòîâ.
Åñëè æå ËÀ íå ðàáîòàåò ñ òàáëèöàìè3.5. Ïðîãðàììèðîâàíèå ëåêñè÷åñêîãî àíàëèçà71îáúåêòîâ, îí âûäà¼ò òèï ëåêñåìû, à å¼ çíà÷åíèå ïåðåäà¼òñÿ, íàïðèìåð, ÷åðåç íåêîòîðóþ ãëîáàëüíóþ ïåðåìåííóþ.Ïîìèìî çíà÷åíèÿ ëåêñåìû, ýòà ãëîáàëüíàÿ ïåðåìåííàÿ ìîæåò ñîäåðæàòü íåêîòîðóþ äîïîëíèòåëüíóþ èíôîðìàöèþ:íîìåð òåêóùåé ñòðîêè, íîìåð ñèìâîëà â ñòðîêå è ò.ä. Ýòàèíôîðìàöèÿ ìîæåò èñïîëüçîâàòüñÿ â ðàçëè÷íûõ öåëÿõ, íàïðèìåð, äëÿ äèàãíîñòèêè. îñíîâå ËÀ ëåæèò äèàãðàììà ïåðåõîäîâ ñîîòâåòñòâóþùåãî êîíå÷íîãî àâòîìàòà.
Îòäåëüíàÿ ïðîáëåìà çäåñü àíàëèç êëþ÷åâûõ ñëîâ. Êàê ïðàâèëî, êëþ÷åâûå ñëîâà ýòî âûäåëåííûå èäåíòèôèêàòîðû. Ïîýòîìó âîçìîæíû äâàîñíîâíûõ ñïîñîáà ðàñïîçíàâàíèÿ êëþ÷åâûõ ñëîâ: ëèáî î÷åðåäíàÿ ëåêñåìà ñíà÷àëà äèàãíîñòèðóåòñÿ íà ñîâïàäåíèå ñêàêèì-ëèáî êëþ÷åâûì ñëîâîì è â ñëó÷àå íåóñïåõà äåëàåòñÿ ïîïûòêà âûäåëèòü ëåêñåìó èç êàêîãî-ëèáî êëàññà, ëèáî,íàîáîðîò, ïîñëå âûáîðêè ëåêñåìû èäåíòèôèêàòîðà ïðîèñõîäèò îáðàùåíèå ê òàáëèöå êëþ÷åâûõ ñëîâ íà ïðåäìåò ñðàâíåíèÿ. Ïîäðîáíåå î ìåõàíèçìàõ ïîèñêà â òàáëèöàõ áóäåòñêàçàíî íèæå (ãë.
7), çäåñü îòìåòèì òîëüêî, ÷òî ïîèñê êëþ÷åâûõ ñëîâ ìîæåò âåñòèñü ëèáî â îñíîâíîé òàáëèöå èì¼íè â ýòîì ñëó÷àå â íå¼ äî íà÷àëà ðàáîòû ËÀ çàãðóæàþòñÿ êëþ÷åâûå ñëîâà, ëèáî â îòäåëüíîé òàáëèöå. Ïðè ïåðâîìñïîñîáå âñå êëþ÷åâûå ñëîâà íåïîñðåäñòâåííî âñòðàèâàþòñÿ â êîíå÷íûé àâòîìàò ËÀ, âî âòîðîì êîíå÷íûé àâòîìàòñîäåðæèò òîëüêî ðàçáîð èäåíòèôèêàòîðîâ. íåêîòîðûõ ÿçûêàõ (íàïðèìåð, ÏË/1 èëè Ôîðòðàí)êëþ÷åâûå ñëîâà ìîãóò èñïîëüçîâàòüñÿ â êà÷åñòâå îáû÷íûõèäåíòèôèêàòîðîâ.  ýòîì ñëó÷àå ðàáîòà ËÀ íå ìîæåò èäòè íåçàâèñèìî îò ðàáîòû ñèíòàêñè÷åñêîãî àíàëèçàòîðà. ÂÔîðòðàíå âîçìîæíû, íàïðèìåð, ñëåäóþùèå ñòðîêè:DO 10 I=1,25DO 10 I=1.25 ïåðâîì ñëó÷àå ñòðîêà ýòî çàãîëîâîê öèêëà DO, âîâòîðîì îïåðàòîð ïðèñâàèâàíèÿ.
Ïîýòîìó, ïðåæäå ÷åììîæíî áóäåò âûäåëèòü ëåêñåìó, ËÀ äîëæåí çàãëÿíóòü äîâîëüíî äàëåêî.72Ãëàâà 3. Ëåêñè÷åñêèé àíàëèçÅù¼ ñëîæíåå äåëî â ÏË/1. Çäåñü âîçìîæíû òàêèå îïåðàòîðû:IF ELSE THEN ELSE = THEN; ELSE THEN = ELSE;èëèDECLARE (A1, A2, ... , AN)è òîëüêî â çàâèñèìîñòè îò òîãî, ÷òî ñòîèò ïîñëå ¾)¿, ìîæíî îïðåäåëèòü, ÿâëÿåòñÿ ëè DECLARE êëþ÷åâûì ñëîâîì èëèèäåíòèôèêàòîðîì. Äëèíà òàêîé ñòðîêè ìîæåò áûòü ñêîëüóãîäíî áîëüøîé è óæå íåâîçìîæíî îòäåëèòü ôàçó ñèíòàêñè÷åñêîãî àíàëèçà îò ôàçû ëåêñè÷åñêîãî àíàëèçà.Ðàññìîòðèì íåñêîëüêî ïîäðîáíåå âîïðîñû ïðîãðàììèðîâàíèÿ ËÀ. Îñíîâíàÿ îïåðàöèÿ ËÀ, íà êîòîðóþ óõîäèòáîëüøàÿ ÷àñòü âðåìåíè åãî ðàáîòû ýòî âçÿòèå î÷åðåäíîãî ñèìâîëà è ïðîâåðêà íà ïðèíàäëåæíîñòü åãî íåêîòîðîìóäèàïàçîíó. Íàïðèìåð, îñíîâíîé öèêë ïðè âûáîðêå ÷èñëà âïðîñòåéøåì ñëó÷àå ìîæåò âûãëÿäåòü ñëåäóþùèì îáðàçîì:while (Insym<='9' && Insym>='0'){ ...
}Ïðîãðàììó ìîæíî çíà÷èòåëüíî óëó÷øèòü ñëåäóþùèìîáðàçîì [5]. Ïóñòü LETTER, DIGIT, BLANK ýëåìåíòû ïåðå÷èñëèìîãî òèïà. Ââåä¼ì ìàññèâ map, âõîäàìè êîòîðîãîáóäóò ñèìâîëû, çíà÷åíèÿìè òèïû ñèìâîëîâ. Èíèöèàëèçèðóåì ìàññèâ map ñëåäóþùèì îáðàçîì:map['a']=LETTER;........map['z']=LETTER;map['0']=DIGIT;........map['9']=DIGIT;map[' ']=BLANK;........3.5.
Ïðîãðàììèðîâàíèå ëåêñè÷åñêîãî àíàëèçà73Òîãäà ïðèâåä¼ííûé öèêë ïðèìåò ñëåäóþùóþ ôîðìó:while (map[Insym]==DIGIT){ ... }Âûäåëåíèå êëþ÷åâûõ ñëîâ ìîæåò îñóùåñòâëÿòüñÿ ïîñëåâûäåëåíèÿ èäåíòèôèêàòîðîâ. ËÀ ðàáîòàåò áûñòðåå, åñëèêëþ÷åâûå ñëîâà âûäåëÿþòñÿ íåïîñðåäñòâåííî.Äëÿ ýòîãî ñòðîèòñÿ êîíå÷íûé àâòîìàò, îïèñûâàþùèéìíîæåñòâî êëþ÷åâûõ ñëîâ. Íà ðèñ. 3.17 ïðèâåä¼í ôðàãìåíòòàêîãî àâòîìàòà.Ðàññìîòðèì ïðèìåð ïðîãðàììèðîâàíèÿ ýòîãî êîíå÷íîãîàâòîìàòà íà ÿçûêå Ñè, ïðèâåä¼ííûé â [17]: IL;md\ZbebpbnjZQDexq_\h_keh\hLIB^_glbnbdZlhjG_Ibg_QG_WWG_[md\Zbg_pbnjZ;md\ZbebpbnjZG_[md\Zbg_pbnjZDexq_\h_keh\hLQWÐèñ.
3.17.........case 'i':if (cp[0]=='f' &&!(map[cp[2]] & (DIGIT | LETTER))){cp++; return IF;}if (cp[0]=='n' && cp[1]=='t'&&!(map[cp] & (DIGIT | LETTER))){cp+=2; return INT;}{ îáðàáîòêà èäåíòèôèêàòîðà }........74Ãëàâà 3. Ëåêñè÷åñêèé àíàëèçÇäåñü cp óêàçàòåëü òåêóùåãî ñèìâîëà.  ìàññèâå mapêëàññû ñèìâîëîâ êîäèðóþòñÿ áèòàìè.Ïîñêîëüêó ËÀ àíàëèçèðóåò êàæäûé ñèìâîë âõîäíîãîïîòîêà, åãî ñêîðîñòü ñóùåñòâåííî çàâèñèò îò ñêîðîñòè âûáîðêè î÷åðåäíîãî ñèìâîëà âõîäíîãî ïîòîêà.  ñâîþ î÷åðåäü, ýòà ñêîðîñòü âî ìíîãîì îïðåäåëÿåòñÿ ñõåìîé áóôåðèçàöèè.
Ðàññìîòðèì âîçìîæíûå ýôôåêòèâíûå ñõåìû áóôåðèçàöèè.1111HRI HRIIjh^\b`_gb_Ijh^\b`_gb_GZqZehGZqZehZ[Ðèñ. 3.18.Áóäåì èñïîëüçîâàòü áóôåð, ñîñòîÿùèé èç äâóõ îäèíàêîâûõ ÷àñòåé äëèíû N (ðèñ. 3.18, à), ãäå N ðàçìåð áëîêà îáìåíà (íàïðèìåð, 1024, 2048 è ò.ä.). ×òîáû íå ÷èòàòüêàæäûé ñèìâîë îòäåëüíî, â êàæäóþ èç ïîëîâèí áóôåðà ïîî÷åðåäíî îäíîé êîìàíäîé ÷òåíèÿ ñ÷èòûâàåòñÿ N ñèìâîëîâ.Åñëè íà âõîäå îñòàëîñü ìåíüøå N ñèìâîëîâ, â áóôåð ïîìåùàåòñÿ ñïåöèàëüíûé ñèìâîë (eof).
Íà áóôåð óêàçûâàþòäâà óêàçàòåëÿ: ïðîäâèæåíèå è íà÷àëî. Ìåæäó óêàçàòåëÿìè ðàçìåùàåòñÿ òåêóùàÿ ëåêñåìà. Âíà÷àëå îíè îáà óêàçûâàþò íà ïåðâûé ñèìâîë âûäåëÿåìîé ëåêñåìû. Îäèí èçíèõ, ïðîäâèæåíèå, ïðîäâèãàåòñÿ âïåð¼ä, ïîêà íå áóäåò âûäåëåíà ëåêñåìà, è óñòàíàâëèâàåòñÿ íà å¼ êîíåö. Ïîñëå îáðàáîòêè ëåêñåìû îáà óêàçàòåëÿ óñòàíàâëèâàþòñÿ íà ñèìâîë, ñëåäóþùèé çà ëåêñåìîé.
Åñëè óêàçàòåëü ïðîäâèæåíèåïåðåõîäèò ñåðåäèíó áóôåðà, ïðàâàÿ ïîëîâèíà çàïîëíÿåòñÿíîâûìè N ñèìâîëàìè. Åñëè óêàçàòåëü ïðîäâèæåíèå ïåðåõîäèò ïðàâóþ ãðàíèöó áóôåðà, ëåâàÿ ïîëîâèíà çàïîëíÿåòñÿN ñèìâîëàìè è óêàçàòåëü ïðîäâèæåíèå óñòàíàâëèâàåòñÿ íà3.6. Êîíñòðóêòîð ëåêñè÷åñêèõ àíàëèçàòîðîâ LEX75íà÷àëî áóôåðà.Ïðè êàæäîì ïðîäâèæåíèè óêàçàòåëÿ íåîáõîäèìî ïðîâåðÿòü, íå äîñòèãëè ëè ìû ãðàíèöû îäíîé èç ïîëîâèí áóôåðà.
Äëÿ âñåõ ñèìâîëîâ, êðîìå ëåæàùèõ â êîíöå ïîëîâèíáóôåðà, òðåáóþòñÿ äâå ïðîâåðêè. ×èñëî ïðîâåðîê ìîæíîñâåñòè ê îäíîé, åñëè â êîíöå êàæäîé ïîëîâèíû ïîìåñòèòüäîïîëíèòåëüíûé ¾ñòîðîæåâîé¿ ñèìâîë, â êà÷åñòâå êîòîðîãîëîãè÷íî âçÿòü eof (ðèñ. 3.18, á). ýòîì ñëó÷àå ïî÷òè äëÿ âñåõ ñèìâîëîâ äåëàåòñÿ åäèíñòâåííàÿ ïðîâåðêà íà ñîâïàäåíèå ñ eof è òîëüêî â ñëó÷àåñîâïàäåíèÿ íóæíî äîïîëíèòåëüíî ïðîâåðèòü, äîñòèãëè ëèìû ñåðåäèíû èëè ïðàâîãî êîíöà.3.6. Êîíñòðóêòîð ëåêñè÷åñêèõ àíàëèçàòîðîâ LEXÄëÿ àâòîìàòèçàöèè ðàçðàáîòêè ËÀ áûëî ñîçäàíî äîâîëüíî ìíîãî ñðåäñòâ. Êàê ïðàâèëî, âõîäíûì ÿçûêîì äëÿíèõ ñëóæàò èëè ïðàâîëèíåéíûå ãðàììàòèêè, èëè ÿçûê ðåãóëÿðíûõ âûðàæåíèé.
Îäíîé èç íàèáîëåå ðàñïðîñòðàí¼ííûõ ñèñòåì ÿâëÿåòñÿ LEX, ðàáîòàþùèé ñ ðàñøèðåííûìè ðåãóëÿðíûìè âûðàæåíèÿìè. LEX-ïðîãðàììà ñîñòîèò èçòð¼õ ÷àñòåé:Îáúÿâëåíèÿ%%Ïðàâèëà òðàíñëÿöèè%%Âñïîìîãàòåëüíûå ïîäïðîãðàììûÑåêöèÿ îáúÿâëåíèé âêëþ÷àåò îáúÿâëåíèÿ ïåðåìåííûõ,êîíñòàíò è îïðåäåëåíèÿ ðåãóëÿðíûõ âûðàæåíèé. Ïðè îïðåäåëåíèè ðåãóëÿðíûõ âûðàæåíèé ìîãóò èñïîëüçîâàòüñÿ ñëåäóþùèå êîíñòðóêöèè:76Ãëàâà 3. Ëåêñè÷åñêèé àíàëèç[abc][a-z]R*R+R1/R2R1|R2R?R$^R[^R]R{n,m}{èìÿ}(R) ëèáî a, ëèáî b, ëèáî c; äèàïàçîí ñèìâîëîâ; 0 èëè áîëåå ïîâòîðåíèé ðåãóëÿðíîãîâûðàæåíèÿ R; 1 èëè áîëåå ïîâòîðåíèé ðåãóëÿðíîãîâûðàæåíèÿ R; R1 , åñëè çà íèì ñëåäóåò R2 ; ëèáî R1 , ëèáî R2 ; åñëè åñòü R, âûáðàòü åãî; âûáðàòü R, åñëè îíî ïîñëåäíåå â ñòðîêå; âûáðàòü R, åñëè îíî ïåðâîå â ñòðîêå; äîïîëíåíèå ê R; ïîâòîðåíèå R îò n äî m ðàç; èìåíîâàííîå ðåãóëÿðíîå âûðàæåíèå; ãðóïïèðîâêà.Ïðàâèëà òðàíñëÿöèè LEXïðîãðàìì èìåþò âèäp_1 { äåéñòâèå_1 }p_2 { äåéñòâèå_2 }................p_n { äåéñòâèå_n }ãäå p_i ðåãóëÿðíîå âûðàæåíèå, à äåéñòâèå_i ôðàãìåíòïðîãðàììû, îïèñûâàþùèé, êàêîå äåéñòâèå äîëæåí ñäåëàòüËÀ, êîãäà îáðàçåö p_i ñîïîñòàâëÿåòñÿ ëåêñåìå.
 LEX äåéñòâèÿ çàïèñûâàþòñÿ íà Ñè.Òðåòüÿ ñåêöèÿ ñîäåðæèò âñïîìîãàòåëüíûå ïðîöåäóðû,íåîáõîäèìûå äëÿ äåéñòâèé. Ýòè ïðîöåäóðû ìîãóò òðàíñëèðîâàòüñÿ ðàçäåëüíî è çàãðóæàòüñÿ ñ ËÀ.ËÀ, ñãåíåðèðîâàííûé LEX, âçàèìîäåéñòâóåò ñ ñèíòàêñè÷åñêèì àíàëèçàòîðîì ñëåäóþùèì îáðàçîì. Ïðè âûçîâååãî ñèíòàêñè÷åñêèì àíàëèçàòîðîì ËÀ ïîñèìâîëüíî ÷èòàåòîñòàòîê âõîäà, ïîêà íå íàõîäèò ñàìûé äëèííûé ïðåôèêñ,êîòîðûé ìîæåò áûòü ñîïîñòàâëåí îäíîìó èç ðåãóëÿðíûõâûðàæåíèé p_i.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
