В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 23
Текст из файла (страница 23)
Ïðîâåðêà êîíòåêñòíûõ óñëîâèéÄëÿ ðåàëèçàöèè íåêîòîðûõ àòðèáóòîâ (â ÷àñòíîñòè ñðåäû, ñïèñêà èäåíòèôèêàòîðîâ è ò.ä.) â êà÷åñòâå òèïîâ äàííûõ ìû áóäåì èñïîëüçîâàòü ðàçëè÷íûå ìíîæåñòâà. Ìíîæåñòâî ìîæåò áûòü óïîðÿäî÷åííûì èëè íåóïîðÿäî÷åííûì,êëþ÷åâûì èëè ïðîñòûì. Ýëåìåíòîì êëþ÷åâîãî ìíîæåñòâàìîæåò áûòü çàïèñü, îäíèì èç ïîëåé êîòîðîé ÿâëÿåòñÿ êëþ÷:SETOF T ïðîñòîå íåóïîðÿäî÷åííîå ìíîæåñòâî îáúåêòîâ òèïà T;KEY K SETOF T êëþ÷åâîå íåóïîðÿäî÷åííîå ìíîæåñòâî îáúåêòîâ òèïà T ñ êëþ÷îì òèïà K;LISTOF T ïðîñòîå óïîðÿäî÷åííîå ìíîæåñòâî îáúåêòîâ òèïà T;KEY K LISTOF T êëþ÷åâîå óïîðÿäî÷åííîå ìíîæåñòâî îáúåêòîâ òèïà T ñ êëþ÷îì òèïà K;Íàä îáúåêòàìè òèïà ìíîæåñòâà îïðåäåëåíû ñëåäóþùèåîïåðàöèè:Init(S) ñîçäàòü è ïðîèíèöèàëèçèðîâàòü ïåðåìåííóþ S;Include(V,S) âêëþ÷èòü îáúåêò V â ìíîæåñòâî S;åñëè ìíîæåñòâî óïîðÿäî÷åííîå, òî âêëþ÷åíèå îñóùåñòâëÿåòñÿ â êà÷åñòâå ïîñëåäíåãî ýëåìåíòà;Find(K,S) âûäàòü óêàçàòåëü íà îáúåêò ñ êëþ÷îì Kâî ìíîæåñòâå S è NIL, åñëè îáúåêò ñ òàêèì êëþ÷îì íåíàéäåí.Èìååòñÿ ñïåöèàëüíûé îïåðàòîð öèêëà, ïðîáåãàþùèéýëåìåíòû ìíîæåñòâà:for (V in S) Îïåðàòîð;Ïåðåìåííàÿ V ïðîáåãàåò âñå çíà÷åíèÿ ìíîæåñòâà.
Åñëèìíîæåñòâî óïîðÿäî÷åíî, òî ýëåìåíòû ïðîáåãàþòñÿ â ýòîìïîðÿäêå, åñëè íåò â ïðîèçâîëüíîì ïîðÿäêå.Ñðåäà ïðåäñòàâëÿåò ñîáîé êëþ÷åâîå ìíîæåñòâî ñ êëþ÷îì èìåíåì îáúåêòà. Èäåíòèôèêàòîðû èìåþò òèï TName.Îáîçíà÷åíèå <Íåòåðìèíàë> â ïîçèöèè òèïà ýòî óêàçàòåëü6.2. Çàíåñåíèå â ñðåäó è ïîèñê îáúåêòîâ159(QY(QY(QY(QY(QY(QY(QYÐèñ. 6.2.íà âåðøèíó òèïà Íåòåðìèíàë. Îáîçíà÷åíèå <Íåòåðìèíàë> ââûðàæåíèè ýòî âçÿòèå çíà÷åíèÿ óêàçàòåëÿ íà áëèæàéøóþ âåðøèíó ââåðõ ïî äåðåâó ðàçáîðà, ïîìå÷åííóþ ñîîòâåòñòâóþùèì íåòåðìèíàëîì.Äëÿ ðåàëèçàöèè ñðåäû êàæäûé íåòåðìèíàë Block èìååòàòðèáóò Env. Äëÿ îáåñïå÷åíèÿ âîçìîæíîñòè ïðîñìàòðèâàòüêîìïîíåíòû ñðåäû â ñîîòâåòñòâèè ñ âëîæåííîñòüþ áëîêîâêàæäûé íåòåðìèíàë Block èìååò àòðèáóò Pred óêàçàòåëü íà îõâàòûâàþùèé áëîê. Êðîìå òîãî, ñðåäà áëîêà êîðíÿäåðåâà (íåòåðìèíàë Prog) ñîäåðæèò âñå ïðåäîïðåäåë¼ííûåîïèñàíèÿ (ðèñ.
6.2). Ýòî çàïîëíåíèå ðåàëèçóåòñÿ ïðîöåäóðîé PreDefine. Àòðèáóò Pred áëîêà êîðíåâîé êîìïîíåíòûèìååò çíà÷åíèå NULL.Àòðèáóòíàÿ ðåàëèçàöèÿ âûãëÿäèò ñëåäóþùèì îáðàçîì.// Îïèñàíèå àòðèáóòîâALPHABETProg:: KEY TName SETOF TElement Env.// Êîðíåâàÿ êîìïîíåíòà, ñîäåðæàùàÿ ïðåäîïðåäåë¼ííûå// îïèñàíèÿ.Block:: KEY TName SETOF TElement Env;<Block> Pred.Ident_List:: SETOF TName Ident_Set.// Ident_Set - ñïèñîê èäåíòèôèêàòîðîâ160Ãëàâà 6. Ïðîâåðêà êîíòåêñòíûõ óñëîâèéType_Defin, Type_Use, Access, Expression::TType ElementType.// ElementType - óêàçàòåëü íà îïèñàíèå òèïàDeclaration, Var_Decl, Type_Decl::.Ident:: TName Val.Index:: int Val.// Îïèñàíèå ñèíòàêñè÷åñêèõ è ñåìàíòè÷åñêèõ ïðàâèëRULEProg ::= 'program' Ident Block '.'SEMANTICS0:{Init(Env<3>);PreDefine(Env<3>);Pred<3>=NULL;}.RULEBlock ::= 'begin'[(Declaration)] [(Statement)]'end'SEMANTICS0: if (<Block>!=NULL){Init(Env<0>);Pred<0>=<Block>;}.RULEDeclaration ::= 'type' ( Type_Decl ).RULEType_Decl ::= Ident '=' Type_DefinSEMANTICSTElement V;if (Find(Val<1>,Env<Block>)!=NULL)Error("Identifier declared twice");// Èäåíòèôèêàòîð óæå îáúÿâëåí â áëîêå//  ëþáîì ñëó÷àå çàíîñèòñÿ íîâîå îïèñàíèåV.Name=Val<1>;6.2.
Çàíåñåíèå â ñðåäó è ïîèñê îáúåêòîâV.Object=TypeObject;V.Type=ElementType<3>;Include(V,Env<Block>).RULEType_Defin ::= 'ARRAY' Index 'OF' Type_DefinSEMANTICSElementType<0>=ArrayType(ElementType<4>,Val<2>).RULEType_Defin ::= Type_UseSEMANTICSElementType<0>=ElementType<1>.RULEType_Use ::= IdentSEMANTICSTElement * PV;PV=FindObject(Val<1>,<Block>,TypeObject,<Prog>);If (PV!=NULL)ElementType<0>=PV->Type.//  ýòîì ïðàâèëå àíàëèçèðóåòñÿ èñïîëüçóþùàÿ// ïîçèöèÿ èäåíòèôèêàòîðà òèïà.RULEDeclaration ::= 'var' ( Var_Decl ).RULEVar_Decl ::= Ident_List ':' Type_Use ';'SEMANTICSTElement V;TName N;for (N in Ident_Set<1>){// Öèêë ïî (íåóïîðÿäî÷åííîìó) ñïèñêó// èäåíòèôèêàòîðîâif (Find(N,Env<Block>)!=NULL)Error("Identifier declared twice");// Èäåíòèôèêàòîð óæå îáúÿâëåí â áëîêå//  ëþáîì ñëó÷àå çàíîñèòñÿ íîâîå îïèñàíèå161162}.//////////Ãëàâà 6.
Ïðîâåðêà êîíòåêñòíûõ óñëîâèéV.Name=N;V.Object=VarObject;V.Type=ElementType<3>;Include(V,Env<Block>);N - ðàáî÷àÿ ïåðåìåííàÿ äëÿ ýëåìåíòîâ ñïèñêà.Äëÿ êàæäîãî èäåíòèôèêàòîðà èç ìíîæåñòâàèäåíòèôèêàòîðîâ Ident_Set<1> ñôîðìèðîâàòüîáúåêò-ïåðåìåííóþ â òåêóùåé êîìïîíåíòå ñðåäûñ ñîîòâåòñòâóþùèìè õàðàêòåðèñòèêàìè.RULEIdent_List ::= ( Ident /',' )SEMANTICS0:Init(Ident_Set<0>);1A:Include(Val<1>,Ident_Set<0>).RULEStatement ::= Block ';'.RULEStatement ::= Variable '=' Variable ';'SEMANTICSif (ElementType<1>!=NULL) && (ElementType<3>!=NULL)&& (ElementType<1>!=ElementType<3>)Error("Incompatible Expression Types").RULEVariable ::= Ident AccessSEMANTICSTElement * PV;PV=FindObject(Val<1>,<Block>,VarObject,<Prog>);if (PV==NULL){Error("Identifier used is not declared");ElementType<2>=NULL ;}elseElementType<2>=PV->Type.RULE6.2.
Çàíåñåíèå â ñðåäó è ïîèñê îáúåêòîâ163Access ::= '[' Expression ']' AccessSEMANTICSElementType<4>=ArrayElementType(ElementType<0>,ElementType<2>).RULEAccess ::=SEMANTICSElementType<Variable>=ElementType<0>.Ïîèñê â ñðåäå îñóùåñòâëÿåòñÿ ñëåäóþùåé ôóíêöèåé:TElement * FindObject(TName Ident, <Block>BlockPointer, TObject Object, <Prog> Prog){ TElement * ElementPointer;// Ïîëó÷èòü óêàçàòåëü íà áëèæàéøèé// îõâàòûâàþùèé áëîêdo{ElementPointer=Find(Ident, BlockPointer->Env);BlockPointer=BlockPointer->Pred;}while (ElementPointer==NULL)&&(BlockPointer!=NULL);// Èñêàòü äî ìîìåíòà, êîãäà ëèáî íàéä¼ì íóæíûé// èäåíòèôèêàòîð, ëèáî äîéä¼ì äî êîðíåâîé// êîìïîíåíòûif (ElementPointer==NULL)&&(BlockPointer==NULL)// Äîøëè äî êîðíåâîé êîìïîíåíòû è åù¼ íå íàøëè// èäåíòèôèêàòîðà// Íàéòè îáúåêò ñðåäè ïðåäîïðåäåë¼ííûõElementPointer=Find(Ident, Prog->Env);if (ElementPointer!=NULL)// Íàøëè îáúåêò ñ äàííûì èäåíòèôèêàòîðîì ëèáî// â î÷åðåäíîì áëîêå, ëèáî ñðåäè ïðåäîïðåäåë¼ííûõif (ElementPointer->Object!=Object){// Ïðîâåðèòü, èìååò ëè íàéäåííûé îáúåêò// íóæíóþ êàòåãîðèþError("Object of specified categoryis not found");ElementPointer=NULL;164Ãëàâà 6.
Ïðîâåðêà êîíòåêñòíûõ óñëîâèé}else// Îáúåêò íå íàéäåíError("Object is not found");return ElementPointer;}Ïåðåìåííàÿ BlockPointer óêàçàòåëü íà áëèæàéøèéîõâàòûâàþùèé áëîê. Ïåðåõîäÿ îò áëîêà ê áëîêó, èùåì îáúåêò â åãî ñðåäå. Åñëè íå íàøëè, òî ïåðåõîäèì ê îõâàòûâàþùåìó áëîêó. Åñëè äîøëè äî êîðíåâîé êîìïîíåíòû, ïûòàåìñÿ íàéòè îáúåêò ñðåäè ïðåäîïðåäåë¼ííûõ îáúåêòîâ. Åñëèîáúåêò íàøëè, íàäî óáåäèòüñÿ, ÷òî îí èìååò íóæíóþ êàòåãîðèþ.Ôóíêöèÿ ArrayElementType(TType EntryType, TTypeExprType) îñóùåñòâëÿåò ïðîâåðêó äîïóñòèìîñòè ïðèìåíåíèÿ îïåðàöèè âçÿòèÿ èíäåêñà ê ïåðåìåííîé è âîçâðàùàåòòèï ýëåìåíòà ìàññèâà.Ôóíêöèÿ ArrayType(TType EntryType, int Val) âîçâðàùàåò îïèñàíèå òèïà ìàññèâà ñ òèïîì ýëåìåíòàEntryType è äèàïàçîíîì èíäåêñà Val.Ãëàâà 7.Îðãàíèçàöèÿ òàáëèöñèìâîëîâ ïðîöåññå ðàáîòû êîìïèëÿòîð õðàíèò èíôîðìàöèþ îáîáúåêòàõ ïðîãðàììû â ñïåöèàëüíûõ òàáëèöàõ ñèìâîëîâ.Êàê ïðàâèëî, èíôîðìàöèÿ î êàæäîì îáúåêòå ñîñòîèò èçäâóõ îñíîâíûõ ýëåìåíòîâ: èìåíè îáúåêòà è îïèñàíèÿ îáúåêòà.
Èíôîðìàöèÿ îá îáúåêòàõ ïðîãðàììû äîëæíà áûòüîðãàíèçîâàíà òàêèì îáðàçîì, ÷òîáû ïîèñê å¼ áûë ïî âîçìîæíîñòè áûñòðåå, à òðåáóåìàÿ ïàìÿòü ïî âîçìîæíîñòèìåíüøå.Êðîìå òîãî, ñî ñòîðîíû ÿçûêà ïðîãðàììèðîâàíèÿ ìîãóòáûòü äîïîëíèòåëüíûå òðåáîâàíèÿ ê îðãàíèçàöèè èíôîðìàöèè. Èìåíà ìîãóò èìåòü îïðåäåë¼ííóþ îáëàñòü âèäèìîñòè.Íàïðèìåð, ïîëå çàïèñè äîëæíî áûòü óíèêàëüíî â ïðåäåëàõñòðóêòóðû (èëè óðîâíÿ ñòðóêòóðû), íî ìîæåò ñîâïàäàòü ñèìåíåì îáúåêòà âíå çàïèñè (èëè äðóãîãî óðîâíÿ çàïèñè). òî æå âðåìÿ èìÿ ïîëÿ ìîæåò îòêðûâàòüñÿ îïåðàòîðîìïðèñîåäèíåíèÿ, è òîãäà ìîæåò âîçíèêíóòü êîíôëèêò èì¼í(èëè íåîäíîçíà÷íîñòü â òðàêòîâêå èìåíè).
Åñëè ÿçûê èìååòáëî÷íóþ ñòðóêòóðó, òî íåîáõîäèìî îáåñïå÷èòü òàêîé ñïîñîá õðàíåíèÿ èíôîðìàöèè, ÷òîáû, âî-ïåðâûõ, ïîääåðæèâàòü áëî÷íûé ìåõàíèçì âèäèìîñòè, à âî-âòîðûõ ýôôåê165166Ãëàâà 7. Îðãàíèçàöèÿ òàáëèö ñèìâîëîâòèâíî îñâîáîæäàòü ïàìÿòü ïðè âûõîäå èç áëîêà.  íåêîòîðûõ ÿçûêàõ (íàïðèìåð, Àäå) îäíîâðåìåííî (â îäíîì áëîêå)ìîãóò áûòü âèäèìû íåñêîëüêî îáúåêòîâ ñ îäíèì èìåíåì, âäðóãèõ òàêàÿ ñèòóàöèÿ íåäîïóñòèìà.Ìû ðàññìîòðèì íåêîòîðûå îñíîâíûå ñïîñîáû îðãàíèçàöèè òàáëèö ñèìâîëîâ â êîìïèëÿòîðå: òàáëèöû èäåíòèôèêàòîðîâ, òàáëèöû ðàññòàíîâêè, äâîè÷íûå äåðåâüÿ è ðåàëèçàöèþ áëî÷íîé ñòðóêòóðû.7.1.
Òàáëèöû èäåíòèôèêàòîðîâÊàê óæå áûëî ñêàçàíî, èíôîðìàöèþ îá îáúåêòå îáû÷íîìîæíî ðàçäåëèòü íà äâå ÷àñòè: èìÿ (èäåíòèôèêàòîð) è îïèñàíèå. Åñëè äëèíà èäåíòèôèêàòîðà îãðàíè÷åíà (èëè èìÿèäåíòèôèöèðóåòñÿ ïî îãðàíè÷åííîìó ÷èñëó ïåðâûõ ñèìâîëîâ èäåíòèôèêàòîðà), òî òàáëèöà ñèìâîëîâ ìîæåò áûòü îðãàíèçîâàíà â âèäå ïðîñòîãî ìàññèâà ñòðîê ôèêñèðîâàííîéäëèíû, êàê ýòî èçîáðàæåíî íà ðèñ. 7.1. Íåêîòîðûå âõîäûìîãóò áûòü çàíÿòû, íåêîòîðûå ñâîáîäíû.ßñíî, ÷òî, âî-ïåðâûõ, ðàçìåð ìàññèâà äîëæåí áûòü íåìåíüøå ÷èñëà èäåíòèôèêàòîðîâ, êîòîðûå ìîãóò ðåàëüíîïîÿâèòüñÿ â ïðîãðàììå (â ïðîòèâíîì ñëó÷àå âîçíèêàåò ïåðåïîëíåíèå òàáëèöû); âî-âòîðûõ, êàê ïðàâèëî, ïîòåíöèàëüíîå ÷èñëî ðàçëè÷íûõ èäåíòèôèêàòîðîâ ñóùåñòâåííî áîëüøå ðàçìåðà òàáëèöû.Çàìåòèì, ÷òî â áîëüøèíñòâå ÿçûêîâ ïðîãðàììèðîâàíèÿñèìâîëüíîå ïðåäñòàâëåíèå èäåíòèôèêàòîðà ìîæåò èìåòüïðîèçâîëüíóþ äëèíó.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
