TweetFollow Us on Twitter

Symbol Tables
Volume Number:6
Issue Number:9
Column Tag:Language Translation

Symbol Tables

By Clifford Story, Mount Prospect, IL

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

A. Introduction

This month, my series on Language Translation returns to lexical analysis, and I present the amazing new, improved Canon tool.

Parts of this tool are identical (or nearly so) to code presented in my third, fourth and fifth installments, and I will not repeat these parts this month (although they are, of course, included on the code disk).

Specifically, the tool is a filter program; I developed a skeleton filter program in my third installment. It uses no fewer than six state machines for lexical analysis and parsing; lexical analysis and state machines were the subject of my fourth part. And it uses the balanced binary tree routines I developed in my fifth part to implement a symbol table.

B. What the Tool Should Do

The Canon tool functions as follows: the program reads in a dictionary of substitutions, then reads input files, performs the substitutions as required, and writes the result. The difference between this Canon tool and the standard MPW Canon is that is will not perform substitutions within comments or strings.

The tool is controlled by the MPW command line. It takes several possible options, which may be in any order.

B(1). The Dictionary File

The dictionary file must be named on the command line, with the “-d <file name>” option. If no dictionary is named, the tool will abort.

The dictionary file’s format is simple: each substitution is specified on a separate line, with the identifier (according to the language’s definition of identifier) to be replaced first, followed by its replacement (which must also be an identifier). For example:

 blip blop

specifies that the identifier “blip” should be replaced by the identifier “blop” whereever it occurs.

There is a second form of substitution, which consists of only one identifier. All identifiers in the input that match the dictionary identifier will be replaced by the dictionary identifier. This can be used to force canonical capitalization.

Finally, the dictionary can include line comments. The tool will ignore everything between a ‘#’ sign and the end of the line. It also ignores blank lines.

B(2). The Input Files

Input files may be specified by simply naming them on the command line.

The input files should be either Pascal or C source files. The tool will read them according to their filename extensions: if the file name ends in “.p”, it will be treated as a Pascal file, and as a C file if it ends in “.c”.

If there are several input files, some “.p” and some “.c”, the first one named on the command line controls. If no input file has either a “.p” or a “.c” extension, then Pascal is the default.

If there are no input files named on the command line, the tool will read from standard input. The language will be Pascal.

The “-p” and “-c” options override all of the above language rules and force the language to Pascal or C, respectively. If there are more than one such option specified, the last one controls.

B(3). Other Command Options

The “-o <file name>” option names an output file. If no output file is named, the tool will write to standard output.

The “-s” option will make the tool case-sensitive. The default is case-insensitive.

B(4). Example

Here is an example of the Canon command line:

 Canon -d dict file1 file2 -p > dummy

tells Canon to read the input files “file1” and “file2”, performing substitutions from the dictionary file “dict”. The input will be treated as Pascal source, and the output will be written to standard output, which is in turn redirected to the file “dummy”.

C. Designing the Tool

You may have formed the impression that I like table-driven software. This program has no fewer than eight tables in it: two for character translation, one character classification table, four lexical analyzers and a parser. These are all kept in the resource fork.

Driving a program with tables makes the coding simpler. The price you pay is that the logic is hidden in a table, and consequently rather obscure. If you lose your notes, you may have to re-write the whole table to make a minor change! Assuming you hang onto your notes, however, tables make your program easy to change.

After I had written this program, I realized that I had forgotten about strings. Sure, I had a version of Canon that did not make substitutions within comments but it still made them within quoted strings. So I added that at the last minute; I added a few lines and columns to the lexical tables in the resource fork, and changed two constants in the code. That was it.

C(1). Main Routine

The main routine reads the command line, sets appropriate flags, reads the dictionary into the symbol table, and finally filters the input file(s).

It reads the command line in two passes. The first pass is for setting flags; the second does the work. I need to set the flags before reading any files because I need to know the source language before I read the dictionary file.

After the first pass, the routine reads in the dictionary, opens the output file (if any), and then goes into the second pass. The second pass reads and filters each input file, writing the result to the output file (or standard output).

C(2). Case Sensitivity

We want the tool to be case-insensitive unless the command line option -s is used. This will require some modifications to last time’s symbol table routines (the only place where string comparisons occur).

