simgear/nasal/parse.c

   1 #include <setjmp.h>
   2
   3 #include "parse.h"
   4
   5 // Static precedence table, from low (loose binding, do first) to high
   6 // (tight binding, do last).
   7 enum { PREC_BINARY, PREC_REVERSE, PREC_PREFIX, PREC_SUFFIX };
   8
   9 #define MAX_PREC_TOKS 5
  10 struct precedence {
  11     int toks[MAX_PREC_TOKS];
  12     int rule;
  13 } PRECEDENCE[] = {
  14     { { TOK_SEMI, TOK_COMMA },                 PREC_REVERSE },
  15     { { TOK_ELLIPSIS },                        PREC_SUFFIX  },
  16     { { TOK_RETURN, TOK_BREAK, TOK_CONTINUE }, PREC_PREFIX  },
  17     { { TOK_ASSIGN },                          PREC_REVERSE },
  18     { { TOK_COLON, TOK_QUESTION },             PREC_REVERSE },
  19     { { TOK_VAR },                             PREC_PREFIX  },
  20     { { TOK_OR },                              PREC_BINARY  },
  21     { { TOK_AND },                             PREC_BINARY  },
  22     { { TOK_EQ, TOK_NEQ },                     PREC_BINARY  },
  23     { { TOK_LT, TOK_LTE, TOK_GT, TOK_GTE },    PREC_BINARY  },
  24     { { TOK_PLUS, TOK_MINUS, TOK_CAT },        PREC_REVERSE },
  25     { { TOK_MUL, TOK_DIV },                    PREC_BINARY  },
  26     { { TOK_MINUS, TOK_NEG, TOK_NOT },         PREC_PREFIX  },
  27     { { TOK_LPAR, TOK_LBRA },                  PREC_SUFFIX  },
  28     { { TOK_DOT },                             PREC_BINARY  },
  29 };
  30 #define PRECEDENCE_LEVELS (sizeof(PRECEDENCE)/sizeof(struct precedence))
  31
  32 void naParseError(struct Parser* p, char* msg, int line)
  33 {
  34     p->err = msg;
  35     p->errLine = line;
  36     longjmp(p->jumpHandle, 1);
  37 }
  38
  39 // A "generic" (too obfuscated to describe) parser error
  40 static void oops(struct Parser* p, struct Token* t)
  41 {
  42     naParseError(p, "parse error", t->line);
  43 }
  44
  45 void naParseInit(struct Parser* p)
  46 {
  47     p->buf = 0;
  48     p->len = 0;
  49     p->lines = 0;
  50     p->nLines = 0;
  51     p->chunks = 0;
  52     p->chunkSizes = 0;
  53     p->nChunks = 0;
  54     p->leftInChunk = 0;
  55     p->cg = 0;
  56
  57     p->tree.type = TOK_TOP;
  58     p->tree.line = 1;
  59     p->tree.str = 0;
  60     p->tree.strlen = 0;
  61     p->tree.num = 0;
  62     p->tree.next = 0;
  63     p->tree.prev = 0;
  64     p->tree.children = 0;
  65     p->tree.lastChild = 0;
  66 }
  67
  68 void naParseDestroy(struct Parser* p)
  69 {
  70     int i;
  71     for(i=0; i<p->nChunks; i++) naFree(p->chunks[i]);
  72     naFree(p->chunks);
  73     naFree(p->chunkSizes);
  74     p->buf = 0;
  75 }
  76
  77 void* naParseAlloc(struct Parser* p, int bytes)
  78 {
  79     char* result;
  80
  81     // Round up to 8 byte chunks for alignment
  82     if(bytes & 0x7) bytes = ((bytes>>3) + 1) << 3;
  83
  84     // Need a new chunk?
  85     if(p->leftInChunk < bytes) {
  86         void* newChunk;
  87         void** newChunks;
  88         int* newChunkSizes;
  89         int sz, i;
  90
  91         sz = p->len;
  92         if(sz < bytes) sz = bytes;
  93         newChunk = naAlloc(sz);
  94
  95         p->nChunks++;
  96
  97         newChunks = naAlloc(p->nChunks * sizeof(void*));
  98         for(i=1; i<p->nChunks; i++) newChunks[i] = p->chunks[i-1];
  99         newChunks[0] = newChunk;
 100         naFree(p->chunks);
 101         p->chunks = newChunks;
 102
 103         newChunkSizes = naAlloc(p->nChunks * sizeof(int));
 104         for(i=1; i<p->nChunks; i++) newChunkSizes[i] = p->chunkSizes[i-1];
 105         newChunkSizes[0] = sz;
 106         naFree(p->chunkSizes);
 107         p->chunkSizes = newChunkSizes;
 108
 109         p->leftInChunk = sz;
 110     }
 111
 112     result = (char *)p->chunks[0] + p->chunkSizes[0] - p->leftInChunk;
 113     p->leftInChunk -= bytes;
 114     return (void*)result;
 115 }
 116
 117 // Remove the child from the list where it exists, and insert it at
 118 // the end of the parents child list.
 119 static void addNewChild(struct Token* p, struct Token* c)
 120 {
 121     if(c->prev) c->prev->next = c->next;
 122     if(c->next) c->next->prev = c->prev;
 123     if(c == c->parent->children)
 124         c->parent->children = c->next;
 125     if(c == c->parent->lastChild)
 126         c->parent->lastChild = c->prev;
 127     c->parent = p;
 128     c->next = 0;
 129     c->prev = p->lastChild;
 130     if(p->lastChild) p->lastChild->next = c;
 131     if(!p->children) p->children = c;
 132     p->lastChild = c;
 133 }
 134
 135 // Follows the token list from start (which must be a left brace of
 136 // some type), placing all tokens found into start's child list until
 137 // it reaches the matching close brace.
 138 static void collectBrace(struct Parser* p, struct Token* start)
 139 {
 140     struct Token* t;
 141     int closer = -1;
 142     if(start->type == TOK_LPAR)  closer = TOK_RPAR;
 143     if(start->type == TOK_LBRA)  closer = TOK_RBRA;
 144     if(start->type == TOK_LCURL) closer = TOK_RCURL;
 145
 146     t = start->next;
 147     while(t) {
 148         struct Token* next;
 149         switch(t->type) {
 150         case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
 151             collectBrace(p, t);
 152             break;
 153         case TOK_RPAR: case TOK_RBRA: case TOK_RCURL:
 154             if(t->type != closer)
 155                 naParseError(p, "mismatched closing brace", t->line);
 156
 157             // Drop this node on the floor, stitch up the list and return
 158             if(start->parent->lastChild == t)
 159                 start->parent->lastChild = t->prev;
 160             start->next = t->next;
 161             if(t->next) t->next->prev = start;
 162             return;
 163         }
 164         // Snip t out of the existing list, and append it to start's
 165         // children.
 166         next = t->next;
 167         addNewChild(start, t);
 168         t = next;
 169     }
 170     naParseError(p, "unterminated brace", start->line);
 171 }
 172
 173 // Recursively find the contents of all matching brace pairs in the
 174 // token list and turn them into children of the left token.  The
 175 // right token disappears.
 176 static void braceMatch(struct Parser* p, struct Token* start)
 177 {
 178     struct Token* t = start;
 179     while(t) {
 180         switch(t->type) {
 181         case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
 182             collectBrace(p, t);
 183             break;
 184         case TOK_RPAR: case TOK_RBRA: case TOK_RCURL:
 185             if(start->type != TOK_LBRA)
 186                 naParseError(p, "stray closing brace", t->line);
 187             break;
 188         }
 189         t = t->next;
 190     }
 191 }
 192
 193 // Allocate and return an "empty" token as a parsing placeholder.
 194 static struct Token* emptyToken(struct Parser* p)
 195 {
 196     struct Token* t = naParseAlloc(p, sizeof(struct Token));
 197     t->type = TOK_EMPTY;
 198     t->line = -1;
 199     t->strlen = 0;
 200     t->num = 0;
 201     t->str = 0;
 202     t->next = t->prev = t->children = t->lastChild = 0;
 203     t->parent = 0;
 204     return t;
 205 }
 206
 207 // Fixes up parenting for obvious parsing situations, like code blocks
 208 // being the child of a func keyword, etc...
 209 static void fixBlockStructure(struct Parser* p, struct Token* start)
 210 {
 211     struct Token *t, *c;
 212     t = start;
 213     while(t) {
 214         switch(t->type) {
 215         case TOK_FUNC:
 216             // Slurp an optional paren block containing an arglist, then
 217             // fall through to parse the curlies...
 218             if(t->next && t->next->type == TOK_LPAR) {
 219                 c = t->next;
 220                 addNewChild(t, c);
 221                 fixBlockStructure(p, c);
 222             }
 223         case TOK_ELSE: // and TOK_FUNC!
 224             // These guys precede a single curly block
 225             if(!t->next || t->next->type != TOK_LCURL) oops(p, t);
 226             c = t->next;
 227             addNewChild(t, c);
 228             fixBlockStructure(p, c);
 229             break;
 230         case TOK_FOR: case TOK_FOREACH: case TOK_WHILE:
 231         case TOK_IF: case TOK_ELSIF:
 232             // Expect a paren and then a curly
 233             if(!t->next || t->next->type != TOK_LPAR) oops(p, t);
 234             c = t->next;
 235             addNewChild(t, c);
 236             fixBlockStructure(p, c);
 237
 238             if(!t->next || t->next->type != TOK_LCURL) oops(p, t);
 239             c = t->next;
 240             addNewChild(t, c);
 241             fixBlockStructure(p, c);
 242             break;
 243         case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
 244             fixBlockStructure(p, t->children);
 245             break;
 246         }
 247         t = t->next;
 248     }
 249
 250     // Another pass to hook up the elsif/else chains.
 251     t = start;
 252     while(t) {
 253         if(t->type == TOK_IF) {
 254             while(t->next && t->next->type == TOK_ELSIF)
 255                 addNewChild(t, t->next);
 256             if(t->next && t->next->type == TOK_ELSE)
 257                 addNewChild(t, t->next);
 258         }
 259         t = t->next;
 260     }
 261
 262     // And a final one to add semicolons.  Always add one after
 263     // for/foreach/while expressions.  Add one after a function lambda
 264     // if it immediately follows an assignment, and add one after an
 265     // if/elsif/else if it is the first token in an expression list
 266     // (i.e has no previous token, or is preceded by a ';' or '{').
 267     // This mimicks common usage and avoids a conspicuous difference
 268     // between this grammar and more common languages.  It can be
 269     // "escaped" with extra parenthesis if necessary, e.g.:
 270     //      a = (func { join(" ", arg) })(1, 2, 3, 4);
 271     t = start;
 272     while(t) {
 273         int addSemi = 0;
 274         switch(t->type) {
 275         case TOK_IF:
 276             if(!t->prev
 277                || t->prev->type == TOK_SEMI
 278                || t->prev->type == TOK_LCURL)
 279                 addSemi = 1;
 280             break;
 281         case TOK_FOR: case TOK_FOREACH: case TOK_WHILE:
 282             addSemi = 1;
 283             break;
 284         case TOK_FUNC:
 285             if(t->prev && t->prev->type == TOK_ASSIGN)
 286                 addSemi = 1;
 287             break;
 288         }
 289         if(t->next && t->next->type == TOK_SEMI)
 290             addSemi = 0; // don't bother if it's already there!
 291         if(addSemi) {
 292             struct Token* semi = emptyToken(p);
 293             semi->type = TOK_SEMI;
 294             semi->line = t->line;
 295             semi->next = t->next;
 296             semi->prev = t;
 297             semi->parent = t->parent;
 298             if(semi->next) semi->next->prev = semi;
 299             t->next = semi;
 300             t = semi; // don't bother checking the new one
 301         }
 302         t = t->next;
 303     }
 304
 305 }
 306
 307 // True if the token's type exists in the precedence level.
 308 static int tokInLevel(struct Token* tok, int level)
 309 {
 310     int i;
 311     for(i=0; i<MAX_PREC_TOKS; i++)
 312         if(PRECEDENCE[level].toks[i] == tok->type)
 313             return 1;
 314     return 0;
 315 }
 316
 317 static int isBrace(int type)
 318 {
 319     return type == TOK_LPAR || type == TOK_LBRA || type == TOK_LCURL;
 320 }
 321
 322 static int isBlock(int t)
 323 {
 324     return t == TOK_IF  || t == TOK_ELSIF   || t == TOK_ELSE
 325         || t == TOK_FOR || t == TOK_FOREACH || t == TOK_WHILE
 326         || t == TOK_FUNC;
 327 }
 328
 329 static void precChildren(struct Parser* p, struct Token* t);
 330 static void precBlock(struct Parser* p, struct Token* t);
 331
 332 static struct Token* parsePrecedence(struct Parser* p,
 333                                      struct Token* start, struct Token* end,
 334                                      int level)
 335 {
 336     int rule;
 337     struct Token *t, *top, *left, *right;
 338     struct Token *a, *b, *c, *d; // temporaries
 339
 340     // This is an error.  No "siblings" are allowed at the bottom level.
 341     if(level >= PRECEDENCE_LEVELS && start != end)
 342         oops(p, start);
 343
 344     // Synthesize an empty token if necessary
 345     if(end == 0 && start == 0)
 346         return emptyToken(p);
 347
 348     // Sanify the list.  This is OK, since we're recursing into the
 349     // list structure; stuff to the left and right has already been
 350     // handled somewhere above.
 351     if(end == 0) end = start;
 352     if(start == 0) start = end;
 353     if(start->prev) start->prev->next = 0;
 354     if(end->next) end->next->prev = 0;
 355     start->prev = end->next = 0;
 356
 357     // Single tokens parse as themselves.  Recurse into braces, and
 358     // parse children of block structure.
 359     if(start == end) {
 360         if(isBrace(start->type)) {
 361             precChildren(p, start);
 362         } else if(isBlock(start->type)) {
 363             precBlock(p, start);
 364         }
 365         return start;
 366     }
 367
 368     // A context-sensitivity: we want to parse ';' and ',' as binary
 369     // operators, but want them to be legal at the beginning and end
 370     // of a list (unlike, say, '+' where we want a parse error).
 371     // Generate empties as necessary.
 372     if(start->type == TOK_SEMI || start->type == TOK_COMMA) {
 373         t = emptyToken(p);
 374         start->prev = t;
 375         t->next = start;
 376         start = t;
 377     }
 378     if(end->type == TOK_SEMI || end->type == TOK_COMMA) {
 379         t = emptyToken(p);
 380         end->next = t;
 381         t->prev = end;
 382         end = t;
 383     }
 384
 385     // Another one: the "." and (postfix) "[]/()" operators should
 386     // really be the same precendence level, but the existing
 387     // implementation doesn't allow for it.  Bump us up a level if we
 388     // are parsing for DOT but find a LPAR/LBRA at the end of the
 389     // list.
 390     if(PRECEDENCE[level].toks[0] == TOK_DOT)
 391         if(end->type == TOK_LPAR || end->type == TOK_LBRA)
 392             level--;
 393
 394     top = left = right = 0;
 395     rule = PRECEDENCE[level].rule;
 396     switch(rule) {
 397     case PREC_PREFIX:
 398         if(tokInLevel(start, level) && start->next) {
 399             a = start->children;
 400             b = start->lastChild;
 401             c = start->next;
 402             d = end;
 403             top = start;
 404             if(a) left = parsePrecedence(p, a, b, 0);
 405             right = parsePrecedence(p, c, d, level);
 406         }
 407         break;
 408     case PREC_SUFFIX:
 409         if(tokInLevel(end, level) && end->prev) {
 410             a = start;
 411             b = end->prev;
 412             c = end->children;
 413             d = end->lastChild;
 414             top = end;
 415             left = parsePrecedence(p, a, b, level);
 416             if(c) right = parsePrecedence(p, c, d, 0);
 417         }
 418         break;
 419     case PREC_BINARY:
 420         t = end->prev;
 421         while(t->prev) {
 422             if(tokInLevel(t, level)) {
 423                 a = t->prev ? start : 0;
 424                 b = t->prev;
 425                 c = t->next;
 426                 d = t->next ? end : 0;
 427                 top = t;
 428                 left = parsePrecedence(p, a, b, level);
 429                 right = parsePrecedence(p, c, d, level+1);
 430                 break;
 431             }
 432             t = t->prev;
 433         }
 434         break;
 435     case PREC_REVERSE:
 436         t = start->next;
 437         while(t->next) {
 438             if(tokInLevel(t, level)) {
 439                 a = t->prev ? start : 0;
 440                 b = t->prev;
 441                 c = t->next;
 442                 d = t->next ? end : 0;
 443                 top = t;
 444                 left = parsePrecedence(p, a, b, level+1);
 445                 right = parsePrecedence(p, c, d, level);
 446                 break;
 447             }
 448             t = t->next;
 449         }
 450         break;
 451     }
 452
 453     // Found nothing, try the next level
 454     if(!top)
 455         return parsePrecedence(p, start, end, level+1);
 456
 457     if(left) {
 458         left->next = right;
 459         left->prev = 0;
 460         left->parent = top;
 461     }
 462     top->children = left;
 463
 464     if(right) {
 465         right->next = 0;
 466         right->prev = left;
 467         right->parent = top;
 468     }
 469     top->lastChild = right;
 470
 471     top->next = top->prev = 0;
 472     return top;
 473 }
 474
 475 static void precChildren(struct Parser* p, struct Token* t)
 476 {
 477     struct Token* top = parsePrecedence(p, t->children, t->lastChild, 0);
 478     t->children = top;
 479     t->lastChild = top;
 480 }
 481
 482 // Run a "block structure" node (if/elsif/else/for/while/foreach)
 483 // through the precedence parser.  The funny child structure makes
 484 // this a little more complicated than it should be.
 485 static void precBlock(struct Parser* p, struct Token* block)
 486 {
 487     struct Token* t = block->children;
 488     while(t) {
 489         if(isBrace(t->type))
 490             precChildren(p, t);
 491         else if(isBlock(t->type))
 492             precBlock(p, t);
 493         t = t->next;
 494     }
 495 }
 496
 497 naRef naParseCode(struct Context* c, naRef srcFile, int firstLine,
 498                   char* buf, int len, int* errLine)
 499 {
 500     naRef codeObj;
 501     struct Token* t;
 502     struct Parser p;
 503
 504     // Protect from garbage collection
 505     naVec_append(c->temps, srcFile);
 506
 507     // Catch parser errors here.
 508     *errLine = 0;
 509     if(setjmp(p.jumpHandle)) {
 510         c->error = p.err;
 511         *errLine = p.errLine;
 512         return naNil();
 513     }
 514
 515     naParseInit(&p);
 516     p.context = c;
 517     p.srcFile = srcFile;
 518     p.firstLine = firstLine;
 519     p.buf = buf;
 520     p.len = len;
 521
 522     // Lexify, match brace structure, fixup if/for/etc...
 523     naLex(&p);
 524     braceMatch(&p, p.tree.children);
 525     fixBlockStructure(&p, p.tree.children);
 526
 527     // Recursively run the precedence parser, and fixup the treetop
 528     t = parsePrecedence(&p, p.tree.children, p.tree.lastChild, 0);
 529     t->prev = t->next = 0;
 530     p.tree.children = t;
 531     p.tree.lastChild = t;
 532
 533     // Generate code!
 534     codeObj = naCodeGen(&p, &(p.tree), 0);
 535
 536     // Clean up our mess
 537     naParseDestroy(&p);
 538     naVec_append(c->temps, codeObj);
 539
 540     return codeObj;
 541 }
 542
 543