Н. Вирт - Программирование на языке Модула-2 (1160777), страница 18
Текст из файла (страница 18)
Тем не менеемы можем сформулировать несколько правил, служащих руководством при разработке модулей.1. Число импортируемых идентификаторов должно быть небольшим.2. Правило 1 особенно важно для модулей определений.3. Экспорт переменных следует считать исключением, все импортируемые переменныеследует использовать лишь для чтения.Завершим эту главу примером, относящимся к третьему случаю.
Пусть нашей цельюявляется разработка генератора перекрестных ссылок для программ, написанных на Модуле.Более точно, задачей программы является чтение текста и получение его распечатки (1),дополненной номерами строк, а также таблицы всех встретившихся слов (идентификаторов) валфавитном порядке (2), причем для каждого слова должен печататься список номеров строк, вкоторых оно встречается. Кроме того, комментарии и строки должны пропускаться (т.е.
непечататься содержащиеся в них слова), не должны также печататься ключевые слова истандартные идентификаторы.В этой задаче можно выделить такие функции: просмотр исходного текста (с пропускомненужных участков), запоминание встретившихся идентификаторов и их последующая печать ввиде таблицы. Первая функция выполняется модулем главной программы, а вторая вспомогательным модулем, который скрывает множество данных и обеспечивает доступ к нимчерез две процедуры: Записать (т.е. занести слово) и Распечатать (т.е. печатать требуемуютаблицу). Третий модуль предназначен для перевода чисел из внутреннего представления впоследовательности десятичных цифр.
Эти три основных модуля называются соответственноXREF, РаботаСТаблицей и InOut.Опишем сначала главную программу XREF, которая просматривает исходный текст. Дляраспознавания ключевых слов используется двоичный поиск. Множество данных имеет типТаблица. Он импортируется из модуля РаботаСТаблицей в скрытом режиме.DEFINITION MODULE РаботаСТаблицей;CONST ШиринаСтроки = 80; ДлинаСлова = 24;TYPE Таблица;VAR переполнение: CARDINAL;(* >0 означает, что таблица полна *)PROCEDURE Инициализировать(VAR t: Таблица);PROCEDURE Записать(t: Таблица;VAR x: ARRAY OF CHAR; n: INTEGER);(* занести пару х,п в таблицустрока х должна заканчиваться пробелом *)PROCEDURE Распечатать(t: Таблица)86END РаботаСТаблицей.MODULE XREF;FROM InOut IMPORTDone,EOL,OpenInput,OpenOutput,Read,Write,WriteCard,WrlteString,CloseInput,CloseOutput;FROM РаботаСТаблицей IMPORTДлинаСлова,Таблица,переполнение,Инициализировать,Записать,Распечатать;TYPE Alfa = ARRAY [0..9] OF CHAR;CONST N =45; (* число ключевых слов *)VAR ch: CHAR.i,k,l,m,r,номстp: CARDINAL;T: Таблица;идент: ARRAY [0..ДлинаСлова-1] OF CHAR;ключ: ARRAY [1..N] OF Alfa;PROCEDURE Копировать;BEGIN Write(ch); Read(ch);END Копировать;PROCEDURE Заголовок;BEGIN номстр := номстр + 1;WriteCard(номстр,5); Write(" ")END Заголовок;BEGIN Инициализировать(T);ключ[1]:= "AND";ключ[2]:= "ARRAY";ключ[3]:="BEGIN";ключ[4]:= "BITSET";ключ[5]:= "BOOLEAN";ключ[6]:="BY";ключ[7]:= "CASE";ключ[8]:= "CARDINAL";ключ[9]:="CHAR";ключ[10]:="CONST";ключ[ll]:-"DIV";ключ[12]: ="DO";87ключ[13]:="ELSE";ключ[14]:="ELSIF";ключ[15]:="END";ключ[16]: ="EXIT";ключ[17]:="EXPORT";ключ[18]:="FALSE";ключ[19]:="FOR";ключ[20]:="FROM";ключ[21]:="IF";ключ[22]:="IMPORT";ключ[23]:="IN";ключ[24]:="INTEGER";ключ[25]:="LOOР";ключ[26]:="MOD";ключ[27]:="MODULE";ключ[28]:="NOT";ключ[29]:="ОР";ключ[30]:="ОР";ключ[31]:="POINTER";ключ[32]:="PROCEDURE";ключ[33]:="QUALIFIED";ключ[34]:="RECORD";ключ[351:="REPEAT";ключ[36]:="RETURN";ключ[37]:="SET";ключ[38]:="THEN";ключ[39]:="ТО";ключ[40J:="TRUE";ключ[4]:="ТУРЕ";ключ[42]:="UNTIL";ключ[43]:="VAR";ключ[44]:="WHILE";ключ[45]:="WITH";OpenInput("MOD");IF NOT Done THEN HALT END;OpenOutput("XREF");номстр := 0: Read(ch);IF Done THEN Заголовок;REPEATIF (CAP(ch) >= "A") & (CAP(ch) <= "Z") THENk := 0;REPEAT идент[k] := ch; k := k + 1; КопироватьUNTIL (ch < "0") OR(ch > "9") & (CAP(ch) < "A") OR(CAP(ch) > "Z");l := 1; r := N; идент[k] := " ";REPEAT m := (i+r) DIV 2; i := 0;(*двоичный поиск*)WHILE (идент[i]=ключ[m,i])&(идент[i]>" ") DO88i := i + 1END;IF идент[i] <= ключ[m,i] THEN r := m - 1 END;IF идент[i] >= ключ[m,i] THEN 1 := m + 1 END;UNTIL l > r;IF l = r + l THEN Записать(t,идент,номстр) ENDELSIF (ch >= "0") & (ch <= "9") THENREPEAT КопироватьUNTIL ((ch<"0")OR(ch>"9")) & ((ch<"A")OR(ch>"z"))ELSIF ch = "(" THENКопировать;IF ch = "*" THEN (*комментарий*)REPEATREPEATIF ch = EOL THENКопировать; ЗаголовокELSE КопироватьENDUNTIL ch = "*";КопироватьUNTIL ch = ")";КопироватьENDELSIF ch = "'" THENREPEAT Копировать UNTIL ch = "'";КопироватьELSIF ch = '"' THENREPEAT Копировать UNTIL ch = '"';КопироватьELSIF ch = EOL THENКопировать;IF Done THEN Заголовок END89ELSE КопироватьENDUNTIL NOT Done OR (переполнение # 0)END;IF переполнение > 0 THENWriteString("Переполнение таблицы");WriteCard(переполнение,6); Write(EOL)END;Write(35C); Распечатать(Т); CloseInput; CloseOutputEND XREF.Теперь опишем модуль РаботаСТаблицей.
Как видно из раздела описаний, онэкспортирует приватный тип Таблица и операции над ним Записать и Распечатать. Обратитевнимание, что структура таблиц, а значит, и алгоритмы поиска и доступа остаются скрытыми. Дванаиболее вероятных способа организации таблиц -это двоичное дерево и хеш-таблица. Намивыбран первый способ. Таким образом, этот пример является дальнейшей иллюстрациейиспользования указателей и динамических структур данных. Модуль содержит процедуру поискаи вставки элемента в дерево, а также процедуру, которая обходит дерево и печатает содержимоетаблицы (см.
также раздел, посвященный динамическим структурам данных). Каждый узел дерева- запись, содержащая следующие компоненты: ключ, ссылки на левого и правого сыновей,заголовок списка, содержащего номера строк.IMPLEMENTATION MODULE РаботаСТаблицей;FROM InOut IMPORT Write,WriteLn,WriteInt;FROM Storage IMPORT Allocate;CONST ДлинаТаблицы = 3000;TYPE УкДерево = POINTER TO Слово;УкСписок = POINTER TO Элемент;Элемент = RECORD номер: INTEGER;следующ: УкСписокEND;Слово = RECORD ключ: CARDINAL; (*индекс таблицы*)первый: УкСписок; (*голова списка*)левый,правый: УкДерево END;Таблица = УкДерево;90VAR идент: ARRAY [0..ДлинаСлова] OF CHAR;ТаблИндекс: CARDINAL;ЛитТаб: ARRAY [0..ДлинаТаблицы-1 ] OF CHAR;PROCEDURE Инициализировать(VAR t: Таблица);BEGIN Allocate(t,SIZE(Слово)); t^.правый := NILEND Инициализировать;PROCEDURE Поиск(р: УкДерево): УкДерево,(*поиск узла с именем, равным идент*)TYPE Отношение = (меньше,равно,больше);VAR q: УкДерево;r: Отношение; i: CARDINAL;PROCEDURE сравн(k: CARDINAL): Отношение;(*сравнение идент с ЛитТаб[k]*)VAR i: CARDINAL;R: Отношение; х,у: CHAR;BEGIN i := 0; R := равно;LOOP x := идент[i]; у := ЛитТаб[k];IF САР(х) # САР(у) THEN EXIT END;IF x <= " " THEN RETURN R END;IF x < у THEN R := меньшеELSIF x > у THEN R := большеEND;i := i + 1: к := к + 1END;IF CAP(x)>CAP(y) THEN RETURN большеELSE RETURN меньшеENDEND сравн;91BEGIN q := р^.
правый; r := больше;WHILE q # NIL DOp := q;r := сравн(р^.ключ);IF r = равно THEN RETURN pELSIF r = меньше THEN q,:= р^. левыйELSE q : = р^.правыйENDEND;Allocate(t,SIZE(Слово)); (*узел не найден, вставка*)IF q # NIL THENWITH q^ DOключ := ТаблИндекс; первый := NIL;левый := NIL; правый := NILEND;IF r = меньше THEN p^.левый := qELSE р^.правый := qEND;i := 0;(*скопировать идентификатор в таблицу ЛитТаб*)WHILE идент[i] > " " DOIF ТаблИндекс = ДлинаТаблицы THENЛитТаб [ТаблИндекс] := " "; идент[i] := " ";переполнение : = 1ELSE ЛитТаб[ТаблИндекс] := идент[i];ТаблИндекс := ТаблИндекс + 1; i := i +1ENDEND;ЛитТаб [ТаблИндекс] := " ";ТаблИндекс := ТаблИндекс + 1;END;RETURN q92END Поиск;PROCEDURE Записать(t: Таблица;VAR x: ARRAY OF CHAR; n: INTEGER);VAR p: УкДерево; q: УкСписок; i: CARDINAL;BEGIN i := 0;REPEAT идент[i] := x[i]; i := i +1UNTIL (идент[i-1] = " ") OR (i = ДлинаСлова);p := Поиск(t);IF p = NIL THEN переполнение := 2ELSE Allocate(q,SIZE(Элемент));IF q = NIL THEN переполнение := 3 ELSEq^.номер := n; q^следующ := p^.первый;p^.первый := qENDENDEND Записать;PROCEDURE Распечатать(t: Таблица);PROCEDURE ПечЭлем(р: УкДерево);CONS L = 6;N = (ШиринаСтроки-ДлинаСлова) DIV L;VAR ch: CHAR;i,k: CARDINAL; q: УкСписок;BEGIN i :- ДлинаСлова + 1; k := р^.ключ;REPEAT ch := ЛитТаб[k];i:=i-1; k:=k+1; Write(ch)UNTIL ch <= " ";WHILE i > 0 DOWrite(" "); i := i-1END;93q := р^.первый; i := N;WHILE q # NIL DOIF i = 0 THENWriteLn; i := ДлинаСлова + 1;REPEAT Write(" "); i := i - 1UNTIL i = 0;i := NEND;WriteInt(q^.номep,L);q := q^.следуют;i := i - 1END;WriteLnEND ПечЭлем;PROCEDURE ОбходДерева(р: УкДерево);BEGINIF p # NIL THENОбходДерева(p^.левый);ПечЭлем(р);ОбходДерева(р^.правый);ENDEND ОбходДерева;BEGIN WriteLn;ОбходДерева(t^.правый)END Распечатать;BEGIN ТаблИндекс := 0; идент[ДлинаСлова] := " ";переполнение := 0END РаботаСТаблицей.9426.
ЛОКАЛЬНЫЕ МОДУЛИМодули, которые нам встречались до сих пор, следовало рассматривать как Фрагментытекста, стоящие "бок о бок". Но модули могут быть и текстуально вложенными. Непосредственноеследствие этого - то, что вложенные модули не компилируются раздельно. Они называютсялокальными модулями и их единственная цель - скрыть детали описания внутренних объектов.Каждый модуль задает область видимости идентификаторов. Подразумевается, чтообъекты, описанные в области (модуле), видимы только в ней. Отметим, что процедуры тожеобразуют область видимости. Однако здесь имеются различия.1.
Для модулей диапазон видимости объекта может быть расширен включением егоидентификатора в экспортный список модуля. Тогда идентификатор становится видимым вокружающей модуль области видимости. Для процедур это невозможно.2. Идентификатор, видимый в области, окружающей процедуру, видим также и . внутрипроцедуры. Для модуля такое утверждение неверно, если только идентификатор не включен вимпортный список этого модуля.Правила видимости для модулей иллюстрируются следующими примерами:VAR а,Ь: CARDINAL;MODULE M;IMPORT a; EXPORT w,x;VAR u,v,w: CARDINAL;MODULE N;IMPORT u; EXPORT x,y;VAR x,y,z: CARDINAL;(* здесь видимы u,x,y,z *)END N;(* здесь видимы a,u,v,w,x,y *)END M;(* здесь видимы a,b,w,x *)Если идентификатор должен пересечь несколько границ областей, то он должен бытьвключен ровно в столько же импортных списков (или же модуль, содержащий идентификатор,должен импортироваться целиком).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