One approach would be to transliterate the key strings before calling “strcmp”. I want to minimize changes to the symbol table routines, though, since I don’t intend to reprint them in this article.

Another way, the way I have chosen, is to write a case-insensitive version of “strcmp”. Then all I need to do is change the name of the call in the “insert” and “lookup” routines.

Probably the most efficient way would be to use the first method in “insert” and the second in “lookup”. Since all the comparisons in “lookup” are between a key string and keys in the table, and the table would already be case-insensitive, I’d need only a “half-case-insensitive” comparison routine for “lookup”.

Of course, I still need to allow for case-sensitive lookup, if the -s flag is set. What I’ll do is have two transliteration tables, one converting uppercase to lower, and the other a straight identity table. I’ll set a global pointer to point to the appropriate table for my comparison routine to use.

C(3). Parsing the Dictionary

The first thing the program has to do is read in the dictionary. It does this in two phases: a lexical analyzer breaks the dictionary into tokens (identifiers, carriage returns, and errors), then a parser finds substitutions in the token stream.

C(3)(a). Lexical Analyser

There are two lexical analyzers, one for Pascal and one for C, because C allows underscores in identifiers. (Another, and probably better, way to do this is to have one lexical analyzer and two character tables.) In the interests of brevity, I will limit the discussion to the Pascal version; the C version is identical, except that it adds “underscore” whereever “letter” appears.

The first piece shows the the pound sign is a line comment character; after reading a pound sign, we scan to the next carriage return and then go back to state 0. We push the return character back onto the input, though, since it isn’t part of the comment.

The second segment reads an identifier. Again, the character that ends the identifier isn’t part of it, so it goes back onto the input. The lozenge thing indicates that we are going to return a token (i.e., accept states). The example lexical analyzer in installment 4 was the whole program, and it never returned anything. This one is called by a parser, and it returns one token each time it is called.

Figure 1: Pascal Dictionary Lexical Analyzer

Finally, the scanner eats white space, returns carriage returns, and if it hits anything else, errors.

Here is the class table:

data ‘TABL’ (1001) {
$”00 00 00 05 00 00 00 00 00 04 00 00 00 05 00 00"
$”00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
$”04 00 0D 06 00 00 00 0E 09 0A 0C 00 00 00 00 0B”
$”02 02 02 02 02 02 02 02 02 02 00 00 00 00 00 00"
$”00 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01"
$”01 01 01 01 01 01 01 01 01 01 01 00 00 00 00 00"
$”00 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01"
$”01 01 01 01 01 01 01 01 01 01 01 07 00 08 00 03"
$”00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
$”00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
$”00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
$”00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
$”00 00 00 00 00 00 00 00 00 00 04 00 00 00 00 00"
$”00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
$”00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
$”00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
};

Here is the state table:

data ‘TABL’ (2001) {
$”FD 02 FD FD 00 FE 01 FD FD FD FD FD FD FD FD”
$”01 01 01 01 01 00 01 01 01 01 01 01 01 01 01"
$”FF 02 02 FF FF FF FF FF FF FF FF FF FF FF FF”
};

The negative numbers correspond to the lozenges.

C(3)(b). Parser

The dictionary parser is a simple hand-made thing, and does not use YACC (that would be like swatting a fly with a hammer). A dictionary is a list of lines; a line may be blank, or it may contain a one-ID specification, or a two-ID specification. That is,

 line -> CR
 line -> ID CR
 line -> ID ID CR

Here’s a state machine to implement that grammar:

Figure 2: Dictionary Parser

Recall that the parser gets its data by calling the lexical analyzer, and thus receives only three tokens: ID, CR and ERR. State 3 is the error recovery state; it reads to the end of the line, and then goes back to state 0 for the next line. Returns to 0 from state 0, 1 and 2 correspond to the three lines of the grammar above. In the latter two cases, the specification is added to the symbol table.

Here is the state table:

data ‘TABL’ (1000) {
 $”01 00 03"
 $”02 00 03"
 $”03 00 03"
 $”03 00 03"
};

C(4). Making Substitutions

To make substitutions in the input file, we begin with a lexical analyzer that finds all the identifiers. Again, there are two versions, one for Pascal and one for C. I will discuss the C version only; Pascal does not allow underscores in identifiers, and the two languages have different comment constructs. See the fourth installment of this series for a lexical analyzer that reads Pascal comments.

