src/lparser.c

   1 /*
   2 ** $Id: lparser.c,v 1.3 1998/07/06 22:07:51 roberto Exp $
   3 ** LL(1) Parser and code generator for Lua
   4 ** See Copyright Notice in lua.h
   5 */
   6
   7
   8 #include <stdio.h>
   9
  10 #include "lauxlib.h"
  11 #include "ldo.h"
  12 #include "lfunc.h"
  13 #include "llex.h"
  14 #include "lmem.h"
  15 #include "lopcodes.h"
  16 #include "lparser.h"
  17 #include "lstate.h"
  18 #include "lstring.h"
  19 #include "lua.h"
  20 #include "luadebug.h"
  21 #include "lzio.h"
  22
  23
  24 /* for limit numbers in error messages */
  25 #define MES_LIM(x)      "(limit=" x ")"
  26
  27
  28 /* size of a "normal" jump instruction: OpCode + 1 byte */
  29 #define JMPSIZE 2
  30
  31 /* maximum number of local variables */
  32 #define MAXLOCALS 32
  33 #define SMAXLOCALS "32"
  34
  35
  36 /* maximum number of upvalues */
  37 #define MAXUPVALUES 16
  38 #define SMAXUPVALUES "16"
  39
  40
  41 /*
  42 ** Variable descriptor:
  43 ** must include a "exp" option because LL(1) cannot distinguish
  44 ** between variables, upvalues and function calls on first sight.
  45 ** VGLOBAL: info is constant index of global name
  46 ** VLOCAL: info is stack index
  47 ** VDOT: info is constant index of index name
  48 ** VEXP: info is pc index of "nparam" of function call (or 0 if exp is closed)
  49 */
  50 typedef enum {VGLOBAL, VLOCAL, VDOT, VINDEXED, VEXP} varkind;
  51
  52 typedef struct {
  53   varkind k;
  54   int info;
  55 } vardesc;
  56
  57
  58 /*
  59 ** Expression List descriptor:
  60 ** tells number of expressions in the list,
  61 ** and, if last expression is open (a function call),
  62 ** where is its pc index of "nparam"
  63 */
  64 typedef struct {
  65   int n;
  66   int pc;  /* 0 if last expression is closed */
  67 } listdesc;
  68
  69
  70 /*
  71 ** Constructors descriptor:
  72 ** "n" indicates number of elements, and "k" signals whether
  73 ** it is a list constructor (k = 0) or a record constructor (k = 1)
  74 ** or empty (k = ';' or '}')
  75 */
  76 typedef struct {
  77   int n;
  78   int k;
  79 } constdesc;
  80
  81
  82 /* state needed to generate code for a given function */
  83 typedef struct FuncState {
  84   TProtoFunc *f;  /* current function header */
  85   struct FuncState *prev;  /* enclosuring function */
  86   int pc;  /* next position to code */
  87   int stacksize;  /* number of values on activation register */
  88   int maxstacksize;  /* maximum number of values on activation register */
  89   int nlocalvar;  /* number of active local variables */
  90   int nupvalues;  /* number of upvalues */
  91   int nvars;  /* number of entries in f->locvars */
  92   int maxcode;  /* size of f->code */
  93   int maxvars;  /* size of f->locvars (-1 if no debug information) */
  94   int maxconsts;  /* size of f->consts */
  95   int lastsetline;  /* line where last SETLINE was issued */
  96   vardesc upvalues[MAXUPVALUES];  /* upvalues */
  97   TaggedString *localvar[MAXLOCALS];  /* store local variable names */
  98 } FuncState;
  99
 100
 101 static int assignment (LexState *ls, vardesc *v, int nvars);
 102 static int cond (LexState *ls);
 103 static int funcname (LexState *ls, vardesc *v);
 104 static int funcparams (LexState *ls, int slf);
 105 static int listfields (LexState *ls);
 106 static int localnamelist (LexState *ls);
 107 static int optional (LexState *ls, int c);
 108 static int recfields (LexState *ls);
 109 static int stat (LexState *ls);
 110 static void block (LexState *ls);
 111 static void body (LexState *ls, int needself, int line);
 112 static void chunk (LexState *ls);
 113 static void constructor (LexState *ls);
 114 static void decinit (LexState *ls, listdesc *d);
 115 static void exp0 (LexState *ls, vardesc *v);
 116 static void exp1 (LexState *ls);
 117 static void exp2 (LexState *ls, vardesc *v);
 118 static void explist (LexState *ls, listdesc *e);
 119 static void explist1 (LexState *ls, listdesc *e);
 120 static void ifpart (LexState *ls);
 121 static void parlist (LexState *ls);
 122 static void part (LexState *ls, constdesc *cd);
 123 static void recfield (LexState *ls);
 124 static void ret (LexState *ls);
 125 static void simpleexp (LexState *ls, vardesc *v);
 126 static void statlist (LexState *ls);
 127 static void var_or_func (LexState *ls, vardesc *v);
 128 static void var_or_func_tail (LexState *ls, vardesc *v);
 129
 130
 131
 132 static void check_pc (FuncState *fs, int n) {
 133   if (fs->pc+n > fs->maxcode)
 134     fs->maxcode = luaM_growvector(&fs->f->code, fs->maxcode,
 135                                   Byte, codeEM, MAX_INT);
 136 }
 137
 138
 139 static void code_byte (FuncState *fs, Byte c) {
 140   check_pc(fs, 1);
 141   fs->f->code[fs->pc++] = c;
 142 }
 143
 144
 145 static void deltastack (LexState *ls, int delta) {
 146   FuncState *fs = ls->fs;
 147   fs->stacksize += delta;
 148   if (fs->stacksize > fs->maxstacksize) {
 149     if (fs->stacksize > 255)
 150       luaX_error(ls, "function/expression too complex");
 151     fs->maxstacksize = fs->stacksize;
 152   }
 153 }
 154
 155
 156 static int code_oparg_at (LexState *ls, int pc, OpCode op, int builtin,
 157                           int arg, int delta) {
 158   Byte *code = ls->fs->f->code;
 159   deltastack(ls, delta);
 160   if (arg < builtin) {
 161     code[pc] = op+1+arg;
 162     return 1;
 163   }
 164   else if (arg <= 255) {
 165     code[pc] = op;
 166     code[pc+1] = arg;
 167     return 2;
 168   }
 169   else if (arg <= MAX_WORD) {
 170     code[pc] = op+1+builtin;
 171     code[pc+1] = arg>>8;
 172     code[pc+2] = arg&0xFF;
 173     return 3;
 174   }
 175   else luaX_error(ls, "code too long " MES_LIM("64K"));
 176   return 0;   /* to avoid warnings */
 177 }
 178
 179
 180 static int fix_opcode (LexState *ls, int pc, OpCode op, int builtin, int arg) {
 181   FuncState *fs = ls->fs;
 182   TProtoFunc *f = fs->f;
 183   if (arg < builtin) {  /* close space */
 184     luaO_memdown(f->code+pc+1, f->code+pc+2, fs->pc-(pc+2));
 185     fs->pc--;
 186   }
 187   else if (arg > 255) {  /* open space */
 188     check_pc(fs, 1);
 189     luaO_memup(f->code+pc+1, f->code+pc, fs->pc-pc);
 190     fs->pc++;
 191   }
 192   return code_oparg_at(ls, pc, op, builtin, arg, 0) - 2;
 193 }
 194
 195 static void code_oparg (LexState *ls, OpCode op, int builtin, int arg,
 196                         int delta) {
 197   check_pc(ls->fs, 3);  /* maximum code size */
 198   ls->fs->pc += code_oparg_at(ls, ls->fs->pc, op, builtin, arg, delta);
 199 }
 200
 201
 202 static void code_opcode (LexState *ls, OpCode op, int delta) {
 203   deltastack(ls, delta);
 204   code_byte(ls->fs, op);
 205 }
 206
 207
 208 static void code_constant (LexState *ls, int c) {
 209   code_oparg(ls, PUSHCONSTANT, 8, c, 1);
 210 }
 211
 212
 213 static int next_constant (FuncState *fs) {
 214   TProtoFunc *f = fs->f;
 215   if (f->nconsts >= fs->maxconsts) {
 216     fs->maxconsts = luaM_growvector(&f->consts, fs->maxconsts, TObject,
 217                                     constantEM, MAX_WORD);
 218   }
 219   return f->nconsts++;
 220 }
 221
 222
 223 static int string_constant (FuncState *fs, TaggedString *s) {
 224   TProtoFunc *f = fs->f;
 225   int c = s->constindex;
 226   if (!(c < f->nconsts &&
 227       ttype(&f->consts[c]) == LUA_T_STRING && tsvalue(&f->consts[c]) == s)) {
 228     c = next_constant(fs);
 229     ttype(&f->consts[c]) = LUA_T_STRING;
 230     tsvalue(&f->consts[c]) = s;
 231     s->constindex = c;  /* hint for next time */
 232   }
 233   return c;
 234 }
 235
 236
 237 static void code_string (LexState *ls, TaggedString *s) {
 238   code_constant(ls, string_constant(ls->fs, s));
 239 }
 240
 241
 242 #define LIM 20
 243 static int real_constant (FuncState *fs, real r) {
 244   /* check whether 'r' has appeared within the last LIM entries */
 245   TObject *cnt = fs->f->consts;
 246   int c = fs->f->nconsts;
 247   int lim = c < LIM ? 0 : c-LIM;
 248   while (--c >= lim) {
 249     if (ttype(&cnt[c]) == LUA_T_NUMBER && nvalue(&cnt[c]) == r)
 250       return c;
 251   }
 252   /* not found; create a luaM_new entry */
 253   c = next_constant(fs);
 254   cnt = fs->f->consts;  /* 'next_constant' may reallocate this vector */
 255   ttype(&cnt[c]) = LUA_T_NUMBER;
 256   nvalue(&cnt[c]) = r;
 257   return c;
 258 }
 259
 260
 261 static void code_number (LexState *ls, real f) {
 262   int i;
 263   if (f >= 0 && f <= (real)MAX_WORD && (real)(i=(int)f) == f)
 264     code_oparg(ls, PUSHNUMBER, 3, i, 1);  /* f has a short integer value */
 265   else
 266     code_constant(ls, real_constant(ls->fs, f));
 267 }
 268
 269
 270 static void flush_record (LexState *ls, int n) {
 271   if (n > 0)
 272     code_oparg(ls, SETMAP, 1, n-1, -2*n);
 273 }
 274
 275
 276 static void flush_list (LexState *ls, int m, int n) {
 277   if (n == 0) return;
 278   code_oparg(ls, SETLIST, 1, m, -n);
 279   code_byte(ls->fs, n);
 280 }
 281
 282
 283 static void luaI_registerlocalvar (FuncState *fs, TaggedString *varname,
 284                                    int line) {
 285   if (fs->maxvars != -1) {  /* debug information? */
 286     TProtoFunc *f = fs->f;
 287     if (fs->nvars >= fs->maxvars)
 288       fs->maxvars = luaM_growvector(&f->locvars, fs->maxvars,
 289                                     LocVar, "", MAX_WORD);
 290     f->locvars[fs->nvars].varname = varname;
 291     f->locvars[fs->nvars].line = line;
 292     fs->nvars++;
 293   }
 294 }
 295
 296
 297 static void luaI_unregisterlocalvar (FuncState *fs, int line) {
 298   luaI_registerlocalvar(fs, NULL, line);
 299 }
 300
 301
 302 static void store_localvar (LexState *ls, TaggedString *name, int n) {
 303   FuncState *fs = ls->fs;
 304   if (fs->nlocalvar+n < MAXLOCALS)
 305     fs->localvar[fs->nlocalvar+n] = name;
 306   else
 307     luaX_error(ls, "too many local variables " MES_LIM(SMAXLOCALS));
 308   luaI_registerlocalvar(fs, name, ls->linenumber);
 309 }
 310
 311
 312 static void add_localvar (LexState *ls, TaggedString *name) {
 313   store_localvar(ls, name, 0);
 314   ls->fs->nlocalvar++;
 315 }
 316
 317
 318 static int aux_localname (FuncState *fs, TaggedString *n) {
 319   int i;
 320   for (i=fs->nlocalvar-1; i >= 0; i--)
 321     if (n == fs->localvar[i]) return i;  /* local var index */
 322   return -1;  /* not found */
 323 }
 324
 325
 326 static void singlevar (LexState *ls, TaggedString *n, vardesc *var, int prev) {
 327   FuncState *fs = prev ? ls->fs->prev : ls->fs;
 328   int i = aux_localname(fs, n);
 329   if (i >= 0) {  /* local value */
 330     var->k = VLOCAL;
 331     var->info = i;
 332   }
 333   else {  /* check shadowing */
 334     FuncState *level = fs;
 335     while ((level = level->prev) != NULL)
 336       if (aux_localname(level, n) >= 0)
 337         luaX_syntaxerror(ls, "cannot access a variable in outer scope", n->str);
 338     var->k = VGLOBAL;
 339     var->info = string_constant(fs, n);
 340   }
 341 }
 342
 343
 344 static int indexupvalue (LexState *ls, TaggedString *n) {
 345   FuncState *fs = ls->fs;
 346   vardesc v;
 347   int i;
 348   singlevar(ls, n, &v, 1);
 349   for (i=0; i<fs->nupvalues; i++) {
 350     if (fs->upvalues[i].k == v.k && fs->upvalues[i].info == v.info)
 351       return i;
 352   }
 353   /* new one */
 354   if (++(fs->nupvalues) > MAXUPVALUES)
 355     luaX_error(ls, "too many upvalues in a single function "
 356                    MES_LIM(SMAXUPVALUES));
 357   fs->upvalues[i] = v;  /* i = fs->nupvalues - 1 */
 358   return i;
 359 }
 360
 361
 362 static void pushupvalue (LexState *ls, TaggedString *n) {
 363   int i;
 364   if (ls->fs->prev == NULL)
 365     luaX_syntaxerror(ls, "cannot access upvalue in main", n->str);
 366   if (aux_localname(ls->fs, n) >= 0)
 367     luaX_syntaxerror(ls, "cannot access an upvalue in current scope", n->str);
 368   i = indexupvalue(ls, n);
 369   code_oparg(ls, PUSHUPVALUE, 2, i, 1);
 370 }
 371
 372
 373
 374 static void check_debugline (LexState *ls) {
 375   if (lua_debug && ls->linenumber != ls->fs->lastsetline) {
 376     code_oparg(ls, SETLINE, 0, ls->linenumber, 0);
 377     ls->fs->lastsetline = ls->linenumber;
 378   }
 379 }
 380
 381
 382 static void adjuststack (LexState *ls, int n) {
 383   if (n > 0)
 384     code_oparg(ls, POP, 2, n-1, -n);
 385   else if (n < 0)
 386     code_oparg(ls, PUSHNIL, 1, (-n)-1, -n);
 387 }
 388
 389
 390 static void close_exp (LexState *ls, int pc, int nresults) {
 391   if (pc > 0) {  /* expression is an open function call */
 392     Byte *code = ls->fs->f->code;
 393     int nparams = code[pc];  /* save nparams */
 394     pc += fix_opcode(ls, pc-2, CALLFUNC, 2, nresults);
 395     code[pc] = nparams;  /* restore nparams */
 396     if (nresults != MULT_RET)
 397       deltastack(ls, nresults);  /* "push" results */
 398     deltastack(ls, -(nparams+1));  /* "pop" params and function */
 399   }
 400 }
 401
 402
 403 static void adjust_mult_assign (LexState *ls, int nvars, listdesc *d) {
 404   int diff = d->n - nvars;
 405   if (d->pc == 0) {  /* list is closed */
 406     /* push or pop eventual difference between list lengths */
 407     adjuststack(ls, diff);
 408   }
 409   else {  /* must correct function call */
 410     diff--;  /* do not count function call itself */
 411     if (diff < 0) {  /* more variables than values */
 412       /* function call must provide extra values */
 413       close_exp(ls, d->pc, -diff);
 414     }
 415     else {  /* more values than variables */
 416       close_exp(ls, d->pc, 0);  /* call should provide no value */
 417       adjuststack(ls, diff);  /* pop eventual extra values */
 418     }
 419   }
 420 }
 421
 422
 423 static void code_args (LexState *ls, int nparams, int dots) {
 424   FuncState *fs = ls->fs;
 425   fs->nlocalvar += nparams;  /* "self" may already be there */
 426   nparams = fs->nlocalvar;
 427   if (!dots) {
 428     fs->f->code[1] = nparams;  /* fill-in arg information */
 429     deltastack(ls, nparams);
 430   }
 431   else {
 432     fs->f->code[1] = nparams+ZEROVARARG;
 433     deltastack(ls, nparams+1);
 434     add_localvar(ls, luaS_new("arg"));
 435   }
 436 }
 437
 438
 439 static void lua_pushvar (LexState *ls, vardesc *var) {
 440   switch (var->k) {
 441     case VLOCAL:
 442       code_oparg(ls, PUSHLOCAL, 8, var->info, 1);
 443       break;
 444     case VGLOBAL:
 445       code_oparg(ls, GETGLOBAL, 8, var->info, 1);
 446       break;
 447     case VDOT:
 448       code_oparg(ls, GETDOTTED, 8, var->info, 0);
 449       break;
 450     case VINDEXED:
 451       code_opcode(ls, GETTABLE, -1);
 452       break;
 453     case VEXP:
 454       close_exp(ls, var->info, 1);  /* function must return 1 value */
 455       break;
 456   }
 457   var->k = VEXP;
 458   var->info = 0;  /* now this is a closed expression */
 459 }
 460
 461
 462 static void storevar (LexState *ls, vardesc *var) {
 463   switch (var->k) {
 464     case VLOCAL:
 465       code_oparg(ls, SETLOCAL, 8, var->info, -1);
 466       break;
 467     case VGLOBAL:
 468       code_oparg(ls, SETGLOBAL, 8, var->info, -1);
 469       break;
 470     case VINDEXED:
 471       code_opcode(ls, SETTABLE0, -3);
 472       break;
 473     default:
 474       LUA_INTERNALERROR("invalid var kind to store");
 475   }
 476 }
 477
 478
 479 static int fix_jump (LexState *ls, int pc, OpCode op, int n) {
 480   /* jump is relative to position following jump instruction */
 481   return fix_opcode(ls, pc, op, 0, n-(pc+JMPSIZE));
 482 }
 483
 484
 485 static void fix_upjmp (LexState *ls, OpCode op, int pos) {
 486   int delta = ls->fs->pc+JMPSIZE - pos;  /* jump is relative */
 487   if (delta > 255) delta++;
 488   code_oparg(ls, op, 0, delta, 0);
 489 }
 490
 491
 492 static void codeIf (LexState *ls, int thenAdd, int elseAdd) {
 493   FuncState *fs = ls->fs;
 494   int elseinit = elseAdd+JMPSIZE;
 495   if (fs->pc == elseinit) {  /* no else part */
 496     fs->pc -= JMPSIZE;
 497     elseinit = fs->pc;
 498   }
 499   else
 500     elseinit += fix_jump(ls, elseAdd, JMP, fs->pc);
 501   fix_jump(ls, thenAdd, IFFJMP, elseinit);
 502 }
 503
 504
 505 static void func_onstack (LexState *ls, FuncState *func) {
 506   FuncState *fs = ls->fs;
 507   int i;
 508   int c = next_constant(fs);
 509   ttype(&fs->f->consts[c]) = LUA_T_PROTO;
 510   fs->f->consts[c].value.tf = func->f;
 511   if (func->nupvalues == 0)
 512     code_constant(ls, c);
 513   else {
 514     for (i=0; i<func->nupvalues; i++)
 515       lua_pushvar(ls, &func->upvalues[i]);
 516     code_oparg(ls, CLOSURE, 0, c, -func->nupvalues+1);
 517     code_byte(fs, func->nupvalues);
 518   }
 519 }
 520
 521
 522 static void init_state (LexState *ls, FuncState *fs, TaggedString *filename) {
 523   TProtoFunc *f = luaF_newproto();
 524   fs->prev = ls->fs;  /* linked list of funcstates */
 525   ls->fs = fs;
 526   fs->stacksize = 0;
 527   fs->maxstacksize = 0;
 528   fs->nlocalvar = 0;
 529   fs->nupvalues = 0;
 530   fs->lastsetline = 0;
 531   fs->f = f;
 532   f->fileName = filename;
 533   fs->pc = 0;
 534   fs->maxcode = 0;
 535   f->code = NULL;
 536   fs->maxconsts = 0;
 537   if (lua_debug)
 538     fs->nvars = fs->maxvars = 0;
 539   else
 540     fs->maxvars = -1;  /* flag no debug information */
 541   code_byte(fs, 0);  /* to be filled with stacksize */
 542   code_byte(fs, 0);  /* to be filled with arg information */
 543 }
 544
 545
 546 static void close_func (LexState *ls) {
 547   FuncState *fs = ls->fs;
 548   TProtoFunc *f = fs->f;
 549   code_opcode(ls, ENDCODE, 0);
 550   f->code[0] = fs->maxstacksize;
 551   f->code = luaM_reallocvector(f->code, fs->pc, Byte);
 552   f->consts = luaM_reallocvector(f->consts, f->nconsts, TObject);
 553   if (fs->maxvars != -1) {  /* debug information? */
 554     luaI_registerlocalvar(fs, NULL, -1);  /* flag end of vector */
 555     f->locvars = luaM_reallocvector(f->locvars, fs->nvars, LocVar);
 556   }
 557   ls->fs = fs->prev;
 558 }
 559
 560
 561
 562 static int expfollow [] = {ELSE, ELSEIF, THEN, IF, WHILE, REPEAT, DO, NAME,
 563    LOCAL, FUNCTION, END, UNTIL, RETURN, ')', ']', '}', ';', EOS, ',',  0};
 564
 565 static int is_in (int tok, int *toks) {
 566   int *t = toks;
 567   while (*t) {
 568     if (*t == tok)
 569       return t-toks;
 570     t++;
 571   }
 572   return -1;
 573 }
 574
 575
 576 static void next (LexState *ls) {
 577   ls->token = luaX_lex(ls);
 578 }
 579
 580
 581 static void error_expected (LexState *ls, int token) {
 582   char buff[100], t[TOKEN_LEN];
 583   luaX_token2str(ls, token, t);
 584   sprintf(buff, "`%s' expected", t);
 585   luaX_error(ls, buff);
 586 }
 587
 588 static void error_unmatched (LexState *ls, int what, int who, int where) {
 589   if (where == ls->linenumber)
 590     error_expected(ls, what);
 591   else {
 592     char buff[100];
 593     char t_what[TOKEN_LEN], t_who[TOKEN_LEN];
 594     luaX_token2str(ls, what, t_what);
 595     luaX_token2str(ls, who, t_who);
 596     sprintf(buff, "`%s' expected (to close `%s' at line %d)",
 597             t_what, t_who, where);
 598     luaX_error(ls, buff);
 599   }
 600 }
 601
 602 static void check (LexState *ls, int c) {
 603   if (ls->token != c)
 604     error_expected(ls, c);
 605   next(ls);
 606 }
 607
 608 static void check_match (LexState *ls, int what, int who, int where) {
 609   if (ls->token != what)
 610     error_unmatched(ls, what, who, where);
 611   check_debugline(ls);  /* to 'mark' the 'what' */
 612   next(ls);
 613 }
 614
 615 static TaggedString *checkname (LexState *ls) {
 616   TaggedString *ts;
 617   if (ls->token != NAME)
 618     luaX_error(ls, "`NAME' expected");
 619   ts = ls->seminfo.ts;
 620   next(ls);
 621   return ts;
 622 }
 623
 624
 625 static int optional (LexState *ls, int c) {
 626   if (ls->token == c) {
 627     next(ls);
 628     return 1;
 629   }
 630   else return 0;
 631 }
 632
 633
 634 TProtoFunc *luaY_parser (ZIO *z) {
 635   struct LexState lexstate;
 636   struct FuncState funcstate;
 637   luaX_setinput(&lexstate, z);
 638   init_state(&lexstate, &funcstate, luaS_new(zname(z)));
 639   next(&lexstate);  /* read first token */
 640   chunk(&lexstate);
 641   if (lexstate.token != EOS)
 642     luaX_error(&lexstate, "<eof> expected");
 643   close_func(&lexstate);
 644   return funcstate.f;
 645 }
 646
 647
 648
 649 /*============================================================*/
 650 /* GRAMAR RULES */
 651 /*============================================================*/
 652
 653 static void chunk (LexState *ls) {
 654   /* chunk -> statlist ret */
 655   statlist(ls);
 656   ret(ls);
 657 }
 658
 659 static void statlist (LexState *ls) {
 660   /* statlist -> { stat [;] } */
 661   while (stat(ls)) {
 662     LUA_ASSERT(ls->fs->stacksize == ls->fs->nlocalvar,
 663                "stack size != # local vars");
 664     optional(ls, ';');
 665   }
 666 }
 667
 668 static int stat (LexState *ls) {
 669   int line = ls->linenumber;  /* may be needed for error messages */
 670   FuncState *fs = ls->fs;
 671   switch (ls->token) {
 672     case IF: {  /* stat -> IF ifpart END */
 673       next(ls);
 674       ifpart(ls);
 675       check_match(ls, END, IF, line);
 676       return 1;
 677     }
 678
 679     case WHILE: {  /* stat -> WHILE cond DO block END */
 680       TProtoFunc *f = fs->f;
 681       int while_init = fs->pc;
 682       int cond_end, cond_size;
 683       next(ls);
 684       cond_end = cond(ls);
 685       check(ls, DO);
 686       block(ls);
 687       check_match(ls, END, WHILE, line);
 688       cond_size = cond_end-while_init;
 689       check_pc(fs, cond_size);
 690       memcpy(f->code+fs->pc, f->code+while_init, cond_size);
 691       luaO_memdown(f->code+while_init, f->code+cond_end, fs->pc-while_init);
 692       while_init += JMPSIZE + fix_jump(ls, while_init, JMP, fs->pc-cond_size);
 693       fix_upjmp(ls, IFTUPJMP, while_init);
 694       return 1;
 695     }
 696
 697     case DO: {  /* stat -> DO block END */
 698       next(ls);
 699       block(ls);
 700       check_match(ls, END, DO, line);
 701       return 1;
 702     }
 703
 704     case REPEAT: {  /* stat -> REPEAT block UNTIL exp1 */
 705       int repeat_init = fs->pc;
 706       next(ls);
 707       block(ls);
 708       check_match(ls, UNTIL, REPEAT, line);
 709       exp1(ls);
 710       fix_upjmp(ls, IFFUPJMP, repeat_init);
 711       deltastack(ls, -1);  /* pops condition */
 712       return 1;
 713     }
 714
 715     case FUNCTION: {  /* stat -> FUNCTION funcname body */
 716       int needself;
 717       vardesc v;
 718       if (ls->fs->prev)  /* inside other function? */
 719         return 0;
 720       check_debugline(ls);
 721       next(ls);
 722       needself = funcname(ls, &v);
 723       body(ls, needself, line);
 724       storevar(ls, &v);
 725       return 1;
 726     }
 727
 728     case LOCAL: {  /* stat -> LOCAL localnamelist decinit */
 729       listdesc d;
 730       int nvars;
 731       check_debugline(ls);
 732       next(ls);
 733       nvars = localnamelist(ls);
 734       decinit(ls, &d);
 735       ls->fs->nlocalvar += nvars;
 736       adjust_mult_assign(ls, nvars, &d);
 737       return 1;
 738     }
 739
 740     case NAME: case '%': {  /* stat -> func | ['%'] NAME assignment */
 741       vardesc v;
 742       check_debugline(ls);
 743       var_or_func(ls, &v);
 744       if (v.k == VEXP) {  /* stat -> func */
 745         if (v.info == 0)  /* is just an upper value? */
 746           luaX_error(ls, "syntax error");
 747         close_exp(ls, v.info, 0);
 748       }
 749       else {
 750         int left = assignment(ls, &v, 1);  /* stat -> ['%'] NAME assignment */
 751         adjuststack(ls, left);  /* remove eventual 'garbage' left on stack */
 752       }
 753       return 1;
 754     }
 755
 756     case RETURN: case ';': case ELSE: case ELSEIF:
 757     case END: case UNTIL: case EOS:  /* 'stat' follow */
 758       return 0;
 759
 760     default:
 761       luaX_error(ls, "<statement> expected");
 762       return 0;  /* to avoid warnings */
 763   }
 764 }
 765
 766 static int SaveWord (LexState *ls) {
 767   int res = ls->fs->pc;
 768   check_pc(ls->fs, JMPSIZE);
 769   ls->fs->pc += JMPSIZE;  /* open space */
 770   return res;
 771 }
 772
 773 static int SaveWordPop (LexState *ls) {
 774   deltastack(ls, -1);  /* pop condition */
 775   return SaveWord(ls);
 776 }
 777
 778 static int cond (LexState *ls) {
 779   /* cond -> exp1 */
 780   exp1(ls);
 781   return SaveWordPop(ls);
 782 }
 783
 784 static void block (LexState *ls) {
 785   /* block -> chunk */
 786   FuncState *fs = ls->fs;
 787   int nlocalvar = fs->nlocalvar;
 788   chunk(ls);
 789   adjuststack(ls, fs->nlocalvar - nlocalvar);
 790   for (; fs->nlocalvar > nlocalvar; fs->nlocalvar--)
 791     luaI_unregisterlocalvar(fs, ls->linenumber);
 792 }
 793
 794 static int funcname (LexState *ls, vardesc *v) {
 795   /* funcname -> NAME [':' NAME | '.' NAME] */
 796   int needself = 0;
 797   singlevar(ls, checkname(ls), v, 0);
 798   if (ls->token == ':' || ls->token == '.') {
 799     needself = (ls->token == ':');
 800     next(ls);
 801     lua_pushvar(ls, v);
 802     code_string(ls, checkname(ls));
 803     v->k = VINDEXED;
 804   }
 805   return needself;
 806 }
 807
 808 static void body (LexState *ls, int needself, int line) {
 809   /* body ->  '(' parlist ')' chunk END */
 810   FuncState newfs;
 811   init_state(ls, &newfs, ls->fs->f->fileName);
 812   newfs.f->lineDefined = line;
 813   check(ls, '(');
 814   if (needself)
 815     add_localvar(ls, luaS_new("self"));
 816   parlist(ls);
 817   check(ls, ')');
 818   chunk(ls);
 819   check_match(ls, END, FUNCTION, line);
 820   close_func(ls);
 821   func_onstack(ls, &newfs);
 822 }
 823
 824 static void ifpart (LexState *ls) {
 825   /* ifpart -> cond THEN block [ELSE block | ELSEIF ifpart] */
 826   int c = cond(ls);
 827   int e;
 828   check(ls, THEN);
 829   block(ls);
 830   e = SaveWord(ls);
 831   switch (ls->token) {
 832     case ELSE:
 833       next(ls);
 834       block(ls);
 835       break;
 836
 837     case ELSEIF:
 838       next(ls);
 839       ifpart(ls);
 840       break;
 841   }
 842   codeIf(ls, c, e);
 843 }
 844
 845 static void ret (LexState *ls) {
 846   /* ret -> [RETURN explist sc] */
 847   if (ls->token == RETURN) {
 848     listdesc e;
 849     check_debugline(ls);
 850     next(ls);
 851     explist(ls, &e);
 852     close_exp(ls, e.pc, MULT_RET);
 853     code_oparg(ls, RETCODE, 0, ls->fs->nlocalvar, 0);
 854     ls->fs->stacksize = ls->fs->nlocalvar;  /* removes all temp values */
 855     optional(ls, ';');
 856   }
 857 }
 858
 859
 860 /*
 861 ** For parsing expressions, we use a classic stack with priorities.
 862 ** Each binary operator is represented by its index in "binop" + FIRSTBIN
 863 ** (EQ=2, NE=3, ... '^'=13). The unary NOT is 0 and UNMINUS is 1.
 864 */
 865
 866 /* code of first binary operator */
 867 #define FIRSTBIN        2
 868
 869 /* code for power operator (last operator)
 870 ** '^' needs special treatment because it is right associative
 871 */
 872 #define POW     13
 873
 874 static int binop [] = {EQ, NE, '>', '<', LE, GE, CONC,
 875                         '+', '-', '*', '/', '^', 0};
 876
 877 static int priority [POW+1] =  {5, 5, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4, 4, 6};
 878
 879 static OpCode opcodes [POW+1] = {NOTOP, MINUSOP, EQOP, NEQOP, GTOP, LTOP,
 880   LEOP, GEOP, CONCOP, ADDOP, SUBOP, MULTOP, DIVOP, POWOP};
 881
 882 #define MAXOPS  20
 883
 884 typedef struct {
 885   int ops[MAXOPS];
 886   int top;
 887 } stack_op;
 888
 889
 890 static void exp1 (LexState *ls) {
 891   vardesc v;
 892   exp0(ls, &v);
 893   lua_pushvar(ls, &v);
 894   if (is_in(ls->token, expfollow) < 0)
 895     luaX_error(ls, "ill formed expression");
 896 }
 897
 898
 899 static void exp0 (LexState *ls, vardesc *v) {
 900   exp2(ls, v);
 901   while (ls->token == AND || ls->token == OR) {
 902     int is_and = (ls->token == AND);
 903     int pc;
 904     lua_pushvar(ls, v);
 905     next(ls);
 906     pc = SaveWordPop(ls);
 907     exp2(ls, v);
 908     lua_pushvar(ls, v);
 909     fix_jump(ls, pc, (is_and?ONFJMP:ONTJMP), ls->fs->pc);
 910   }
 911 }
 912
 913
 914 static void push (LexState *ls, stack_op *s, int op) {
 915   if (s->top == MAXOPS)
 916     luaX_error(ls, "expression too complex");
 917   s->ops[s->top++] = op;
 918 }
 919
 920
 921 static void prefix (LexState *ls, stack_op *s) {
 922   while (ls->token == NOT || ls->token == '-') {
 923     push(ls, s, ls->token==NOT?0:1);
 924     next(ls);
 925   }
 926 }
 927
 928 static void pop_to (LexState *ls, stack_op *s, int prio) {
 929   int op;
 930   while (s->top > 0 && priority[(op=s->ops[s->top-1])] >= prio) {
 931     code_opcode(ls, opcodes[op], op<FIRSTBIN?0:-1);
 932     s->top--;
 933   }
 934 }
 935
 936 static void exp2 (LexState *ls, vardesc *v) {
 937   stack_op s;
 938   int op;
 939   s.top = 0;
 940   prefix(ls, &s);
 941   simpleexp(ls, v);
 942   while ((op = is_in(ls->token, binop)) >= 0) {
 943     op += FIRSTBIN;
 944     lua_pushvar(ls, v);
 945     /* '^' is right associative, so must 'simulate' a higher priority */
 946     pop_to(ls, &s, (op == POW)?priority[op]+1:priority[op]);
 947     push(ls, &s, op);
 948     next(ls);
 949     prefix(ls, &s);
 950     simpleexp(ls, v);
 951     lua_pushvar(ls, v);
 952   }
 953   if (s.top > 0) {
 954     lua_pushvar(ls, v);
 955     pop_to(ls, &s, 0);
 956   }
 957 }
 958
 959
 960 static void simpleexp (LexState *ls, vardesc *v) {
 961   check_debugline(ls);
 962   switch (ls->token) {
 963     case '(':  /* simpleexp -> '(' exp0 ')' */
 964       next(ls);
 965       exp0(ls, v);
 966       check(ls, ')');
 967       break;
 968
 969     case NUMBER:  /* simpleexp -> NUMBER */
 970       code_number(ls, ls->seminfo.r);
 971       next(ls);
 972       v->k = VEXP; v->info = 0;
 973       break;
 974
 975     case STRING:  /* simpleexp -> STRING */
 976       code_string(ls, ls->seminfo.ts);
 977       next(ls);
 978       v->k = VEXP; v->info = 0;
 979       break;
 980
 981     case NIL:  /* simpleexp -> NIL */
 982       adjuststack(ls, -1);
 983       next(ls);
 984       v->k = VEXP; v->info = 0;
 985       break;
 986
 987     case '{':  /* simpleexp -> constructor */
 988       constructor(ls);
 989       v->k = VEXP; v->info = 0;
 990       break;
 991
 992     case FUNCTION: {  /* simpleexp -> FUNCTION body */
 993       int line = ls->linenumber;
 994       next(ls);
 995       body(ls, 0, line);
 996       v->k = VEXP; v->info = 0;
 997       break;
 998     }
 999
1000     case NAME: case '%':
1001       var_or_func(ls, v);
1002       break;
1003
1004     default:
1005       luaX_error(ls, "<expression> expected");
1006       break;
1007   }
1008 }
1009
1010 static void var_or_func (LexState *ls, vardesc *v) {
1011   /* var_or_func -> ['%'] NAME var_or_func_tail */
1012   if (optional(ls, '%')) {  /* upvalue? */
1013     pushupvalue(ls, checkname(ls));
1014     v->k = VEXP;
1015     v->info = 0;  /* closed expression */
1016   }
1017   else  /* variable name */
1018     singlevar(ls, checkname(ls), v, 0);
1019   var_or_func_tail(ls, v);
1020 }
1021
1022 static void var_or_func_tail (LexState *ls, vardesc *v) {
1023   for (;;) {
1024     switch (ls->token) {
1025       case '.':  /* var_or_func_tail -> '.' NAME */
1026         next(ls);
1027         lua_pushvar(ls, v);  /* 'v' must be on stack */
1028         v->k = VDOT;
1029         v->info = string_constant(ls->fs, checkname(ls));
1030         break;
1031
1032       case '[':  /* var_or_func_tail -> '[' exp1 ']' */
1033         next(ls);
1034         lua_pushvar(ls, v);  /* 'v' must be on stack */
1035         exp1(ls);
1036         check(ls, ']');
1037         v->k = VINDEXED;
1038         break;
1039
1040       case ':':  /* var_or_func_tail -> ':' NAME funcparams */
1041         next(ls);
1042         lua_pushvar(ls, v);  /* 'v' must be on stack */
1043         code_oparg(ls, PUSHSELF, 8, string_constant(ls->fs, checkname(ls)), 1);
1044         v->k = VEXP;
1045         v->info = funcparams(ls, 1);
1046         break;
1047
1048       case '(': case STRING: case '{':  /* var_or_func_tail -> funcparams */
1049         lua_pushvar(ls, v);  /* 'v' must be on stack */
1050         v->k = VEXP;
1051         v->info = funcparams(ls, 0);
1052         break;
1053
1054       default: return;  /* should be follow... */
1055     }
1056   }
1057 }
1058
1059 static int funcparams (LexState *ls, int slf) {
1060   FuncState *fs = ls->fs;
1061   int nparams = 1;  /* default value */
1062   switch (ls->token) {
1063     case '(': {  /* funcparams -> '(' explist ')' */
1064       listdesc e;
1065       next(ls);
1066       explist(ls, &e);
1067       check(ls, ')');
1068       close_exp(ls, e.pc, 1);
1069       nparams = e.n;
1070       break;
1071     }
1072
1073     case '{':  /* funcparams -> constructor */
1074       constructor(ls);
1075       break;
1076
1077     case STRING:  /* funcparams -> STRING */
1078       code_string(ls, ls->seminfo.ts);
1079       next(ls);
1080       break;
1081
1082     default:
1083       luaX_error(ls, "function arguments expected");
1084       break;
1085   }
1086   code_byte(fs, 0);  /* save space for opcode */
1087   code_byte(fs, 0);  /* and nresult */
1088   code_byte(fs, nparams+slf);
1089   return fs->pc-1;
1090 }
1091
1092 static void explist (LexState *ls, listdesc *d) {
1093   switch (ls->token) {
1094     case ELSE: case ELSEIF: case END: case UNTIL:
1095     case EOS: case ';': case ')':
1096       d->pc = 0;
1097       d->n = 0;
1098       break;
1099
1100     default:
1101       explist1(ls, d);
1102   }
1103 }
1104
1105 static void explist1 (LexState *ls, listdesc *d) {
1106   vardesc v;
1107   exp0(ls, &v);
1108   d->n = 1;
1109   while (ls->token == ',') {
1110     d->n++;
1111     lua_pushvar(ls, &v);
1112     next(ls);
1113     exp0(ls, &v);
1114   }
1115   if (v.k == VEXP)
1116     d->pc = v.info;
1117   else {
1118     lua_pushvar(ls, &v);
1119     d->pc = 0;
1120   }
1121 }
1122
1123 static void parlist (LexState *ls) {
1124   int nparams = 0;
1125   int dots = 0;
1126   switch (ls->token) {
1127     case DOTS:  /* parlist -> DOTS */
1128       next(ls);
1129       dots = 1;
1130       break;
1131
1132     case NAME:  /* parlist, tailparlist -> NAME [',' tailparlist] */
1133       init:
1134       store_localvar(ls, checkname(ls), nparams++);
1135       if (ls->token == ',') {
1136         next(ls);
1137         switch (ls->token) {
1138           case DOTS:  /* tailparlist -> DOTS */
1139             next(ls);
1140             dots = 1;
1141             break;
1142
1143           case NAME:  /* tailparlist -> NAME [',' tailparlist] */
1144             goto init;
1145
1146           default: luaX_error(ls, "NAME or `...' expected");
1147         }
1148       }
1149       break;
1150
1151     case ')': break;  /* parlist -> empty */
1152
1153     default: luaX_error(ls, "NAME or `...' expected");
1154   }
1155   code_args(ls, nparams, dots);
1156 }
1157
1158 static int localnamelist (LexState *ls) {
1159   /* localnamelist -> NAME {',' NAME} */
1160   int i = 1;
1161   store_localvar(ls, checkname(ls), 0);
1162   while (ls->token == ',') {
1163     next(ls);
1164     store_localvar(ls, checkname(ls), i++);
1165   }
1166   return i;
1167 }
1168
1169 static void decinit (LexState *ls, listdesc *d) {
1170   /* decinit -> ['=' explist1] */
1171   if (ls->token == '=') {
1172     next(ls);
1173     explist1(ls, d);
1174   }
1175   else {
1176     d->n = 0;
1177     d->pc = 0;
1178   }
1179 }
1180
1181 static int assignment (LexState *ls, vardesc *v, int nvars) {
1182   int left = 0;
1183   /* dotted variables <a.x> must be stored like regular indexed vars <a["x"]> */
1184   if (v->k == VDOT) {
1185     code_constant(ls, v->info);
1186     v->k = VINDEXED;
1187   }
1188   if (ls->token == ',') {  /* assignment -> ',' NAME assignment */
1189     vardesc nv;
1190     next(ls);
1191     var_or_func(ls, &nv);
1192     if (nv.k == VEXP)
1193       luaX_error(ls, "syntax error");
1194     left = assignment(ls, &nv, nvars+1);
1195   }
1196   else {  /* assignment -> '=' explist1 */
1197     listdesc d;
1198     check(ls, '=');
1199     explist1(ls, &d);
1200     adjust_mult_assign(ls, nvars, &d);
1201   }
1202   if (v->k != VINDEXED || left+(nvars-1) == 0) {
1203     /* global/local var or indexed var without values in between */
1204     storevar(ls, v);
1205   }
1206   else {  /* indexed var with values in between*/
1207     code_oparg(ls, SETTABLE, 0, left+(nvars-1), -1);
1208     left += 2;  /* table/index are not popped, because they aren't on top */
1209   }
1210   return left;
1211 }
1212
1213 static void constructor (LexState *ls) {
1214   /* constructor -> '{' part [';' part] '}' */
1215   int line = ls->linenumber;
1216   int pc = SaveWord(ls);
1217   int nelems;
1218   constdesc cd;
1219   deltastack(ls, 1);
1220   check(ls, '{');
1221   part(ls, &cd);
1222   nelems = cd.n;
1223   if (ls->token == ';') {
1224     constdesc other_cd;
1225     next(ls);
1226     part(ls, &other_cd);
1227     if (cd.k == other_cd.k)  /* repeated parts? */
1228       luaX_error(ls, "invalid constructor syntax");
1229     nelems += other_cd.n;
1230   }
1231   check_match(ls, '}', '{', line);
1232   fix_opcode(ls, pc, CREATEARRAY, 2, nelems);
1233 }
1234
1235 static void part (LexState *ls, constdesc *cd) {
1236   switch (ls->token) {
1237     case ';': case '}':  /* part -> empty */
1238       cd->n = 0;
1239       cd->k = ls->token;
1240       return;
1241
1242     case NAME: {
1243       vardesc v;
1244       exp0(ls, &v);
1245       if (ls->token == '=') {
1246         switch (v.k) {
1247           case VGLOBAL:
1248             code_constant(ls, v.info);
1249             break;
1250           case VLOCAL:
1251             code_string(ls, ls->fs->localvar[v.info]);
1252             break;
1253           default:
1254             luaX_error(ls, "`=' unexpected");
1255         }
1256         next(ls);
1257         exp1(ls);
1258         cd->n = recfields(ls);
1259         cd->k = 1;  /* record */
1260       }
1261       else {
1262         lua_pushvar(ls, &v);
1263         cd->n = listfields(ls);
1264         cd->k = 0;  /* list */
1265       }
1266       break;
1267     }
1268
1269     case '[':  /* part -> recfield recfields */
1270       recfield(ls);
1271       cd->n = recfields(ls);
1272       cd->k = 1;  /* record */
1273       break;
1274
1275     default:  /* part -> exp1 listfields */
1276       exp1(ls);
1277       cd->n = listfields(ls);
1278       cd->k = 0;  /* list */
1279       break;
1280   }
1281 }
1282
1283 static int recfields (LexState *ls) {
1284   /* recfields -> { ',' recfield } [','] */
1285   int n = 1;  /* one has been read before */
1286   while (ls->token == ',') {
1287     next(ls);
1288     if (ls->token == ';' || ls->token == '}')
1289       break;
1290     recfield(ls);
1291     n++;
1292     if (n%RFIELDS_PER_FLUSH == 0)
1293       flush_record(ls, RFIELDS_PER_FLUSH);
1294   }
1295   flush_record(ls, n%RFIELDS_PER_FLUSH);
1296   return n;
1297 }
1298
1299 static int listfields (LexState *ls) {
1300   /* listfields -> { ',' exp1 } [','] */
1301   int n = 1;  /* one has been read before */
1302   while (ls->token == ',') {
1303     next(ls);
1304     if (ls->token == ';' || ls->token == '}')
1305       break;
1306     exp1(ls);
1307     n++;
1308     if (n%LFIELDS_PER_FLUSH == 0)
1309       flush_list(ls, n/LFIELDS_PER_FLUSH - 1, LFIELDS_PER_FLUSH);
1310   }
1311   flush_list(ls, n/LFIELDS_PER_FLUSH, n%LFIELDS_PER_FLUSH);
1312   return n;
1313 }
1314
1315 static void recfield (LexState *ls) {
1316   /* recfield -> (NAME | '['exp1']') = exp1 */
1317   switch (ls->token) {
1318     case NAME:
1319       code_string(ls, checkname(ls));
1320       break;
1321
1322     case '[':
1323       next(ls);
1324       exp1(ls);
1325       check(ls, ']');
1326       break;
1327
1328     default: luaX_error(ls, "NAME or `[' expected");
1329   }
1330   check(ls, '=');
1331   exp1(ls);
1332 }
1333