home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / net / markov / markov3.l < prev    next >
Encoding:
Lex Description  |  1987-03-06  |  11.5 KB  |  479 lines
  1. %{
  2. /*
  3.  * Copyright (c) 1986, 1987 by Joe Buck
  4.  *
  5.  * Permission is granted to use, redistribute, or modify this program,
  6.  * as long as you don't pretend you wrote it.  Send improvements or
  7.  * bug reports to {ihnp4,hplabs,ames,sun}!oliveb!epimass!jbuck.
  8.  *
  9.  * The program generates simulated Usenet articles, given Usenet articles
  10.  * as input.
  11.  *
  12.  * This program constructs a table of frequencies for a token appearing,
  13.  * given the two preceding tokens.  A "token" is a sequence of non-blank
  14.  * characters.  An entirely blank line is also treated as a token, as is
  15.  * the beginning and end of an article.
  16.  *
  17.  * The program is designed to process news articles, rejecting text from
  18.  * the header, signature, and included text, together with cruft inserted
  19.  * by rn and notes.  A paragraph of included text is treated like a token.
  20.  *
  21.  * After the table is built (and it can be big), articles are generated
  22.  * on the standard output.
  23.  */
  24. #ifndef lint
  25. static char *sccs_id = "@(#)markov3.l    1.1 3/6/87 epimass!jbuck";
  26. #endif
  27. #include <sys/types.h>        /* for time_t */
  28. int in_included_text = 0;
  29. %}
  30. %Start HDR BODY SIG
  31. %%
  32. <HDR>^[^ \t]+:.*\n    ;    /* Header line, e.g. "From: foo@bar.UUCP" */
  33. <HDR>^[ \t]+[^ \t].*\n    ;    /* Continuation of header line */
  34. <HDR>^[ \t]*$        BEGIN BODY;
  35. <BODY>^"-- "$        BEGIN SIG;
  36. <BODY>^[><)|#}].*\n    { /* 50% rule gets people to change ">"
  37.                  to other characters; this gets most of them */
  38.               if (!in_included_text) {
  39.                       in_included_text = 1;
  40.                   process_token ("\n> ...\n\n");
  41.               }
  42.             }
  43. <BODY>"]".*\n        { /* should have been included in the above.  My
  44.                  lex generates bad C code if I say [[><...]
  45.                  even though ed(1) says that's a valid regular
  46.                  expression. */
  47.               if (!in_included_text) {
  48.                   in_included_text = 1;
  49.                   process_token ("\n> ...\n\n");
  50.               }
  51.             }
  52. <BODY>^"In article".*\n    ;    /* Reject rn crud */
  53. <BODY>^"/* Written".*"*/"\n    ;        /* Also NOTES crud */
  54. <BODY>^"/* End of text from".*"*/"\n    ;        /* NOTES */
  55. <BODY>^"/* ----------".*"----------*/"\n    ;        /* NOTES */
  56. <BODY>[ \t]+        ;    /* Skip white space */
  57. <BODY>\n[ \t\n]*\n    { process_token ("\n"); /* Paragraph break */}
  58. <BODY>[^ \t\n]+        { in_included_text = 0; process_token (yytext); }
  59. <HDR>.            ;    /* Eat anything that escaped */
  60. <HDR>\n            ;
  61. <BODY>\n        ;
  62. <SIG>.            ;
  63. <SIG>\n            ;
  64. %%
  65. void perror(), exit();
  66. char *strcpy(), *malloc();
  67. extern int optind;
  68. extern char *optarg;
  69.  
  70. /*
  71.  * hashtab is a hash table storing all the tokens we encounter.
  72.  */
  73. struct htentry {
  74.     char *htext;
  75.     struct htentry *hlink;
  76. };
  77.  
  78. #define HSIZE 3557        /* Should be prime */
  79. #define Fprintf (void)fprintf
  80. #define Printf (void)printf
  81.  
  82. struct htentry hashtab[HSIZE];
  83.  
  84. /*
  85.  * node and succnode are portions of the big structure we're going to build.
  86.  * node represents something like ("was", "a") in a binary tree.
  87.  * a linked list of succnodes contain tokens that may follow ("was", "a")
  88.  */
  89. struct node {
  90.     char *text;
  91.     char *text2;
  92.     int ocount;
  93.     struct node *lc, *rc;
  94.     struct succnode *succ;
  95. };
  96.  
  97. struct succnode {
  98.     struct node *scnod;
  99.     int    count;
  100.     struct succnode *link;
  101. };
  102.  
  103.  
  104. struct node *prev_code = NULL;
  105. char *prev_token = NULL, **Argv;
  106. int init_state = HDR;
  107. int verbose = 0;
  108. struct node *root = NULL, *tknptr;
  109. struct succnode *start = NULL;
  110. int n_pairs = 0, n_tokens = 0, n_files = 0, n_total = 0;
  111.  
  112. struct node *insert_token();
  113. char *savetoken();
  114.  
  115. process_token (txt)
  116. char *txt;
  117. {
  118.      struct node *code;
  119.      char *token = savetoken (txt);
  120. /* We have a new token.  Say the previous two tokens were "one" "way"
  121.  * and the current token is "to".  Then prev_code points to a node
  122.  * for ("one", "way") and token is "to".  This function adds ("way", "to") as a
  123.  * successor to ("one","way") and makes prev_code point to ("way","to").
  124.  */
  125.      code = insert_token (prev_token, token);
  126.      insert_pair (prev_code, code);
  127.      prev_code = code;
  128.      prev_token = token;
  129.      return;
  130. }
  131.  
  132. /*
  133.  * here it is, the main function.
  134.  */
  135. main (argc, argv)
  136. int argc;
  137. char  **argv;
  138. {
  139.     int     i, c, n_articles = 10, sflag = 0;
  140.     char *dumpfile = NULL;
  141.     extern int  optind;
  142.     extern char *optarg;
  143.  
  144.     while ((c = getopt (argc, argv, "pxvn:d:s:")) != EOF) {
  145.     switch (c) {
  146.         case 'v':
  147.         verbose = 1;
  148.         break;
  149.         case 'p':        /* Input is plain text, not Usenet stuff */
  150.         init_state = BODY;
  151.         break;
  152.         case 'n':         /* # articles to generate */
  153.         n_articles = atoi (optarg);
  154.         break;
  155.         case 'd':        /* where to dump the data structure */
  156.         dumpfile = optarg;
  157.         break;
  158.         case 's':        /* Set the seed for rand; fall through */
  159.         srand (atoi (optarg));
  160.         case 'x':        /* set flag to prevent srand */
  161.         sflag++;
  162.         break;
  163.         default:
  164.         Fprintf (stderr,
  165.          "Usage: markov3 [-pvx] [-s seed] [-n n_art] [-d dump] files\n");
  166.         exit (1);
  167.     }
  168.     }
  169.     BEGIN init_state;        /* initial state of lexical analyzer */
  170.     if (!sflag)            /* set random number generator */
  171.     srand ((int)time ((time_t *)0));
  172. /* Note: if optind == argc, there are no file arguments.  yyin is left
  173.  * initialized to stdin.
  174.  */
  175.     if (optind < argc) {
  176. /* yyin is lex input stream.  Point to first file. */
  177.     if ((yyin = fopen (argv[optind], "r")) == NULL) {
  178.         perror (argv[optind]);
  179.         exit (1);
  180.     }
  181.     optind++;        /* skip to next file */
  182.     }
  183.     Argv = argv;        /* make it global so yywrap can access it */
  184.     n_files = 1;
  185. /* yylex puts all the input files through the lexical analyzer and builds
  186.  * the database.
  187.  */
  188.     (void) yylex ();
  189.     if (dumpfile)
  190.     dump_database (dumpfile);
  191.     if (verbose)
  192.     Fprintf (stderr,
  193.      "Total of %d tokens (%d different), %d different pairs, %d files\n",
  194.         n_total, n_tokens, n_pairs, n_files);
  195. /* Generate the articles, separated by form feeds */
  196.     for (i = 0; i < n_articles; i++) {
  197.     if (i > 0) output_word ("\n\f\n");
  198.     generate_article ();
  199.     }
  200.     return 0;
  201. }
  202.  
  203. /*
  204.  * Lex calls this when EOF is reached.  It opens the next file if there
  205.  * is one.  Lex interprets a return value of 1 to mean "all done" and 0
  206.  * to mean "keep going".
  207.  */
  208. yywrap () {
  209.     (void) fclose (yyin);
  210.     insert_pair (prev_code, (struct node *)0);
  211.     prev_code = NULL;
  212.     if (Argv[optind] == NULL) return 1;
  213.     else if ((yyin = fopen (Argv[optind], "r")) == NULL) {
  214.     perror (Argv[optind]);
  215.     exit (1);
  216.     }
  217.     optind++;
  218.     in_included_text = 0;
  219.     if (verbose && n_files % 10 == 0)
  220.     Fprintf (stderr, "%d files\n", n_files);
  221.     n_files++;
  222.     BEGIN init_state;
  223.     return 0;
  224. }
  225.  
  226. /*
  227.  * This function saves a token in the hash table (if it isn't there
  228.  * already) and returns a pointer to the stored copy.
  229.  */
  230. char *
  231. savetoken (txt)
  232. char *txt;
  233. {
  234.     int h;
  235.     char *p;
  236.     struct htentry *hp;
  237.  
  238.     n_total++;
  239.     for (p = txt, h = 0; *p; h += *p++);
  240.     hp = hashtab + (h % HSIZE);
  241.     while (hp->hlink) {
  242.     if (strcmp (hp->htext, txt) == 0) {
  243.         return hp->htext;
  244.     }
  245.     hp = hp->hlink;
  246.     }
  247. /* OK, it's a new token.  Make hp->hlink point to a new,
  248.  * null block and make hp->htext point to the text.
  249.  */
  250.     hp->hlink = (struct htentry *) malloc (sizeof *hp);
  251.     hp->htext = malloc ((unsigned)(strlen (txt) + 1));
  252.     (void) strcpy (hp->htext, txt);
  253.     hp->hlink->hlink = NULL;
  254.     hp->hlink->htext = NULL;
  255.     n_tokens++;
  256.     return hp->htext;
  257. }
  258.  
  259. /*
  260.  * This recursive function inserts a token pair into the tree.
  261.  */
  262. struct node *
  263. insert_in_tree (p, txt, txt2)
  264. struct node *p;
  265. char *txt, *txt2;
  266. {
  267.     int cmp;
  268.     if (p == NULL) {
  269. /* Create a new node. */
  270.     p = (struct node *) malloc (sizeof *p);
  271.     p->text = txt;
  272.     p->text2 = txt2;
  273.     p->lc = p->rc = NULL;
  274.     p->succ = NULL;
  275.     p->ocount = 1;
  276.     tknptr = p;
  277.     n_pairs++;
  278.     if (verbose && n_pairs % 1000 == 0)
  279.         Fprintf (stderr, "%d pairs\n", n_pairs);
  280.     return p;
  281.     }
  282.     cmp = my_strcmp (p->text, txt);
  283.     if (cmp == 0) cmp = my_strcmp (p->text2, txt2);
  284.     if (cmp == 0) {
  285. /* It's a match.  Increment the count. */
  286.         tknptr = p;
  287.     p->ocount += 1;
  288.     }
  289. /* Look in the subtrees. */
  290.     else if (cmp < 0) p->lc = insert_in_tree (p->lc, txt, txt2);
  291.     else p->rc = insert_in_tree (p->rc, txt, txt2);
  292.     return p;
  293. }
  294.  
  295. /*
  296.  * This just calls insert_in_tree starting at the root
  297.  */
  298. struct node *
  299. insert_token (txt, txt2)
  300. char *txt,*txt2;
  301. {
  302.     root = insert_in_tree (root, txt, txt2);
  303.     return tknptr;
  304. }
  305.  
  306. /*
  307.  * This function adds a successor.
  308.  */
  309. struct succnode *
  310. insert_in_succ_chain (sp, np)
  311. struct succnode *sp;
  312. struct node *np;
  313. {
  314.     if (sp == NULL) {
  315.     sp = (struct succnode *) malloc (sizeof *sp);
  316.     sp->scnod = np;
  317.     sp->count = 1;
  318.     sp->link = NULL;
  319.     }
  320.     else if (sp->scnod == np)
  321.     sp->count += 1;
  322.     else sp->link = insert_in_succ_chain (sp->link, np);
  323.     return sp;
  324. }
  325.  
  326. /*
  327.  * This calls insert_in_succ_chain starting at the right place.
  328.  */
  329. insert_pair (p1, p2)
  330. struct node *p1, *p2;
  331. {
  332.     if (p1) p1->succ = insert_in_succ_chain (p1->succ, p2);
  333.     else start = insert_in_succ_chain (start, p2);
  334. }
  335.  
  336. /*
  337.  * This function dumps the stored data structure onto a file.
  338.  * Now if only I had a function to read it back in.
  339.  */
  340. char *
  341. pr_token (txt)
  342. char *txt;
  343. {
  344.     if (txt[0] != '\n')
  345.     return txt;
  346.     return txt[1] ? "<INCL>" : "<LF>";
  347. }
  348.  
  349. treedump (tree, fp)
  350. struct node *tree;
  351. FILE *fp;
  352. {
  353.     if (tree) {
  354.     treedump (tree->rc, fp);
  355.     Fprintf (fp, "( %s %s ) %d", pr_token (tree->text),
  356.             pr_token (tree->text2), tree->ocount);
  357.     chaindump (tree->succ, fp);
  358.     treedump (tree->lc, fp);
  359.     }
  360. }
  361.  
  362. /*
  363.  * Subroutine of treedump; it does one row.
  364.  */
  365. chaindump (p, fp)
  366. struct succnode *p;
  367. FILE *fp;
  368. {
  369.     char   *text;
  370.     while (p) {
  371.     if (p->scnod == NULL)
  372.         text = "<EOF>";
  373.     else text = pr_token (p->scnod->text2);
  374.     Fprintf (fp, " %s %d", text, p->count);
  375.     p = p->link;
  376.     }
  377.     putc ('\n', fp);
  378. }
  379.  
  380. /*
  381.  * This routine generates the dump file (-d option)
  382.  */
  383. dump_database (file)
  384. char *file;
  385. {
  386.     FILE *fp = fopen (file, "w");
  387.     if (fp == NULL) {
  388.     Fprintf (stderr, "markov: can't open ");
  389.     perror (file);
  390.     exit (1);
  391.     }
  392.     Fprintf (fp, "START:");
  393.     chaindump (start, fp);
  394.     treedump (root, fp);
  395. }
  396.  
  397. /* roll (n) generates a uniformly distributed rv between 0 and n-1.
  398.  * This code is stolen from "hack" and should be portable.  If you
  399.  * change this, remember that different systems have rand functions
  400.  * with different ranges, and the bottom bits are often no good.
  401.  */
  402. #define roll(n) ((rand() >> 3) % n)
  403.  
  404. /*
  405.  * This function generates an article by traversing the
  406.  * structure we've built.
  407.  */
  408. generate_article () {
  409.     struct succnode *p = start;
  410.     int ncounts = n_files;
  411.     int n, accum;
  412.     char *tp;
  413.  
  414.     while (1) {
  415. /* Roll the dice to find out the next token.  The code below selects the
  416.  * next token, and the new state, with a probability corresponding to the
  417.  * frequency in the input.
  418.  */
  419.     n = roll (ncounts);
  420.     accum = p->count;
  421.     while (accum <= n && p->link) {
  422.         p = p->link;
  423.         accum += p->count;
  424.     }
  425.     if (p->scnod == NULL)
  426.         break;
  427.     tp = p->scnod->text2;
  428. /* Check for "end of story" */
  429.     if (tp == NULL)
  430.         break;
  431.     output_word (tp);
  432.     ncounts = p->scnod->ocount;
  433.     p = p->scnod->succ;
  434.     }
  435.     output_word ("\n");    /* This will flush the buffer as well. */
  436.     return;
  437. }
  438.  
  439. /*
  440.  * This version handles null strings *
  441.  */
  442. my_strcmp (a, b)
  443. register char *a, *b;
  444. {
  445.     if (a == NULL) return b ? -1 : 0;
  446.     if (b == NULL) return 1;
  447.     return strcmp (a, b);
  448. }
  449.  
  450. #define LEN 75
  451. output_word (word)
  452. char *word;
  453. {
  454.     static char line[LEN+1];
  455.     static int room = LEN;
  456.     int l;
  457.  
  458.     if (word == NULL) return;
  459.     l = strlen (word);
  460. /* If word won't fit, or starts with \n, dump the current line */
  461.     if ((l >= room || word[0] == '\n') && line[0]) {
  462.     Printf ("%s\n", line);
  463.     line[0] = 0;
  464.     room = LEN;
  465.     }
  466. /* If word won't fit in the buffer or starts with \n, print it now */
  467.     if (l >= LEN)
  468.     Printf ("%s\n", word);
  469.     else if (word[0] == '\n')
  470.     Printf ("%s", word);
  471. /* Otherwise fill it in */
  472.     else {
  473.     (void)strcat (line, word);
  474.     (void)strcat (line, " ");
  475.     room -= (l + 1);
  476.     }
  477.     return;
  478. }
  479.