The first segment reads comments, and is identical to the comment-reader presented in the fourth installment. The next two read strings. (The second segment is also present in the Pascal version, for compatibility, even though Pascal doesn’t use quotation marks for anything.) Canon does not do any syntax checking, and will read strings that go beyond the end of the line.

The fourth segment reads identifiers. When it finds one, the lozenge means “look it up and see if there’s a substitution to be made”. This scanner, unlike the dictionary scanner, doesn’t return anything; it runs until it finds the end of file, making substitutions as appropriate.

Here is the state table (which uses the same class table as the dictionary lexical analyzer):

data ‘TABL’ (3002) {
$”00 07 00 07 00 00 00 00 00 00 00 02 00 05 06"
$”01 01 01 01 01 00 01 01 01 01 01 01 01 01 01"
$”00 00 00 00 00 00 00 00 00 00 00 01 03 00 00"
$”03 03 03 03 03 03 03 03 03 03 03 03 04 03 03"
$”03 03 03 03 03 03 03 03 03 03 03 00 04 03 03"
$”05 05 05 05 05 05 05 05 05 05 05 05 05 00 05"
$”06 06 06 06 06 06 06 06 06 06 06 06 06 06 00"
$”FF 07 07 07 FF FF FF FF FF FF FF FF FF FF FF”
};

Figure 3: C Source Lexical Analyzer

D. Coding the Tool

What follows does not include all the code for the tool. Parts of it are scattered through my last two articles; refer back to those if you need to see it all. Alternately, the entire source is included on the MacTutor source code disk.

// Constants and Macros
 
#define nil 0
 
#define stdinfd  0
#define stdoutfd 1
#define stderrfd 2
 
#define stdunit(x) ((x >= stdinfd)
 && (x <= stderrfd))
#define notstdunit(x)(x > stderrfd)

#define nombuffsize1024
#define truebuffsize 1200

#define classcount 15
#define idstate  7
 
// Types
 
typedef enum 
 {false, true} 
logical;

typedef enum
 {nocode, pascalcode, ccode}
codetype;

typedef struct node
 {
 char   *key;
 struct node*left;
 struct node*right;
 int    balance;
 char   *data;
 } node;
 
// Globals
 
 unsigned char   *CASETABLE;
 
// Prototypes
 
void initmac();
int openoutput(char *thename, int output);
int readinput(int input, Handle inbuffer);
int filter(char *inbuffer, 
 int buffersize, int output,
codetype language, node *symbols);
int writeoutput(int output, 
 char *outbuffer, int buffersize);
node *parser(char *dictname, codetype language);
int gettoken(char *buffer, 
 int buffersize, char *thestring,
char *classtable, char *statetable);
node *createnode(char *thekey, char *thedata);
unsigned int insert(node *parent, 
 char *thekey, char *thedata, int depth);
node *lookup(node *thetable, char *thekey);
void destroy(node *thetable);
void dump(node *thetable);
int compare(unsigned char *string1, unsigned char *string2);
D(1).  Main Routine

// main
 
