Parser/parser.c

   1 /***********************************************************
   2 Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
   3 Amsterdam, The Netherlands.
   4
   5                         All Rights Reserved
   6
   7 Permission to use, copy, modify, and distribute this software and its
   8 documentation for any purpose and without fee is hereby granted,
   9 provided that the above copyright notice appear in all copies and that
  10 both that copyright notice and this permission notice appear in
  11 supporting documentation, and that the names of Stichting Mathematisch
  12 Centrum or CWI not be used in advertising or publicity pertaining to
  13 distribution of the software without specific, written prior permission.
  14
  15 STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
  16 THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17 FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
  18 FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  19 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  20 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  21 OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22
  23 ******************************************************************/
  24
  25 /* Parser implementation */
  26
  27 /* For a description, see the comments at end of this file */
  28
  29 /* XXX To do: error recovery */
  30
  31 #include "pgenheaders.h"
  32 #include "assert.h"
  33 #include "token.h"
  34 #include "grammar.h"
  35 #include "node.h"
  36 #include "parser.h"
  37 #include "errcode.h"
  38
  39
  40 #ifdef DEBUG
  41 extern int debugging;
  42 #define D(x) if (!debugging); else x
  43 #else
  44 #define D(x)
  45 #endif
  46
  47
  48 /* STACK DATA TYPE */
  49
  50 static void s_reset PROTO((stack *));
  51
  52 static void
  53 s_reset(s)
  54         stack *s;
  55 {
  56         s->s_top = &s->s_base[MAXSTACK];
  57 }
  58
  59 #define s_empty(s) ((s)->s_top == &(s)->s_base[MAXSTACK])
  60
  61 static int s_push PROTO((stack *, dfa *, node *));
  62
  63 static int
  64 s_push(s, d, parent)
  65         register stack *s;
  66         dfa *d;
  67         node *parent;
  68 {
  69         register stackentry *top;
  70         if (s->s_top == s->s_base) {
  71                 fprintf(stderr, "s_push: parser stack overflow\n");
  72                 return -1;
  73         }
  74         top = --s->s_top;
  75         top->s_dfa = d;
  76         top->s_parent = parent;
  77         top->s_state = 0;
  78         return 0;
  79 }
  80
  81 #ifdef DEBUG
  82
  83 static void s_pop PROTO((stack *));
  84
  85 static void
  86 s_pop(s)
  87         register stack *s;
  88 {
  89         if (s_empty(s)) {
  90                 fprintf(stderr, "s_pop: parser stack underflow -- FATAL\n");
  91                 abort();
  92         }
  93         s->s_top++;
  94 }
  95
  96 #else /* !DEBUG */
  97
  98 #define s_pop(s) (s)->s_top++
  99
 100 #endif
 101
 102
 103 /* PARSER CREATION */
 104
 105 parser_state *
 106 newparser(g, start)
 107         grammar *g;
 108         int start;
 109 {
 110         parser_state *ps;
 111
 112         if (!g->g_accel)
 113                 addaccelerators(g);
 114         ps = NEW(parser_state, 1);
 115         if (ps == NULL)
 116                 return NULL;
 117         ps->p_grammar = g;
 118         ps->p_tree = newtree(start);
 119         if (ps->p_tree == NULL) {
 120                 DEL(ps);
 121                 return NULL;
 122         }
 123         s_reset(&ps->p_stack);
 124         (void) s_push(&ps->p_stack, finddfa(g, start), ps->p_tree);
 125         return ps;
 126 }
 127
 128 void
 129 delparser(ps)
 130         parser_state *ps;
 131 {
 132         /* NB If you want to save the parse tree,
 133            you must set p_tree to NULL before calling delparser! */
 134         freetree(ps->p_tree);
 135         DEL(ps);
 136 }
 137
 138
 139 /* PARSER STACK OPERATIONS */
 140
 141 static int shift PROTO((stack *, int, char *, int, int));
 142
 143 static int
 144 shift(s, type, str, newstate, lineno)
 145         register stack *s;
 146         int type;
 147         char *str;
 148         int newstate;
 149         int lineno;
 150 {
 151         assert(!s_empty(s));
 152         if (addchild(s->s_top->s_parent, type, str, lineno) == NULL) {
 153                 fprintf(stderr, "shift: no mem in addchild\n");
 154                 return -1;
 155         }
 156         s->s_top->s_state = newstate;
 157         return 0;
 158 }
 159
 160 static int push PROTO((stack *, int, dfa *, int, int));
 161
 162 static int
 163 push(s, type, d, newstate, lineno)
 164         register stack *s;
 165         int type;
 166         dfa *d;
 167         int newstate;
 168         int lineno;
 169 {
 170         register node *n;
 171         n = s->s_top->s_parent;
 172         assert(!s_empty(s));
 173         if (addchild(n, type, (char *)NULL, lineno) == NULL) {
 174                 fprintf(stderr, "push: no mem in addchild\n");
 175                 return -1;
 176         }
 177         s->s_top->s_state = newstate;
 178         return s_push(s, d, CHILD(n, NCH(n)-1));
 179 }
 180
 181
 182 /* PARSER PROPER */
 183
 184 static int classify PROTO((grammar *, int, char *));
 185
 186 static int
 187 classify(g, type, str)
 188         grammar *g;
 189         register int type;
 190         char *str;
 191 {
 192         register int n = g->g_ll.ll_nlabels;
 193
 194         if (type == NAME) {
 195                 register char *s = str;
 196                 register label *l = g->g_ll.ll_label;
 197                 register int i;
 198                 for (i = n; i > 0; i--, l++) {
 199                         if (l->lb_type == NAME && l->lb_str != NULL &&
 200                                         l->lb_str[0] == s[0] &&
 201                                         strcmp(l->lb_str, s) == 0) {
 202                                 D(printf("It's a keyword\n"));
 203                                 return n - i;
 204                         }
 205                 }
 206         }
 207
 208         {
 209                 register label *l = g->g_ll.ll_label;
 210                 register int i;
 211                 for (i = n; i > 0; i--, l++) {
 212                         if (l->lb_type == type && l->lb_str == NULL) {
 213                                 D(printf("It's a token we know\n"));
 214                                 return n - i;
 215                         }
 216                 }
 217         }
 218
 219         D(printf("Illegal token\n"));
 220         return -1;
 221 }
 222
 223 int
 224 addtoken(ps, type, str, lineno)
 225         register parser_state *ps;
 226         register int type;
 227         char *str;
 228         int lineno;
 229 {
 230         register int ilabel;
 231
 232         D(printf("Token %s/'%s' ... ", tok_name[type], str));
 233
 234         /* Find out which label this token is */
 235         ilabel = classify(ps->p_grammar, type, str);
 236         if (ilabel < 0)
 237                 return E_SYNTAX;
 238
 239         /* Loop until the token is shifted or an error occurred */
 240         for (;;) {
 241                 /* Fetch the current dfa and state */
 242                 register dfa *d = ps->p_stack.s_top->s_dfa;
 243                 register state *s = &d->d_state[ps->p_stack.s_top->s_state];
 244
 245                 D(printf(" DFA '%s', state %d:",
 246                         d->d_name, ps->p_stack.s_top->s_state));
 247
 248                 /* Check accelerator */
 249                 if (s->s_lower <= ilabel && ilabel < s->s_upper) {
 250                         register int x = s->s_accel[ilabel - s->s_lower];
 251                         if (x != -1) {
 252                                 if (x & (1<<7)) {
 253                                         /* Push non-terminal */
 254                                         int nt = (x >> 8) + NT_OFFSET;
 255                                         int arrow = x & ((1<<7)-1);
 256                                         dfa *d1 = finddfa(ps->p_grammar, nt);
 257                                         if (push(&ps->p_stack, nt, d1,
 258                                                 arrow, lineno) < 0) {
 259                                                 D(printf(" MemError: push.\n"));
 260                                                 return E_NOMEM;
 261                                         }
 262                                         D(printf(" Push ...\n"));
 263                                         continue;
 264                                 }
 265
 266                                 /* Shift the token */
 267                                 if (shift(&ps->p_stack, type, str,
 268                                                 x, lineno) < 0) {
 269                                         D(printf(" MemError: shift.\n"));
 270                                         return E_NOMEM;
 271                                 }
 272                                 D(printf(" Shift.\n"));
 273                                 /* Pop while we are in an accept-only state */
 274                                 while (s = &d->d_state
 275                                                 [ps->p_stack.s_top->s_state],
 276                                         s->s_accept && s->s_narcs == 1) {
 277                                         D(printf("  Direct pop.\n"));
 278                                         s_pop(&ps->p_stack);
 279                                         if (s_empty(&ps->p_stack)) {
 280                                                 D(printf("  ACCEPT.\n"));
 281                                                 return E_DONE;
 282                                         }
 283                                         d = ps->p_stack.s_top->s_dfa;
 284                                 }
 285                                 return E_OK;
 286                         }
 287                 }
 288
 289                 if (s->s_accept) {
 290                         /* Pop this dfa and try again */
 291                         s_pop(&ps->p_stack);
 292                         D(printf(" Pop ...\n"));
 293                         if (s_empty(&ps->p_stack)) {
 294                                 D(printf(" Error: bottom of stack.\n"));
 295                                 return E_SYNTAX;
 296                         }
 297                         continue;
 298                 }
 299
 300                 /* Stuck, report syntax error */
 301                 D(printf(" Error.\n"));
 302                 return E_SYNTAX;
 303         }
 304 }
 305
 306
 307 #ifdef DEBUG
 308
 309 /* DEBUG OUTPUT */
 310
 311 void
 312 dumptree(g, n)
 313         grammar *g;
 314         node *n;
 315 {
 316         int i;
 317
 318         if (n == NULL)
 319                 printf("NIL");
 320         else {
 321                 label l;
 322                 l.lb_type = TYPE(n);
 323                 l.lb_str = STR(n);
 324                 printf("%s", labelrepr(&l));
 325                 if (ISNONTERMINAL(TYPE(n))) {
 326                         printf("(");
 327                         for (i = 0; i < NCH(n); i++) {
 328                                 if (i > 0)
 329                                         printf(",");
 330                                 dumptree(g, CHILD(n, i));
 331                         }
 332                         printf(")");
 333                 }
 334         }
 335 }
 336
 337 void
 338 showtree(g, n)
 339         grammar *g;
 340         node *n;
 341 {
 342         int i;
 343
 344         if (n == NULL)
 345                 return;
 346         if (ISNONTERMINAL(TYPE(n))) {
 347                 for (i = 0; i < NCH(n); i++)
 348                         showtree(g, CHILD(n, i));
 349         }
 350         else if (ISTERMINAL(TYPE(n))) {
 351                 printf("%s", tok_name[TYPE(n)]);
 352                 if (TYPE(n) == NUMBER || TYPE(n) == NAME)
 353                         printf("(%s)", STR(n));
 354                 printf(" ");
 355         }
 356         else
 357                 printf("? ");
 358 }
 359
 360 void
 361 printtree(ps)
 362         parser_state *ps;
 363 {
 364         if (debugging) {
 365                 printf("Parse tree:\n");
 366                 dumptree(ps->p_grammar, ps->p_tree);
 367                 printf("\n");
 368                 printf("Tokens:\n");
 369                 showtree(ps->p_grammar, ps->p_tree);
 370                 printf("\n");
 371         }
 372         printf("Listing:\n");
 373         listtree(ps->p_tree);
 374         printf("\n");
 375 }
 376
 377 #endif /* DEBUG */
 378
 379 /*
 380
 381 Description
 382 -----------
 383
 384 The parser's interface is different than usual: the function addtoken()
 385 must be called for each token in the input.  This makes it possible to
 386 turn it into an incremental parsing system later.  The parsing system
 387 constructs a parse tree as it goes.
 388
 389 A parsing rule is represented as a Deterministic Finite-state Automaton
 390 (DFA).  A node in a DFA represents a state of the parser; an arc represents
 391 a transition.  Transitions are either labeled with terminal symbols or
 392 with non-terminals.  When the parser decides to follow an arc labeled
 393 with a non-terminal, it is invoked recursively with the DFA representing
 394 the parsing rule for that as its initial state; when that DFA accepts,
 395 the parser that invoked it continues.  The parse tree constructed by the
 396 recursively called parser is inserted as a child in the current parse tree.
 397
 398 The DFA's can be constructed automatically from a more conventional
 399 language description.  An extended LL(1) grammar (ELL(1)) is suitable.
 400 Certain restrictions make the parser's life easier: rules that can produce
 401 the empty string should be outlawed (there are other ways to put loops
 402 or optional parts in the language).  To avoid the need to construct
 403 FIRST sets, we can require that all but the last alternative of a rule
 404 (really: arc going out of a DFA's state) must begin with a terminal
 405 symbol.
 406
 407 As an example, consider this grammar:
 408
 409 expr:   term (OP term)*
 410 term:   CONSTANT | '(' expr ')'
 411
 412 The DFA corresponding to the rule for expr is:
 413
 414 ------->.---term-->.------->
 415         ^          |
 416         |          |
 417         \----OP----/
 418
 419 The parse tree generated for the input a+b is:
 420
 421 (expr: (term: (NAME: a)), (OP: +), (term: (NAME: b)))
 422
 423 */