§1  Tablehandler  TABLE HANDLER: AN EXAMPLE OF MWEB 1

1. Table Handler: An example of MWEB. The following program is based on the TableHandler module in Niklaus Wirth’s Programming in Modula-2. This is the implementation module; the definition module is in a separate source file.

implementation module table handler ; ⟨ Import List 2 ⟩ const ⟨ Constants of the module 3 ⟩ type ⟨ Global types 4 ⟩

2. We are going to be doing some string handling, so we need to import some things from the Logitech module Strings . The boxes signify words that must not be forced to uppercase when the program is , since Modula-2 is case-sensitive.

define length of string ≡ \underline{\overline{␣ ␣}} (∗ get the length of a string ∗) define copy string ≡ \underline{\overline{␣ ␣}} (∗ Assign one string to another ∗)

⟨ Import List 2 ⟩ ≡

from \underline{\overline{␣ ␣}} import length of string , copy string ;

See also section 6. This code is used in section 1.

3. ⟨ Constants of the module 3 ⟩ ≡ max card = 65535;

This code is used in section 1.

4. This is the format of the an entry in the symbol table tree. As we define the record type, we define a few symbols to make it easier to access the fields.

define symbol ptr ≡ p↑.str define symbol defined ≡ p↑.defined define symbol value ≡ p↑.num define left sub tree ≡ p↑.left define right sub tree ≡ p↑.right

⟨ Global types 4 ⟩ ≡ treeptr = pointer to tree record ; tree record = record

str : symbol string ptr ; num: cardinal ; defined : boolean; left , right : treeptr ; end ;

See also sections 5 and 14. This code is used in section 1.

2  TABLE HANDLER: AN EXAMPLE OF MWEB  Tablehandler §5

5. We define a structure containing information application to an entire table.

define head of table ≡ the table↑.the tree↑.right ⟨ Global types 4 ⟩ +≡

table record = record next entry : cardinal ; the tree: treeptr ; user err routine: error proc; last entry found : treeptr ; case sensitive: boolean; end ;

tableptr = pointer to table record ; symbol table = tableptr ;

6. Since we intend to do heap operations, it might help to import the allocate and deallocate procedures from standard module Storage. We define a macro to determine if a given amount of space is available.