int main(int argc, char *argv[])
 {
 int    output;
 logicalsensitive;
 codetype language;
 char   *outputname;
 char   *dictname;
 logicalerrors;
 int    index;
 char   *thetail;
 Handle thehandle;
 node   *symbols;
 int    input;
 int    buffersize;
 
 initmac();
 
// “output” is the fd of the output file, initially stdout
// “sensitive” is the case sensitivity, initially insensitive
// “language” is the language to parse, initially unknown
 
 output = stdoutfd;
 sensitive = false;
 language = nocode;
 
// “outputname” is the name of the output file
// “dictname” is the name of the dictionary file
// “errors” is the error flag, initially indicating no errors
 
 outputname = nil;
 dictname = nil;
 errors = false;
 
// command line interpreter: first pass
 
 for (index = 1; index < argc; index++)
 {
 
 if (argv[index][0] == ‘-’)
 {
 
 switch (argv[index][1])
 {
 
// “-p” and “-c” options set 
// language type; these override 
// any previous setting
 
 case ‘C’:
 case ‘c’:
 language = ccode;
 break;
 
 case ‘P’:
 case ‘p’:
 language = pascalcode;
 break;
 
// “-s” option makes Canon case sensitive
 
 case ‘S’:
 case ‘s’:
 sensitive = true;
 break;
 
// “-o” option names the output file; 
// remember the name and read 
// the file later
 
 case ‘O’:
 case ‘o’:
 index++;
 if (outputname == nil)
 outputname = argv[index];
 else
 errors = true;
 break;
 
// “-d” option names the dictionary file; 
// remember the name and read 
// the file later
 
 case ‘D’:
 case ‘d’:
 index++;
 if (dictname == nil)
 dictname = argv[index];
 else
 errors = true;
 break;
 
 default:
 errors = true;
 break;
 
 }
 
 }
 else if (language == nocode)
 {
// argv[index] is the name of an 
// input file; if “language” has 
// not changed since initialization,
// set “language” according to 
// file name
 thetail = argv[index] 
 + strlen(argv[index]) - 2;
 if (compare(thetail, “.p”) == 0)
 language = pascalcode;
 else if (compare(thetail, “.c”) == 0)
 language = ccode;
 }
 }
 
// exit if errors were found in the first pass
 if (errors)
 exit(2);
 
// if “language” is still unknown, set it to Pascal
 if (language == nocode)
 language = pascalcode;
 
// load the case table
 if (sensitive)
 thehandle = GetResource(‘TABL’, 4002);
 else
 thehandle = GetResource(‘TABL’, 4001);
 HLock(thehandle);
 CASETABLE = (unsigned char *) *thehandle;
 
// copy the dictionary into the symbol table
 if (dictname == nil)
 exit(2);
 
 symbols = parser(dictname, language);
 if (symbols == nil)
 exit(2);
 
// if “outputname” has been found, open the output file
 if (outputname != nil)
 {
 output = openoutput( argv[++index], output);
 if (output < 0)
 exit(2);
 }
 
// “input” is the fd of the input file, initially stdin
// “thehandle” is the input buffer, initially empty
// “buffersize” is the size of “thehandle”
 input = stdinfd;
 thehandle = NewHandle(0);
 buffersize = 0;
 
// command line interpreter: second pass
 for (index = 1; index < argc; index++)
 {
// skip all options (read in first pass)
 if (argv[index][0] == ‘-’)
 {
 switch (argv[index][1])
 {
 case ‘D’:
 case ‘O’:
 case ‘d’:
 case ‘o’:
 index++;
 }
 }
 else
 {
 
// argv[index] is the name of an 
// input file; open the file and 
// read it into the input buffer
 input = open(argv[index], O_RDONLY);
 if (input < 0)
 exit(2);
 
 buffersize = readinput(input, thehandle);
 if (buffersize < 0)
 exit(2);
 
 close(input);
 
// call “filter” to read the input buffer 
// and write filtered output
 HLock(thehandle);
 filter(*thehandle, buffersize, 
 output, language, symbols);
 HUnlock(thehandle);
 }
 }
 
// if “input” is still a standard unit 
// number, then no input file was 
// opened, and input must be from
// standard input
 if (stdunit(input))
 {
 buffersize = readinput(input, thehandle);
 if (buffersize < 0)
 exit(2);
 
// call “filter” to read the input buffer 
// and write filtered output
 HLock(thehandle);
 filter(*thehandle, buffersize, 
 output, language, symbols);
 HUnlock(thehandle);
 }
 
// wrapup:  dispose of the input buffer, 
// close “output” if the program 
// opened it and dispose of the symbol table
 DisposHandle(thehandle);
 
 if (notstdunit(output))
 close(output);
 destroy(symbols);
 
 exit(0);
 }

D(2). Case Sensitivity

This is the string comparison routine to use in place of “strcmp” in the symbol table “insert” and “lookup” routines. The only other change I made to those routines was to rename the local variable “compare” “difference” (to avoid conflicts with this routine name).

The routine functions just like the C routine: it returns a negative number if string1 is less than string2, positive it string1 > string2, and zero if they’re equal. The actual number returned is simply the difference between the first pair of different characters. CASETABLE is a global pointer to the appropriate transliteration table.

// compare
int compare(unsigned char *string1, 
 unsigned char *string2)
 {
 register int    char1;
 register int    char2;
 register int    difference;
 
 char1 = *string1++;
 char2 = *string2++;
 
 while (char1 || char2)
 {
 difference = CASETABLE[char1]  - CASETABLE[char2];
 if (difference)
 return(difference);
 
 char1 = *string1++;
 char2 = *string2++;
 }
 return(0);
 }

