source: abnfparser/bap/main.c @ 405

Last change on this file since 405 was 405, checked in by julian.reschke@…, 13 years ago

add custom version of Bill Fenner's ABNF Parser (BAP)

File size: 18.2 KB
Line 
1/*
2 * Bill's ABNF Parser
3 * Copyright 2002-2006 William C. Fenner <fenner@research.att.com>
4 *  All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the names of contributors
15 *    may be used to endorse or promote products derived from this software
16 *    without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY WILLIAM C. FENNER ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
20 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL WILLIAM C. FENNER OR HIS
22 * BROTHER B1FF BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
25 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
26 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
28 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 * DAMAGE.
30 */
31
32#include "config.h"
33#include <stdio.h>
34#include <stdlib.h>
35#include <search.h>
36#include <unistd.h>
37#include <ctype.h>
38#include <string.h>
39#include "common.h"
40
41static const char rcsid[] =
42  "$Id: main.c,v 1.3 2008-05-30 12:33:45 jre Exp $";
43static const char versionstring[] = PACKAGE_VERSION;
44
45static void printobjasxml(object *, int);
46static void printobj_r(object *, int, int);
47static void printobjasxml_r(object *, int, int);
48static void canonify(struct rule *);
49static void canonify_r(struct object **);
50static void parse_from(char *filename);
51static void predefine(fn_list *ifile);
52static int summary(void);
53
54#define MAXRULE         1000    /* XXX */
55
56struct rule *rules = NULL;
57char *input_file; /* of current input file */
58
59char *top_rule_name = "ABNF";
60
61int cflag = 0;          /* include line number comments */
62int c2flag = 0;         /* include comments for printable constants */
63int tflag = 0;          /* print type info */
64int permissive = 1;     /* Be permissive (e.g. accept '|') */
65int qflag = 0;          /* quiet */
66int canon = 1;          /* canonify */
67int asxml = 0;    /* output XML */
68
69int yyparse(void);
70
71void
72usage(void)
73{
74        fprintf(stderr, "Bill's ABNF Parser version %s\n", versionstring);
75        fprintf(stderr, "usage: bap [-cikntq] [ file ]\n");
76        fprintf(stderr, " parse ABNF grammar from file or stdin\n");
77        fprintf(stderr, " -c      : include rule definition line # in comment\n");
78        fprintf(stderr, " -k      : add comments for printable characters specified as %%x\n");
79        fprintf(stderr, " -n      : don't \"canonify\" result\n");
80        fprintf(stderr, " -i file : read predefined rules from \"file\"\n");
81        fprintf(stderr, " -t      : include type info in result\n");
82        fprintf(stderr, " -q      : don't print parsed grammar\n");
83        fprintf(stderr, " -S name : name rule as production start\n");
84        fprintf(stderr, " -x      : output XML\n");
85        exit(1);
86}
87
88int
89main(int argc, char **argv)
90{
91        int ch;
92        int rc = 0;
93        struct rule *r;
94        fn_list *pre_input = NULL;
95 
96#ifdef YYDEBUG
97        extern int yydebug;
98
99        yydebug = 0;
100#endif
101        hcreate(MAXRULE);
102
103        while ((ch = getopt(argc, argv, "cdi:kntqS:x")) != -1) {
104                switch (ch) {
105                case 'c':
106                        cflag++;
107                        break;
108
109                case 'd':
110#ifdef YYDEBUG
111                        yydebug = 1;
112#else
113                        fprintf(stderr, "Rebuild with -DYYDEBUG to use -d.\n");
114#endif
115                        break;
116
117                case 'k':
118                        c2flag++;
119                        break;
120
121                case 'n':
122                        canon = 0;
123                        break;
124
125                case 'i': {
126                        fn_list *ifile = calloc(sizeof(fn_list), 1);
127                        ifile->filename = optarg;
128                        ifile->next = pre_input;
129                        pre_input = ifile;
130                        break;
131                }
132     
133                case 't':
134                        tflag++;
135                        break;
136
137                case 'p':
138                        permissive = 0;
139                        break;
140
141                case 'q':
142                        qflag++;
143                        break;
144
145                case 'S':
146                        top_rule_name = optarg;
147                        break;
148     
149                case 'x':
150                        asxml = 1;
151                        break;
152
153                default:
154                        usage();
155                }
156        }
157        argc -= optind;
158        argv += optind;
159
160        if (argc > 1)
161                usage();
162
163        predefine(pre_input);   
164 
165        /* Parse the grammar, perhaps spouting errors. */
166        parse_from((argc > 0)? argv[0] : NULL);
167
168        /* If we're not quiet, then output the grammar again. */
169        if (!qflag) {
170                if (canon)
171                        canonify(rules);
172    if (!asxml) {
173                for (r = rules; r; r = r->next) {
174                        if (r->predefined) {
175                                /* do not output */
176                        }
177                        else if (r->rule) {
178                                printf("%s = ", r->name);
179                                printobj(r->rule, tflag);
180                                if (cflag)
181                                        printf(" ; line %d", r->line);
182                                printf("\n");
183                        } else {
184                                printf("; %s UNDEFINED\n", r->name);
185                        }
186                        if (r->next == rules)
187                                break;
188                }
189                for (r = rules; r; r = r->next) {
190                        if (r->used == 0
191                                && r->predefined == 0
192                                && r->rule
193                                && strcmp(r->name, top_rule_name))
194                                printf("; %s defined but not used\n", r->name);
195                        if (r->next == rules)
196                                break;
197                }
198    }
199    else {
200      printf("<abnf xmlns='tag:greenbytes.de,2008:abnf'>\n");
201                for (r = rules; r; r = r->next) {
202                        if (r->predefined) {
203                                /* do not output */
204                        }
205                        else if (r->rule) {
206          printf("  <rule name='%s'", r->name);
207                                if (cflag)
208                                        printf(" line='%d'", r->line);
209          printf(">");
210                                printobjasxml(r->rule, 2);
211          printf("\n  </rule>\n");
212                        } else {
213                                printf("  <undefined name='%s'/>\n", r->name);
214                        }
215                        if (r->next == rules)
216                                break;
217                }
218      printf("</abnf>\n");
219    }
220        }
221 
222        rc = summary();
223        hdestroy();
224        exit(rc);
225}
226
227void
228canonify(struct rule *rules)
229{
230        struct rule *r;
231
232        for (r = rules; r; r = r->next) {
233                if (r->rule)
234                        canonify_r(&r->rule);
235                if (r->next == rules)
236                        break;
237        }
238}
239
240/* XXX may need to modify in the future? */
241void
242canonify_r(struct object **op)
243{
244        struct object *o = *op;
245        while (o) {
246                switch (o->type) {
247                case T_ALTERNATION:
248                        canonify_r(&o->u.alternation.left);
249                        canonify_r(&o->u.alternation.right);
250                        break;
251                case T_RULE:
252                        /* nothing to do */
253                        break;
254                case T_GROUP:
255                        canonify_r(&o->u.e.e.group);
256                        break;
257                case T_TERMSTR:
258                        while (o->next && o->next->type == T_TERMSTR &&
259                            o->u.e.repetition.lo == 1 && o->u.e.repetition.hi == 1 &&
260                            o->next->u.e.repetition.lo == 1 && o->next->u.e.repetition.hi == 1 &&
261                            ((o->u.e.e.termstr.flags & F_CASESENSITIVE) ==
262                             (o->next->u.e.e.termstr.flags & F_CASESENSITIVE))) {
263                                int len = strlen(o->u.e.e.termstr.str) + strlen(o->next->u.e.e.termstr.str);
264                                char *p = malloc(len + 1);
265                                strcpy(p, o->u.e.e.termstr.str);
266                                strcat(p, o->next->u.e.e.termstr.str);
267                                free(o->u.e.e.termstr.str);
268                                o->u.e.e.termstr.str = p;
269                                /* XXX leak o->next */
270                                o->next = o->next->next;
271                        }
272                        if (o->u.e.e.termstr.flags & F_CASESENSITIVE) {
273                                int anybad = 0;
274                                char *p;
275                                for (p = o->u.e.e.termstr.str; *p; p++) {
276                                        if (isalpha(*p) || *p == '"' || !isprint(*p)) {
277                                                anybad = 1;
278                                                break;
279                                        }
280                                }
281                                if (anybad == 0)
282                                        o->u.e.e.termstr.flags &= ~F_CASESENSITIVE;
283                        }
284                case T_TERMRANGE:
285                case T_PROSE:
286                default:
287                        /* nothing to do */
288                        break;
289                }
290                o = o->next;
291        }
292}
293
294void
295printrep(struct range *rep)
296{
297        if (rep->lo == 1 && rep->hi == 1)
298                return;
299        if (rep->lo > 0)
300                printf("%d", rep->lo);
301        if (rep->lo == rep->hi) {
302                if (rep->lo == 0)
303                        printf("0");
304                return;
305        }
306        printf("*");
307        if (rep->hi != -1)
308                printf("%d", rep->hi);
309}
310
311void
312printobj(object *o, int tflag)
313{
314        /* T_GROUP means don't put grouping characters
315         * around the top level. */
316        printobj_r(o, T_GROUP, tflag);
317}
318
319void
320printobjasxml(object *o, int indent)
321{
322        /* T_GROUP means don't put grouping characters
323         * around the top level. */
324        printobjasxml_r(o, T_GROUP, indent);
325}
326
327/*
328 * No paren needed around a group that's:
329 * - not concatenation (no next)
330 * - not an ALTERNATION
331 * - got a repeat count of 1
332 */
333#define NOPAREN(o)      ((o->next == NULL) && (o->type != T_ALTERNATION) && (o->u.e.repetition.lo == 1 && o->u.e.repetition.hi == 1))
334
335/*
336 * No brackets needed around a group that
337 * contains a single element that has a
338 * possible repetition of 0.
339 */
340#define NOBRACKET(o)    ((o->next == NULL) && (o->u.e.repetition.lo == 0))
341
342static void
343printobj_r(object *o, int parenttype, int tflag)
344{
345        int iterating = 0;
346
347        /* Put parenthesis around concatenations */
348        if (parenttype != T_GROUP && o->next) {
349                iterating = 1;
350                printf("( ");
351        }
352        while (o) {
353                switch (o->type) {
354                case T_ALTERNATION:
355                        if (tflag)
356                                printf("{ALTERNATION}");
357                        if (o->next)
358                                printf("( ");
359                        printobj_r(o->u.alternation.left, o->type, tflag);
360                        printf(" / ");
361                        printobj_r(o->u.alternation.right, o->type, tflag);
362                        if (o->next)
363                                printf(" )");
364                        break;
365                case T_RULE:
366                        if (tflag)
367                                printf("{RULE}");
368                        if (o->u.e.islist) {
369        if (o->u.e.repetition.lo == 0) {
370          printf("( [ *LWS ");
371                          if (o->u.e.e.rule.rule) {
372                                  printf("%s", o->u.e.e.rule.rule->name);
373                                  o->u.e.e.rule.rule->used = 1;
374                          }
375          else {
376                                  printf("%s", o->u.e.e.rule.name);
377          }
378          printf(" ] *( *LWS \",\" *LWS ");
379                          if (o->u.e.e.rule.rule) {
380                                  printf("%s", o->u.e.e.rule.rule->name);
381                                  o->u.e.e.rule.rule->used = 1;
382                          }
383          else {
384                                  printf("%s", o->u.e.e.rule.name);
385          }
386          printf(" ) )");
387        }
388        else if (o->u.e.repetition.lo == 1) {
389          printf("( *LWS ");
390                          if (o->u.e.e.rule.rule) {
391                                  printf("%s", o->u.e.e.rule.rule->name);
392                                  o->u.e.e.rule.rule->used = 1;
393                          }
394          else {
395                                  printf("%s", o->u.e.e.rule.name);
396          }
397          printf(" *( *LWS \",\" *LWS ");
398                          if (o->u.e.e.rule.rule) {
399                                  printf("%s", o->u.e.e.rule.rule->name);
400                                  o->u.e.e.rule.rule->used = 1;
401                          }
402          else {
403                                  printf("%s", o->u.e.e.rule.name);
404          }
405          printf(" ) )");
406        }
407        else {
408          printf("TODO: something is wrong");
409        }
410      }
411      else {
412        printrep(&o->u.e.repetition);
413                          if (o->u.e.e.rule.rule) {
414                                  printf("%s", o->u.e.e.rule.rule->name);
415                                  o->u.e.e.rule.rule->used = 1;
416                          }
417        else {
418                                  printf("%s", o->u.e.e.rule.name);
419        }
420      }
421                        break;
422                case T_GROUP:
423                        if (tflag)
424                                printf("{GROUP}");
425      if (o->u.e.islist) {
426        if (o->u.e.repetition.lo == 0) {
427          printf("( [ *LWS ");
428          printobj_r(o->u.e.e.group, o->type, tflag);
429          printf(" ] *( *LWS \",\" *LWS ");
430          printobj_r(o->u.e.e.group, o->type, tflag);
431          printf(" ) )");
432        }
433        else if (o->u.e.repetition.lo == 1) {
434          printf("( *LWS ");
435          printobj_r(o->u.e.e.group, o->type, tflag);
436          printf(" *( *LWS \",\" *LWS ");
437          printobj_r(o->u.e.e.group, o->type, tflag);
438          printf(" ) )");
439        }
440        else {
441          printf("TODO: something is wrong");
442        }
443      }
444      else {
445                        if (o->u.e.repetition.lo == 0 &&
446                            o->u.e.repetition.hi == 1) {
447                                if (!NOBRACKET(o->u.e.e.group))
448                                        printf("[ ");
449                        } else {
450                                printrep(&o->u.e.repetition);
451                                if (!NOPAREN(o->u.e.e.group))
452                                        printf("( ");
453                        }
454                        printobj_r(o->u.e.e.group, o->type, tflag);
455                        if (o->u.e.repetition.lo == 0 &&
456                            o->u.e.repetition.hi == 1) {
457                                if (!NOBRACKET(o->u.e.e.group))
458                                        printf(" ]");
459                        } else {
460                                if (!NOPAREN(o->u.e.e.group))
461                                        printf(" )");
462                        }
463      }
464                        break;
465                case T_TERMSTR:
466                        if (tflag)
467                                printf("{TERMSTR}");
468                        printrep(&o->u.e.repetition);
469                        if (o->u.e.e.termstr.flags & F_CASESENSITIVE) {
470                                unsigned char *p = (unsigned char*)o->u.e.e.termstr.str;
471                                char sep;
472                                int allprintable = 1;
473                                printf("%%");
474                                sep = 'x';
475                                while (*p) {
476                                        if (!isgraph(*p)) allprintable = 0;
477                                        printf("%c%02X", sep, *p++);
478                                        sep = '.';
479                                }
480                                if (c2flag && allprintable)
481                                        printf(" ; %s\n", o->u.e.e.termstr.str);
482                        } else {
483                                printf("%c%s%c", '"', o->u.e.e.termstr.str, '"');
484                        }
485                        break;
486                case T_TERMRANGE:
487                        if (tflag)
488                                printf("{TERMRANGE}");
489                        printrep(&o->u.e.repetition);
490                        printf("%%x%02X-%02X",
491                                o->u.e.e.termrange.lo,
492                                o->u.e.e.termrange.hi);
493                        /* XXX isprint does not handle non-ASCII */
494                        if (c2flag &&
495                            isprint(o->u.e.e.termrange.lo) &&
496                            isprint(o->u.e.e.termrange.hi)) {
497                                printf(" ; '%c'-'%c'\n",
498                                        o->u.e.e.termrange.lo,
499                                        o->u.e.e.termrange.hi);
500                        }
501                        break;
502                case T_PROSE:
503                        if (tflag)
504                                printf("{PROSE}");
505                        printrep(&o->u.e.repetition);
506                        printf("<%s>", o->u.e.e.proseval);
507                        break;
508                default:
509                        printf("{UNKNOWN OBJECT TYPE %d}", o->type);
510                        break;
511                }
512                if (o->next)
513                        printf(" ");
514                o = o->next;
515        }
516        if (iterating)
517                printf(" )");
518}
519
520static void
521escaped(char *c) {
522  while (*c) {
523    if (*c == '&') {
524      printf("&amp;");
525    }
526    else if (*c == '<') {
527      printf("&lt;");
528    }
529    else {
530      printf("%c", *c);
531    }
532    c += 1;
533  }
534}
535
536static void
537printobjasxml_r(object *o, int parenttype, int indent)
538{
539        while (o) {
540                switch (o->type) {
541                case T_ALTERNATION:
542      printf("<alternation>\n");
543      printf("<alternative>");
544      printobjasxml_r(o->u.alternation.left, o->type, indent + 2);
545      printf("</alternative>\n");
546      printf("<alternative>");
547                        printobjasxml_r(o->u.alternation.right, o->type, indent + 2);
548      printf("</alternative>\n");
549      printf("</alternation>\n");
550                        break;
551                case T_RULE:
552                        if (o->u.e.islist) {
553        printf("<list min='%d' max='%d'>\n", o->u.e.repetition.lo, o->u.e.repetition.hi);
554                          if (o->u.e.e.rule.rule) {
555                                  printf("<rule ref='%s'/>", o->u.e.e.rule.rule->name);
556                                  o->u.e.e.rule.rule->used = 1;
557                          }
558        else {
559                                  printf("<rule ref='%s'/>", o->u.e.e.rule.name);
560        }
561        printf("</list>\n");
562      }
563      else {
564                          if (o->u.e.e.rule.rule) {
565                                  printf("<rule min='%d' max='%d' ref='%s'/>", o->u.e.repetition.lo, o->u.e.repetition.hi, o->u.e.e.rule.rule->name);
566                                  o->u.e.e.rule.rule->used = 1;
567                          }
568        else {
569                                  printf("<rule min='%d' max='%d' ref='%s'/>", o->u.e.repetition.lo, o->u.e.repetition.hi, o->u.e.e.rule.name);
570        }
571      }
572                        break;
573                case T_GROUP:
574      if (o->u.e.islist) {
575        printf("<list min='%d' max='%d'>\n", o->u.e.repetition.lo, o->u.e.repetition.hi);
576        printobjasxml_r(o->u.e.e.group, o->type, indent + 2);
577        printf("</list>");
578      }
579      else {
580        printf("<group min='%d' max='%d'>\n", o->u.e.repetition.lo, o->u.e.repetition.hi);
581                        printobjasxml_r(o->u.e.e.group, o->type, indent + 2);
582                printf("</group>");
583      }
584                        break;
585                case T_TERMSTR:
586      printf("<term min='%d' max='%d'>", o->u.e.repetition.lo, o->u.e.repetition.hi);
587                        if (o->u.e.e.termstr.flags & F_CASESENSITIVE) {
588                                unsigned char *p = (unsigned char*)o->u.e.e.termstr.str;
589                                char sep;
590                                int allprintable = 1;
591                                printf("%%");
592                                sep = 'x';
593                                while (*p) {
594                                        if (!isgraph(*p)) allprintable = 0;
595                                        printf("%c%02X", sep, *p++);
596                                        sep = '.';
597                                }
598                        } else {
599        printf("\"");
600        escaped(o->u.e.e.termstr.str);
601        printf("\"");
602                }
603      printf("</term>");
604                        break;
605                case T_TERMRANGE:
606      printf("<termrange min='%d' max='%d'>", o->u.e.repetition.lo, o->u.e.repetition.hi);
607                        printf("%%x%02X-%02X",
608                                o->u.e.e.termrange.lo,
609                                o->u.e.e.termrange.hi);
610                        /* XXX isprint does not handle non-ASCII */
611                        if (c2flag &&
612                            isprint(o->u.e.e.termrange.lo) &&
613                            isprint(o->u.e.e.termrange.hi)) {
614                                printf(" ; '%c'-'%c'\n",
615                                        o->u.e.e.termrange.lo,
616                                        o->u.e.e.termrange.hi);
617                        }
618      printf("</termrange>");
619                        break;
620                case T_PROSE:
621      printf("<prose min='%d' max='%d'>", o->u.e.repetition.lo, o->u.e.repetition.hi);
622                        escaped(o->u.e.e.proseval);
623      printf("</prose>");
624                        break;
625                default:
626                        printf("{UNKNOWN OBJECT TYPE %d}", o->type);
627                        break;
628                }
629                if (o->next)
630                        printf(" ");
631                o = o->next;
632        }
633}
634
635struct rule *
636findrule(char *name)
637{
638        char *lowername;
639        char *p, *q;
640        ENTRY *e;
641        ENTRY search;
642        struct rule *r;
643
644        lowername = malloc(strlen(name) + 1);
645        for (p = name, q = lowername; *p; p++, q++)
646                if (isupper(*p))
647                        *q = tolower(*p);
648                else
649                        *q = *p;
650        *q = '\0';
651        search.key = lowername;
652        search.data = NULL;
653        e = hsearch(search, FIND);
654        if (e == NULL) {
655                r = calloc(1, sizeof(struct rule));
656                r->name = name;
657                r->lowername = lowername;
658                search.data = r;
659                e = hsearch(search, ENTER);
660                if (e == NULL) {
661                        fprintf(stderr, "hash table full -- increase MAXRULE\n");
662                        exit(1);
663                }
664                if (rules) {
665                        r->next = rules;
666                        r->prev = rules->prev;
667                        rules->prev->next = r;
668                        rules->prev = r;
669                } else {
670                        rules = r->next = r->prev = r;
671                }
672                return r;
673        } else {
674                free(lowername);
675                return (struct rule *)e->data;
676        }
677}
678
679void
680parse_from(char *filename) {
681        extern FILE *yyin;
682        FILE *fin = NULL;
683 
684        if (filename != NULL) {
685                fin = fopen (filename, "rt");
686                if (!fin) {
687                        fprintf(stderr, "input file not found: %s\n", filename);
688                        exit(1);
689                }
690   
691                input_file = filename;
692                yyin = fin;
693        }
694        else {
695                yyin = stdin;
696                input_file = "stdin";
697        }
698 
699        scanreset();
700        yyparse();
701 
702        if (fin) fclose(fin); 
703}
704
705void
706predefine(fn_list *ifile) {
707        struct rule *r;
708        for (;ifile; ifile = ifile->next) {
709                parse_from(ifile->filename);
710        }
711 
712        for (r = rules; r; r = r->next) {
713                /* struct without rule definitions are created when names are used
714                they are != null when the rule was actually defined */
715                if (r->rule)
716                        r->predefined = 1;
717                else
718                        r->used = 1;
719
720                if (r->next == rules)
721                        break;
722        }
723}
724
725int
726summary(void) {
727        extern int yyerrors;
728        if (yyerrors > 0) {
729                fflush(stdout);
730                fprintf(stderr, "parsing failed: %d errors encountered\n", yyerrors);
731        }
732        return yyerrors;
733}
734
Note: See TracBrowser for help on using the repository browser.