Parser/parser.c

   1 /***********************************************************
   2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
   3 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                 fatal("s_pop: parser stack underflow -- FATAL");
  91         s->s_top++;
  92 }
  93
  94 #else /* !DEBUG */
  95
  96 #define s_pop(s) (s)->s_top++
  97
  98 #endif
  99
 100
 101 /* PARSER CREATION */
 102
 103 parser_state *
 104 newparser(g, start)
 105         grammar *g;
 106         int start;
 107 {
 108         parser_state *ps;
 109
 110         if (!g->g_accel)
 111                 addaccelerators(g);
 112         ps = NEW(parser_state, 1);
 113         if (ps == NULL)
 114                 return NULL;
 115         ps->p_grammar = g;
 116         ps->p_tree = newtree(start);
 117         if (ps->p_tree == NULL) {
 118                 DEL(ps);
 119                 return NULL;
 120         }
 121         s_reset(&ps->p_stack);
 122         (void) s_push(&ps->p_stack, finddfa(g, start), ps->p_tree);
 123         return ps;
 124 }
 125
 126 void
 127 delparser(ps)
 128         parser_state *ps;
 129 {
 130         /* NB If you want to save the parse tree,
 131            you must set p_tree to NULL before calling delparser! */
 132         freetree(ps->p_tree);
 133         DEL(ps);
 134 }
 135
 136
 137 /* PARSER STACK OPERATIONS */
 138
 139 static int shift PROTO((stack *, int, char *, int, int));
 140
 141 static int
 142 shift(s, type, str, newstate, lineno)
 143         register stack *s;
 144         int type;
 145         char *str;
 146         int newstate;
 147         int lineno;
 148 {
 149         assert(!s_empty(s));
 150         if (addchild(s->s_top->s_parent, type, str, lineno) == NULL) {
 151                 fprintf(stderr, "shift: no mem in addchild\n");
 152                 return -1;
 153         }
 154         s->s_top->s_state = newstate;
 155         return 0;
 156 }
 157
 158 static int push PROTO((stack *, int, dfa *, int, int));
 159
 160 static int
 161 push(s, type, d, newstate, lineno)
 162         register stack *s;
 163         int type;
 164         dfa *d;
 165         int newstate;
 166         int lineno;
 167 {
 168         register node *n;
 169         n = s->s_top->s_parent;
 170         assert(!s_empty(s));
 171         if (addchild(n, type, (char *)NULL, lineno) == NULL) {
 172                 fprintf(stderr, "push: no mem in addchild\n");
 173                 return -1;
 174         }
 175         s->s_top->s_state = newstate;
 176         return s_push(s, d, CHILD(n, NCH(n)-1));
 177 }
 178
 179
 180 /* PARSER PROPER */
 181
 182 static int classify PROTO((grammar *, int, char *));
 183
 184 static int
 185 classify(g, type, str)
 186         grammar *g;
 187         register int type;
 188         char *str;
 189 {
 190         register int n = g->g_ll.ll_nlabels;
 191
 192         if (type == NAME) {
 193                 register char *s = str;
 194                 register label *l = g->g_ll.ll_label;
 195                 register int i;
 196                 for (i = n; i > 0; i--, l++) {
 197                         if (l->lb_type == NAME && l->lb_str != NULL &&
 198                                         l->lb_str[0] == s[0] &&
 199                                         strcmp(l->lb_str, s) == 0) {
 200                                 D(printf("It's a keyword\n"));
 201                                 return n - i;
 202                         }
 203                 }
 204         }
 205
 206         {
 207                 register label *l = g->g_ll.ll_label;
 208                 register int i;
 209                 for (i = n; i > 0; i--, l++) {
 210                         if (l->lb_type == type && l->lb_str == NULL) {
 211                                 D(printf("It's a token we know\n"));
 212                                 return n - i;
 213                         }
 214                 }
 215         }
 216
 217         D(printf("Illegal token\n"));
 218         return -1;
 219 }
 220
 221 int
 222 addtoken(ps, type, str, lineno)
 223         register parser_state *ps;
 224         register int type;
 225         char *str;
 226         int lineno;
 227 {
 228         register int ilabel;
 229
 230         D(printf("Token %s/'%s' ... ", tok_name[type], str));
 231
 232         /* Find out which label this token is */
 233         ilabel = classify(ps->p_grammar, type, str);
 234         if (ilabel < 0)
 235                 return E_SYNTAX;
 236
 237         /* Loop until the token is shifted or an error occurred */
 238         for (;;) {
 239                 /* Fetch the current dfa and state */
 240                 register dfa *d = ps->p_stack.s_top->s_dfa;
 241                 register state *s = &d->d_state[ps->p_stack.s_top->s_state];
 242
 243                 D(printf(" DFA '%s', state %d:",
 244                         d->d_name, ps->p_stack.s_top->s_state));
 245
 246                 /* Check accelerator */
 247                 if (s->s_lower <= ilabel && ilabel < s->s_upper) {
 248                         register int x = s->s_accel[ilabel - s->s_lower];
 249                         if (x != -1) {
 250                                 if (x & (1<<7)) {
 251                                         /* Push non-terminal */
 252                                         int nt = (x >> 8) + NT_OFFSET;
 253                                         int arrow = x & ((1<<7)-1);
 254                                         dfa *d1 = finddfa(ps->p_grammar, nt);
 255                                         if (push(&ps->p_stack, nt, d1,
 256                                                 arrow, lineno) < 0) {
 257                                                 D(printf(" MemError: push.\n"));
 258                                                 return E_NOMEM;
 259                                         }
 260                                         D(printf(" Push ...\n"));
 261                                         continue;
 262                                 }
 263
 264                                 /* Shift the token */
 265                                 if (shift(&ps->p_stack, type, str,
 266                                                 x, lineno) < 0) {
 267                                         D(printf(" MemError: shift.\n"));
 268                                         return E_NOMEM;
 269                                 }
 270                                 D(printf(" Shift.\n"));
 271                                 /* Pop while we are in an accept-only state */
 272                                 while (s = &d->d_state
 273                                                 [ps->p_stack.s_top->s_state],
 274                                         s->s_accept && s->s_narcs == 1) {
 275                                         D(printf("  Direct pop.\n"));
 276                                         s_pop(&ps->p_stack);
 277                                         if (s_empty(&ps->p_stack)) {
 278                                                 D(printf("  ACCEPT.\n"));
 279                                                 return E_DONE;
 280                                         }
 281                                         d = ps->p_stack.s_top->s_dfa;
 282                                 }
 283                                 return E_OK;
 284                         }
 285                 }
 286
 287                 if (s->s_accept) {
 288                         /* Pop this dfa and try again */
 289                         s_pop(&ps->p_stack);
 290                         D(printf(" Pop ...\n"));
 291                         if (s_empty(&ps->p_stack)) {
 292                                 D(printf(" Error: bottom of stack.\n"));
 293                                 return E_SYNTAX;
 294                         }
 295                         continue;
 296                 }
 297
 298                 /* Stuck, report syntax error */
 299                 D(printf(" Error.\n"));
 300                 return E_SYNTAX;
 301         }
 302 }
 303
 304
 305 #ifdef DEBUG
 306
 307 /* DEBUG OUTPUT */
 308
 309 void
 310 dumptree(g, n)
 311         grammar *g;
 312         node *n;
 313 {
 314         int i;
 315
 316         if (n == NULL)
 317                 printf("NIL");
 318         else {
 319                 label l;
 320                 l.lb_type = TYPE(n);
 321                 l.lb_str = STR(n);
 322                 printf("%s", labelrepr(&l));
 323                 if (ISNONTERMINAL(TYPE(n))) {
 324                         printf("(");
 325                         for (i = 0; i < NCH(n); i++) {
 326                                 if (i > 0)
 327                                         printf(",");
 328                                 dumptree(g, CHILD(n, i));
 329                         }
 330                         printf(")");
 331                 }
 332         }
 333 }
 334
 335 void
 336 showtree(g, n)
 337         grammar *g;
 338         node *n;
 339 {
 340         int i;
 341
 342         if (n == NULL)
 343                 return;
 344         if (ISNONTERMINAL(TYPE(n))) {
 345                 for (i = 0; i < NCH(n); i++)
 346                         showtree(g, CHILD(n, i));
 347         }
 348         else if (ISTERMINAL(TYPE(n))) {
 349                 printf("%s", tok_name[TYPE(n)]);
 350                 if (TYPE(n) == NUMBER || TYPE(n) == NAME)
 351                         printf("(%s)", STR(n));
 352                 printf(" ");
 353         }
 354         else
 355                 printf("? ");
 356 }
 357
 358 void
 359 printtree(ps)
 360         parser_state *ps;
 361 {
 362         if (debugging) {
 363                 printf("Parse tree:\n");
 364                 dumptree(ps->p_grammar, ps->p_tree);
 365                 printf("\n");
 366                 printf("Tokens:\n");
 367                 showtree(ps->p_grammar, ps->p_tree);
 368                 printf("\n");
 369         }
 370         printf("Listing:\n");
 371         listtree(ps->p_tree);
 372         printf("\n");
 373 }
 374
 375 #endif /* DEBUG */
 376
 377 /*
 378
 379 Description
 380 -----------
 381
 382 The parser's interface is different than usual: the function addtoken()
 383 must be called for each token in the input.  This makes it possible to
 384 turn it into an incremental parsing system later.  The parsing system
 385 constructs a parse tree as it goes.
 386
 387 A parsing rule is represented as a Deterministic Finite-state Automaton
 388 (DFA).  A node in a DFA represents a state of the parser; an arc represents
 389 a transition.  Transitions are either labeled with terminal symbols or
 390 with non-terminals.  When the parser decides to follow an arc labeled
 391 with a non-terminal, it is invoked recursively with the DFA representing
 392 the parsing rule for that as its initial state; when that DFA accepts,
 393 the parser that invoked it continues.  The parse tree constructed by the
 394 recursively called parser is inserted as a child in the current parse tree.
 395
 396 The DFA's can be constructed automatically from a more conventional
 397 language description.  An extended LL(1) grammar (ELL(1)) is suitable.
 398 Certain restrictions make the parser's life easier: rules that can produce
 399 the empty string should be outlawed (there are other ways to put loops
 400 or optional parts in the language).  To avoid the need to construct
 401 FIRST sets, we can require that all but the last alternative of a rule
 402 (really: arc going out of a DFA's state) must begin with a terminal
 403 symbol.
 404
 405 As an example, consider this grammar:
 406
 407 expr:   term (OP term)*
 408 term:   CONSTANT | '(' expr ')'
 409
 410 The DFA corresponding to the rule for expr is:
 411
 412 ------->.---term-->.------->
 413         ^          |
 414         |          |
 415         \----OP----/
 416
 417 The parse tree generated for the input a+b is:
 418
 419 (expr: (term: (NAME: a)), (OP: +), (term: (NAME: b)))
 420
 421 */