D(3). Parsing the Dictionary

I parse the dictionary in two steps: lexical analysis and parsing. The “gettoken” routine breaks the input into tokens, which the “parser” routine fits together into substitution specifications.

D(3)(a). Lexical Analyser

This routine is similar to the lexical analyzer I used in my fourth article. The major difference is that it returns tokens as it finds them, rather than keeping control from the beginning to the end of the file. It knows that it has found a token when it gets a negative state number; it converts it into the token number that the parser expects, and returns it. (This is probably unduly complex; I should have just let the parser use negative token numbers and avoided the conversion.)

// gettoken
 
int gettoken(char *buffer, 
 int buffersize, char *thestring,
 char *classtable, char *statetable)
 {
 static int position = 0;
 
 int    thestate;
 unsigned char   thechar;
 int    theclass;
 int    newstate;
 
// start the machine in state 0
 thestate = 0;
 
 while (position < buffersize)
 {
// read the next character, look up its 
// class, and get the new state
 thechar = buffer[position++];
 theclass = classtable[thechar];
 newstate = statetable[classcount * thestate + theclass];
 
 switch (newstate)
 {
// -3 => ERR, -2 => CR; in either case, 
// just return the the token number
 case -3:
 case -2:
 return(- 1 - newstate);
 
// -1 => ID; return the token number
// and the identifier in “thestring”
 case -1:
 *thestring = ‘\0’;
 position--;
 return(- 1 - newstate);
 
 case 0:
 if (thestate == 1)
 position--;
 break;
 
 case 1:
 break;
 
 case 2:
 *thestring++ = thechar;
 break;
 }
 
 thestate = newstate;
 
 }
 return(-1);
 }

D(3)(b). Parser

The first half of this routine is set-up work. In addition to loading its own state machine, the parser also fetches gettoken’s state machine. It’s easier to do the work once, here, than to repeat it each time I can gettoken. The it also opens the dictionary file, reads it in, and so on. Eventually, it gets to do some parsing, and this should look familiar.

There is one complication: gettoken will not only return a token number but will, in the case of an identifier, also return the token’s text. I don’t want to overwrite one identifier when I read the next, so I pass a pointer to one string at the beginning of the line, and then a pointer to a second string when I want to read the next identifier.

// parser
node *parser(char *dictname, 
 codetype language)
 {
 Handle thehandle;
 char   *parsetable;
 char   *classtable;
 char   *statetable;
 int    thefile;
 int    buffersize;
 char   *buffer;
 node   *symbols;
 int    thestate;
 int    newstate;
 int    theline;
 int    errors;
 int    thetoken;
 char   thekey[256];
 char   thedata[256];
 char   dummy[256];
 char   *thestring;
 
// “parsetable” is the parser’s state machine
 thehandle = GetResource(‘TABL’, 1000);
 HLock(thehandle);
 parsetable = *thehandle;
 
// “classtable” is the character class table
 thehandle = GetResource(‘TABL’, 1001);
 HLock(thehandle);
 classtable = *thehandle;
 
// “statetable” is the lexical state machine
 if (language == pascalcode)
 thehandle = GetResource(TABL’, 2001);
 else
 thehandle = GetResource(‘TABL’, 2002);
 HLock(thehandle);
 statetable = *thehandle;
 
// open the dictionary file...
 thefile = open(dictname, O_RDONLY);
 if (thefile < 0)
 return(nil);
 
// and read it into the buffer
 thehandle = NewHandle(0);
 buffersize = readinput(thefile, thehandle);
 if (buffersize < 0)
 {
 close(thefile);
 return(nil);
 }
 
 close(thefile);
 
 HLock(thehandle);
 buffer = (char *)*thehandle;
 
// “symbols” is the symbol table
 symbols = createnode(“”, “”);
 
// start the machine in state 0, and on line 1
 thestate = 0;
 theline = 1;
 errors = 0;
 
// read the first identifier into “thekey”
 thestring = &thekey;
 thetoken = gettoken(buffer, buffersize, thestring, 
 classtable, statetable);
 
 while (thetoken >= 0)
 {
 newstate = parsetable[ 3 * thestate + thetoken];
 
 switch (newstate)
 {
// if we got here from state 1, then we 
// read only one identifier; if from 
// state 2, we read both “thekey”
// and “thedata”
// state 0 is the beginning of a line, so 
// increment the line counter and set 
// “thestring” to “thekey”
 
 case 0:
 if (thestate == 1)
 thetoken = insert(symbols, thekey, thekey, 0);
 else if (thestate == 2)
 thetoken = insert(symbols, thekey, thedata, 0);
 if (thetoken == 4)
 errors++;
 theline++;
 thestring = &thekey;
 break;
 
// having read one identifier into 
// “thekey”, the next one should go 
// into “thedata”
 case 1:
 thestring = &thedata;
 break;
 
// having read one identifier into 
// “thekey”, and the next one 
// “thedata”, read anything else into
// “dummy”
 case 2:
 thestring = &dummy;
 break;
 
// case 3 is the error case; if we just 
// got here, write an error message
 case 3:
 if (thestate != newstate)
 fprintf(stderr,  “”);
 errors++;
 break;
 }
 
 thestate = newstate;
 thetoken = gettoken(buffer,
 buffersize, thestring, 
 classtable, statetable);
 }
 
 DisposHandle(thehandle);
 
 if (errors > 0)
 {
 destroy(symbols);
 return(nil);
 }
 
 return(symbols);
 }

