examples/fadot.c

   1 /*
   2  * fadot.c: example usage of finite automata library
   3  *
   4  * Copyright (C) 2009, Francis Giraldeau
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
  19  *
  20  * Author: Francis Giraldeau <francis.giraldeau@usherbrooke.ca>
  21  */
  22
  23 /*
  24  * The purpose of this example is to show the usage of libfa
  25  */
  26
  27 #include <stdio.h>
  28 #include <unistd.h>
  29 #include <ctype.h>
  30 #include <string.h>
  31 #include <stdlib.h>
  32 #include <limits.h>
  33
  34 #include <fa.h>
  35
  36 #define UCHAR_NUM (UCHAR_MAX+1)
  37
  38 const char *progname;
  39
  40 static const char *const escape_chars    = "\"\a\b\t\n\v\f\r\\";
  41 static const char *const escape_names = "\"abtnvfr\\";
  42
  43 __attribute__((noreturn))
  44 static void usage(void) {
  45   fprintf(stderr, "\nUsage: %s [OPTIONS] REGEXP\n", progname);
  46   fprintf(stderr, "\nCompile REGEXP and apply operation to them. By default, just print\n");
  47   fprintf(stderr, "the minimized regexp.\n");
  48   fprintf(stderr, "\nOptions:\n\n");
  49   fprintf(stderr, "  -o OPERATION       one of : show concat union intersect json\n");
  50   fprintf(stderr, "                              complement minus example print\n");
  51   fprintf(stderr, "  -f DOT_FILE        Path of output .dot file\n");
  52   fprintf(stderr, "  -n                 do not minimize resulting finite automaton\n");
  53
  54   exit(EXIT_FAILURE);
  55 }
  56
  57 int main (int argc, char **argv) {
  58
  59   opterr = 0;
  60
  61   int reduce = 1;
  62   char *file_output = NULL;
  63   const char *operation = NULL;
  64   FILE *fd;
  65   int c;
  66   int nb_regexp = 0;
  67
  68   progname = argv[0];
  69
  70   while ((c = getopt (argc, argv, "nhf:o:")) != -1)
  71     switch (c)
  72       {
  73       case 'n':
  74         reduce = 0;
  75         break;
  76       case 'f':
  77         file_output = optarg;
  78         break;
  79       case 'h':
  80         usage();
  81         break;
  82       case 'o':
  83         operation = optarg;
  84         break;
  85       case '?':
  86         if (optopt == 'o' || optopt == 'f')
  87           fprintf (stderr, "Option -%c requires an argument.\n", optopt);
  88         else if (isprint (optopt))
  89           fprintf (stderr, "Unknown option `-%c'.\n", optopt);
  90         else
  91           fprintf (stderr,
  92                    "Unknown option character `\\x%x'.\n",
  93                    optopt);
  94         usage();
  95         break;
  96       default:
  97         usage();
  98         break;
  99       }
 100
 101   //printf ("reduce = %d, file_output = %s, operation = %s\n",
 102   //        reduce, file_output, operation);
 103
 104   if (operation == NULL)
 105     operation = "show";
 106
 107   for (int i = optind; i < argc; i++) {
 108     nb_regexp++;
 109   }
 110
 111   if (nb_regexp == 0) {
 112     printf("Please specify regexp to process.\n");
 113     usage();
 114   }
 115
 116   struct fa* fa_result = NULL;
 117
 118   if (!strcmp(operation,"show")) {
 119     fa_compile(argv[optind], strlen(argv[optind]), &fa_result);
 120   } else if (!strcmp(operation,"concat")) {
 121
 122     if (nb_regexp < 2) {
 123       fprintf(stderr,"Please specify 2 or more regexp to concat");
 124       return 1;
 125     }
 126
 127     fa_result = fa_make_basic(FA_EPSILON);
 128     struct fa* fa_tmp;
 129     for (int i = optind; i < argc; i++) {
 130       fa_compile(argv[i], strlen(argv[i]), &fa_tmp);
 131       fa_result = fa_concat(fa_result, fa_tmp);
 132     }
 133
 134   } else if (!strcmp(operation, "union")) {
 135
 136     if (nb_regexp < 2) {
 137       fprintf(stderr,"Please specify 2 or more regexp to union");
 138       return 1;
 139     }
 140
 141     fa_result = fa_make_basic(FA_EMPTY);
 142
 143     struct fa* fa_tmp;
 144     for (int i = optind; i < argc; i++) {
 145       fa_compile(argv[i], strlen(argv[i]), &fa_tmp);
 146       fa_result = fa_union(fa_result, fa_tmp);
 147     }
 148
 149   } else if (!strcmp(operation, "intersect")) {
 150
 151     if (nb_regexp < 2) {
 152       fprintf(stderr,"Please specify 2 or more regexp to intersect");
 153       return 1;
 154     }
 155
 156     fa_compile(argv[optind], strlen(argv[optind]), &fa_result);
 157     struct fa* fa_tmp;
 158
 159     for (int i = optind+1; i < argc; i++) {
 160       fa_compile(argv[i], strlen(argv[i]), &fa_tmp);
 161       fa_result = fa_intersect(fa_result, fa_tmp);
 162     }
 163
 164   } else if (!strcmp(operation, "complement")) {
 165
 166     if (nb_regexp >= 2) {
 167       fprintf(stderr,"Please specify one regexp to complement");
 168       return 1;
 169     }
 170
 171     fa_compile(argv[optind], strlen(argv[optind]), &fa_result);
 172     fa_result = fa_complement(fa_result);
 173
 174   } else if (!strcmp(operation, "minus")) {
 175
 176     if (nb_regexp != 2) {
 177       fprintf(stderr,"Please specify 2 regexp for operation minus");
 178       return 1;
 179     }
 180
 181     struct fa* fa_tmp1;
 182     struct fa* fa_tmp2;
 183     fa_compile(argv[optind], strlen(argv[optind]), &fa_tmp1);
 184     fa_compile(argv[optind+1], strlen(argv[optind+1]), &fa_tmp2);
 185     fa_result = fa_minus(fa_tmp1, fa_tmp2);
 186
 187   } else if (!strcmp(operation, "example")) {
 188
 189     if (nb_regexp != 1) {
 190       fprintf(stderr,"Please specify one regexp for operation example");
 191       return 1;
 192     }
 193
 194     char* word = NULL;
 195     size_t word_len = 0;
 196     fa_compile(argv[optind], strlen(argv[optind]), &fa_result);
 197     fa_example(fa_result, &word, &word_len);
 198     printf("Example word = %s\n", word);
 199
 200   } else if (!strcmp(operation, "json")) {
 201     if (nb_regexp != 1) {
 202       fprintf(stderr,"Please specify one regexp for operation example");
 203       return 1;
 204     }
 205
 206     fa_compile(argv[optind], strlen(argv[optind]), &fa_result);
 207
 208     if (reduce) {
 209       fa_minimize(fa_result);
 210     }
 211
 212     if (file_output != NULL) {
 213       if ((fd = fopen(file_output, "w")) == NULL) {
 214         fprintf(stderr, "Error while opening file %s \n", file_output);
 215         return 1;
 216       }
 217
 218       fa_json(fd, fa_result);
 219       fclose(fd);
 220     } else {
 221       fa_json(stdout, fa_result);
 222     }
 223
 224     return 0;
 225
 226   } else if (!strcmp(operation, "print")) {
 227     if (nb_regexp != 1) {
 228       fprintf(stderr,"Please specify one regexp for operation example");
 229       return 1;
 230     }
 231
 232     fa_compile(argv[optind], strlen(argv[optind]), &fa_result);
 233
 234     if (reduce) {
 235       fa_minimize(fa_result);
 236     }
 237
 238     struct state *st, *st2;
 239     uint32_t num_trans, i;
 240     unsigned char begin, end;
 241
 242     st = fa_state_initial(fa_result);
 243
 244     printf("%s. Initial state: %p", fa_is_deterministic(fa_result) ? "DFA" : "NFA", fa_result);
 245
 246     while (st != NULL) {
 247       num_trans = fa_state_num_trans(st);
 248       printf("\nFrom state %p (final = %s):\n", st, fa_state_is_accepting(st) == 1 ? "true" : "false");
 249       for (i = 0; i < num_trans; i++) {
 250         if (fa_state_trans(st, i, &st2, &begin, &end) < 0) {
 251           printf("Some error occur. \n");
 252         }
 253         if (begin == end)
 254           printf("     to: %p, label: %d\n", st2, begin);
 255         else
 256           printf("     to: %p, label: %d-%d\n", st2, begin, end);
 257       }
 258       st = fa_state_next(st);
 259     }
 260
 261     return 0;
 262
 263   }
 264
 265   if (reduce) {
 266     fa_minimize(fa_result);
 267   }
 268
 269   if (file_output != NULL) {
 270     if ((fd = fopen(file_output, "w")) == NULL) {
 271       fprintf(stderr, "Error while opening file %s \n", file_output);
 272       return 1;
 273     }
 274
 275     fa_dot(fd, fa_result);
 276     fclose(fd);
 277   } else {
 278     int r;
 279     char *rx;
 280     size_t rx_len;
 281
 282     r = fa_as_regexp(fa_result, &rx, &rx_len);
 283     if (r < 0) {
 284       fprintf(stderr, "Converting FA to regexp failed\n");
 285       return 1;
 286     }
 287
 288     for (size_t i=0; i < rx_len; i++) {
 289       char *p;
 290       if (rx[i] && ((p = strchr(escape_chars, rx[i])) != NULL)) {
 291         printf("\\%c", escape_names[p - escape_chars]);
 292       } else if (! isprint(rx[i])) {
 293         printf("\\%030o", (unsigned char) rx[i]);
 294       } else {
 295         putchar(rx[i]);
 296       }
 297     }
 298     putchar('\n');
 299     free(rx);
 300   }
 301
 302   return 0;
 303 }