chiark - git - mdw - anag/blob - anag.c

   1 /* -*-c-*-
   2  *
   3  * $Id: anag.c,v 1.1 2001/02/04 17:14:42 mdw Exp $
   4  *
   5  * Main driver for anag
   6  *
   7  * (c) 2001 Mark Wooding
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Anag: a simple wordgame helper.
  13  *
  14  * Anag is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * Anag is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with Anag; if not, write to the Free Software Foundation,
  26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  */
  28
  29 /*----- Revision history --------------------------------------------------*
  30  *
  31  * $Log: anag.c,v $
  32  * Revision 1.1  2001/02/04 17:14:42  mdw
  33  * Initial checkin
  34  *
  35  */
  36
  37 /*----- Header files ------------------------------------------------------*/
  38
  39 #include "anag.h"
  40
  41 /*----- Static variables --------------------------------------------------*/
  42
  43 static const char *file = DICTIONARY;
  44
  45 /*----- Help text functions -----------------------------------------------*/
  46
  47 static void usage(FILE *fp)
  48 {
  49   pquis(fp, "Usage: $ [-f file] expression\n");
  50 }
  51
  52 static void version(FILE *fp)
  53 {
  54   pquis(fp, "$, version " VERSION "\n");
  55 }
  56
  57 static void help(FILE *fp)
  58 {
  59   version(fp);
  60   fputc('\n', fp);
  61   usage(fp);
  62   fputs("\n\
  63 Searches a wordlist, printing all of the words which match an expression.\n\
  64 The basic tests in the expression are:\n\
  65 \n\
  66 -anagram WORD           matches a full-length anagram\n\
  67 -subgram WORD           matches words which only use letters in WORD\n\
  68 -wildcard PATTERN       matches with wildcards `*' and `?'\n\
  69 -trackword WORD         matches words which can be found in a trackword\n\
  70 \n\
  71 These simple tests can be combined using the operators `-a', `-o' and `-n'\n\
  72 (for `and', `or' and `not'; they may also be written `&', `|' and `!' if\n\
  73 you like), and grouped using parentheses `(' and `)'.\n\
  74 ", fp);
  75 }
  76
  77 /*----- The options parser ------------------------------------------------*/
  78
  79 /* --- Options table structure --- */
  80
  81 struct opt {
  82   const char *name;
  83   unsigned nargs;
  84   unsigned f;
  85   unsigned tag;
  86 };
  87
  88 enum {
  89   O_HELP, O_VERSION, O_USAGE,
  90   O_FILE,
  91   O_AND, O_OR, O_NOT, O_LPAREN, O_RPAREN,
  92   O_ANAG, O_SUBG, O_WILD, O_TRACK,
  93   O_EOF
  94 };
  95
  96 #define OF_SHORT 1u
  97
  98 static const struct opt opttab[] = {
  99
 100   /* --- Options -- don't form part of the language --- */
 101
 102   { "help",             0,      OF_SHORT,       O_HELP },
 103   { "version",          0,      OF_SHORT,       O_VERSION },
 104   { "usage",            0,      OF_SHORT,       O_USAGE },
 105   { "file",             1,      OF_SHORT,       O_FILE },
 106
 107   /* --- Operators -- provide the basic structure of the language --- *
 108    *
 109    * These are also given magical names by the parser.
 110    */
 111
 112   { "and",              0,      OF_SHORT,       O_AND },
 113   { "or",               0,      OF_SHORT,       O_OR },
 114   { "not",              0,      OF_SHORT,       O_NOT },
 115
 116   /* --- Actual matching oeprations -- do something useful --- */
 117
 118   { "anagram",          1,      0,              O_ANAG },
 119   { "subgram",          1,      0,              O_SUBG },
 120   { "wildcard",         1,      0,              O_WILD },
 121   { "trackword",        1,      0,              O_TRACK },
 122
 123   /* --- End marker --- */
 124
 125   { 0,                  0,      0,              0 }
 126 };
 127
 128 static int ac;
 129 static const char *const *av;
 130 static int ai;
 131
 132 /* --- @nextopt@ --- *
 133  *
 134  * Arguments:   @const char ***arg@ = where to store the arg pointer
 135  *
 136  * Returns:     The tag of the next option.
 137  *
 138  * Use:         Scans the next option off the command line.  If the option
 139  *              doesn't form part of the language, it's processed internally,
 140  *              and you'll never see it from here.  On exit, the @arg@
 141  *              pointer is set to contain the address of the option scanned,
 142  *              followed by its arguments if any.  You're expected to know
 143  *              how many arguments there are for your option.
 144  */
 145
 146 static unsigned nextopt(const char *const **arg)
 147 {
 148   for (;;) {
 149     const struct opt *o, *oo;
 150     size_t sz;
 151     const char *p;
 152
 153     /* --- Pick the next option off the front --- */
 154
 155     *arg = av + ai;
 156     if (ai >= ac)
 157       return (O_EOF);
 158     p = av[ai++];
 159
 160     /* --- Cope with various forms of magic --- */
 161
 162     if (p[0] != '-') {
 163       if (!p[1]) switch (*p) {
 164         case '&': return (O_AND);
 165         case '|': return (O_OR);
 166         case '!': return (O_NOT);
 167         case '(': return (O_LPAREN);
 168         case ')': return (O_RPAREN);
 169       }
 170       goto bad;
 171     }
 172
 173     /* --- Now cope with other sorts of weirdies --- *
 174      *
 175      * By the end of this, a leading `-' or `--' will have been stripped.
 176      */
 177
 178     p++;
 179     if (!*p)
 180       goto bad;
 181     if (*p == '-')
 182       p++;
 183     if (!*p) {
 184       if (ai < ac)
 185         die("syntax error near `--': rubbish at end of line");
 186       return (O_EOF);
 187     }
 188
 189     /* --- Now look the word up in my table --- */
 190
 191     sz = strlen(p);
 192     oo = 0;
 193     for (o = opttab; o->name; o++) {
 194       if (strncmp(p, o->name, sz) == 0) {
 195         if (strlen(o->name) == sz || ((o->f & OF_SHORT) && sz == 1)) {
 196           oo = o;
 197           break;
 198         }
 199         if (oo) {
 200           die("ambiguous option name `-%s' (could match `-%s' or `-%s')",
 201               p, oo->name, o->name);
 202         }
 203         oo = o;
 204       }
 205     }
 206     if (!oo)
 207       die("unrecognized option name `-%s'", p);
 208
 209     /* --- Sort out the arguments --- */
 210
 211     if (ai + oo->nargs > ac)
 212       die("too few arguments for `-%s' (need %u)", oo->name, oo->nargs);
 213     ai += oo->nargs;
 214
 215     /* --- Now process the option --- */
 216
 217     switch (oo->tag) {
 218       case O_HELP:
 219         help(stdout);
 220         exit(0);
 221       case O_VERSION:
 222         version(stdout);
 223         exit(0);
 224       case O_USAGE:
 225         usage(stdout);
 226         exit(0);
 227       case O_FILE:
 228         file = (*arg)[1];
 229         break;
 230       default:
 231         return (oo->tag);
 232     }
 233   bad:
 234     die("syntax error near `%s': unknown token type", av[ai - 1]);
 235   }
 236 }
 237
 238 /*----- Node types for operators ------------------------------------------*/
 239
 240 /* --- Node structures --- */
 241
 242 typedef struct node_bin {
 243   node n;
 244   node *left;
 245   node *right;
 246 } node_bin;
 247
 248 typedef struct node_un {
 249   node n;
 250   node *arg;
 251 } node_un;
 252
 253 /* --- Node functions --- */
 254
 255 static int n_or(node *nn, const char *p, size_t sz)
 256 {
 257   node_bin *n = (node_bin *)nn;
 258   return (n->left->func(n->left, p, sz) || n->right->func(n->right, p, sz));
 259 }
 260
 261 static int n_and(node *nn, const char *p, size_t sz)
 262 {
 263   node_bin *n = (node_bin *)nn;
 264   return (n->left->func(n->left, p, sz) && n->right->func(n->right, p, sz));
 265 }
 266
 267 static int n_not(node *nn, const char *p, size_t sz)
 268 {
 269   node_un *n = (node_un *)nn;
 270   return (!n->arg->func(n->arg, p, sz));
 271 }
 272
 273 /*----- Parser for the expression syntax ----------------------------------*/
 274
 275 /* --- A parser context --- */
 276
 277 typedef struct p_ctx {
 278   unsigned t;
 279   const char *const *a;
 280 } p_ctx;
 281
 282 /* --- Parser structure --- *
 283  *
 284  * This is a simple recursive descent parser.  The context retains
 285  * information about the current token.  Each function is passed the address
 286  * of a node pointer to fill in.  This simplifies the binary operator code
 287  * somewhat, relative to returning pointers to node trees.
 288  */
 289
 290 static void p_expr(p_ctx *p, node **/*nn*/);
 291
 292 static void p_next(p_ctx *p)
 293 {
 294   static const char *const eof[] = { "<end>", 0 };
 295   p->t = nextopt(&p->a);
 296   if (p->t == O_EOF)
 297     p->a = eof;
 298 }
 299
 300 static void p_factor(p_ctx *p, node **nn)
 301 {
 302   node_un *n;
 303   if (p->t == O_LPAREN) {
 304     p_next(p);
 305     p_expr(p, nn);
 306     if (p->t != O_RPAREN)
 307       die("syntax error near `%s': missing `('", *p->a);
 308     p_next(p);
 309   } else if (p->t == O_NOT) {
 310     n = xmalloc(sizeof(node_un));
 311     n->n.func = n_not;
 312     *nn = &n->n;
 313     p_next(p);
 314     p_factor(p, &n->arg);
 315   } else {
 316     switch (p->t) {
 317       case O_ANAG: *nn = anagram(p->a + 1); break;
 318       case O_SUBG: *nn = subgram(p->a + 1); break;
 319       case O_WILD: *nn = wildcard(p->a + 1); break;
 320       case O_TRACK: *nn = trackword(p->a + 1); break;
 321       default: die("syntax error near `%s': unexpected token", *p->a);
 322     }
 323     p_next(p);
 324   }
 325 }
 326
 327 static void p_term(p_ctx *p, node **nn)
 328 {
 329   node_bin *n;
 330   for (;;) {
 331     p_factor(p, nn);
 332     switch (p->t) {
 333       case O_AND:
 334         p_next(p);
 335       default:
 336         break;
 337       case O_LPAREN:
 338       case O_RPAREN:
 339       case O_OR:
 340       case O_EOF:
 341         return;
 342     }
 343     n = xmalloc(sizeof(node_bin));
 344     n->left = *nn;
 345     n->n.func = n_and;
 346     *nn = &n->n;
 347     nn = &n->right;
 348   }
 349 }
 350
 351 static void p_expr(p_ctx *p, node **nn)
 352 {
 353   node_bin *n;
 354   for (;;) {
 355     p_term(p, nn);
 356     if (p->t != O_OR)
 357       break;
 358     p_next(p);
 359     n = xmalloc(sizeof(node_bin));
 360     n->left = *nn;
 361     n->n.func = n_or;
 362     *nn = &n->n;
 363     nn = &n->right;
 364   }
 365 }
 366
 367 /* --- @p_argv@ --- *
 368  *
 369  * Arguments:   @int argc@ = number of command-line arguments
 370  *              @const char *const argv[]@ = vectoor of arguments
 371  *
 372  * Returns:     A compiled node, parsed from the arguments.
 373  *
 374  * Use:         Does the donkey-work of parsing a command-line.
 375  */
 376
 377 static node *p_argv(int argc, const char *const argv[])
 378 {
 379   p_ctx p;
 380   node *n;
 381
 382   av = argv;
 383   ac = argc;
 384   ai = 1;
 385   p_next(&p);
 386   p_expr(&p, &n);
 387   if (p.t != O_EOF) {
 388     die("syntax error near `%s': rubbish at end of line (too many `)'s?)",
 389         *p.a);
 390   }
 391   return (n);
 392 }
 393
 394 /*----- Main code ---------------------------------------------------------*/
 395
 396 /* --- @main@ --- *
 397  *
 398  * Arguments:   @int argc@ = number of command-line arguments
 399  *              @char *argv[]@ = vector of argument words
 400  *
 401  * Returns:     Zero on success, nonzero on failure.
 402  *
 403  * Use:         Picks entries from a word list which match particular
 404  *              expressions.  This might be of assistance to word-game types.
 405  */
 406
 407 int main(int argc, char *argv[])
 408 {
 409   node *n;
 410   FILE *fp;
 411   dstr d = DSTR_INIT;
 412   char *p, *q, *l;
 413
 414   ego(argv[0]);
 415   n = p_argv(argc, (const char *const *)argv);
 416
 417   if ((fp = fopen(file, "r")) == 0)
 418     die("error opening `%s': %s", file, strerror(errno));
 419   for (;;) {
 420     dstr_reset(&d);
 421     if (dstr_putline(&d, fp) < 0)
 422       break;
 423     l = d.buf + d.len;
 424     for (p = q = d.buf; p < l; p++) {
 425       if (!isalnum((unsigned char)*p))
 426         continue;
 427       *q++ = tolower((unsigned char)*p);
 428     }
 429     *q = 0;
 430     d.len = q - d.buf;
 431     if (n->func(n, d.buf, d.len)) {
 432       fwrite(d.buf, 1, d.len, stdout);
 433       fputc('\n', stdout);
 434     }
 435   }
 436   if (!feof(fp))
 437     die("error reading `%s': %s", file, strerror(errno));
 438   fclose(fp);
 439   return (0);
 440 }
 441
 442 /*----- That's all, folks -------------------------------------------------*/