D(4). Making Substitutions

This routine should be familiar by now, except for when it finds an identifier. The state table flags identifiers with a state of -1; when the routine reaches that state, it looks up the identifier in the symbol table and performs any required substitution. In all other cases (things other than identifiers, or identifiers with no substitution), the routine simply copies the input to the output.

// filter
int filter(char *inbuffer, 
 int buffersize, int output,
 codetype language, node *symbols)
 {
 
 int    inposition;
 int    outposition;
 int    thetoken;
 node   *thenode;
 int    thelength;
 Handle thehandle;
 char   *classtable;
 char   *statetable;
 char   outbuffer[truebuffsize];
 int    thestate;
 unsigned char   thechar;
 int    theclass;
 int    newstate;
 int    writesize;

// “inposition” is the current read position
// “outposition” is the current write position
// “thetoken” is the position of the 
// beginning of the current identifier
 inposition = 0;
 outposition = 0;
 thetoken = 0;

// “classtable” converts characters into classes
 thehandle = GetResource(‘TABL’, 1001);
 HLock(thehandle);
 classtable = *thehandle;

// “statetable” is the state machine
 if (language == pascalcode)
 thehandle = GetResource(‘TABL’, 3001);
 else
 thehandle = GetResource(‘TABL’, 3002);
 HLock(thehandle);
 statetable = *thehandle;
 
// start the machine in state 0
 thestate = 0;
 while (inposition < buffersize)
 {
// read the next character, find its class and the new state
 thechar = inbuffer[inposition++];
 theclass = classtable[thechar];
 newstate = statetable[classcount * thestate + theclass];
 
 switch (newstate)
 {
// found an identifier:  if it is in the 
// symbol table, replace it with the 
// table’s data.  Then go to state 0.
 case -1:
 inposition--;
 outbuffer[outposition] = ‘\0’;
 thenode = lookup(symbols, &outbuffer[thetoken]);
 if (thenode != nil)
 {
 outposition -= strlen(&outbuffer[thetoken]);
 thelength = strlen(thenode->data);
 BlockMove((Ptr)thenode->data,
 &outbuffer[outposition], thelength);
 outposition += thelength;
 }
 newstate = 0;
 break;

// retract if going from state 2 to state 
// 0; otherwise, copy input to output
 case 0:
 if (thestate == 2)
 inposition--;
 else
 outbuffer[outposition++] = thechar;
 break;

// reading an identifier:  if this is the 
// beginning, record the position for 
// later use.  Then, fall through to 
// the default
 case idstate:
 if (thestate != idstate)
 thetoken = outposition;

// all other cases, copy input to output
 default:
 outbuffer[outposition++] = thechar;
 break;
 }

// if the output buffer fills up, and 
// we’re not in the middle of an 
// identifier, write it to disk
 if ((outposition >= nombuffsize)
 && (thestate != idstate) 
 && (newstate != idstate))
 {
 outposition = writeoutput(
 output, outbuffer, outposition);
 if (outposition < 0)
 return(outposition);
 }
 
 thestate = newstate;
 }

// write the output buffer to disk
 writesize = write(output, outbuffer, outposition);
 return(writesize);
 }

