home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume28 / grok / part01 next >
Encoding:
Text File  |  1994-05-29  |  75.7 KB  |  2,924 lines
  1. Newsgroups: comp.sources.unix
  2. From: wendt@cs.colostate.edu (alan l wendt)
  3. Subject: v28i044: grok - match regular expressions and correct errors, V1.0, Part01/01
  4. Message-id: <1.770288657.8654@gw.home.vix.com>
  5. Sender: unix-sources-moderator@gw.home.vix.com
  6. Approved: vixie@gw.home.vix.com
  7.  
  8. Submitted-By: wendt@cs.colostate.edu (alan l wendt)
  9. Posting-Number: Volume 28, Issue 44
  10. Archive-Name: grok/part01
  11.  
  12. Grok (get regular expression and make OK) is like grep except that it
  13. corrects its input to instances of the regular expression, using a
  14. minimum-cost correction.  Grok uses flex code.  Its only argument is a
  15. filename containing character-to-character correction costs, a maximum
  16. acceptable cost for the string, and a regular expression.
  17.  
  18. The code has been tested on 286 Xenix 2.3.2 (large model) and DEC 3100
  19. Ultrix 4.2.
  20.  
  21. This is version 1.0.
  22.  
  23. Contributors:  Alan Wendt, Vern Paxson, Eugene Myers
  24.  
  25. #    This is a shell archive.
  26. #    Remove everything above and including the cut line.
  27. #    Then run the rest of the file through sh.
  28. #----cut here-----cut here-----cut here-----cut here----#
  29. #!/bin/sh
  30. # shar:    Shell Archiver
  31. #    Run the following text with /bin/sh to create:
  32. #    Makefile
  33. #    README
  34. #    ccl.c
  35. #    flexdef.h
  36. #    grok.1
  37. #    misc.c
  38. #    ncnb.def
  39. #    nfa.c
  40. #    parse.h
  41. #    parse.y
  42. #    scan.l
  43. #    sym.c
  44. #    test.in
  45. #    test.out
  46. # This archive created: Tue Nov 17 09:30:20 1992
  47. cat << \SHAR_EOF > Makefile
  48.  
  49. #
  50. # DEC 3100 Ultrix
  51. #
  52. LDFLAGS =
  53. CFLAGS =
  54.  
  55. #
  56. # Xenix 286 2.3.2 large model
  57. #
  58. #LDFLAGS = -M2l -g -F 4000 
  59. #CFLAGS = -I$I -DUNIX=1 -LARGE -DUSG=1 -DSV
  60.  
  61. .c.o:    ;     -$(CC) $(LDFLAGS) $(CFLAGS) -c $*.c
  62.  
  63. # correction
  64.  
  65. scan.c:    scan.l
  66.     flex -I scan.l
  67.     mv lex.yy.c scan.c
  68.  
  69. REPAIRFILES =  nfa.o ccl.o parse.o sym.o misc.o scan.o
  70.  
  71. parse.h parse.c : parse.y
  72.     yacc -d parse.y
  73.     @mv y.tab.c parse.c
  74.     @mv y.tab.h parse.h
  75.  
  76. grok:    $(REPAIRFILES)
  77.     cc $(LDFLAGS) -o grok $(REPAIRFILES)
  78.  
  79. clean:
  80.     rm *.o *.log scan.c parse.c
  81.  
  82. test:    grok
  83.     grok ncnb.def < test.in > test.out.tmp
  84.     diff test.out test.out.tmp
  85. SHAR_EOF
  86. cat << \SHAR_EOF > README
  87.  
  88. Grok (get regular expression and make OK) is like grep except that it
  89. corrects its input to instances of the regular expression, using a
  90. minimum-cost correction.  Grok uses flex code.  Its only argument is
  91. a filename containing character-to-character correction costs, a
  92. maximum acceptable cost for the string, and a regular expression.
  93.  
  94. The code has been tested on 286 Xenix 2.3.2 (large model)
  95. and DEC 3100 Ultrix 4.2.
  96.  
  97. Contributors:  Alan Wendt, Vern Paxson, Eugene Myers
  98. SHAR_EOF
  99. cat << \SHAR_EOF > ccl.c
  100. /* ccl - routines for character classes */
  101.  
  102. /*
  103.  * Copyright (c) 1987, the University of California
  104.  * 
  105.  * The United States Government has rights in this work pursuant to
  106.  * contract no. DE-AC03-76SF00098 between the United States Department of
  107.  * Energy and the University of California.
  108.  * 
  109.  * This program may be redistributed.  Enhancements and derivative works
  110.  * may be created provided the new works, if made available to the general
  111.  * public, are made available for use by anyone.
  112.  */
  113.  
  114. #include "flexdef.h"
  115.  
  116. /* ccladd - add a single character to a ccl
  117.  *
  118.  * synopsis
  119.  *    int cclp;
  120.  *    char ch;
  121.  *    ccladd( cclp, ch );
  122.  */
  123.  
  124. ccltest( cclp, ch )
  125.     struct Ccl *cclp;
  126.     char ch;
  127.     {
  128.     /* SUPPRESS 53 */
  129.     return cclp->c[(ch & (CSIZE - 1)) >> 3] & (1 << (ch & 7));
  130.     }
  131.  
  132. ccladd( cclp, ch )
  133.     struct Ccl *cclp;
  134.     char ch;
  135.     {
  136.     /* SUPPRESS 53 */
  137.     cclp->c[(ch & (CSIZE - 1)) >> 3] |= 1 << (ch & 7);
  138.     }
  139.  
  140.  
  141. /* cclinit - make an empty ccl
  142.  *
  143.  * synopsis
  144.  *    int cclinit();
  145.  *    cclinit( &newccl );
  146.  */
  147.  
  148. void cclinit( ccl )
  149.     struct Ccl *ccl;
  150.     {
  151.     bzero(ccl->c, sizeof(*ccl));
  152.     }
  153.  
  154.  
  155. /* cclnegate - negate a ccl
  156.  *
  157.  * synopsis
  158.  *    int cclp;
  159.  *    cclnegate( ccl );
  160.  */
  161.  
  162. cclnegate( cclp )
  163.     struct Ccl *cclp;
  164.     {
  165.     int        i;
  166.     for (i = 0; i < sizeof(*cclp); i++)
  167.     {
  168.     cclp->c[i] ^= -1;
  169.     }
  170.     }
  171.  
  172.  
  173.     
  174. /*  BUGGY IF CCL IS EMPTY!!! */
  175. int ccl2nfa( cclp )
  176.     struct Ccl *cclp;
  177.     {
  178.     int        i, j;
  179.     int            result = 0;
  180.  
  181.     for (i = 0; i < CSIZE; i++)
  182.     {
  183.     j = cclp->c[i >> 3];
  184.     if (j & (1 << (i & 7)))  
  185.         {
  186.         if (result == 0)
  187.         {
  188.         result = mkstate( i );
  189.         }
  190.         else
  191.         {
  192.         result = mkor( result, mkstate( i ) );
  193.         }
  194.         }
  195.     }
  196.     return result;
  197.     }
  198. SHAR_EOF
  199. cat << \SHAR_EOF > flexdef.h
  200. #include <stdio.h>
  201.  
  202. #ifdef SV
  203. #include <string.h>
  204. #define bzero(s, n) memset((char *)(s), '\000', (unsigned)(n))
  205. #else
  206. #include <strings.h>
  207. #endif
  208.  
  209. char *sprintf(); /* keep lint happy */
  210.  
  211. #define min(x,y) (x < y ? x : y)
  212. #define max(x,y) (x > y ? x : y)
  213.  
  214. #define true 1
  215. #define false 0
  216.  
  217. /* NIL must be 0.  If not, its special meaning when making equivalence classes
  218.  * (it marks the representative of a given e.c.) will be unidentifiable
  219.  */
  220. #define NIL 0
  221.  
  222. #define NO_TRANSITION NIL
  223. #define INFINITY -1    /* for x{5,} constructions */
  224.  
  225. /* variables used in the flex input routines:
  226.  * datapos - characters on current output line
  227.  * dataline - number of contiguous lines of data in current data
  228.  *    statement.  Used to generate readable -f output
  229.  * skelfile - fd of the skeleton file
  230.  * yyin - input file
  231.  * temp_action_file - temporary file to hold actions
  232.  * action_file_name - name of the temporary file
  233.  * infilename - name of input file
  234.  * linenum - current input line number
  235.  */
  236.  
  237. extern int linenum;
  238.  
  239. /* size of input alphabet - should be size of ASCII set */
  240. #define CSIZE 128
  241.  
  242. struct Ccl
  243.     {
  244.     char    c[CSIZE/8];
  245.     };
  246.  
  247.  
  248. /* variables for flags:
  249.  * syntaxerror - true if a syntax error has been found
  250.  */
  251.  
  252. extern int syntaxerror;
  253.  
  254. #define SYM_EPSILON 0    /* to mark transitions on the symbol epsilon */
  255.  
  256. /* variables for nfa machine data:
  257.  * current_mns - current maximum on number of NFA states
  258.  * firstst - first physical state of a fragment
  259.  * lastst - last physical state of fragment
  260.  * finalst - last logical state of fragment
  261.  * transchar - transition character that got us into this state
  262.  * accptnum - accepting number
  263.  * lastnfa - last nfa state number created
  264.  * edgeptr - pointer to first Edge out of this state
  265.  * first logical state of a fragment is its machine number
  266.  */
  267.  
  268. #define MAXIMUM_MNS 30000
  269.  
  270. struct state {
  271.     struct Edge    *edgeptr;
  272.     int        firstst;
  273.     int        lastst;
  274.     int        finalst;
  275.     int        ninedges;
  276.     int        noutedges;
  277.     int        temp;
  278.     unsigned char transchar;
  279.     } *states[15000];
  280.  
  281. extern int current_mns;
  282. extern int lastnfa, firstnfa;
  283.  
  284.  
  285. extern int ccl2nfa();
  286.  
  287. #if 0
  288. /*
  289.  *  transfrom - from edge state number
  290.  *  transto   - to state number
  291.  */
  292. #define INITIAL_MNE 2000    /* default maximum number of nfa edges */
  293. #define MNE_INCREMENT 1000    /* amount to bump above by if it's not enough */
  294. #define MAXIMUM_MNE 31999
  295. extern int current_mne;        /* current max # of edges */
  296. extern int current_ne;        /* current # of edges */
  297. #endif
  298.  
  299. struct Edge {
  300.     struct Edge *next, *prior;    /* links all edges from a given state */
  301.     int    from, to;        /* from & to state numbers */
  302.     };
  303.  
  304. /*
  305.  * num_reallocs - number of times it was necessary to realloc() a group
  306.  *          of arrays
  307.  */
  308. extern int num_reallocs;
  309.  
  310. extern char *malloc(), *realloc(), *sbrk();
  311.  
  312. #define allocate_integer_array(size) \
  313.     (int *) allocate_array( size, sizeof( int ) )
  314.  
  315. #define reallocate_integer_array(array,size) \
  316.     (int *) reallocate_array( (char *) array, size, sizeof( int ) )
  317. char *allocate_array(), *reallocate_array();
  318.  
  319. struct hash_entry
  320.     {
  321.     struct hash_entry *prev, *next;
  322.     char *name;
  323.     char *str_val;
  324.     int int_val;
  325.     } ;
  326.  
  327. typedef struct hash_entry *hash_table[];
  328.  
  329. #define NAME_TABLE_HASH_SIZE 101
  330. #define START_COND_HASH_SIZE 101
  331.  
  332. /* maximum line length we'll have to deal with */
  333. #define MAXLINE BUFSIZ
  334.  
  335. #define allocate_character_array(size) allocate_array( size, sizeof( char ) )
  336.  
  337. #define reallocate_character_array(array,size) \
  338.     reallocate_array( array, size, sizeof( char ) )
  339. /*
  340.  * nmstr - last NAME scanned by the scanner
  341.  */
  342.  
  343. extern char nmstr[MAXLINE];
  344.  
  345. /* used to communicate between scanner and parser.  The type should really
  346.  * be YYSTYPE, but we can't easily get our hands on it.
  347.  */
  348. extern int yylval;
  349.  
  350. char    delete_cost[128];
  351. char    insert_cost[128];
  352. char    correct_cost[128][128];
  353. int    tolerance;            /* maximum tolerable error */
  354. SHAR_EOF
  355. cat << \SHAR_EOF > grok.1
  356. .\"
  357. .\"    @(#)grok.1    6.5 (CSU) 10/11/91
  358. .\"
  359.  
  360. .TH GROK 1 "November 11, 1991
  361. .SH NAME
  362. grok \- Match and repair errors in regular expressions
  363. .SH SYNOPSIS
  364. .in +\w'\fBgrok \fR'u
  365. .ti -\w'\fBgrok \fR'u
  366. \fBgrok \fR \fIdefinition-file\fR
  367.  
  368. .SH DESCRIPTION
  369. .I Grok
  370. matches instances of \fIlex\fR-style regular expressions from the input
  371. and prints them.
  372. In addition, it tries to repair input lines to make them instances of the
  373. regular expression, using single-character insertions, deletions, and 
  374. substitutions.
  375. Different single-character edits can be assigned different costs,
  376. and \fIgrok\fR will find a repair of lowest total cost.
  377.  
  378. The algorithm used to find lowest-cost repairs takes time proportional
  379. to the product of the length of the input and the cost of the repair.
  380. A maximum repair cost tolerance must be supplied.
  381. \fIgrok\fR ignores input lines that cannot be repaired within the tolerance.
  382. The match is \fIanchored\fR, unlike the matching performed by \fIgrep\fR.
  383.  
  384. The \fIdefinition-file\fR contains entries to define character
  385. repair costs, followed by a pair of percent signs alone on a line,
  386. followed by a single regular expression.   For example, the following 
  387. defines repair for lines scanned from a bank statement:
  388.  
  389. .ne 4
  390. .nf
  391. .ft L
  392. % correct anything to anything else for 3
  393. %correct        .        .        3
  394.  
  395. % a number of common numeric misreads.  4 is often read as (+
  396. % but we cannot correct string to string.
  397. %correct        "Z"        "2"        1
  398. %correct        "z"        "2"        1
  399. %correct        "S"        "5"        1
  400. %correct        "s"        "5"        1
  401. %correct        "l"        "1"        1
  402. %correct        "i"        "1"        1
  403. %correct        "I"        "1"        1
  404. %correct        "o"        "0"        1
  405. %correct        "O"        "0"        1
  406. %correct        "r"        "5"        1
  407. %correct        "?"        "9"        1
  408. %correct        "+"        "4"        1
  409.  
  410. % default insertion cost is 2
  411. %insert         .          2
  412.  
  413. % charge extra for numbers to avoid hallucinating numbers.
  414. %insert         [0-9]      3
  415.  
  416. % delete anything for 2.  correction cost <= insert + delete.
  417. %delete         .          2
  418. %delete         [0-9]      3
  419.  
  420. % the maximum tolerable error cost 
  421. %tolerance      20
  422. %%
  423. ([ ]{20,30}[+ ]([ ]{5,7}[0-9]{5}|"NO ITEM # ")[ ]{3,4}[0-9]{9}
  424. [ ]{5,7}[0-1][0-9]-[0-3][0-9][ ]{6,13}(""|[1-9][0-9]{0,2}|[1-9]
  425. [0-9]{0,2}","[0-9]{3})\.[0-9]{2}([ ]{5,10}[+ ]([ ]{5,7}[0-9]{5}|
  426. "NO ITEM # ")[ ]{3,4}[0-9]{9}[ ]{5,7}[0-1][0-9]-[0-3][0-9][ ]{6,13}
  427. (""|[1-9][0-9]{0,2}|[1-9][0-9]{0,2}","[0-9]{3})\.[0-9]{2})?)|
  428. ("       ENCLOSED           NUMBER        NUMBER".*)
  429.  
  430. .ft R
  431. .fi
  432.  
  433. \fB%correct\fR, \fB%insert\fR, and \fB%delete\fR lines supply repair costs
  434. to replace each character with each other, as well as for insertions
  435. and deletions.  Single-character regular expressions are accepted,
  436. and later costs overwrite earlier ones.
  437.  
  438. The regular expression has been broken into several lines for display.
  439. It defines the expected
  440. structure of important lines on one style of bank statement.
  441.  
  442. \fBGrok\fR outputs the repaired lines.
  443.  
  444. .SH BUGS
  445. No provision is made for breaking long defining expressions across lines.
  446. The NFA optimization is too slow.
  447.  
  448. .SH AUTHOR
  449. Alan Wendt.  Contributors include Eugene Myers (repair algorithm), Vern Paxson (\fBflex\fR code).
  450. SHAR_EOF
  451. cat << \SHAR_EOF > misc.c
  452. /* misc - miscellaneous flex routines */
  453.  
  454. /*
  455.  * Copyright (c) 1987, the University of California
  456.  * 
  457.  * The United States Government has rights in this work pursuant to
  458.  * contract no. DE-AC03-76SF00098 between the United States Department of
  459.  * Energy and the University of California.
  460.  * 
  461.  * This program may be redistributed.  Enhancements and derivative works
  462.  * may be created provided the new works, if made available to the general
  463.  * public, are made available for use by anyone.
  464.  */
  465.  
  466. #include <ctype.h>
  467. #include "flexdef.h"
  468.  
  469. char *malloc(), *realloc();
  470.  
  471.  
  472. /* allocate_array - allocate memory for an integer array of the given size */
  473.  
  474. char *allocate_array( size, element_size )
  475. int size, element_size;
  476.  
  477.     {
  478.     register char *mem = malloc( (unsigned) (element_size * size) );
  479.  
  480.     if ( mem == NULL )
  481.     flexfatal( "memory allocation failed in allocate_array()" );
  482.  
  483.     return ( mem );
  484.     }
  485.  
  486.  
  487. /* clower - replace upper-case letter to lower-case
  488.  *
  489.  * synopsis:
  490.  *    char clower(), c;
  491.  *    c = clower( c );
  492.  */
  493.  
  494. char clower( c )
  495. register char c;
  496.  
  497.     {
  498.     return ( isupper(c) ? tolower(c) : c );
  499.     }
  500.  
  501.  
  502. /* copy_string - returns a dynamically allocated copy of a string
  503.  *
  504.  * synopsis
  505.  *    char *str, *copy, *copy_string();
  506.  *    copy = copy_string( str );
  507.  */
  508.  
  509. char *copy_string( str )
  510. register char *str;
  511.  
  512.     {
  513.     register char *c;
  514.     char *copy;
  515.  
  516.     /* find length */
  517.     for ( c = str; *c; ++c )
  518.     continue;
  519.  
  520.     copy = malloc( (unsigned) ((c - str + 1) * sizeof( char )) );
  521.  
  522.     if ( copy == NULL )
  523.     flexfatal( "dynamic memory failure in copy_string()" );
  524.  
  525.     /* SUPPRESS 560 */
  526.     for ( c = copy; (*c++ = *str++); )
  527.        continue;
  528.  
  529.     return ( copy );
  530.     }
  531.  
  532.  
  533. /* lerrif - report an error message formatted with one integer argument
  534.  *
  535.  * synopsis
  536.  *    char msg[];
  537.  *    int arg;
  538.  *    lerrif( msg, arg );
  539.  */
  540.  
  541. lerrif( msg, arg )
  542. char msg[];
  543. int arg;
  544.  
  545.     {
  546.     char errmsg[MAXLINE];
  547.     (void) sprintf( errmsg, msg, arg );
  548.     flexerror( errmsg );
  549.     }
  550.  
  551.  
  552. /* lerrsf - report an error message formatted with one string argument
  553.  *
  554.  * synopsis
  555.  *    char msg[], arg[];
  556.  *    lerrsf( msg, arg );
  557.  */
  558.  
  559. lerrsf( msg, arg )
  560. char msg[], arg[];
  561.  
  562.     {
  563.     char errmsg[MAXLINE];
  564.  
  565.     (void) sprintf( errmsg, msg, arg );
  566.     flexerror( errmsg );
  567.     }
  568.  
  569.  
  570. /* flexerror - report an error message and terminate
  571.  *
  572.  * synopsis
  573.  *    char msg[];
  574.  *    flexerror( msg );
  575.  */
  576.  
  577. flexerror( msg )
  578. char msg[];
  579.  
  580.     {
  581.     fprintf( stderr, "flex: %s\n", msg );
  582.     exit( 1 );
  583.     }
  584.  
  585.  
  586. /* flexfatal - report a fatal error message and terminate
  587.  *
  588.  * synopsis
  589.  *    char msg[];
  590.  *    flexfatal( msg );
  591.  */
  592.  
  593. flexfatal( msg )
  594. char msg[];
  595.  
  596.     {
  597.     fprintf( stderr, "flex: fatal internal error %s\n", msg );
  598.     exit( 1 );
  599.     }
  600.  
  601.  
  602.  
  603.  
  604.  
  605.  
  606. /* myctoi - return the integer represented by a string of digits
  607.  *
  608.  * synopsis
  609.  *    char array[];
  610.  *    int val, myctoi();
  611.  *    val = myctoi( array );
  612.  *
  613.  */
  614.  
  615. int myctoi( array )
  616. char array[];
  617.  
  618.     {
  619.     int val = 0;
  620.  
  621.     (void) sscanf( array, "%d", &val );
  622.  
  623.     return ( val );
  624.     }
  625.  
  626.  
  627. /* myesc - return character corresponding to escape sequence
  628.  *
  629.  * synopsis
  630.  *    char array[], c, myesc();
  631.  *    c = myesc( array );
  632.  *
  633.  */
  634.  
  635. char myesc( array )
  636. char array[];
  637.  
  638.     {
  639.     switch ( array[1] )
  640.     {
  641.     case 'n': return ( '\n' );
  642.     case 't': return ( '\t' );
  643.     case 'f': return ( '\f' );
  644.     case 'r': return ( '\r' );
  645.     case 'b': return ( '\b' );
  646.  
  647.     case '0':
  648.         if ( isdigit(array[2]) )
  649.         { /* \0<octal> */
  650.         char c, esc_char;
  651.         register int sptr = 2;
  652.  
  653.         while ( isdigit(array[sptr]) )
  654.             /* don't increment inside loop control because the
  655.              * macro will expand it to two increments!  (Not a
  656.              * problem with the C version of the macro)
  657.              */
  658.             ++sptr;
  659.  
  660.         c = array[sptr];
  661.         array[sptr] = '\0';
  662.  
  663.         esc_char = otoi( array + 2 );
  664.         array[sptr] = c;
  665.  
  666.         if ( esc_char == '\0' )
  667.             {
  668.             synerr( "escape sequence for null not allowed" );
  669.             return ( 1 );
  670.             }
  671.  
  672.         return ( esc_char );
  673.         }
  674.  
  675.         else
  676.         {
  677.         synerr( "escape sequence for null not allowed" );
  678.         return ( 1 );
  679.         }
  680.  
  681. #ifdef NOTDEF
  682.     case '^':
  683.         {
  684.         register char next_char = array[2];
  685.  
  686.         if ( next_char == '?' )
  687.         return ( 0x7f );
  688.         
  689.         else if ( next_char >= 'A' && next_char <= 'Z' )
  690.         return ( next_char - 'A' + 1 );
  691.     
  692.         else if ( next_char >= 'a' && next_char <= 'z' )
  693.         return ( next_char - 'z' + 1 );
  694.     
  695.         synerr( "illegal \\^ escape sequence" );
  696.  
  697.         return ( 1 );
  698.         }
  699. #endif
  700.     }
  701.     
  702.     return ( array[1] );
  703.     }
  704.  
  705.  
  706. /* otoi - convert an octal digit string to an integer value
  707.  *
  708.  * synopsis:
  709.  *    int val, otoi();
  710.  *    char str[];
  711.  *    val = otoi( str );
  712.  */
  713.  
  714. int otoi( str )
  715. char str[];
  716.  
  717.     {
  718. #ifdef FTLSOURCE
  719.     fortran int gctoi()
  720.     int dummy = 1;
  721.  
  722.     return ( gctoi( str, dummy, 8 ) );
  723. #else
  724.     int result;
  725.  
  726.     (void) sscanf( str, "%o", &result );
  727.  
  728.     return ( result );
  729. #endif
  730.     }
  731.  
  732.  
  733.  
  734. #if 0
  735. /* reallocate_array - increase the size of a dynamic array */
  736.  
  737. char *reallocate_array( array, size, element_size )
  738. char *array;
  739. int size, element_size;
  740.  
  741.     {
  742.     register char *new_array = realloc( array,
  743.                     (unsigned) (size * element_size ));
  744.  
  745.     if ( new_array == NULL )
  746.     flexfatal( "attempt to increase array size failed" );
  747.     
  748.     return ( new_array );
  749.     }
  750.  
  751.  
  752. #endif
  753. SHAR_EOF
  754. cat << \SHAR_EOF > ncnb.def
  755. % correct anything to anything else for 3
  756. %correct    .    .    3
  757.  
  758. % a number of common numeric misreads.  4 is often read as (+
  759. % but we cannot correct string to string.
  760. %correct    "Z"    "2"    1
  761. %correct    "z"    "2"    1
  762. %correct    "S"    "5"    1
  763. %correct    "s"    "5"    1
  764. %correct    "l"    "1"    1
  765. %correct    "i"    "1"    1
  766. %correct    "I"    "1"    1
  767. %correct    "o"    "0"    1
  768. %correct    "O"    "0"    1
  769. %correct    "r"    "5"    1
  770. %correct    "?"    "9"    1
  771. %correct    "+"    "4"    1
  772.  
  773. % default insertion cost is 2
  774. %insert        .    2
  775.  
  776. % charge extra for numbers to avoid hallucinations.
  777. %insert        [0-9]    3
  778.  
  779. % delete anything for 2.  correct cost <= insert + delete.
  780. %delete        .    2
  781. %delete        [0-9]    3
  782.  
  783. % the maximum tolerable error cost 
  784. %tolerance    20
  785. %%
  786. ([ ]{20,30}[+ ]([ ]{5,7}[0-9]{5}|"NO ITEM # ")[ ]{3,4}[0-9]{9}[ ]{5,7}[0-1][0-9]-[0-3][0-9][ ]{6,13}(""|[1-9][0-9]{0,2}|[1-9][0-9]{0,2}","[0-9]{3})\.[0-9]{2}([ ]{5,10}[+ ]([ ]{5,7}[0-9]{5}|"NO ITEM # ")[ ]{3,4}[0-9]{9}[ ]{5,7}[0-1][0-9]-[0-3][0-9][ ]{6,13}(""|[1-9][0-9]{0,2}|[1-9][0-9]{0,2}","[0-9]{3})\.[0-9]{2})?)|("       ENCLOSED           NUMBER        NUMBER".*)
  787. SHAR_EOF
  788. cat << \SHAR_EOF > nfa.c
  789. /* nfa - NFA construction routines */
  790.  
  791. /* Construct a state-labelled epsilon nfa for a regular expression.
  792.  * Then read input and output a word from the language defined
  793.  * by the nfa that is as close as possible to the input.
  794.  */
  795.  
  796. /*
  797.  * Copyright (c) 1987, the University of California
  798.  * 
  799.  * The United States Government has rights in this work pursuant to
  800.  * contract no. DE-AC03-76SF00098 between the United States Department of
  801.  * Energy and the University of California.
  802.  * 
  803.  * This program may be redistributed.  Enhancements and derivative works
  804.  * may be created provided the new works, if made available to the general
  805.  * public, are made available for use by anyone.
  806.  */
  807.  
  808. /*  Changes copyright (c) 1991,  Alan Wendt.  This work is hereby made
  809.  *  available to the general public, for use by anyone.  The changes
  810.  *  may be redistributed only if this notice is removed and the
  811.  *  "Lumberjack Song" substituted in its place, and you must also cut
  812.  *  down the largest tree in the forest with a herring.
  813.  */
  814.  
  815.  
  816. #include "flexdef.h"
  817.  
  818. #define FIRSTST(x)   states[x]->firstst
  819. #define LASTST(x)    states[x]->lastst
  820. #define FINALST(x)   states[x]->finalst
  821. #define EDGEPTR(x)   states[x]->edgeptr
  822. #define NOUTEDGES(x) states[x]->noutedges
  823. #define ACCPTNUM(x)  ((x) == finalst)
  824. #define NINEDGES(x)  states[x]->ninedges
  825. #define TRANSCHAR(x) states[x]->transchar
  826. #define TEMP(x)      states[x]->temp
  827.  
  828. #define EDGE_FROM(x)  (x)->from
  829. #define EDGE_TO(x)    (x)->to
  830.  
  831.  
  832. #define DELETE_COST(x) delete_cost[x]
  833. #define INSERT_COST(x) insert_cost[x]
  834. #define CORRECT_COST(x,y) correct_cost[x][y]
  835.  
  836. #define MAXCOST 31
  837.  
  838. int lastnfa, finalst;
  839. int tolerance = 15;        /* maximum tolerable error */
  840.  
  841. #define MAXMEM 32000L
  842. char        *banks[40];
  843. int        nbanks = 0;
  844. long        memx;            /* memory allocation counter    */
  845. int        globcost;        /* cost of repair    */
  846. struct BackEdge    *globword;        /* the repaired word    */
  847.  
  848. static char *getword();        /* reconstruct the repaired word */
  849. static void advance();
  850.  
  851. char    *ralloc(n)            /* allocate memory */
  852.     int        n;
  853.     {
  854.     long    result;
  855.  
  856.     retry:
  857.  
  858.     memx += sizeof(int) - 1;        /* align    */
  859.     memx &= ~(sizeof(int) - 1);
  860.     result = memx;
  861.     memx += n;
  862.     if (nbanks == 0 || memx > MAXMEM) {
  863.     nbanks++;
  864.     if (nbanks > 40)
  865.         {
  866.         fprintf(stderr, "no memory in ralloc\n");
  867.         exit(1);
  868.         }
  869.     memx = 0;
  870.     if (banks[nbanks - 1] == NULL)
  871.         {
  872.         banks[nbanks - 1] = sbrk((int)MAXMEM);
  873.         }
  874.     goto retry;
  875.     }
  876.     return banks[nbanks - 1]+result;
  877.     }
  878.  
  879.  
  880. /* add_accept - add an accepting state to a machine
  881.  *
  882.  * synopsis
  883.  *
  884.  *   add_accept( mach );
  885.  *
  886.  */
  887.  
  888. add_accept( mach )
  889. int mach;
  890.     {
  891.     finalst = FINALST(mach);
  892.     /*    fprintf(stderr, "final state = %d\n", finalst);    */
  893.     }
  894.  
  895. /* copysingl - make a given number of copies of a singleton machine
  896.  *
  897.  * synopsis
  898.  *
  899.  *   newsng = copysingl( singl, num );
  900.  *
  901.  *     newsng - a new singleton composed of num copies of singl
  902.  *     singl  - a singleton machine
  903.  *     num    - the number of copies of singl to be present in newsng
  904.  */
  905.  
  906. int copysingl( singl, num )
  907. int singl, num;
  908.  
  909.     {
  910.     int copy, i;
  911.  
  912.     copy = mkstate( SYM_EPSILON );
  913.  
  914.     for ( i = 1; i <= num; ++i )
  915.     copy = link_machines( copy, dupmachine( singl ) );
  916.  
  917.     return ( copy );
  918.     }
  919.  
  920.  
  921. /* dumpnfa - debugging routine to write out an nfa
  922.  *
  923.  * synopsis
  924.  *    int state1;
  925.  *    dumpnfa( state1 );
  926.  */
  927.  
  928. dumpnfa( state1 )
  929. int state1;
  930.  
  931.     {
  932.     int ns, j;
  933.     struct Edge *e;
  934.  
  935.     fprintf( stderr, "\n\n********** beginning dump of state-labelled epsilon nfa with start state %d\n",
  936.          state1 );
  937.  
  938.     /* we probably should loop starting at FIRSTST(state1) and going to
  939.      * LASTST(state1), but they're not maintained properly when we "or"
  940.      * all of the rules together.  So we use our knowledge that the machine
  941.      * starts at state 1 and ends at lastnfa.
  942.      */
  943.  
  944.     /* for ( ns = FIRSTST(state1); ns <= LASTST(state1); ++ns ) */
  945.     for ( ns = 1; ns <= lastnfa; ++ns )
  946.     {
  947.     fprintf( stderr, "state # %4d:\t  %4d", ns, TRANSCHAR(ns));
  948.     if (' ' <= TRANSCHAR(ns) && TRANSCHAR(ns) <= '~')
  949.         fprintf(stderr, "'%c'", TRANSCHAR(ns));
  950.     else
  951.         fprintf(stderr, "   ");
  952.  
  953.     fprintf(stderr, ", %d nedges %3d\n", ns == finalst, NOUTEDGES(ns) );
  954.  
  955.     for (e = EDGEPTR(ns), j = 0; j < NOUTEDGES(ns); e = e->next, j++)
  956.         fprintf( stderr, "from %4d to %4d\n", EDGE_FROM(e), EDGE_TO(e));
  957.     }
  958.  
  959.     fprintf( stderr, "********** end of dump\n" );
  960.     }
  961.  
  962.  
  963. /* dupmachine - make a duplicate of a given machine
  964.  *
  965.  * synopsis
  966.  *
  967.  *   copy = dupmachine( mach );
  968.  *
  969.  *     copy - holds duplicate of mach
  970.  *     mach - machine to be duplicated
  971.  *
  972.  * note that the copy of mach is NOT an exact duplicate; rather, all the
  973.  * transition states values are adjusted so that the copy is self-contained,
  974.  * as the original should have been.
  975.  *
  976.  * also note that the original MUST be contiguous, with its low and high
  977.  * states accessible by the arrays firstst and lastst
  978.  */
  979.  
  980. int dupmachine( mach )
  981. int mach;
  982.  
  983.     {
  984.     int i, j, state, init, last = LASTST(mach), state_offset;
  985.     struct Edge *e;
  986.  
  987.     for ( i = FIRSTST(mach); i <= last; ++i )
  988.     {
  989.     state = mkstate( TRANSCHAR(i) );
  990.     }
  991.  
  992.     state_offset = state - i + 1;
  993.     init = mach + state_offset;
  994.  
  995.     for ( i = FIRSTST(mach); i <= last; ++i )
  996.     for (j = 0, e = EDGEPTR(i); j < NOUTEDGES(i); j++, e = e->next)
  997.         mkxtion(e->from + state_offset, e->to + state_offset, __LINE__);
  998.  
  999.     FIRSTST(init) = FIRSTST(mach) + state_offset;
  1000.     FINALST(init) = FINALST(mach) + state_offset;
  1001.     LASTST(init) = LASTST(mach) + state_offset;
  1002.  
  1003.     return ( init );
  1004.     }
  1005.  
  1006.  
  1007. /* link_machines - connect two machines together
  1008.  *
  1009.  * synopsis
  1010.  *
  1011.  *   new = link_machines( first, last );
  1012.  *
  1013.  *     new    - a machine constructed by connecting first to last
  1014.  *     first  - the machine whose successor is to be last
  1015.  *     last   - the machine whose predecessor is to be first
  1016.  *
  1017.  * note: this routine concatenates the machine first with the machine
  1018.  *  last to produce a machine new which will pattern-match first first
  1019.  *  and then last, and will fail if either of the sub-patterns fails.
  1020.  *  FIRST is set to new by the operation.  last is unmolested.
  1021.  */
  1022.  
  1023. int link_machines( first, last )
  1024. int first, last;
  1025.  
  1026.     {
  1027. #if 0
  1028.     fprintf(stderr, "link_machines(%d,%d)\n", first, last);
  1029. #endif
  1030.     if ( first == NIL )
  1031.     {
  1032.     return ( last );
  1033.     }
  1034.  
  1035.     else if ( last == NIL )
  1036.     {
  1037.     return ( first );
  1038.     }
  1039.  
  1040.     else
  1041.     {
  1042.     mkxtion( FINALST(first), last, __LINE__ );
  1043.     FINALST(first) = FINALST(last);
  1044.     LASTST(first) = max( LASTST(first), LASTST(last) );
  1045.     FIRSTST(first) = min( FIRSTST(first), FIRSTST(last) );
  1046.  
  1047.     return ( first );
  1048.     }
  1049.     }
  1050.  
  1051.  
  1052. /* mkclos - convert a machine into a closure
  1053.  *
  1054.  * synopsis
  1055.  *   new = mkclos( state );
  1056.  *
  1057.  *     new - a new state which matches the closure of "state"
  1058.  */
  1059.  
  1060. int mkclos( state )
  1061. int state;
  1062.  
  1063.     {
  1064.     return ( mkopt( mkposcl( state ) ) );
  1065.     }
  1066.  
  1067.  
  1068. /* mkopt - make a machine optional
  1069.  *
  1070.  * synopsis
  1071.  *
  1072.  *   new = mkopt( mach );
  1073.  *
  1074.  *     new  - a machine which optionally matches whatever mach matched
  1075.  *     mach - the machine to make optional
  1076.  *
  1077.  * notes:
  1078.  *     1. mach must be the last machine created
  1079.  *     2. mach is destroyed by the call
  1080.  */
  1081.  
  1082. int mkopt( mach )
  1083. int mach;
  1084.  
  1085.     {
  1086.     return mkor( mach, mkstate( SYM_EPSILON ) );
  1087.     }
  1088.  
  1089.  
  1090. /* mkor - make a machine that matches either one of two machines
  1091.  *
  1092.  * synopsis
  1093.  *
  1094.  *   new = mkor( first, second );
  1095.  *
  1096.  *     new - a machine which matches either first's pattern or second's
  1097.  *     first, second - machines whose patterns are to be or'ed (the | operator)
  1098.  *
  1099.  * note that first and second are both destroyed by the operation
  1100.  * the code is rather convoluted because an attempt is made to minimize
  1101.  * the number of epsilon states needed
  1102.  */
  1103.  
  1104. int mkor( first, second )
  1105. int first, second;
  1106.  
  1107.     {
  1108.     int eps, result, newedges = 0;
  1109.  
  1110. #if 0
  1111.     fprintf(stderr, "mkor(%d,%d)", first, second);
  1112. #endif
  1113.     if ( first == NIL )
  1114.     return ( second );
  1115.  
  1116.     else if ( second == NIL )
  1117.     return ( first );
  1118.  
  1119.     eps = mkstate( SYM_EPSILON );
  1120.  
  1121.     mkxtion( FINALST(first), eps, __LINE__ );
  1122.     mkxtion( FINALST(second), eps, __LINE__ );
  1123.     FINALST(second) = FINALST(first) = eps;
  1124.     LASTST(first) = LASTST(second) = eps;
  1125.     newedges += 2;
  1126.     eps = mkstate( SYM_EPSILON );
  1127.     mkxtion( eps, first, __LINE__ );
  1128.     mkxtion( eps, second, __LINE__ );
  1129.     LASTST(first) = LASTST(second) = eps;
  1130.     newedges += 2;
  1131.     result = eps;
  1132.  
  1133.     FINALST(result) = FINALST(first);
  1134.     if ( FIRSTST(first) < FIRSTST(result) )
  1135.     FIRSTST(result) = FIRSTST(first);
  1136.     if ( FIRSTST(second) < FIRSTST(result) )
  1137.     FIRSTST(result) = FIRSTST(second);
  1138.     if ( LASTST(first) > LASTST(result) )
  1139.     LASTST(result) = LASTST(first);
  1140.     if ( LASTST(second) > LASTST(result) )
  1141.     LASTST(result) = LASTST(second);
  1142.  
  1143. #if 0
  1144.     fprintf(stderr, "mkor returns %d\n", result);
  1145. #endif
  1146.     return result;
  1147.     }
  1148.  
  1149.  
  1150. /* mkposcl - convert a machine into a positive closure
  1151.  *
  1152.  * synopsis
  1153.  *   new = mkposcl( state );
  1154.  *
  1155.  *    new - a machine matching the positive closure of "state"
  1156.  */
  1157.  
  1158. int mkposcl( state )
  1159. int state;
  1160.  
  1161.     {
  1162.     int        eps;
  1163.     if (TRANSCHAR(state) == SYM_EPSILON)
  1164.     {
  1165.     mkxtion( FINALST(state), state, __LINE__ );
  1166.     return ( state );
  1167.     }
  1168.  
  1169.     eps = mkstate( SYM_EPSILON );
  1170.     mkxtion( FINALST(state), eps, __LINE__ );
  1171.     mkxtion( eps, state, __LINE__ );
  1172.     FIRSTST(eps) = FIRSTST(state);
  1173.     LASTST(eps) = eps;
  1174.     FINALST(eps) = FINALST(state);
  1175.     return eps;
  1176.     }
  1177.  
  1178.  
  1179. /* mkrep - make a replicated machine
  1180.  *
  1181.  * synopsis
  1182.  *   new = mkrep( mach, lb, ub );
  1183.  *
  1184.  *    new - a machine that matches whatever "mach" matched from "lb"
  1185.  *          number of times to "ub" number of times
  1186.  *
  1187.  * note
  1188.  *   if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach"
  1189.  */
  1190.  
  1191. int mkrep( mach, lb, ub )
  1192. int mach, lb, ub;
  1193.  
  1194.     {
  1195.     int base, tail, copy, i;
  1196.  
  1197.     base = copysingl( mach, lb - 1 );
  1198.  
  1199.     if ( ub == INFINITY )
  1200.     {
  1201.     copy = dupmachine( mach );
  1202.     mach = link_machines( mach, link_machines( base, mkclos( copy ) ) );
  1203.     }
  1204.  
  1205.     else
  1206.     {
  1207.     tail = mkstate( SYM_EPSILON );
  1208.  
  1209.     for ( i = lb; i < ub; ++i )
  1210.         {
  1211.         copy = dupmachine( mach );
  1212.         tail = mkopt( link_machines( copy, tail ) );
  1213.         }
  1214.  
  1215.     mach = link_machines( mach, link_machines( base, tail ) );
  1216.     }
  1217.  
  1218.     return ( mach );
  1219.     }
  1220.  
  1221.  
  1222. /* mkstate - create a state with a transition on a given symbol
  1223.  *
  1224.  * synopsis
  1225.  *
  1226.  *   state = mkstate( sym );
  1227.  *
  1228.  *     state - a new state matching sym
  1229.  *     sym   - the symbol the new state is to have its in-transitions on
  1230.  *             (state-labelled epsilon-nfa)
  1231.  *
  1232.  * note that this routine makes new states in ascending order through the
  1233.  * state array (and increments LASTNFA accordingly).  The routine DUPMACHINE
  1234.  * relies on machines being made in ascending order and that they are
  1235.  * CONTIGUOUS.  Change it and you will have to rewrite DUPMACHINE (kludge
  1236.  * that it admittedly is)
  1237.  */
  1238.  
  1239. int mkstate( sym )
  1240. int sym;
  1241.  
  1242.     {
  1243.     if (++lastnfa >= MAXIMUM_MNS)
  1244.     {
  1245.     lerrif( "input rules are too complicated (>= %d NFA states)",
  1246.         MAXIMUM_MNS );
  1247.     }
  1248.  
  1249.     states[lastnfa] = (struct state *)malloc(sizeof(struct state));
  1250.  
  1251.     if (!states[lastnfa])
  1252.         {
  1253.         lerrif("out of memory at line %d\n", __LINE__);
  1254.         }
  1255.  
  1256.     TRANSCHAR(lastnfa) = sym;
  1257.     FIRSTST(lastnfa) = lastnfa;
  1258.     FINALST(lastnfa) = lastnfa;
  1259.     LASTST(lastnfa) = lastnfa;
  1260.     EDGEPTR(lastnfa) = NULL;
  1261.     NOUTEDGES(lastnfa) = 0;
  1262.     NINEDGES(lastnfa) = 0;
  1263.  
  1264.     return ( lastnfa );
  1265.     }
  1266.  
  1267. #define INSERT_LIST(head, new, next, prior)  { \
  1268.     if (head == NULL) { \
  1269.     head = new->next = new->prior = new; \
  1270.     } \
  1271.     else { \
  1272.     new->next = head; \
  1273.     new->prior = head->prior; \
  1274.     new->prior->next = new; \
  1275.     new->next->prior = new; \
  1276.     head = new; \
  1277.     } \
  1278.     }
  1279.  
  1280. #define UNLINK(x, type) { \
  1281.     type *next, *prior;  \
  1282.     next = x->next; \
  1283.     prior = x->prior; \
  1284.     prior->next = next; \
  1285.     next->prior = prior; \
  1286.     }
  1287.  
  1288. /* delxtion - delete a transition
  1289.  *
  1290.  * synopsis
  1291.  *
  1292.  *   delxtion( edgeptr )
  1293.  *
  1294.  *       edgeptr - a pointer to the struct Edge that is to be deleted
  1295.  */
  1296. delxtion( edgeptr )
  1297.     struct Edge *edgeptr;
  1298.     {
  1299.     NOUTEDGES(EDGE_FROM(edgeptr))--;
  1300.     NINEDGES(EDGE_TO(edgeptr))--;
  1301.     UNLINK(edgeptr, struct Edge);
  1302.     if (EDGEPTR(EDGE_FROM(edgeptr)) == edgeptr)
  1303.     EDGEPTR(EDGE_FROM(edgeptr)) = edgeptr->next;
  1304.     if (NOUTEDGES(EDGE_FROM(edgeptr)) == 0)
  1305.     EDGEPTR(EDGE_FROM(edgeptr)) = NULL;
  1306.     free(edgeptr);
  1307.     }
  1308.  
  1309. /* mkxtion - make a transition from one state to another
  1310.  *
  1311.  * synopsis
  1312.  *
  1313.  *   mkxtion( statefrom, stateto );
  1314.  *
  1315.  *     statefrom - the state from which the transition is to be made
  1316.  *     stateto   - the state to which the transition is to be made
  1317.  */
  1318.  
  1319. /* SUPPRESS 590 */
  1320. mkxtion( statefrom, stateto, fromline )
  1321. int statefrom, stateto;
  1322.     {
  1323.     struct Edge    *newedge;
  1324.  
  1325.     /*
  1326.     fprintf(stderr, "mkxtion(%d,%d,%d)\n", statefrom, stateto, fromline);
  1327.     */
  1328.  
  1329.     newedge = (struct Edge *)malloc(sizeof(struct Edge));
  1330.     if (!newedge)
  1331.     {
  1332.     fprintf(stderr, "no memory in mkxtion\n");
  1333.     exit(1);
  1334.     }
  1335.  
  1336.     NOUTEDGES(statefrom)++;
  1337.     NINEDGES(stateto)++;
  1338.     newedge->from = statefrom;
  1339.     newedge->to = stateto;
  1340.     INSERT_LIST(EDGEPTR(statefrom), newedge, next, prior)
  1341.     }
  1342.  
  1343. static int    bflen;        /* length of the buffer */
  1344. static char    bf[512];    /* the buffer */
  1345. extern FILE    *yyin;
  1346.  
  1347. /* v[j][q] records the cost of the cheapest way to get to state q
  1348.  * having consumed j characters.
  1349.  */
  1350. static int maxj = 0;        /* # of allocated vectors in v */
  1351. static unsigned char *v[MAXLINE + 1];
  1352.  
  1353. /* Back-edge is used to record the history of edits made by the system
  1354.  * as it finds the cost of edits to get the cheapest match.  It is used
  1355.  * to reconstruct a word that is a closest match.
  1356.  */
  1357. struct BackEdge {
  1358.     struct BackEdge *prior;
  1359.     char    c;
  1360.     };
  1361.  
  1362. struct Work
  1363.     {
  1364.     struct Work *next;
  1365.     int        q;            /* a state number */
  1366.     int        j;            /* a number of characters consumed */
  1367.     struct BackEdge *backedge;
  1368.     } *worklist[MAXCOST+1], *workend[MAXCOST+1];
  1369.  
  1370. #define Q_PUT(type, head, tail, state, chars, word)  { \
  1371.     type  *newptr; \
  1372.     newptr = (type *)ralloc(sizeof(type)); \
  1373.     newptr->q = state; \
  1374.     newptr->j = chars; \
  1375.     newptr->backedge = word; \
  1376.     if (head == NULL)  head = newptr;  \
  1377.     else  tail->next = newptr;  \
  1378.     newptr->next = NULL; \
  1379.     tail = newptr; \
  1380.     }
  1381.  
  1382. #define Q_EMPTY(head) (head == NULL)
  1383.  
  1384. /*  Get the next element off the queue.  Make sure the queue is not
  1385.  *  empty before you do this.
  1386.  */
  1387. #define Q_GET(type, head, new) { \
  1388.     type *next; \
  1389.     new = *(head); \
  1390.     next = (head)->next; \
  1391.     (head) = next; \
  1392.     }
  1393.  
  1394.  /*  This constructs a state-labelled epsilon-nfa from a regular expression.
  1395.   *  Then it constructs a two-dimensional array v[j][n].  j corresponds
  1396.   *  to the number of characters that have been read from the string, so
  1397.   *  0 <= j <= strlen(input).  n corresponds to the states of the nfa.
  1398.   *  Entries in v represent the cheapest cost of driving the nfa to state
  1399.   *  n, having read j characters from the input.  Initially the nfa is
  1400.   *  in state 0, having read 0 characters from the input, so v[0][0] = 0.
  1401.   *  The algorithm uses a dynamic programming algorithm based upon Dikstra's
  1402.   *  shortest-path (with discrete bucketing) to find the cheapest path to
  1403.   *  v[strlen(input)][nf] where nf is the nfa final state.  If the cost
  1404.   *  exceeds the tolerance, the search is abandoned.
  1405.   */
  1406. main(argc, argv)
  1407.     int        argc;
  1408.     char    **argv;
  1409.     {
  1410.     int        i, j;
  1411.  
  1412.     if (argc == 2)
  1413.     {
  1414.     yyin = fopen(argv[1], "r");
  1415.     if (!yyin) {
  1416.         fprintf(stderr, "cannot open %s\n", argv[1]);
  1417.         exit(1);
  1418.         }
  1419.     }
  1420.  
  1421.     for (i = 0; i < 128; i++)
  1422.     {
  1423.     delete_cost[i] = insert_cost[i] = 1;
  1424.     for (j = 0; j < 128; j++)
  1425.         correct_cost[i][j] = 1;
  1426.     }
  1427.  
  1428.     yyparse();
  1429.  
  1430.  
  1431.     firstnfa = link_machines( mkstate( SYM_EPSILON ), firstnfa );
  1432.  
  1433.     optimize_nfa();
  1434.  
  1435.     checkedges(__LINE__, __FILE__);
  1436.  
  1437.     /*
  1438.     fprintf(stderr, "firstnfa %d last %d\n", firstnfa, lastnfa);
  1439.     dumpnfa( firstnfa );
  1440.     fprintf(stderr, "\n\n");
  1441.     */
  1442.  
  1443.     while (gets( bf ))
  1444.     {
  1445.     /*    fprintf(stderr, "bf   = %s\n", bf);    */
  1446.     bflen = strlen( bf );
  1447.     while (maxj <= bflen)
  1448.         {
  1449.         v[maxj] = (unsigned char *)
  1450.         allocate_array( lastnfa + 1, sizeof(*v[0]) );
  1451.         maxj++;
  1452.         }
  1453.  
  1454.     for (j = 0; j <= bflen; j++)
  1455.         memset((char *)(v[j]), '\377', (unsigned)(lastnfa + 1));
  1456.  
  1457.     nbanks = memx = 0;
  1458.     for (i = 0; i <= MAXCOST; i++)
  1459.         {
  1460.         worklist[i] = NULL;
  1461.         workend[i] = NULL;
  1462.         }
  1463.     getcosts(tolerance);
  1464.     if (globword)
  1465.         {
  1466.         /*
  1467.         fprintf(stderr, "cost = %d\nword = '%s'\n",
  1468.         globcost, getword(globword));
  1469.         */
  1470.         puts(getword(globword));
  1471.         }
  1472.     }
  1473.     /* fprintf(stderr, "done!\n");    */
  1474.     }
  1475.  
  1476. getcosts(maxcost)
  1477.     {
  1478.     int        cost = 0, modcost;
  1479.     struct Work new;
  1480.  
  1481.     /*  We can get to the first nfa state, scanning zero characters,
  1482.      *    for a cost of 0.  Start off by sticking this fact into the queue.
  1483.      */
  1484.     globword = NULL;
  1485.     record(firstnfa, 0, 0, (struct BackEdge *)0);
  1486.  
  1487.     /*  allow increasing costs and see how far we can get */
  1488.     for (cost = 0; cost <= maxcost; cost++)
  1489.     {
  1490.     modcost = cost % (MAXCOST + 1);
  1491.  
  1492.     /*  process until we exhaust the work queue */
  1493.     while (!Q_EMPTY(worklist[modcost]))
  1494.         {
  1495.         Q_GET(struct Work, worklist[modcost], new);
  1496.  
  1497.         /*
  1498.         fprintf(stderr, "Pull chars=%d state=%d cost=%d from queue\n",
  1499.         new.j, new.q, cost);
  1500.         */
  1501.         if ( v[new.j][new.q] < cost )
  1502.         {
  1503.         /*
  1504.         fprintf(stderr, "discard chars=%d state=%d cost=%d\n",
  1505.             new.j, new.q, cost);
  1506.         */
  1507.         continue;
  1508.         }
  1509.  
  1510.         advance(new.q, new.j, cost, new.backedge);
  1511.         }
  1512.  
  1513.     if (globword)
  1514.         {
  1515.         return;
  1516.         }
  1517.     }
  1518.     }
  1519.  
  1520. static char word[MAXLINE];
  1521.  
  1522. static char *getword(edge)
  1523.     struct BackEdge *edge;
  1524.     {
  1525.     int        first = 0, last = 0;
  1526.     int        t;
  1527.  
  1528.     /*  trace back and collect the corrected word into a buffer */
  1529.     for (; edge; edge = edge->prior)
  1530.     {
  1531.     word[last++] = edge->c;
  1532.     }
  1533.  
  1534.     word[last--] = 0;
  1535.  
  1536.     /*  reverse the buffer */
  1537.     for (; last > first; last--, first++)
  1538.     {
  1539.     t = word[last]; word[last] = word[first]; word[first] = t;
  1540.     }
  1541.  
  1542.     return word;
  1543.     }
  1544.  
  1545. /*  A call to record says that we can get to a given state for a
  1546.  *  given cost k.  If this is further than we have gotten yet for
  1547.  *  that much cost we put this info on the end of the worklist[k]
  1548.  *  and also into v[cost][state].
  1549.  */
  1550. record(state, chars, cost, word)
  1551.     int        state;        /* state we can get to for given cost */
  1552.     int        chars;        /* having consumed this many characters */
  1553.     int        cost;        /* cost */
  1554.     struct BackEdge *word;    /* last node in a word that works */
  1555.     {
  1556.     int        modcost;
  1557.  
  1558.     /*
  1559.     fprintf(stderr, "record state=%d chars=%d cost=%d word='%s'\n",
  1560.     state, chars, cost, getword(word));
  1561.     */
  1562.  
  1563.     if (state == finalst && chars == bflen && (!globword || cost < globcost))
  1564.     {
  1565.     globcost = cost;
  1566.     globword = word;
  1567.     }
  1568.  
  1569.     /*  Is this a newly-discovered cheaper way to get here? */
  1570.     if (cost < v[chars][state])
  1571.     {
  1572.     v[chars][state] = cost;
  1573.     modcost = cost % (MAXCOST + 1);
  1574.     Q_PUT(struct Work, worklist[modcost], workend[modcost],
  1575.         state, chars, word);
  1576.     /*
  1577.     fprintf(stderr, "new v[%d][%d]=%d\n\n", chars, state, cost);
  1578.     */
  1579.     }
  1580.     }
  1581.  
  1582. #define TRACE_ADVANCE 0
  1583.  
  1584. /*  A call to advance(state, chars, cost, word) asserts that cost is the
  1585.  *  cheapest way we know to get to the given state after consuming chars
  1586.  *  of the input, and demands that the closure of this assertion be
  1587.  *  taken.
  1588.  *
  1589.  *  Advance goes one more step and enters the new values in v.  Advance will
  1590.  *  eventually get called for everything that it puts in v, so recursive
  1591.  *  calls are not necessary.
  1592.  */
  1593. static void advance(state, chars, cost, word)
  1594.     int        state;        /* we can get to state p */
  1595.     int        chars;        /* after consuming so many characters */
  1596.     int        cost;        /* for a given cost */
  1597.     struct BackEdge *word;    /* last char in a word that works */
  1598.     {
  1599.     register    q;        /* another state */
  1600.     struct Edge *e;
  1601.     struct BackEdge *new;
  1602.  
  1603. #if TRACE_ADVANCE
  1604.     fprintf(stderr,
  1605.     "got to state %d at cost %d using %d input chars\n",
  1606.     state, cost, chars);
  1607. #endif
  1608.  
  1609.     /*  we can always consume one character and stay in the same state,
  1610.      *  by incurring a "deletion charge".
  1611.      */
  1612.     if (chars < bflen)
  1613.     {
  1614. #if TRACE_ADVANCE
  1615.     fprintf(stderr,
  1616.         "get to state %d at cost %d using %d chars by deleting 1 char\n",
  1617.         state, cost + DELETE_COST(bf[chars]), chars + 1);
  1618. #endif
  1619.     record(state, chars + 1, cost + DELETE_COST(bf[chars]), word);
  1620.     }
  1621.  
  1622.     /*  for each edge out of state p */
  1623.     for (e = EDGEPTR(state); e;)
  1624.     {
  1625.     q = EDGE_TO(e);
  1626.  
  1627.     /*  If we have an epsilon edge to a new state, we can get
  1628.      *  there for no additional charge and without consuming
  1629.      *  any characters.
  1630.      */
  1631.     if (TRANSCHAR(q) == SYM_EPSILON)
  1632.         {
  1633. #if TRACE_ADVANCE
  1634.         fprintf(stderr,
  1635.         "get to state %d at cost %d using %d chars with e-edge\n",
  1636.         q, cost, chars);
  1637. #endif
  1638.         record(q, chars, cost, word);
  1639.         }
  1640.  
  1641.     else {
  1642.         /*  We can incur an "insertion charge" and get to the
  1643.          *  next state without using up any input characters.
  1644.          */
  1645.         new = (struct BackEdge *)ralloc(sizeof(struct BackEdge));
  1646.         new->c = TRANSCHAR(q);
  1647.         new->prior = word;
  1648.  
  1649. #if TRACE_ADVANCE
  1650.         fprintf(stderr,
  1651.         "get to state %d at cost %d using %d chars by insert %c\n",
  1652.         q, cost + INSERT_COST(new->c), chars, new->c);
  1653. #endif
  1654.  
  1655.         record( q, chars, cost + INSERT_COST(new->c), new );
  1656.  
  1657.         /*  If we have a transition to a new state that is labelled
  1658.          *  correctly, we can get there for no additional charge.
  1659.          */
  1660.         if (chars < bflen)
  1661.         {
  1662.         if (new->c == bf[chars])
  1663.             {
  1664. #if TRACE_ADVANCE
  1665.             fprintf(stderr, 
  1666.             "get to state %d cost %d using %d chars following %c edge\n",
  1667.                 q, cost, chars + 1, new->c);
  1668. #endif
  1669.             record(q, chars + 1, cost, new);
  1670.             }
  1671.  
  1672.         else {
  1673.             /*  If we have a transition to a new state that is not
  1674.              *  labelled correctly, we can get there by incurring a
  1675.              *  correction cost.
  1676.              */
  1677. #if TRACE_ADVANCE
  1678.             fprintf(stderr, 
  1679.             "get to state %d cost %d using %d chars changing %c to %c\n",
  1680.                 q, cost + CORRECT_COST(bf[chars], new->c),
  1681.                 chars + 1, bf[chars], new->c);
  1682. #endif
  1683.             record( q, chars + 1,
  1684.                cost + CORRECT_COST(bf[chars], new->c), new );
  1685.             }
  1686.         }
  1687.         }
  1688.  
  1689.  
  1690.     e = e->next;
  1691.     if (e == EDGEPTR(state))
  1692.         break;
  1693.     }
  1694.     }
  1695.  
  1696. /*  nfa branch chaining.  Find a state A with an out-edge that points
  1697.  *  to an epsilon state B.  Remove the edge and duplicate the out-edges
  1698.  *  of B into A.  When you remove all of the in-edges of some state,
  1699.  *  you can remove the state unless it is the start state.
  1700.  *
  1701.  *  Straightfoward application of this principal makes the nfa 
  1702.  *  slower and larger.  What happens is on something like
  1703.  *  [0-9][0-9] the original machine had an e-state in between 10
  1704.  *  left-hand states and 10 right-hand states, and this replaced
  1705.  *  20 edges with 100 in order to eliminate the e-state.  This caused
  1706.  *  5 times more calls to record.  Now we do not perform this opt
  1707.  *  unless the product of B's inedges and B's outedges is <= their
  1708.  *  sum.  Optimize_nfa still usually eliminates half of the input
  1709.  *  states.
  1710.  *
  1711.  *  A worklist algorithm would probably improve the speed.
  1712.  */
  1713. optimize_nfa()
  1714.     {
  1715.     int        A, B, C, k, kk, changes;
  1716.     struct Edge *e, *nexte, *ee, *nextee;
  1717.  
  1718.  
  1719.     for (changes = 1; changes;)
  1720.     {
  1721.     changes = 0;
  1722.  
  1723.  
  1724.     changes = 0;
  1725.     for (A = 1; A <= lastnfa; A++)
  1726.         {
  1727.  
  1728.  
  1729.         /*  If an edge from this state goes to an epsilon state */
  1730.         for (e = EDGEPTR(A); EDGEPTR(A); e = nexte) {
  1731.  
  1732.         nexte = e->next;
  1733.         B = EDGE_TO(e);
  1734.         if (TRANSCHAR(B) == SYM_EPSILON && B != finalst &&
  1735.             NINEDGES(B) * NOUTEDGES(B) <= NINEDGES(B) + NOUTEDGES(B)) {
  1736.  
  1737.             /*  delete A->B edge */
  1738.             delxtion(e);
  1739.  
  1740.             /*  copy B's out-edges to A */
  1741.             for (kk = 0, ee = EDGEPTR(B); kk < NOUTEDGES(B);
  1742.                             ee = ee->next, kk++)
  1743.             {
  1744.             mkxtion(A, EDGE_TO(ee), __LINE__);
  1745.             /*  Fix the case in which there was only one out edge
  1746.              *  which is being replaced by a different one.
  1747.              *  If we don't do this, e will point to the deleted 
  1748.              *  edge on the next loop iteration.
  1749.              */
  1750.             if (e == nexte)
  1751.                 nexte = EDGEPTR(A);
  1752.             }
  1753.  
  1754.             /*  delete B if it has no incoming edges */
  1755.             if (NINEDGES(B) == 0)
  1756.             {
  1757.             delete_state(B);
  1758.             A--;
  1759.             changes = 1;
  1760.             goto nextA;    /* avoid second loop in case A=0 */
  1761.             }
  1762.             changes = 1;
  1763.             }
  1764.         if (nexte == EDGEPTR(A)) break;
  1765.         }
  1766.  
  1767.         for (k = 0, e = EDGEPTR(A); k < NOUTEDGES(A); k++, e = nexte) {
  1768.  
  1769.         nexte = e->next;
  1770.         B = EDGE_TO(e);
  1771.  
  1772.         if (TRANSCHAR(B) == SYM_EPSILON
  1773.             && NOUTEDGES(B) == 1
  1774.             && TRANSCHAR(C = EDGE_TO(EDGEPTR(B))) == SYM_EPSILON
  1775.             && ACCPTNUM(B) <= ACCPTNUM(C)) {
  1776.             /*
  1777.             fprintf(stderr, "%d -> eps %d -> eps %d\n", A, B, C);
  1778.             */
  1779.  
  1780.             delxtion(e);
  1781.             mkxtion(A, C, __LINE__);
  1782.             if (NINEDGES(B) == 0) {
  1783.             delete_state(B);
  1784.             A--;
  1785.             }
  1786.             changes = 1;
  1787.             }
  1788.         }
  1789.         nextA:;
  1790.         }
  1791.     }
  1792.  
  1793.     }
  1794.  
  1795. /*  delete an nfa state which has lost all of its in-edges */
  1796. delete_state(d)
  1797.     int        d;
  1798.     {
  1799.     int        dd;    
  1800.     struct Edge *e, *nexte;
  1801.  
  1802.     retry:
  1803. #if 0
  1804.     fprintf(stderr, "delete_state(%d)\n", d);
  1805. #endif
  1806.  
  1807.     if (firstnfa == lastnfa)
  1808.     firstnfa = d;
  1809.     if (finalst == lastnfa)
  1810.     finalst = d;
  1811.  
  1812.     /*  Delete all of the edges emanating from the losing state.
  1813.      *  Uncount the in-edge count of each state pointed to.
  1814.      */
  1815.     /* SUPPRESS 560 */
  1816.     while (e = EDGEPTR(d))
  1817.     delxtion(e);
  1818.  
  1819.     states[d] = states[lastnfa--];        /* overwrite the losing state */
  1820.  
  1821.     /*  fix up the edges out of the state that moved */
  1822.     for (e = EDGEPTR(d); e; e = nexte)
  1823.     {
  1824.     nexte = e->next;
  1825.     if (EDGE_TO(e) == lastnfa + 1)
  1826.         {
  1827.         fprintf(stderr, "can't happen at line %d\n", __LINE__, __FILE__);
  1828.         exit(1);
  1829.         }
  1830.     EDGE_FROM(e) = d;
  1831.     if (nexte == EDGEPTR(d))
  1832.         break;
  1833.     }
  1834.  
  1835.     /*  fix up the edges into the state that moved */
  1836.     for (dd = 1; dd <= lastnfa; dd++) 
  1837.     {
  1838.     for (e = EDGEPTR(dd); e; e = nexte)
  1839.         {
  1840.         nexte = e->next;
  1841.         if (EDGE_TO(e) == lastnfa + 1)
  1842.         {
  1843.         EDGE_TO(e) = d;
  1844.         }
  1845.         if (nexte == EDGEPTR(dd))
  1846.         break;
  1847.         }
  1848.     }
  1849.  
  1850.  
  1851.     /*  delete any states (except the start state) which have
  1852.      *  lost all of their incoming edges.
  1853.      */
  1854.     for (d = 1; d <= lastnfa ; d++)
  1855.     if (NINEDGES(d) == 0 && d != firstnfa)
  1856.         goto retry;
  1857.  
  1858.     }
  1859.  
  1860. /*  Check the nfa to make sure the in-edge and out-edge counts are
  1861.  *  correct.  If you suspect nfa structure problems, call this from
  1862.  *  all over the place.
  1863.  */
  1864.  
  1865. /* SUPPRESS 590 */
  1866. checkedges(fromline, fromfile)
  1867.     int        fromline;
  1868.     char    *fromfile;
  1869.     {
  1870.  
  1871.     int        i;
  1872.     int        k;
  1873.     struct Edge *e, *nexte;
  1874.     for (i = 1; i <= lastnfa; i++)
  1875.     TEMP(i) = 0;
  1876.  
  1877.     /*  count the edges into and from each state */
  1878.     for (i = 1; i <= lastnfa; i++) 
  1879.     {
  1880.     k = 0;
  1881.     for (e = EDGEPTR(i); e; e = nexte)
  1882.         {
  1883.         k++;
  1884.         nexte = e->next;
  1885.         TEMP(EDGE_TO(e))++;
  1886.         if (EDGE_FROM(e) != i)
  1887.         {
  1888.         fprintf(stderr, "EDGE_FROM(%d) is %d should be %d\n",
  1889.             e, EDGE_FROM(e), i);    
  1890.         }
  1891.         if (nexte == EDGEPTR(i))
  1892.         break;
  1893.         }
  1894.     if (NOUTEDGES(i) != k)
  1895.         {
  1896.         fprintf(stderr, "noutedges[%d] is %d should be %d line %d %s\n",
  1897.         i, NOUTEDGES(i), k, fromline, fromfile);
  1898.         }
  1899.     }
  1900.  
  1901.     for (i = 1; i <= lastnfa; i++)
  1902.     if (TEMP(i) != NINEDGES(i))
  1903.         {
  1904.         fprintf(stderr, "ninedges[%d] is %d should be %d line %d %s\n",
  1905.         i, NINEDGES(i), TEMP(i), fromline, fromfile);
  1906.         }
  1907.     }
  1908.  
  1909.  
  1910. SHAR_EOF
  1911. cat << \SHAR_EOF > parse.h
  1912. # define CHAR 257
  1913. # define NUMBER 258
  1914. # define SECTEND 259
  1915. # define SCDECL 260
  1916. # define XSCDECL 261
  1917. # define WHITESPACE 262
  1918. # define NAME 263
  1919. # define CORRECT 264
  1920. # define STRING 265
  1921. # define DELETE 266
  1922. # define INSERT 267
  1923. # define TOLERANCE 268
  1924. SHAR_EOF
  1925. cat << \SHAR_EOF > parse.y
  1926. /* parse.y - parser for flex input */
  1927.  
  1928. /*
  1929.  * Copyright (c) 1987, the University of California
  1930.  * 
  1931.  * The United States Government has rights in this work pursuant to
  1932.  * contract no. DE-AC03-76SF00098 between the United States Department of
  1933.  * Energy and the University of California.
  1934.  * 
  1935.  * This program may be redistributed.  Enhancements and derivative works
  1936.  * may be created provided the new works, if made available to the general
  1937.  * public, are made available for use by anyone.
  1938.  */
  1939.  
  1940. %token CHAR NUMBER SECTEND SCDECL XSCDECL WHITESPACE NAME CORRECT
  1941. %token STRING DELETE INSERT TOLERANCE
  1942.  
  1943. %{
  1944. #include "flexdef.h"
  1945.  
  1946. struct Ccl ccl, anyccl, ccl0;
  1947.  
  1948. int pat, eps, lastchar, i, firstnfa, finalst;
  1949. char clower();
  1950.  
  1951. int linenum, syntaxerror;
  1952.  
  1953.  
  1954. static void makeany()
  1955.     {
  1956.     static int madeany = false;
  1957.     if ( ! madeany )
  1958.     {
  1959.     /* create the '.' character class */
  1960.     checkedges(__LINE__, __FILE__);
  1961.     cclinit( &anyccl );
  1962.     ccladd( &anyccl, '\n' );
  1963.     checkedges(__LINE__, __FILE__);
  1964.     cclnegate( &anyccl );
  1965.     checkedges(__LINE__, __FILE__);
  1966.  
  1967.     madeany = true;
  1968.     }
  1969.     }
  1970.  
  1971.  
  1972. %}
  1973.  
  1974. %%
  1975. goal            :  initlex correctionrules sect2
  1976.         ;
  1977.  
  1978. initlex         :
  1979.             {
  1980.             /* initialize for processing rules */
  1981.             }
  1982.         ;
  1983.  
  1984. correctionrules    :    correctionrules onerule
  1985.         |
  1986.         ;
  1987.  
  1988. onerule        :    CORRECT item
  1989.             {
  1990.             ccl0 = ccl;
  1991.             }
  1992.             item NUMBER '\n'
  1993.             {
  1994.             int    i, j;
  1995.             for (i = 0; i < 128; i++)
  1996.                 {
  1997.                 for (j = 0; j < 128; j++)
  1998.                 {
  1999.                 if (ccltest( &ccl0, i) && ccltest( &ccl, j))
  2000.                     {
  2001.                     correct_cost[i][j] = $5;
  2002.                     }
  2003.                 }
  2004.                 }
  2005.             }
  2006.  
  2007.         |       DELETE item NUMBER '\n'
  2008.             {
  2009.             int    i, j;
  2010.             for (i = 0; i < 128; i++)
  2011.                 {
  2012.                 if (ccltest( &ccl, i))
  2013.                 {
  2014.                 delete_cost[i] = $3;
  2015.                 }
  2016.                 }
  2017.             }
  2018.  
  2019.         |    '\n'
  2020.             {
  2021.             }
  2022.  
  2023.         |    INSERT item NUMBER '\n'
  2024.             {
  2025.             int    i;
  2026.             for (i = 0; i < 128; i++)
  2027.                 {
  2028.                 if (ccltest( &ccl, i))
  2029.                 {
  2030.                 insert_cost[i] = $3;
  2031.                 }
  2032.                 }
  2033.             }
  2034.  
  2035.         |    TOLERANCE NUMBER '\n'
  2036.             {
  2037.             tolerance = $2;
  2038.             }
  2039.         ;
  2040.  
  2041. item        :    '.'
  2042.             {
  2043.             makeany();
  2044.             ccl = anyccl;
  2045.             }
  2046.  
  2047.         |    fullccl
  2048.             {
  2049.             }
  2050.  
  2051.         |    CHAR
  2052.             {
  2053.             cclinit( &ccl );
  2054.             ccladd( &ccl, $1 );
  2055.             }
  2056.  
  2057.         |    '"' CHAR '"'
  2058.             {
  2059.             cclinit( &ccl );
  2060.             ccladd( &ccl, $2 );
  2061.             }
  2062.  
  2063. sect2           :  sect2 initforrule flexrule '\n'
  2064.         |
  2065.         ;
  2066.  
  2067. initforrule     :
  2068.             {
  2069.             /* initialize for a parse of one rule */
  2070.             }
  2071.         ;
  2072.  
  2073. flexrule        : '^' re eol 
  2074.             {
  2075.             checkedges(__LINE__, __FILE__);
  2076.             pat = link_machines( $2, $3 );
  2077.             checkedges(__LINE__, __FILE__);
  2078.             add_accept( pat );
  2079.  
  2080.             checkedges(__LINE__, __FILE__);
  2081.             firstnfa = pat;
  2082.             }
  2083.  
  2084.                 |  re  eol 
  2085.             {
  2086.             checkedges(__LINE__, __FILE__);
  2087.             pat = link_machines( $1, $2 );
  2088.             checkedges(__LINE__, __FILE__);
  2089.             add_accept( pat );
  2090.             checkedges(__LINE__, __FILE__);
  2091.             firstnfa = pat;
  2092.             }
  2093.  
  2094.                 |  error
  2095.             { synerr( "unrecognized rule" ); }
  2096.         ;
  2097.  
  2098. eol             :  '$'
  2099.                         {
  2100.             checkedges(__LINE__, __FILE__);
  2101.             eps = mkstate( SYM_EPSILON );
  2102.             checkedges(__LINE__, __FILE__);
  2103.             $$ = link_machines( eps, mkstate( '\n' ) );
  2104.             checkedges(__LINE__, __FILE__);
  2105.             }
  2106.  
  2107.         |
  2108.                 {
  2109.             checkedges(__LINE__, __FILE__);
  2110.                 $$ = mkstate( SYM_EPSILON );
  2111.             checkedges(__LINE__, __FILE__);
  2112.                 }
  2113.         ;
  2114.  
  2115. re              :  re '|' series
  2116.                         {
  2117.             checkedges(__LINE__, __FILE__);
  2118.             $$ = mkor( $1, $3 );
  2119.             checkedges(__LINE__, __FILE__);
  2120.             }
  2121.  
  2122.         |  series
  2123.             {
  2124.             $$ = $1;
  2125.             }
  2126.         ;
  2127.  
  2128.  
  2129. series          :  series singleton
  2130.                         {
  2131.             /* this is where concatenation of adjacent patterns
  2132.              * gets done
  2133.              */
  2134.             checkedges(__LINE__, __FILE__);
  2135.             $$ = link_machines( $1, $2 );
  2136.             checkedges(__LINE__, __FILE__);
  2137.             }
  2138.  
  2139.         |  singleton
  2140.             { $$ = $1; }
  2141.         ;
  2142.  
  2143. singleton       :  singleton '*'
  2144.                         {
  2145.             checkedges(__LINE__, __FILE__);
  2146.             $$ = mkclos( $1 );
  2147.             checkedges(__LINE__, __FILE__);
  2148.             }
  2149.             
  2150.         |  singleton '+'
  2151.             {
  2152.             checkedges(__LINE__, __FILE__);
  2153.             $$ = mkposcl( $1 );
  2154.             checkedges(__LINE__, __FILE__);
  2155.             }
  2156.  
  2157.         |  singleton '?'
  2158.             {
  2159.             checkedges(__LINE__, __FILE__);
  2160.             $$ = mkopt( $1 );
  2161.             checkedges(__LINE__, __FILE__);
  2162.             }
  2163.  
  2164.         |  singleton '{' NUMBER ',' NUMBER '}'
  2165.             {
  2166.             if ( $3 > $5 || $3 < 0 )
  2167.                 {
  2168.                 synerr( "bad iteration values" );
  2169.                 $$ = $1;
  2170.                 }
  2171.             else {
  2172.                 if ( $3 == 0 )
  2173.                 {
  2174.                 checkedges(__LINE__, __FILE__);
  2175.                 $$ = mkrep( $1, 1, $5 );
  2176.                 checkedges(__LINE__, __FILE__);
  2177.                 $$ = mkopt( $$ );
  2178.                 checkedges(__LINE__, __FILE__);
  2179.                 }
  2180.                 else {
  2181.                 checkedges(__LINE__, __FILE__);
  2182.                 $$ = mkrep( $1, $3, $5 );
  2183.                 checkedges(__LINE__, __FILE__);
  2184.                 }
  2185.                 }
  2186.             }
  2187.                 
  2188.         |  singleton '{' NUMBER ',' '}'
  2189.             {
  2190.             if ( $3 <= 0 )
  2191.                 {
  2192.                 synerr( "iteration value must be positive" );
  2193.                 $$ = $1;
  2194.                 }
  2195.  
  2196.             else
  2197.                 $$ = mkrep( $1, $3, INFINITY );
  2198.             }
  2199.  
  2200.         |  singleton '{' NUMBER '}'
  2201.             {
  2202.             if ( $3 <= 0 )
  2203.                 {
  2204.                 synerr( "iteration value must be positive" );
  2205.                 $$ = $1;
  2206.                 }
  2207.  
  2208.             else {
  2209.                 checkedges(__LINE__, __FILE__);
  2210.                 $$ = link_machines( $1, copysingl( $1, $3 - 1 ) );
  2211.                 checkedges(__LINE__, __FILE__);
  2212.                 }
  2213.             }
  2214.  
  2215.         |  '.'
  2216.             {
  2217.  
  2218.             makeany();
  2219.             $$ = ccl2nfa( &anyccl );
  2220.             checkedges(__LINE__, __FILE__);
  2221.             }
  2222.  
  2223.         |  fullccl
  2224.             {
  2225.             $$ = ccl2nfa( &ccl );
  2226.             }
  2227.  
  2228.  
  2229.         |  '"' string '"'
  2230.             { $$ = $2; }
  2231.  
  2232.         |  '(' re ')'
  2233.             { $$ = $2; }
  2234.  
  2235.         |  CHAR
  2236.             {
  2237.             if ( $1 == '\0' )
  2238.                 synerr( "null in rule" );
  2239.  
  2240.             checkedges(__LINE__, __FILE__);
  2241.             $$ = mkstate( $1 );
  2242.             checkedges(__LINE__, __FILE__);
  2243.             }
  2244.         ;
  2245.  
  2246. fullccl        :  '[' ccl ']'
  2247.  
  2248.         |  '[' '^' ccl ']'
  2249.             {
  2250.             checkedges(__LINE__, __FILE__);
  2251.             cclnegate( &ccl );
  2252.             checkedges(__LINE__, __FILE__);
  2253.             }
  2254.         ;
  2255.  
  2256. ccl             :  ccl CHAR '-' CHAR
  2257.                         {
  2258.             if ( $2 > $4 )
  2259.                 synerr( "negative range in character class" );
  2260.  
  2261.             else
  2262.                 {
  2263.                 for ( i = $2; i <= $4; ++i )
  2264.                 {
  2265.                 checkedges(__LINE__, __FILE__);
  2266.                     ccladd( &ccl, i );
  2267.                 checkedges(__LINE__, __FILE__);
  2268.                 }
  2269.  
  2270.                 checkedges(__LINE__, __FILE__);
  2271.                 lastchar = $4;
  2272.                 }
  2273.             
  2274.             $$ = $1;
  2275.             }
  2276.  
  2277.         |  ccl CHAR
  2278.                 {
  2279.             checkedges(__LINE__, __FILE__);
  2280.             ccladd( &ccl, $2 );
  2281.             checkedges(__LINE__, __FILE__);
  2282.             lastchar = $2;
  2283.             checkedges(__LINE__, __FILE__);
  2284.             $$ = $1;
  2285.             }
  2286.  
  2287.         |
  2288.             {
  2289.             checkedges(__LINE__, __FILE__);
  2290.             lastchar = 0;
  2291.             checkedges(__LINE__, __FILE__);
  2292.             cclinit( &ccl );
  2293.             checkedges(__LINE__, __FILE__);
  2294.             }
  2295.         ;
  2296.  
  2297. string        :  string CHAR
  2298.                         {
  2299.             checkedges(__LINE__, __FILE__);
  2300.             $$ = link_machines( $1, mkstate( $2 ) );
  2301.             checkedges(__LINE__, __FILE__);
  2302.             }
  2303.  
  2304.         |
  2305.             {
  2306.             checkedges(__LINE__, __FILE__);
  2307.             $$ = mkstate( SYM_EPSILON );
  2308.             checkedges(__LINE__, __FILE__);
  2309.             }
  2310.         ;
  2311.  
  2312. %%
  2313.  
  2314. /* synerr - report a syntax error
  2315.  *
  2316.  * synopsis
  2317.  *    char str[];
  2318.  *    synerr( str );
  2319.  */
  2320.  
  2321. synerr( str )
  2322. char str[];
  2323.  
  2324.     {
  2325.     syntaxerror = true;
  2326.     fprintf( stderr, "Syntax error at line %d:  %s\n", linenum, str );
  2327.     }
  2328.  
  2329.  
  2330. /* yyerror - eat up an error message from the parser
  2331.  *
  2332.  * synopsis
  2333.  *    char msg[];
  2334.  *    yyerror( msg );
  2335.  */
  2336.  
  2337. yyerror( msg )
  2338. char msg[];
  2339.  
  2340.     {
  2341.     }
  2342.  
  2343. SHAR_EOF
  2344. cat << \SHAR_EOF > scan.l
  2345. /* scan.l - scanner for flex input */
  2346.  
  2347. /*
  2348.  * Copyright (c) 1987, the University of California
  2349.  * 
  2350.  * The United States Government has rights in this work pursuant to
  2351.  * contract no. DE-AC03-76SF00098 between the United States Department of
  2352.  * Energy and the University of California.
  2353.  * 
  2354.  * This program may be redistributed.  Enhancements and derivative works
  2355.  * may be created provided the new works, if made available to the general
  2356.  * public, are made available for use by anyone.
  2357.  */
  2358.  
  2359. %{
  2360. #include "flexdef.h"
  2361. #include "parse.h"
  2362.  
  2363. char nmstr[MAXLINE];
  2364.  
  2365. #define RETURNCHAR \
  2366.     yylval = yytext[0]; \
  2367.     return ( CHAR );
  2368.  
  2369. #define RETURNNAME \
  2370.     (void) strcpy( nmstr, yytext ); \
  2371.     return ( NAME );
  2372.  
  2373. #define RETURNSTRING \
  2374.     (void) strcpy( nmstr, yytext ); \
  2375.     return ( STRING );
  2376.  
  2377. #define PUT_BACK_STRING(str, start) \
  2378.     for ( i = strlen( str ) - 1; i >= start; --i ) \
  2379.         unput(str[i])
  2380. %}
  2381.  
  2382. %x MAIN NUM QUOTE BRACEERROR FIRSTCCL CCL COR QUOTECOR
  2383. %x FIRSTCCLCOR CCLCOR
  2384.  
  2385. C    ([a-zA-Z0-9_()%<>[\]{},.;&!~*/+\-=^|?:@`$# ])
  2386. cchar    ((\\?)({C}|\"))|(\\\')|(\\\\)|(\\([0-7]{1,3}))
  2387. schar    ((\\?)({C}|\'))|(\\\")|(\\\\)|(\\([0-7]{1,3}))
  2388. WS        [ \t]+
  2389.  
  2390. NAME        [a-z_][a-z_0-9]*
  2391.  
  2392. ESCSEQ        \\([^^\n]|"^".|0[0-9]{1,3})
  2393.  
  2394. %%
  2395.     static int bracelevel, didadef;
  2396.     int i;
  2397.     char myesc();
  2398.  
  2399.  
  2400. <INITIAL,COR>^%correct    {
  2401.             BEGIN(COR);
  2402.             return CORRECT;
  2403.             }
  2404.  
  2405. <INITIAL,COR>^"%"{WS}.*"\n"    {
  2406.             /* I'm a comment */
  2407.             }
  2408.  
  2409. <INITIAL,COR>^%tolerance  {
  2410.             BEGIN(COR);
  2411.             return TOLERANCE;
  2412.             }
  2413.  
  2414. <INITIAL,COR>^%insert  {
  2415.             BEGIN(COR);
  2416.             return INSERT;
  2417.             }
  2418.  
  2419. <INITIAL,COR>^%delete     {
  2420.             BEGIN(COR);
  2421.             return DELETE;
  2422.             }
  2423.  
  2424. <COR>{WS}        {
  2425.             }
  2426.  
  2427. <COR>[0-9]+        {
  2428.             yylval = myctoi( yytext );
  2429.             return ( NUMBER );
  2430.             }
  2431.  
  2432. <COR>\"            {
  2433.             BEGIN(QUOTECOR);
  2434.             return '"';
  2435.             }
  2436.  
  2437. <QUOTECOR>\"        {
  2438.             BEGIN(COR);
  2439.             return '"';
  2440.             }
  2441.  
  2442. <QUOTECOR>.        {
  2443.             RETURNCHAR;
  2444.             }
  2445.  
  2446. <COR>\.            {
  2447.             return '.';
  2448.             }
  2449.  
  2450. <COR>"\n"        {
  2451.             return '\n';
  2452.             }
  2453.  
  2454. <COR>.            {
  2455.             RETURNCHAR;
  2456.             }
  2457.  
  2458. <INITIAL,COR>"["([^\\\]\n]|{ESCSEQ})+"]"    {
  2459.             (void) strcpy( nmstr, yytext );
  2460.  
  2461.             /* push back everything but the leading bracket
  2462.              * so the ccl can be rescanned
  2463.              */
  2464.             PUT_BACK_STRING(nmstr, 1);
  2465.  
  2466.             BEGIN(FIRSTCCLCOR);
  2467.             return ( '[' );
  2468.             }
  2469.  
  2470. <FIRSTCCLCOR>"^"/[^-\n]    BEGIN(CCLCOR); return ( '^' );
  2471. <FIRSTCCLCOR>"^"/-        return ( '^' );
  2472. <FIRSTCCLCOR>-        BEGIN(CCLCOR); yylval = '-'; return ( CHAR );
  2473. <FIRSTCCLCOR>.        BEGIN(CCLCOR); RETURNCHAR;
  2474. <FIRSTCCLCOR>{ESCSEQ}    {
  2475.             yylval = myesc( yytext );
  2476.             BEGIN(CCLCOR);
  2477.             return ( CHAR );
  2478.             }
  2479.  
  2480. <CCLCOR>-/[^\]\n]        return ( '-' );
  2481. <CCLCOR>[^\]\n]        RETURNCHAR;
  2482. <CCLCOR>"]"        BEGIN(COR); return ( ']' );
  2483.  
  2484.  
  2485. <INITIAL,COR>^"%%".*\n    {
  2486.             BEGIN(MAIN);
  2487.             }
  2488.  
  2489.  
  2490. <MAIN>^"^"        return ( '^' );
  2491. <MAIN>\"        BEGIN(QUOTE); return ( '"' );
  2492. <MAIN>"{"/[0-9]        BEGIN(NUM); return ( '{' );
  2493. <MAIN>"{"[^0-9\n][^}\n]*    BEGIN(BRACEERROR);
  2494. <MAIN>"$"/[ \t\n]    return ( '$' );
  2495.  
  2496. <MAIN>{WS}        { /* needs to be separate from following rule due to
  2497.                * bug with trailing context
  2498.                */
  2499.             bracelevel = 0;
  2500.             return ( '\n' );
  2501.             }
  2502.  
  2503. <MAIN>"["([^\\\]\n]|{ESCSEQ})+"]"    {
  2504.             (void) strcpy( nmstr, yytext );
  2505.  
  2506.             /* push back everything but the leading bracket
  2507.              * so the ccl can be rescanned
  2508.              */
  2509.             PUT_BACK_STRING(nmstr, 1);
  2510.  
  2511.             BEGIN(FIRSTCCL);
  2512.             return ( '[' );
  2513.             }
  2514.  
  2515. <MAIN>"{"{NAME}"}"    {
  2516.             register char *nmdefptr;
  2517.             char *ndlookup();
  2518.  
  2519.             (void) strcpy( nmstr, yytext );
  2520.             nmstr[yyleng - 1] = '\0';  /* chop trailing brace */
  2521.  
  2522.             /* lookup from "nmstr + 1" to chop leading brace */
  2523.             if ( ! (nmdefptr = ndlookup( nmstr + 1 )) )
  2524.                 synerr( "undefined {name}" );
  2525.  
  2526.             else
  2527.                 { /* push back name surrounded by ()'s */
  2528.                 unput(')');
  2529.                 PUT_BACK_STRING(nmdefptr, 0);
  2530.                 unput('(');
  2531.                 }
  2532.             }
  2533.  
  2534. <MAIN>[/|*+?.()]    return ( yytext[0] );
  2535. <MAIN>.            RETURNCHAR;
  2536. <MAIN>\n        ++linenum; return ( '\n' );
  2537.  
  2538.  
  2539. <QUOTE>[^"\n]        RETURNCHAR;
  2540. <QUOTE>\"        BEGIN(MAIN); return ( '"' );
  2541.  
  2542. <QUOTE>\n        {
  2543.             synerr( "missing quote" );
  2544.             BEGIN(MAIN);
  2545.             ++linenum;
  2546.             return ( '"' );
  2547.             }
  2548.  
  2549.  
  2550. <FIRSTCCL>"^"/[^-\n]    BEGIN(CCL); return ( '^' );
  2551. <FIRSTCCL>"^"/-        return ( '^' );
  2552. <FIRSTCCL>-        BEGIN(CCL); yylval = '-'; return ( CHAR );
  2553. <FIRSTCCL>.        BEGIN(CCL); RETURNCHAR;
  2554. <FIRSTCCL>{ESCSEQ}    {
  2555.             yylval = myesc( yytext );
  2556.             BEGIN(CCL);
  2557.             return ( CHAR );
  2558.             }
  2559.  
  2560. <CCL>-/[^\]\n]        return ( '-' );
  2561. <CCL>[^\]\n]        RETURNCHAR;
  2562. <CCL>"]"        BEGIN(MAIN); return ( ']' );
  2563.  
  2564.  
  2565.  
  2566. <NUM>[0-9]+        {
  2567.             yylval = myctoi( yytext );
  2568.             return ( NUMBER );
  2569.             }
  2570.  
  2571. <NUM>","            return ( ',' );
  2572. <NUM>"}"            BEGIN(MAIN); return ( '}' );
  2573.  
  2574. <NUM>.            {
  2575.             synerr( "bad character inside {}'s" );
  2576.             BEGIN(MAIN);
  2577.             return ( '}' );
  2578.             }
  2579.  
  2580. <NUM>\n            {
  2581.             synerr( "missing }" );
  2582.             BEGIN(MAIN);
  2583.             ++linenum;
  2584.             return ( '}' );
  2585.             }
  2586.  
  2587.  
  2588. <BRACEERROR>"}"        synerr( "bad name in {}'s" ); BEGIN(MAIN);
  2589. <BRACEERROR>\n        synerr( "missing }" ); ++linenum; BEGIN(MAIN);
  2590.  
  2591.  
  2592.  
  2593. <INITIAL,MAIN,QUOTE,CCL>{ESCSEQ}    {
  2594.             yylval = myesc( yytext );
  2595.             return ( CHAR );
  2596.             }
  2597.  
  2598.  
  2599.  
  2600. %%
  2601. SHAR_EOF
  2602. cat << \SHAR_EOF > sym.c
  2603. /* sym - symbol table routines */
  2604.  
  2605. /*
  2606.  * Copyright (c) 1987, the University of California
  2607.  * 
  2608.  * The United States Government has rights in this work pursuant to
  2609.  * contract no. DE-AC03-76SF00098 between the United States Department of
  2610.  * Energy and the University of California.
  2611.  * 
  2612.  * This program may be redistributed.  Enhancements and derivative works
  2613.  * may be created provided the new works, if made available to the general
  2614.  * public, are made available for use by anyone.
  2615.  */
  2616.  
  2617. #include "flexdef.h"
  2618.  
  2619. struct hash_entry *ndtbl[NAME_TABLE_HASH_SIZE];
  2620. struct hash_entry *sctbl[START_COND_HASH_SIZE];
  2621.  
  2622. struct hash_entry *findsym();
  2623.  
  2624.  
  2625. /* addsym - add symbol and definitions to symbol table
  2626.  *
  2627.  * synopsis
  2628.  *    char sym[], *str_def;
  2629.  *    int int_def;
  2630.  *    hash_table table;
  2631.  *    int table_size;
  2632.  *    0 / -1 = addsym( sym, def, int_def, table, table_size );
  2633.  *
  2634.  * -1 is returned if the symbol already exists, and the change not made.
  2635.  */
  2636.  
  2637. int addsym( sym, str_def, int_def, table, table_size )
  2638. register char sym[];
  2639. char *str_def;
  2640. int int_def;
  2641. hash_table table;
  2642. int table_size;
  2643.  
  2644.     {
  2645.     int hash_val = hashfunct( sym, table_size );
  2646.     register struct hash_entry *entry = table[hash_val];
  2647.     register struct hash_entry *new_entry;
  2648.     register struct hash_entry *successor;
  2649.     char *malloc();
  2650.  
  2651.     while ( entry )
  2652.     {
  2653.     if ( ! strcmp( sym, entry->name ) )
  2654.         { /* entry already exists */
  2655.         return ( -1 );
  2656.         }
  2657.     
  2658.     entry = entry->next;
  2659.     }
  2660.  
  2661.     /* create new entry */
  2662.     new_entry = (struct hash_entry *) malloc( sizeof( struct hash_entry ) );
  2663.  
  2664.     if ( new_entry == NULL )
  2665.     flexfatal( "symbol table memory allocation failed" );
  2666.  
  2667.     if ( (successor = table[hash_val]) )
  2668.     {
  2669.     new_entry->next = successor;
  2670.     successor->prev = new_entry;
  2671.     }
  2672.     else
  2673.     new_entry->next = NULL;
  2674.  
  2675.     new_entry->prev = NULL;
  2676.     new_entry->name = sym;
  2677.     new_entry->str_val = str_def;
  2678.     new_entry->int_val = int_def;
  2679.  
  2680.     table[hash_val] = new_entry;
  2681.  
  2682.     return ( 0 );
  2683.     }
  2684.  
  2685.  
  2686. /* findsym - find symbol in symbol table
  2687.  *
  2688.  * synopsis
  2689.  *    char sym[];
  2690.  *    hash_table table;
  2691.  *    int table_size;
  2692.  *    struct hash_entry *entry, *findsym();
  2693.  *    entry = findsym( sym, table, table_size );
  2694.  */
  2695.  
  2696. struct hash_entry *findsym( sym, table, table_size )
  2697. register char sym[];
  2698. hash_table table;
  2699. int table_size;
  2700.  
  2701.     {
  2702.     register struct hash_entry *entry = table[hashfunct( sym, table_size )];
  2703.     static struct hash_entry empty_entry =
  2704.     {
  2705.     (struct hash_entry *) 0, (struct hash_entry *) 0, NULL, NULL, 0,
  2706.     } ;
  2707.  
  2708.     while ( entry )
  2709.     {
  2710.     if ( ! strcmp( sym, entry->name ) )
  2711.         return ( entry );
  2712.     entry = entry->next;
  2713.     }
  2714.  
  2715.     return ( &empty_entry );
  2716.     }
  2717.  
  2718.     
  2719. /* hashfunct - compute the hash value for "str" and hash size "hash_size"
  2720.  *
  2721.  * synopsis
  2722.  *    char str[];
  2723.  *    int hash_size, hash_val;
  2724.  *    hash_val = hashfunct( str, hash_size );
  2725.  */
  2726.  
  2727. int hashfunct( str, hash_size )
  2728. register char str[];
  2729. int hash_size;
  2730.  
  2731.     {
  2732.     register int hashval;
  2733.     register int locstr;
  2734.  
  2735.     hashval = 0;
  2736.     locstr = 0;
  2737.  
  2738.     while ( str[locstr] )
  2739.     hashval = ((hashval << 1) + str[locstr++]) % hash_size;
  2740.  
  2741.     return ( hashval );
  2742.     }
  2743.  
  2744.  
  2745. /* ndinstal - install a name definition
  2746.  *
  2747.  * synopsis
  2748.  *    char nd[], def[];
  2749.  *    ndinstal( nd, def );
  2750.  */
  2751.  
  2752. ndinstal( nd, def )
  2753. char nd[], def[];
  2754.  
  2755.     {
  2756.     char *copy_string();
  2757.  
  2758.     if ( addsym( copy_string( nd ), copy_string( def ), 0,
  2759.          ndtbl, NAME_TABLE_HASH_SIZE ) )
  2760.     synerr( "name defined twice" );
  2761.     }
  2762.  
  2763.  
  2764. /* ndlookup - lookup a name definition
  2765.  *
  2766.  * synopsis
  2767.  *    char nd[], *def;
  2768.  *    char *ndlookup();
  2769.  *    def/NULL = ndlookup( nd );
  2770.  */
  2771.  
  2772. char *ndlookup( nd )
  2773. char nd[];
  2774.  
  2775.     {
  2776.     return ( findsym( nd, ndtbl, NAME_TABLE_HASH_SIZE )->str_val );
  2777.     }
  2778.  
  2779.  
  2780. SHAR_EOF
  2781. cat << \SHAR_EOF > test.in
  2782.        LmC"L4m!3
  2783.  
  2784.                            NCNB Nitionil Bank                                      0 2 - 2 8-9 1
  2785.                                                                                     2 9 4
  2786.  
  2787.  
  2788.  
  2789.  
  2790.  
  2791.  
  2792.  
  2793.  
  2794.  
  2795.  
  2796.  
  2797.  
  2798.  
  2799.          DEBITS               CHECK        REFERENCE       DATE                                 CHECK        REFERENCE       DATE
  2800.         ENCLOSED              NU4BER           ?UMBER      POSTED        AMOUNT                 NUMBER           NUMBER      POSTED        AMOUNT
  2801.                                   56818    060202238       02-21          1,463.96                  56885    050406145       02-26              621. 34
  2802.                           +       56820    061508340       02-19             414.00                 56886    051309782       02-25              212.40
  2803.                                   56821    060561884       OZ-20             380.00         +       56888    060203646       02-26              316.80
  2804.                                   56322    050308612       02-20             363.60                 56839    050000681       OZ-27              349.80
  2805.                                   S6823    OS100SO88       02-19             206.57                 56890    060701340       02-26              380.00
  2806.                                   56824    OS1215839       02-19             190.80                 56891    OS2104948       02-25              123.20
  2807.                           +       56826    051215810       02-19             119.42                 56892    osoilOS09       02-27              588.38
  2808.                                   56827    051009745       02-19             258.00                 56893    050106127       02-28              161.60
  2809.                                   56828    060-,41320      02-20             621.83                 56894    OS2104867       C2-2S              168.00
  2810.                                   56829    060006534       02-20             541.21                 56895    061000900       02-26              63.00
  2811.                                   56830    OS1216101       02-19          19216.00                  56896    050307144       02-27              703.52
  2812.                           +       56832    05111167S       02-19             269.90                 56897    0605OS986       02-26              242.04
  2813.                                   56833    060003876       02-20          1,987.50                  56898    050106126       02-28              161.60
  2814.                           +       56836    051201744       02-21             182,40                 56899    060708682       02-26              964,08
  2815.                                   56837    050202940       02-21          1;219.20                  56900    060708683       02-26              64.68
  2816.                           +       56839    06000451S       02-21             491.10                 56901    061308454       02-26              173.70
  2817.                                   56840    OS020209S       02-25             389.60                 S6902    060809S84       02-26              213,38
  2818.                                   56841    050308595       02-20             91-52                  56903    061308450       02-26           1,202.00
  2819.                                   56842    050007600       02-20             596.75         +       5690S    060114198       02-27              604.18
  2820.                                   56843    050111266       02-22             372.28         +       56908    OS1103408       02-27              108.80
  2821.                                   56844    260208095       OZ-21             67.50                  56909    051507798       02-27              104.65
  2822.                                   5684S    060802989       02-20          1,108.8S                  56910    050104176       OZ-28              171.70
  2823.                           +       56847    060109317       02-21             412.70                 56911    051606473       02-27              98.48
  2824.                                   56848    050307489       02-21             914.80                 56912    051312820       02-27              676.40
  2825.                           +       56852    051607269       02-21             562.60         +       56916    050603S74       02-28              15S.20
  2826.                                   56853    050007191       02-26             161.60                 56917    050603564       02-28              530.40
  2827.                                   56854    OS1103024       02-21             54.00                  56918    050603S65       02-28              710.64
  2828.                                   56855    0511028?5       02-21             161.60                 56919    050607308       0 2 - 28           217.90
  2829.                           +       56857    050513006       OZ-22             105.9z                 56920    050310013       02-23              347.65
  2830.                                   56858    050202096       02-25             108.80         +       56922    OS0310012       02-28              429.8S
  2831.                                   56859    060808589       O2-2S             356.40                 56923    060601777       02-28              617.69
  2832.                                   56860    050806133       02-22             406.36                 56924    060709449       02-28              201.70
  2833.                                   56861    050808783       02-22             454.8S         +       57091    050608090       02-27              210.38
  2834.                                   56862    060200919       02-25             291.62                 57092    060012187       02-25              629.40
  2835.                                   56863    050207083       02-25             112.40                 57093    050202097       02-25              161.60
  2836.                                   56864    060312068       02-22             640.58                 57094    051012134       02-22              168.79
  2837.                                   56865    OSIO01219       O2-2S             242.80                 57095    OSIO04287       02-22              338.00
  2838.                                   56866    060804384       02-25             732.40                 57096    0607042SS       02-22              lSl.20
  2839.                                   56867    051500756       02-25             312.80                 57097    060006924       02-26              200.40
  2840.                                   56868    060511506       02-25             50.40                  57098    050102456       02-26              410.90
  2841.                                   56369    060508702       02-2s             9S.36                  57099    050102583       02-25              8S.75
  2842.                           +       56872    060525998       02-25             226.00                 57100    060100999       02-20              672.00
  2843.                           +       56874    060212912       02-26             192.00                 57101    050906894       02-20              50. 96
  2844.                                   56875    OS1500744       02-25             39-5.44                S7102    051009816       02-19              468.00
  2845.                                   56876    050007022       02-27             259.80                 57103    050308609       02-20              396.00
  2846.                                   56877    060006155       02-27             298.80         +       57105    060212020       02-20              161.60
  2847.                                   56878    050201596       02-27             176.00                 S7106    051002151       02-22              397.84
  2848.                                   56879    250211326       02-27             199.75                 57107    060002931       02-20              382.40
  2849.                                   56880    050406092       02-26             940.89                 57108    OS02074S9       02-12              41S.06
  2850.                           +       56882    050007659       02-27             899.20                 57109    051909717       02-11              94.40
  2851.                                   56883    060213188       02-26             221.10                 57110    060503196       OZ-12              119.70
  2852.                                   56884    061308451       OZ-26             253.60         NO ITEM 9        051204273       02-22              273.80
  2853.  
  2854.                           + INDICATES BREAK IN NUMERICAL SEQUENCE
  2855.  
  2856.  
  2857.  
  2858.  
  2859.  
  2860.  
  2861.  
  2862.  
  2863.    NdnT'rg QPP nw/rDOL, Qlngl C:C)Q INADOOTAPI-R It,([:(-)DRAATir)rll                                                 kA,-h., P:ni(,
  2864.  
  2865.         iNCR!=9                                                         XXXXXXXXXX
  2866. SHAR_EOF
  2867. cat << \SHAR_EOF > test.out
  2868.        ENCLOSED           NUMBER        NUMBER      POSTED        AMOUNT                 NUMBER           NUMBER      POSTED        AMOUNT
  2869.                                   56818    060202238       02-21          1,463.96                  56885    050406145       02-26             621.34
  2870.                           +       56820    061508340       02-19             414.00                 56886    051309782       02-25             212.40
  2871.                                   56821    060561884       02-20             380.00         +       56888    060203646       02-26             316.80
  2872.                                   56322    050308612       02-20             363.60                 56839    050000681       02-27             349.80
  2873.                                   56823    051005088       02-19             206.57                 56890    060701340       02-26             380.00
  2874.                                   56824    051215839       02-19             190.80                 56891    052104948       02-25             123.20
  2875.                           +       56826    051215810       02-19             119.42                 56892    050110509       02-27             588.38
  2876.                                   56827    051009745       02-19             258.00                 56893    050106127       02-28             161.60
  2877.                                   56828    060841320      02-20             621.83                 56894    052104867       12-25             168.00
  2878.                                   56829    060006534       02-20             541.21                 56895    061000900       02-26             63.00
  2879.                                   56830    051216101       02-19          19,216.00                  56896    050307144       02-27             703.52
  2880.                           +       56832    051111675       02-19             269.90                 56897    060505986       02-26             242.04
  2881.                                   56833    060003876       02-20          1,987.50                  56898    050106126       02-28             161.60
  2882.                           +       56836    051201744       02-21             182.40                 56899    060708682       02-26             964.08
  2883.                                   56837    050202940       02-21          1,219.20                  56900    060708683       02-26             64.68
  2884.                           +       56839    060004515       02-21             491.10                 56901    061308454       02-26             173.70
  2885.                                   56840    050202095       02-25             389.60                 56902    060809584       02-26             213.38
  2886.                                   56841    050308595       02-20             91.52                  56903    061308450       02-26           1,202.00
  2887.                                   56842    050007600       02-20             596.75         +       56905    060114198       02-27             604.18
  2888.                                   56843    050111266       02-22             372.28         +       56908    051103408       02-27             108.80
  2889.                                   56844    260208095       02-21             67.50                  56909    051507798       02-27             104.65
  2890.                                   56845    060802989       02-20          1,108.85                  56910    050104176       02-28             171.70
  2891.                           +       56847    060109317       02-21             412.70                 56911    051606473       02-27             98.48
  2892.                                   56848    050307489       02-21             914.80                 56912    051312820       02-27             676.40
  2893.                           +       56852    051607269       02-21             562.60         +       56916    050603574       02-28             155.20
  2894.                                   56853    050007191       02-26             161.60                 56917    050603564       02-28             530.40
  2895.                                   56854    051103024       02-21             54.00                  56918    050603565       02-28             710.64
  2896.                                   56855    051102895       02-21             161.60                 56919    050607308       02-28           217.90
  2897.                           +       56857    050513006       02-22             105.92                 56920    050310013       02-23             347.65
  2898.                                   56858    050202096       02-25             108.80         +       56922    050310012       02-28             429.85
  2899.                                   56859    060808589       02-25             356.40                 56923    060601777       02-28             617.69
  2900.                                   56860    050806133       02-22             406.36                 56924    060709449       02-28             201.70
  2901.                                   56861    050808783       02-22             454.85         +       57091    050608090       02-27             210.38
  2902.                                   56862    060200919       02-25             291.62                 57092    060012187       02-25             629.40
  2903.                                   56863    050207083       02-25             112.40                 57093    050202097       02-25             161.60
  2904.                                   56864    060312068       02-22             640.58                 57094    051012134       02-22             168.79
  2905.                                   56865    051001219       02-25             242.80                 57095    051004287       02-22             338.00
  2906.                                   56866    060804384       02-25             732.40                 57096    060704255       02-22             151.20
  2907.                                   56867    051500756       02-25             312.80                 57097    060006924       02-26             200.40
  2908.                                   56868    060511506       02-25             50.40                  57098    050102456       02-26             410.90
  2909.                                   56369    060508702       02-25             95.36                  57099    050102583       02-25             85.75
  2910.                           +       56872    060525998       02-25             226.00                 57100    060100999       02-20             672.00
  2911.                           +       56874    060212912       02-26             192.00                 57101    050906894       02-20             50.96
  2912.                                   56875    051500744       02-25             395.44                57102    051009816       02-19             468.00
  2913.                                   56876    050007022       02-27             259.80                 57103    050308609       02-20             396.00
  2914.                                   56877    060006155       02-27             298.80         +       57105    060212020       02-20             161.60
  2915.                                   56878    050201596       02-27             176.00                 57106    051002151       02-22             397.84
  2916.                                   56879    250211326       02-27             199.75                 57107    060002931       02-20             382.40
  2917.                                   56880    050406092       02-26             940.89                 57108    050207459       02-12             415.06
  2918.                           +       56882    050007659       02-27             899.20                 57109    051909717       02-11             94.40
  2919.                                   56883    060213188       02-26             221.10                 57110    060503196       02-12             119.70
  2920.                                   56884    061308451       02-26             253.60         NO ITEM #     051204273       02-22             273.80
  2921. SHAR_EOF
  2922. #    End of shell archive
  2923. exit 0
  2924.