home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 218_01 / hyphen.c < prev    next >
Text File  |  1979-12-31  |  8KB  |  290 lines
  1. /*
  2.  * HYPHEN.C
  3.  *
  4.  * Hyphenation module. Adapted from the Bell Labs hyphenation algorithm.
  5.  * Suffix and digram tables taken from several public domain sources,
  6.  * including DECUS RUNOFF.
  7.  *
  8.  * Basically a toy until a decent exception list is added.
  9.  *
  10.  * Edits:
  11.  *    01 13-May-81 RBD  Initial edit.
  12.  */
  13. #include <stdio.h>
  14. #include <ctype.h>
  15.  
  16. #define NULL 0
  17.  
  18. /*
  19.  * Custom C control construct: cycle/recycle/quit
  20.  */
  21.  
  22. #define cycle while(1) {
  23. #define recycle continue
  24. #define quit break
  25. #define endcycle }
  26.  
  27. /*
  28.  * External statics and functions.
  29.  */
  30. extern char *wdstart, *wdend;          /* Pointers to 1st and last chars */
  31. extern char *hyptr[];                  /* Table of ptrs to hyp pos's */
  32. /* extern char tolower(); */                /* Fold character to lower case */
  33.  
  34. /*
  35.  * Internal statics.
  36.  */
  37. static char *hyend;                    /* Working scan pointer */
  38. static char **hyp;                     /* Scan ptr for hyptr table */
  39.  
  40. /*
  41.  * Digram tables, table of pointers to suffix tables.
  42.  */
  43. extern char bxh[26][13], bxxh[26][13], xxh[26][13], xhx[26][13], hxx[26][13];
  44. extern char *suftab[];
  45.  
  46. #define THRESH 160                     /* Digram goodness threshold */
  47.  
  48. /*
  49.  * Mark word for hyphenation.
  50.  *
  51.  * Inputs:
  52.  *       wp = pointer to start of word to hyphenate.
  53.  *
  54.  * Outputs:
  55.  *       returns 0
  56.  *       wdstart --> first letter
  57.  *       wdend   --> last letter
  58.  *       hyend   --> letter before first hyphenation break
  59.  *       hyptr[] --> locations where hyphenation is OK
  60.  */
  61. hyphen(wp)
  62. char *wp;
  63.    {
  64.    register char *ch;
  65.    register char **h;
  66.    register int i;
  67. /*
  68.  * Skip by leading punctuation
  69.  */
  70.    ch = wp;
  71. /******** TEMP
  72.    while(punct(*ch++))
  73.       ;
  74. */
  75.    ch++;    /* Fake it */
  76. /*
  77. *********/
  78.  
  79. /*
  80.  * If word doesn't start with alpha, don't hyphenate.
  81.  */
  82.    if (!isalpha(*--ch))
  83.       return;
  84. /*
  85.  * Mark the special places in the word.
  86.  */
  87.    wdstart = ch++;                     /* wdstart --> 1st alpha */
  88.    while(isalpha(*ch++))
  89.       ;
  90.    hyend = wdend = --ch-1;             /* hyend --> last letter */
  91.  
  92. /******** TEMP **********
  93.    while(punct(*ch++))  */               /* (skip trailing punctuation) */
  94.    ch++; /* Fake it */
  95. /*      ;
  96. *************************/
  97. /*
  98.  * Don't hyphenate unless that was trailing punctuation, not
  99.  * punctuation within a word. Assumes word ends in NULL. Also,
  100.  * don't hyphenate if word is shorter than 5 characters.
  101.  */
  102.    if (*--ch)
  103.       return;
  104.    if ((wdend-wdstart-4) < 0)
  105.       return;
  106.  
  107.    hyp = hyptr;                        /* hyp --> first cell in hyptr */
  108.    *hyp = NULL;                        /* hyptr[0] <-- 0 */
  109.  
  110.    suffix();                           /* Mark suffix based hyp points */
  111.    digram();                           /* Mark usable digrams in the word */
  112.    *hyp++ = NULL;                      /* Terminate the list with a NULL */
  113.  
  114.    /*
  115.     * Do a bubble sort on the hyphenation pointers in hyptr[]
  116.     * so they point to spots in the word from left to right.
  117.     */
  118.    if (*hyptr)
  119.       for(i = 1; i;)
  120.          {
  121.          i = 0;
  122.          for(h = hyptr+1; *h != 0; h++)
  123.             {
  124.             if (*(h-1) > *h)
  125.                {
  126.                i++;
  127.                ch = *h; *h = *(h-1); *(h-1) = ch;
  128.                }
  129.             }
  130.          }
  131.    }
  132.  
  133. /*
  134.  * Suffix test and processing. Handles multiple suffices, such as
  135.  * "ationalism".
  136.  */
  137. suffix()
  138.    {
  139.    register char *s, *s0, *w;
  140.    char ch;
  141.    char *chkvow();
  142.  
  143.    /*
  144.     * Do this from right to left, recognizing suffix forms which make
  145.     * up a concatenated multi-suffix.
  146.     */
  147.    cycle
  148.       /*
  149.        * Make ch = lower case last character for this suffix try.
  150.        */
  151.       if (!isalpha(ch = *hyend))       /* Done if non-alpha */
  152.          return(0);
  153.       /*
  154.        * Point s0 at suffix table for the last letter in this word.
  155.        * If there is no suffix table, return failure.
  156.        */
  157.       if ((s0 = suftab[tolower(ch)-'a']) == NULL)
  158.          return(0);
  159.       /*
  160.        * Test word for match to nodes in suffix table. Done if end of
  161.        * table reached.
  162.        */
  163.       cycle
  164.          if ((ch = *s0 & 017) == '\0') /* ch = # chars in this node */
  165.             return(0);                 /* Done if none (end of table) */
  166.          s = s0 + ch - 1;              /* s --> last char in node */
  167.          w = hyend - 1;                /* w --> next to last char in word */
  168.  
  169.          while(((s > s0) && (w >= wdstart)) && ((*s & 0177) == tolower(*w)))
  170.             {
  171.             s--;
  172.             w--;
  173.             }
  174.  
  175.          if (s == s0)                  /* If the entire suffix matched ... */
  176.             quit;                      /* ... quit the cycle. Found one. */
  177.          s0 += ch;                     /* No match, go to next node */
  178.       endcycle
  179.  
  180.       s = s0 + ch - 1;                 /* s --> last char in node */
  181.       w = hyend;                       /* w --> last char in word */
  182.       if (*s0 & 0200) goto mark;       /* If hyp flag set, mark hyp spot */
  183.       /*
  184.        * Mark the places where it can be hyphenated.
  185.        */
  186.       while(s > s0)
  187.          {
  188.          --w;
  189.          if (*s-- & 0200)              /* If this is a legal hyp spot */
  190.             {
  191. mark:                                  /* Mark it as a hyphenation spot */
  192.             hyend = w - 1;             /* hyend --> word b4 hyp spot */
  193.             /*
  194.              * If bit 6 set in first cell, it means
  195.              * supress actual hyphenation.
  196.              */
  197.             if (*s0 & 0100)            /* If supress, keep moving left */
  198.                continue;
  199.             if (!chkvow(w))            /* Done if no vowels precede this */
  200.                return(0);
  201.             *hyp++ = w;                /* Fill in a hyphenation pointer */
  202.             }
  203.          }
  204. /*
  205.  * End of suffix node. If bit 5 set in first cell, supress multi
  206.  * suffix processing, done. Otherwise, look further to the left
  207.  * for more suffices and hyphenation points.
  208.  */
  209.       if (*s0 & 040)
  210.          return(0);
  211.    endcycle
  212.    }
  213.  
  214. /*
  215.  * Test if the supplied letter is a vowel.
  216.  */
  217. vowel(ch)
  218. int ch;
  219.    {
  220.    switch(tolower(ch))
  221.       {
  222.       case 'a':
  223.       case 'e':
  224.       case 'i':
  225.       case 'o':
  226.       case 'u':
  227.       case 'y':
  228.          return(1);
  229.       default:
  230.          return(0);
  231.       }
  232.    }
  233.  
  234. /*
  235.  * Check if any letters to the left of *w are vowels.
  236.  */
  237. char *chkvow(w)
  238. char *w;
  239.    {
  240.    while(--w >= wdstart) if(vowel(*w)) return(w);
  241.    return(0);
  242.    }
  243.  
  244. /*
  245.  * Digram processing. Magic here.
  246.  */
  247. digram()
  248.    {
  249.    register char *w;
  250.    register int val;
  251.    char *nhyend, *maxw;
  252.    int maxval;
  253.    char *chkvow();
  254.  
  255.    cycle
  256.       if (!(w=chkvow(hyend+1))) return;
  257.       hyend = w;
  258.       if (!(w=chkvow(hyend))) return;
  259.       nhyend = w;
  260.       maxval = 0;
  261.       w--;
  262.       while((++w < hyend) && (w < (wdend-1)))
  263.          {
  264.          val = 1;
  265.          if (w == wdstart) val *= dilook('a',*w,bxh);
  266.          else if(w == wdstart+1) val *= dilook(*(w-1),*w,bxxh);
  267.          else val *= dilook(*(w-1),*w,xxh);
  268.          val *= dilook(*w, *(w+1), xhx);
  269.          val *= dilook(*(w+1), *(w+2), hxx);
  270.          if (val > maxval)
  271.             {
  272.             maxval = val;
  273.             maxw = w + 1;
  274.             }
  275.          }
  276.       hyend = nhyend;
  277.       if (maxval > THRESH)*hyp++ = maxw;
  278.    endcycle
  279. }
  280.  
  281. dilook(a,b,t)
  282. char a, b;
  283. char t[26][13];
  284.    {
  285.    register char i, j;
  286.  
  287.    i = t[tolower(a)-'a'][(j = tolower(b)-'a')/2];
  288.    if (!(j & 01))i >>= 4;
  289.    return(i & 017);
  290.    }