E. Conclusion

The tool, as I have presented it here, is not quite perfect. It is very slow. I ran it using the “cannon.dict” file that comes with MPW; after first finding all the duplicate lines, it took 22 minutes just to load the dictionary! I was stunned.

The problem, it turned out, was the “createnode” routine. There are over 3200 lines in the dictionary file, and “createnode” calls “NewPtr” three times for each line, for a total of almost 10,000 calls to NewPtr. And NewPtr is very slow. When I re-wrote the tool to reduce the 10,000 to a few dozen, the time to load the dictionary dropped to 16 seconds. (Yes, I’m bragging...)

I chose not to present the faster version in this article, because I feel it confuses the issue. The changes I made are not related to the topic, and make the code more complicated. Instead, I’ve included both versions on the source code disk, and I’ll now give a quick description of the differences between the two.

I got rid of two-thirds of the NewPtr calls by leaving the data where I found it. In the above version, I read the file into memory, then find identifiers in the data and copy them into strings, which I pass to “createnode”. Createnode in turn copies these strings into its data structures. In the faster version, I find identifiers in the data and write nulls at their ends, then pass pointers to “createnode”, which simply copies the pointers into the appropriate node fields. So in addition to 6000 NewPtrs, I’ve saved 12,000 string copies.

The complication is writing the null character. There are times when you don’t want to overwrite the following character right away. Suppose it’s a return character...

I reduced the remaining 3000 calls to a handful by allocating the nodes in large arrays. I put new nodes in the free slots of the array until it fills up, with no calls to NewPtr. Once the array is full, I have to use NewPtr to create a new one, but since I use a large array size, this doesn’t happen very often.

 
AAPL
$118.93
Apple Inc.
-0.07
MSFT
$47.81
Microsoft Corpora
+0.06
GOOG
$541.83
Google Inc.
+1.46

MacTech Search:
Community Search:

Software Updates via MacUpdate

Adobe Photoshop Elements 13.0 - Consumer...
Adobe Photoshop Elements 12--the #1 selling consumer photo editing software--helps you edit pictures with powerful, easy-to-use options and share them via print, the web, Facebook, and more.Version... Read more
Skype 7.2.0.412 - Voice-over-internet ph...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
HoudahSpot 3.9.6 - Advanced file search...
HoudahSpot is a powerful file search tool built upon MacOS X Spotlight. Spotlight unleashed Create detailed queries to locate the exact file you need Narrow down searches. Zero in on files Save... Read more
RapidWeaver 6.0.3 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
iPhoto Library Manager 4.1.10 - Manage m...
iPhoto Library Manager lets you organize your photos into multiple iPhoto libraries. Separate your high school and college photos from your latest summer vacation pictures. Or keep some photo... Read more
iExplorer 3.5.1.9 - View and transfer al...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
MacUpdate Desktop 6.0.3 - Discover and i...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
SteerMouse 4.2.2 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. It also supports Apple Mighty Mouse very well. SteerMouse can assign various functions to buttons that Apple's software does not allow,... Read more
iMazing 1.1 - Complete iOS device manage...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
PopChar X 7.0 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more

Latest Forum Discussions

See All