define mem available ≡ \underline{\overline{␣ ␣}} define enough memory (#) ≡ mem available(#)

§7  Tablehandler  MAIN TABLE LOOKUP PROCEDURE 3

⟨ Import List 2 ⟩ +≡ from \underline{\overline{␣ ␣}} import allocate, deallocate, mem available; from system import tsize; 7. Main Table Lookup Procedure. This is the main symbol table lookup procedure, the one visible to the calling program. If the entry does not exist it is created. procedure get value of symbol ( the table : symbol table; target symbol : array of char ;

this is a definition: boolean; var string ptr : symbol string ptr ) : cardinal ;

⟨ Procedures local to get value of symbol 11 ⟩ var p: treeptr ; n: cardinal ; current symbol : symbol string ; begin

the table↑.last entry found ← nil; copy string (target symbol , current symbol ); ⟨ If table is not case-sensitive, force string to uppercase 8 ⟩; p ← search(the table↑.the tree); if p = nil then

the table↑.user err routine(memory exhausted , ´ ␣´ );

return max card ; else

⟨ If this is a definition, check for duplicates 9 ⟩

⟨ If name has been referenced before definition, reset the value 10 ⟩ string ptr ← symbol ptr ; the table↑.last entry found ← p; return symbol value;

end ; end get value of symbol ;

8. ⟨ If table is not case-sensitive, force string to uppercase 8 ⟩ ≡

if ¬the table↑.case sensitive then

for n ← 0 to length of string (current symbol ) − 1 do

current symbol [n] ← cap(current symbol [n]); end ;

end ;

This code is used in section 7.

9. ⟨ If this is a definition, check for duplicates 9 ⟩ ≡

if this is a definition then
if symbol defined then

the table↑.user err routine(duplicate symbol , current symbol ); return max card ;

else

symbol defined ← true; end ;

end ;

This code is used in section 7.

10. ⟨ If name has been referenced before definition, reset the value 10 ⟩ ≡

if symbol value = max card then

symbol value ← the table↑.next entry ; inc(the table↑.next entry ); end ;

This code is used in section 7.

4  MAIN TABLE LOOKUP PROCEDURE  Tablehandler §11

11. This function procedure returns with a pointer to either the entry matching the target symbol or a newly created entry if no match is found. ⟨ Procedures local to get value of symbol 11 ⟩ ≡ procedure search(p : treeptr ): treeptr ;

var q: treeptr ; r: relation; i: cardinal ; slen: cardinal ; begin

q ← right sub tree; r ← greater ; while q ≠ nil do

p ← q; r ← relation of (symbol ptr );

if r = equal then

return p

elsif r = less then

q ← left sub tree else

q ← right sub tree end

end ; ⟨ Create new table entry 12 ⟩; return q;

end search;

See also section 15. This code is used in section 7.

12. We have to create a new entry in the symbol table. First we allocate the space for the entry using the standard function new . Then we initialize the fields. Finally we allocate space for the string itself and copy it.

define initialize entry (#) ≡ # ← nil;

if enough memory (tsize(tree record )) then new (#); with #↑ do

str ← nil; left ← nil; right ← nil; defined ← false; num ← max card ; end ;

else

the table↑.user err routine(memory exhausted , ´ ␣´ ); end ;

⟨ Create new table entry 12 ⟩ ≡ q ← nil; slen ← length of string (current symbol ) + 1; if enough memory (tsize(tree record ) + slen) then

initialize entry (q); with q↑ do

allocate(str , slen); copy string (current symbol , str ↑); end ; ⟨ Put this new entry on proper subtree 13 ⟩;

else

the table↑.user err routine(memory exhausted , ´ ␣´ ); end ;

This code is used in section 11.

13. ⟨ Put this new entry on proper subtree 13 ⟩ ≡

if r = less then

left sub tree ← q; else

right sub tree ← q; end ;

This code is used in section 12.

14. ⟨ Global types 4 ⟩ +≡ relation = (less , equal , greater );

15. This function procedure determines the relationship (less , equal , greater ) of the string current symbol to that of the current table entry (pointed to by k). ⟨ Procedures local to get value of symbol 11 ⟩ +≡ procedure relation of (k : symbol string ptr ): relation;

var i: cardinal ; r: relation; x, y: char ; begin

i ← 0; r ← equal ;

loop x ← current symbol [i]; y ← k↑[i]; if cap(x) ≠ cap(y) then

exit ; end ; if x ≤ ´ ␣´ then

return r

end ;

if x < y then r ← less elsif x > y then r ← greater

end ; i ← i + 1;

end ;

⟨ Return the result of the comparison 16 ⟩; end relation of ;

16. ⟨ Return the result of the comparison 16 ⟩ ≡

if cap(x) > cap(y) then

return greater

else

return less

end ;

This code is used in section 15.

17. We provide a procedure to set the table entry to a specific value. procedure set value of symbol ( the table : symbol table; target symbol : array of char ;

this is a definition: boolean; var string ptr : symbol string ptr ; the val : cardinal ) ; var ent : cardinal ; begin

the table↑.last entry found ← nil; ent ← get value of symbol (the table, target symbol , this is a definition, string ptr ); if the table↑.last entry found ≠ nil then

the table↑.last entry found ↑.num ← the val ; end ;

end set value of symbol ;

18. We provide a function procedure to determine if a particular symbol has been defined. procedure symbol is defined (the table : symbol table; target symbol : array of char ): boolean;

var ent : cardinal ; string ptr : symbol string ptr ; begin

the table↑.last entry found ← nil; ent ← get value of symbol (the table, target symbol , false, string ptr ); if the table↑.last entry found ≠ nil then

return the table↑.last entry found ↑.defined ; else

return false; end ;

end symbol is defined ;

§19  Tablehandler  UNDEFINED SYMBOL CHECK 7

19. Undefined Symbol Check. This procedure checks the integretity of the table by searching for entries that have been referenced, but never defined. It calls this node is undefined with the pointer to the root node, and this node is undefined will recursively check each entry in the tree for undefined symbols, eventually returning with a boolean value containing the result of the search. If undefined symbols are found, the user-supplied error routine is called for each. procedure undefined symbols in table(the table : symbol table;

undefined symbol handling routine : error proc): boolean; ⟨ Procedure to check an individual node 20 ⟩

begin

return this node is undefined (head of table); end undefined symbols in table;

20. This procedure checks an individual tree entry for undefined symbols. It also calls itself recursively to check the subtrees below it for the same condition. If this node or any sub-nodes has a undefined symbol, then the result for this node is true. This procedure must be declared as a local procedure to undefined symbols in table, because the user-supplied undefined symbol handling routine only exists within the scope of undefined symbols in table. ⟨ Procedure to check an individual node 20 ⟩ ≡ procedure this node is undefined (p : treeptr ): boolean;

var undefined was found , undefined symbol in left subtree, undefined symbol in right subtree: boolean; begin

undefined was found ← false;

if p ≠ nil then

if ¬symbol defined then

undefined symbol handling routine(undefined symbol , symbol ptr ↑); end ; undefined symbol in left subtree ← this node is undefined (left sub tree); undefined symbol in right subtree ← this node is undefined (right sub tree); undefined was found ← (¬symbol defined ) ∨ undefined symbol in left subtree ∨

undefined symbol in right subtree; end ; return undefined was found ;

end this node is undefined ;

This code is used in section 19.

8  TABLE SEARCH PROCEDURES  Tablehandler §21

21. Table Search Procedures. The following procedures are used to perform a user-provided operation on every entry in the table. procedure search symbol table(the table : symbol table; user action routine : table proc);

⟨ Procedure to search an individual node 22 ⟩ begin

search a node(head of table); end search symbol table;

22. This procedure searches an individual node and all of the nodes below it. As each node is processed, a user-provided procedure is called, with the value stored with this name as a parameter. The user procedure is free to perform any operation it wishes. The nodes are processed alphabetically, because this procedure will perform the processing on its left subtree before its own processing, followed by the right subtree. This procedure must be declared as a local procedure to search symbol table, because the user-supplied user action routine only exists within the scope of search symbol table. ⟨ Procedure to search an individual node 22 ⟩ ≡ procedure search a node(p : treeptr );

begin

if p ≠ nil then search a node(left sub tree); user action routine(symbol value, symbol ptr , symbol defined ); search a node(right sub tree);

end ; end search a node;

This code is used in section 21.

§23  Tablehandler  TABLE DELETION PROCEDURES 9

23. Table Deletion Procedures. The following procedures are used to delete the table and free the memory allocated to it. procedure delete symbol table(var the table : symbol table);

begin

if the table ≠ nil then

delete a node(head of table); dispose(the table); the table ← nil; end ;

end delete symbol table;

24. This procedure first deletes the subtrees below it, then deletes itself. procedure delete a node(var p : treeptr );

var slen: cardinal ;

begin

if p ≠ nil then with p↑ do

delete a node(left ); delete a node(right ); slen ← length of string (str ↑) + 1; deallocate(str , slen); end ; dispose(p); p ← nil;

end ; end delete a node;

10  TABLE INITIALIZATION  Tablehandler §25

25. Table Initialization. The following procedure is used to create a symbol table. procedure create symbol table(var the table : symbol table; case sens : boolean;

user error routine : error proc); begin

⟨ Initialize the symbol table 26 ⟩ end create symbol table;

26. To initialze the symbol table, we create a root node with initialized fields. The right node of this entry is the head of the table. ⟨ Initialize the symbol table 26 ⟩ ≡

if enough memory (tsize(table record ) + tsize(tree record )) then new (the table); with the table↑ do

user err routine ← user error routine; initialize entry (the tree); next entry ← 0; case sensitive ← case sens ;

end ; else

user error routine(memory exhausted , ´ ␣´ ); end ;

This code is used in section 25.

27. The following procedure is used to change the user-defined error handler for a symbol table. procedure set error handler (the table : symbol table; user error routine : error proc);

begin

the table↑.user err routine ← user error routine; end set error handler ;

28. Here is the end of the module.

end table handler .

§29  Tablehandler  INDEX 11

29. Index. Here is the index of names.

allocate: \underline{6}, 12. boolean: 4, 5, 7, 17, 18, 19, 20, 25. cap: 8, 15, 16. cardinal : 4, 5, 7, 11, 15, 17, 18, 24. case sens : \underline{25}, 26. case sensitive: \underline{5}, 8, 26. char : 7, 15, 17, 18. copy string : \underline{2}, 7, 12. create symbol table: \underline{25}. current symbol : \underline{7}, 8, 9, 12, 15. deallocate: \underline{6}, 24. defined : \underline{4}, 12, 18. delete a node: 23, \underline{24}. delete symbol table: \underline{23}. dispose: 23, 24. duplicate symbol : 9. enough memory : \underline{6}, 12, 26. ent : \underline{17}, \underline{18}. equal : 11, 14, 15. error proc: 5, 19, 25, 27. false: 12, 18, 20. get value of symbol : \underline{7}, 17, 18. greater : 11, 14, 15, 16. head of table: \underline{5}, 19, 21, 23. i: \underline{11}, \underline{15}. inc: 10. initialize entry : \underline{12}, 26. k: \underline{15}. last entry found : \underline{5}, 7, 17, 18. left : \underline{4}, 12, 24. left sub tree: \underline{4}, 11, 13, 20, 22. length of string : \underline{2}, 8, 12, 24. less : 11, 13, 14, 15, 16. max card : \underline{3}, 7, 9, 10, 12. mem available: \underline{6}. memory exhausted : 7, 12, 26. n: \underline{7}. new : 12, 26. next entry : \underline{5}, 10, 26. num: \underline{4}, 12, 17. p: \underline{7}, \underline{11}, \underline{20}, \underline{22}, \underline{24}. q: \underline{11}. r: \underline{11}, \underline{15}. relation: 11, \underline{14}, 15. relation of : 11, \underline{15}. right : \underline{4}, 5, 12, 24. right sub tree: \underline{4}, 11, 13, 20, 22. search: 7, \underline{11}. search a node: 21, \underline{22}. search symbol table: \underline{21}, 22. set error handler : \underline{27}. set value of symbol : \underline{17}. slen: \underline{11}, 12, \underline{24}. Storage: 6. str : \underline{4}, 12, 24. string ptr : \underline{7}, \underline{17}, \underline{18}. Strings : 2. symbol defined : \underline{4}, 9, 20, 22. symbol is defined : \underline{18}. symbol ptr : \underline{4}, 7, 11, 20, 22. symbol string : 7. symbol string ptr : 4, 7, 15, 17, 18. symbol table: \underline{5}, 7, 17, 18, 19, 21, 23, 25, 27. symbol value: \underline{4}, 7, 10, 22. system: \underline{6}. table handler : \underline{1}, 28. table proc: 21. table record : \underline{5}, 26. tableptr : \underline{5}. target symbol : \underline{7}, \underline{17}, \underline{18}. the table: 5, \underline{7}, 8, 9, 10, 12, \underline{17}, \underline{18}, \underline{19}, \underline{21},

\underline{23}, \underline{25}, 26, \underline{27}.

the tree: \underline{5}, 7, 26.

the val : 17.

this is a definition: \underline{7}, 9, \underline{17}. this node is undefined : 19, \underline{20}. tree record : \underline{4}, 12, 26. treeptr : \underline{4}, 5, 7, 11, 20, 22, 24. true: 9. tsize: \underline{6}, 12, 26. undefined symbol : 20. undefined symbol handling routine: \underline{19}, 20. undefined symbol in left subtree: \underline{20}. undefined symbol in right subtree: \underline{20}. undefined symbols in table: \underline{19}, 20. undefined was found : \underline{20}. user action routine: \underline{21}, 22. user err routine: \underline{5}, 7, 9, 12, 26, 27. user error routine: \underline{25}, 26, \underline{27}. Wirth,Niklaus : 1. x: \underline{15}. y: \underline{15}.

12  NAMES OF THE SECTIONS  Tablehandler §29

⟨ Constants of the module 3 ⟩ Used in section 1. ⟨ Create new table entry 12 ⟩ Used in section 11.

⟨ Global types 4, 5, 14 ⟩ Used in section 1.

⟨ If name has been referenced before definition, reset the value 10 ⟩ Used in section 7. ⟨ If table is not case-sensitive, force string to uppercase 8 ⟩ Used in section 7. ⟨ If this is a definition, check for duplicates 9 ⟩ Used in section 7.

⟨ Import List 2, 6 ⟩ Used in section 1.

⟨ Initialize the symbol table 26 ⟩ Used in section 25. ⟨ Procedure to check an individual node 20 ⟩ Used in section 19. ⟨ Procedure to search an individual node 22 ⟩ Used in section 21.

⟨ Procedures local to get value of symbol 11, 15 ⟩ Used in section 7.

⟨ Put this new entry on proper subtree 13 ⟩ Used in section 12. ⟨ Return the result of the comparison 16 ⟩ Used in section 15.

Tablehandler

Section Page

Table Handler: An example of MWEB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Main Table Lookup Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Undefined Symbol Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 7 Table Search Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 8 Table Deletion Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9 Table Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 10 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 11