Mystery Case Files: Dire Grove, Sacred G...
Mystery Case Files: Dire Grove, Sacred Grove HD Review By Jennifer Allen on November 28th, 2014 Our Rating: iPad Only App - Designed for the iPad A decent new installment for the popular Mystery Case Files series.   | Read more »
Castaway Paradise – Tips, Tricks, and St...
Ahoy there, castaways: Were you curious about our own thoughts regarding this pristine shipwreck? Check out our Castaway Paradise review! Castaway Paradise is out for iOS, finally giving mobile gamers the opportunity to enjoy the idyllic lifestyle... | Read more »
Castaway Paradise VIP Subs are on Sale f...
Castaway Paradise VIP Subs are on Sale for a Limited Time, and a Special Holiday Update is Coming Soon Posted by Rob Rich on November 28th, 2014 [ | Read more »
Primitive Review
Primitive Review By Jordan Minor on November 28th, 2014 Our Rating: :: FOLK ARTUniversal App - Designed for iPhone and iPad True to its name, Primitive is about as straightforward as runners get.   | Read more »
7 tips to get ahead of the competition i...
7 tips to get ahead of the competition in Dynasty of Dungeons Posted by Simon Reed on November 28th, 2014 [ permalink ] Playcrab has launched their action-packed new dungeon crawler, Dynasty of Dungeons, today. | Read more »
Master of Tea Kung Fu Review
Master of Tea Kung Fu Review By Jordan Minor on November 28th, 2014 Our Rating: :: ONE DROP RULESUniversal App - Designed for iPhone and iPad Master of Tea Kung Fu is a creative and complex caffeinated brawler.   | Read more »
Monster Strike Review
Monster Strike Review By Campbell Bird on November 28th, 2014 Our Rating: :: BILLIARD STRATEGYUniversal App - Designed for iPhone and iPad Collect monsters and battle by flinging them across the battlefield in this strangely... | Read more »
Proun+ Review
Proun+ Review By Jennifer Allen on November 28th, 2014 Our Rating: :: TWITCHY RACINGUniversal App - Designed for iPhone and iPad Twitchy racing aplenty in Proun+, an enjoyably tricky title.   | Read more »
Lucha Amigos (Games)
Lucha Amigos 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Forget Ninja Turtles, and meet Wrestlers Turtles! Crazier, Spicier and…Bouncier! Sling carapaces of 7 Luchadores to knock all... | Read more »
Record of Agarest War Zero (Games)
Record of Agarest War Zero 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: HyperDevbox Holiday Turkey Black Friday Special Pricing! To celebrate the opening of the holiday season HyperDevbox... | Read more »

Price Scanner via MacPrices.net

Best Black Friday Deal: 15-inch Retina MacBoo...
 B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for $300 off MSRP as part of their Black Friday sale. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina... Read more
Up To 75% Off Infovole Text Apps Over Black F...
Infovole’s entire range of apps, including the Textkraft family of word processors for iPads and iPhones, is being offered at 50-75% off over the Black Friday and Cyber Monday weekend. The five-day... Read more
Black Friday: Up to $60 off Mac minis, NY tax...
 B&H Photo has new 2014 Mac minis on sale for up to $60 off MSRP as part of their Black Friday sale. Shipping is free, and B&H charges NY sales tax only: - 1.4GHz Mac mini: $449.99 $50 off... Read more
Black Friday: 27-inch 5K iMac for $2299, save...
 B&H Photo continues to offer Black Friday sale prices on the 27″ 3.5GHz 5K iMac, in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP... Read more
Karalux Announces 24K Gold-Plated iPhone 6
Karalux, a Vietnam-based jewellery firm, has launched a unique 24 karat gold-plated iPhone 6 version with gold-cast monolithic dragon on its back panel. The real 24 karat gold plated enclosure doesn’... Read more
Black Friday: 13-inch 2.6GHz Retina MacBook P...
 B&H Photo has lowered their price for the 13″ 2.6GHz/128GB Retina MacBook Pro to $1159 for Black Friday. That’s $140 off MSRP, and it’s the lowest price for this model (except for Apple’s $1099... Read more
View all the Black Friday sales on our Mac Pr...
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers. View Black Friday sale prices at a... Read more
Black Friday: 11-inch MacBook Air for $779, s...
 Best Buy has lowered their price for the 2014 11″ 1.4GHz/128GB MacBook Air to $779.99 for Black Friday. That’s $120 off MSRP. Choose free shipping or free local store pickup (if available). Sale... Read more
Apple Store Black Friday sale for 2014: $100...
BLACK FRIDAY The Apple Store has posted their Black Friday deals for 2014. Receive a $100 PRODUCT(RED) branded iTunes gift card with the purchase of select Macs, $50 with iPads, and $25 with iPods,... Read more
Black Friday: 15% off iTunes Gift Cards
Staples is offering 15% off $50 and $100 iTunes Gift Cards on their online store as part of their Black Friday sale. Click here for more information. Shipping is free. Best Buy is offering $100... Read more

Jobs Board

Position Opening at *Apple* - Apple (United...
…Summary** As a Specialist, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** Being a Business Manager at an Apple Store means you're the catalyst for businesses to discover and leverage the power, ease, and flexibility of Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.