contrib/luasrcdiet/lua/lparser.lua

   1 --[[--------------------------------------------------------------------
   2
   3   lparser.lua: Lua 5.1 parser in Lua
   4   This file is part of LuaSrcDiet, based on Yueliang material.
   5
   6   Copyright (c) 2008 Kein-Hong Man <khman@users.sf.net>
   7   The COPYRIGHT file describes the conditions
   8   under which this software may be distributed.
   9
  10   See the ChangeLog for more information.
  11
  12 ----------------------------------------------------------------------]]
  13
  14 --[[--------------------------------------------------------------------
  15 -- NOTES:
  16 -- * This is a version of the native 5.1.x parser from Yueliang 0.4.0,
  17 --   with significant modifications to handle LuaSrcDiet's needs:
  18 --   (1) needs pre-built token tables instead of a module.method
  19 --   (2) lparser.error is an optional error handler (from llex)
  20 --   (3) not full parsing, currently fakes raw/unlexed constants
  21 --   (4) parser() returns globalinfo, localinfo tables
  22 -- * Please read technotes.txt for more technical details.
  23 -- * NO support for 'arg' vararg functions (LUA_COMPAT_VARARG)
  24 -- * A lot of the parser is unused, but might later be useful for
  25 --   full-on parsing and analysis for a few measly bytes saved.
  26 ----------------------------------------------------------------------]]
  27
  28 local base = _G
  29 local string = require "string"
  30 module "lparser"
  31 local _G = base.getfenv()
  32
  33 --[[--------------------------------------------------------------------
  34 -- variable and data structure initialization
  35 ----------------------------------------------------------------------]]
  36
  37 ----------------------------------------------------------------------
  38 -- initialization: main variables
  39 ----------------------------------------------------------------------
  40
  41 local toklist,                  -- grammar-only token tables (token table,
  42       seminfolist,              -- semantic information table, line number
  43       toklnlist,                -- table, cross-reference table)
  44       xreflist,
  45       tpos,                     -- token position
  46
  47       line,                     -- start line # for error messages
  48       lastln,                   -- last line # for ambiguous syntax chk
  49       tok, seminfo, ln, xref,   -- token, semantic info, line
  50       nameref,                  -- proper position of <name> token
  51       fs,                       -- current function state
  52       top_fs,                   -- top-level function state
  53
  54       globalinfo,               -- global variable information table
  55       globallookup,             -- global variable name lookup table
  56       localinfo,                -- local variable information table
  57       ilocalinfo,               -- inactive locals (prior to activation)
  58       ilocalrefs                -- corresponding references to activate
  59
  60 -- forward references for local functions
  61 local explist1, expr, block, exp1, body, chunk
  62
  63 ----------------------------------------------------------------------
  64 -- initialization: data structures
  65 ----------------------------------------------------------------------
  66
  67 local gmatch = string.gmatch
  68
  69 local block_follow = {}         -- lookahead check in chunk(), returnstat()
  70 for v in gmatch("else elseif end until <eof>", "%S+") do
  71   block_follow[v] = true
  72 end
  73
  74 local stat_call = {}            -- lookup for calls in stat()
  75 for v in gmatch("if while do for repeat function local return break", "%S+") do
  76   stat_call[v] = v.."_stat"
  77 end
  78
  79 local binopr_left = {}          -- binary operators, left priority
  80 local binopr_right = {}         -- binary operators, right priority
  81 for op, lt, rt in gmatch([[
  82 {+ 6 6}{- 6 6}{* 7 7}{/ 7 7}{% 7 7}
  83 {^ 10 9}{.. 5 4}
  84 {~= 3 3}{== 3 3}
  85 {< 3 3}{<= 3 3}{> 3 3}{>= 3 3}
  86 {and 2 2}{or 1 1}
  87 ]], "{(%S+)%s(%d+)%s(%d+)}") do
  88   binopr_left[op] = lt + 0
  89   binopr_right[op] = rt + 0
  90 end
  91
  92 local unopr = { ["not"] = true, ["-"] = true,
  93                 ["#"] = true, } -- unary operators
  94 local UNARY_PRIORITY = 8        -- priority for unary operators
  95
  96 --[[--------------------------------------------------------------------
  97 -- support functions
  98 ----------------------------------------------------------------------]]
  99
 100 ----------------------------------------------------------------------
 101 -- formats error message and throws error (duplicated from llex)
 102 -- * a simplified version, does not report what token was responsible
 103 ----------------------------------------------------------------------
 104
 105 local function errorline(s, line)
 106   local e = error or base.error
 107   e(string.format("(source):%d: %s", line or ln, s))
 108 end
 109
 110 ----------------------------------------------------------------------
 111 -- handles incoming token, semantic information pairs
 112 -- * NOTE: 'nextt' is named 'next' originally
 113 ----------------------------------------------------------------------
 114
 115 -- reads in next token
 116 local function nextt()
 117   lastln = toklnlist[tpos]
 118   tok, seminfo, ln, xref
 119     = toklist[tpos], seminfolist[tpos], toklnlist[tpos], xreflist[tpos]
 120   tpos = tpos + 1
 121 end
 122
 123 -- peek at next token (single lookahead for table constructor)
 124 local function lookahead()
 125   return toklist[tpos]
 126 end
 127
 128 ----------------------------------------------------------------------
 129 -- throws a syntax error, or if token expected is not there
 130 ----------------------------------------------------------------------
 131
 132 local function syntaxerror(msg)
 133   local tok = tok
 134   if tok ~= "<number>" and tok ~= "<string>" then
 135     if tok == "<name>" then tok = seminfo end
 136     tok = "'"..tok.."'"
 137   end
 138   errorline(msg.." near "..tok)
 139 end
 140
 141 local function error_expected(token)
 142   syntaxerror("'"..token.."' expected")
 143 end
 144
 145 ----------------------------------------------------------------------
 146 -- tests for a token, returns outcome
 147 -- * return value changed to boolean
 148 ----------------------------------------------------------------------
 149
 150 local function testnext(c)
 151   if tok == c then nextt(); return true end
 152 end
 153
 154 ----------------------------------------------------------------------
 155 -- check for existence of a token, throws error if not found
 156 ----------------------------------------------------------------------
 157
 158 local function check(c)
 159   if tok ~= c then error_expected(c) end
 160 end
 161
 162 ----------------------------------------------------------------------
 163 -- verify existence of a token, then skip it
 164 ----------------------------------------------------------------------
 165
 166 local function checknext(c)
 167   check(c); nextt()
 168 end
 169
 170 ----------------------------------------------------------------------
 171 -- throws error if condition not matched
 172 ----------------------------------------------------------------------
 173
 174 local function check_condition(c, msg)
 175   if not c then syntaxerror(msg) end
 176 end
 177
 178 ----------------------------------------------------------------------
 179 -- verifies token conditions are met or else throw error
 180 ----------------------------------------------------------------------
 181
 182 local function check_match(what, who, where)
 183   if not testnext(what) then
 184     if where == ln then
 185       error_expected(what)
 186     else
 187       syntaxerror("'"..what.."' expected (to close '"..who.."' at line "..where..")")
 188     end
 189   end
 190 end
 191
 192 ----------------------------------------------------------------------
 193 -- expect that token is a name, return the name
 194 ----------------------------------------------------------------------
 195
 196 local function str_checkname()
 197   check("<name>")
 198   local ts = seminfo
 199   nameref = xref
 200   nextt()
 201   return ts
 202 end
 203
 204 ----------------------------------------------------------------------
 205 -- adds given string s in string pool, sets e as VK
 206 ----------------------------------------------------------------------
 207
 208 local function codestring(e, s)
 209   e.k = "VK"
 210 end
 211
 212 ----------------------------------------------------------------------
 213 -- consume a name token, adds it to string pool
 214 ----------------------------------------------------------------------
 215
 216 local function checkname(e)
 217   codestring(e, str_checkname())
 218 end
 219
 220 --[[--------------------------------------------------------------------
 221 -- variable (global|local|upvalue) handling
 222 -- * to track locals and globals, we can extend Yueliang's minimal
 223 --   variable management code with little trouble
 224 -- * entry point is singlevar() for variable lookups
 225 -- * lookup tables (bl.locallist) are maintained awkwardly in the basic
 226 --   block data structures, PLUS the function data structure (this is
 227 --   an inelegant hack, since bl is nil for the top level of a function)
 228 ----------------------------------------------------------------------]]
 229
 230 ----------------------------------------------------------------------
 231 -- register a local variable, create local variable object, set in
 232 -- to-activate variable list
 233 -- * used in new_localvarliteral(), parlist(), fornum(), forlist(),
 234 --   localfunc(), localstat()
 235 ----------------------------------------------------------------------
 236
 237 local function new_localvar(name, special)
 238   local bl = fs.bl
 239   local locallist
 240   -- locate locallist in current block object or function root object
 241   if bl then
 242     locallist = bl.locallist
 243   else
 244     locallist = fs.locallist
 245   end
 246   -- build local variable information object and set localinfo
 247   local id = #localinfo + 1
 248   localinfo[id] = {             -- new local variable object
 249     name = name,                -- local variable name
 250     xref = { nameref },         -- xref, first value is declaration
 251     decl = nameref,             -- location of declaration, = xref[1]
 252   }
 253   if special then               -- "self" must be not be changed
 254     localinfo[id].isself = true
 255   end
 256   -- this can override a local with the same name in the same scope
 257   -- but first, keep it inactive until it gets activated
 258   local i = #ilocalinfo + 1
 259   ilocalinfo[i] = id
 260   ilocalrefs[i] = locallist
 261 end
 262
 263 ----------------------------------------------------------------------
 264 -- actually activate the variables so that they are visible
 265 -- * remember Lua semantics, e.g. RHS is evaluated first, then LHS
 266 -- * used in parlist(), forbody(), localfunc(), localstat(), body()
 267 ----------------------------------------------------------------------
 268
 269 local function adjustlocalvars(nvars)
 270   local sz = #ilocalinfo
 271   -- i goes from left to right, in order of local allocation, because
 272   -- of something like: local a,a,a = 1,2,3 which gives a = 3
 273   while nvars > 0 do
 274     nvars = nvars - 1
 275     local i = sz - nvars
 276     local id = ilocalinfo[i]            -- local's id
 277     local obj = localinfo[id]
 278     local name = obj.name               -- name of local
 279     obj.act = xref                      -- set activation location
 280     ilocalinfo[i] = nil
 281     local locallist = ilocalrefs[i]     -- ref to lookup table to update
 282     ilocalrefs[i] = nil
 283     local existing = locallist[name]    -- if existing, remove old first!
 284     if existing then                    -- do not overlap, set special
 285       obj = localinfo[existing]         -- form of rem, as -id
 286       obj.rem = -id
 287     end
 288     locallist[name] = id                -- activate, now visible to Lua
 289   end
 290 end
 291
 292 ----------------------------------------------------------------------
 293 -- remove (deactivate) variables in current scope (before scope exits)
 294 -- * zap entire locallist tables since we are not allocating registers
 295 -- * used in leaveblock(), close_func()
 296 ----------------------------------------------------------------------
 297
 298 local function removevars()
 299   local bl = fs.bl
 300   local locallist
 301   -- locate locallist in current block object or function root object
 302   if bl then
 303     locallist = bl.locallist
 304   else
 305     locallist = fs.locallist
 306   end
 307   -- enumerate the local list at current scope and deactivate 'em
 308   for name, id in base.pairs(locallist) do
 309     local obj = localinfo[id]
 310     obj.rem = xref                      -- set deactivation location
 311   end
 312 end
 313
 314 ----------------------------------------------------------------------
 315 -- creates a new local variable given a name
 316 -- * skips internal locals (those starting with '('), so internal
 317 --   locals never needs a corresponding adjustlocalvars() call
 318 -- * special is true for "self" which must not be optimized
 319 -- * used in fornum(), forlist(), parlist(), body()
 320 ----------------------------------------------------------------------
 321
 322 local function new_localvarliteral(name, special)
 323   if string.sub(name, 1, 1) == "(" then  -- can skip internal locals
 324     return
 325   end
 326   new_localvar(name, special)
 327 end
 328
 329 ----------------------------------------------------------------------
 330 -- search the local variable namespace of the given fs for a match
 331 -- * returns localinfo index
 332 -- * used only in singlevaraux()
 333 ----------------------------------------------------------------------
 334
 335 local function searchvar(fs, n)
 336   local bl = fs.bl
 337   local locallist
 338   if bl then
 339     locallist = bl.locallist
 340     while locallist do
 341       if locallist[n] then return locallist[n] end  -- found
 342       bl = bl.prev
 343       locallist = bl and bl.locallist
 344     end
 345   end
 346   locallist = fs.locallist
 347   return locallist[n] or -1  -- found or not found (-1)
 348 end
 349
 350 ----------------------------------------------------------------------
 351 -- handle locals, globals and upvalues and related processing
 352 -- * search mechanism is recursive, calls itself to search parents
 353 -- * used only in singlevar()
 354 ----------------------------------------------------------------------
 355
 356 local function singlevaraux(fs, n, var)
 357   if fs == nil then  -- no more levels?
 358     var.k = "VGLOBAL"  -- default is global variable
 359     return "VGLOBAL"
 360   else
 361     local v = searchvar(fs, n)  -- look up at current level
 362     if v >= 0 then
 363       var.k = "VLOCAL"
 364       var.id = v
 365       --  codegen may need to deal with upvalue here
 366       return "VLOCAL"
 367     else  -- not found at current level; try upper one
 368       if singlevaraux(fs.prev, n, var) == "VGLOBAL" then
 369         return "VGLOBAL"
 370       end
 371       -- else was LOCAL or UPVAL, handle here
 372       var.k = "VUPVAL"  -- upvalue in this level
 373       return "VUPVAL"
 374     end--if v
 375   end--if fs
 376 end
 377
 378 ----------------------------------------------------------------------
 379 -- consume a name token, creates a variable (global|local|upvalue)
 380 -- * used in prefixexp(), funcname()
 381 ----------------------------------------------------------------------
 382
 383 local function singlevar(v)
 384   local name = str_checkname()
 385   singlevaraux(fs, name, v)
 386   ------------------------------------------------------------------
 387   -- variable tracking
 388   ------------------------------------------------------------------
 389   if v.k == "VGLOBAL" then
 390     -- if global being accessed, keep track of it by creating an object
 391     local id = globallookup[name]
 392     if not id then
 393       id = #globalinfo + 1
 394       globalinfo[id] = {                -- new global variable object
 395         name = name,                    -- global variable name
 396         xref = { nameref },             -- xref, first value is declaration
 397       }
 398       globallookup[name] = id           -- remember it
 399     else
 400       local obj = globalinfo[id].xref
 401       obj[#obj + 1] = nameref           -- add xref
 402     end
 403   else
 404     -- local/upvalue is being accessed, keep track of it
 405     local id = v.id
 406     local obj = localinfo[id].xref
 407     obj[#obj + 1] = nameref             -- add xref
 408   end
 409 end
 410
 411 --[[--------------------------------------------------------------------
 412 -- state management functions with open/close pairs
 413 ----------------------------------------------------------------------]]
 414
 415 ----------------------------------------------------------------------
 416 -- enters a code unit, initializes elements
 417 ----------------------------------------------------------------------
 418
 419 local function enterblock(isbreakable)
 420   local bl = {}  -- per-block state
 421   bl.isbreakable = isbreakable
 422   bl.prev = fs.bl
 423   bl.locallist = {}
 424   fs.bl = bl
 425 end
 426
 427 ----------------------------------------------------------------------
 428 -- leaves a code unit, close any upvalues
 429 ----------------------------------------------------------------------
 430
 431 local function leaveblock()
 432   local bl = fs.bl
 433   removevars()
 434   fs.bl = bl.prev
 435 end
 436
 437 ----------------------------------------------------------------------
 438 -- opening of a function
 439 -- * top_fs is only for anchoring the top fs, so that parser() can
 440 --   return it to the caller function along with useful output
 441 -- * used in parser() and body()
 442 ----------------------------------------------------------------------
 443
 444 local function open_func()
 445   local new_fs  -- per-function state
 446   if not fs then  -- top_fs is created early
 447     new_fs = top_fs
 448   else
 449     new_fs = {}
 450   end
 451   new_fs.prev = fs  -- linked list of function states
 452   new_fs.bl = nil
 453   new_fs.locallist = {}
 454   fs = new_fs
 455 end
 456
 457 ----------------------------------------------------------------------
 458 -- closing of a function
 459 -- * used in parser() and body()
 460 ----------------------------------------------------------------------
 461
 462 local function close_func()
 463   removevars()
 464   fs = fs.prev
 465 end
 466
 467 --[[--------------------------------------------------------------------
 468 -- other parsing functions
 469 -- * for table constructor, parameter list, argument list
 470 ----------------------------------------------------------------------]]
 471
 472 ----------------------------------------------------------------------
 473 -- parse a function name suffix, for function call specifications
 474 -- * used in primaryexp(), funcname()
 475 ----------------------------------------------------------------------
 476
 477 local function field(v)
 478   -- field -> ['.' | ':'] NAME
 479   local key = {}
 480   nextt()  -- skip the dot or colon
 481   checkname(key)
 482   v.k = "VINDEXED"
 483 end
 484
 485 ----------------------------------------------------------------------
 486 -- parse a table indexing suffix, for constructors, expressions
 487 -- * used in recfield(), primaryexp()
 488 ----------------------------------------------------------------------
 489
 490 local function yindex(v)
 491   -- index -> '[' expr ']'
 492   nextt()  -- skip the '['
 493   expr(v)
 494   checknext("]")
 495 end
 496
 497 ----------------------------------------------------------------------
 498 -- parse a table record (hash) field
 499 -- * used in constructor()
 500 ----------------------------------------------------------------------
 501
 502 local function recfield(cc)
 503   -- recfield -> (NAME | '['exp1']') = exp1
 504   local key, val = {}, {}
 505   if tok == "<name>" then
 506     checkname(key)
 507   else-- tok == '['
 508     yindex(key)
 509   end
 510   checknext("=")
 511   expr(val)
 512 end
 513
 514 ----------------------------------------------------------------------
 515 -- emit a set list instruction if enough elements (LFIELDS_PER_FLUSH)
 516 -- * note: retained in this skeleton because it modifies cc.v.k
 517 -- * used in constructor()
 518 ----------------------------------------------------------------------
 519
 520 local function closelistfield(cc)
 521   if cc.v.k == "VVOID" then return end  -- there is no list item
 522   cc.v.k = "VVOID"
 523 end
 524
 525 ----------------------------------------------------------------------
 526 -- parse a table list (array) field
 527 -- * used in constructor()
 528 ----------------------------------------------------------------------
 529
 530 local function listfield(cc)
 531   expr(cc.v)
 532 end
 533
 534 ----------------------------------------------------------------------
 535 -- parse a table constructor
 536 -- * used in funcargs(), simpleexp()
 537 ----------------------------------------------------------------------
 538
 539 local function constructor(t)
 540   -- constructor -> '{' [ field { fieldsep field } [ fieldsep ] ] '}'
 541   -- field -> recfield | listfield
 542   -- fieldsep -> ',' | ';'
 543   local line = ln
 544   local cc = {}
 545   cc.v = {}
 546   cc.t = t
 547   t.k = "VRELOCABLE"
 548   cc.v.k = "VVOID"
 549   checknext("{")
 550   repeat
 551     if tok == "}" then break end
 552     -- closelistfield(cc) here
 553     local c = tok
 554     if c == "<name>" then  -- may be listfields or recfields
 555       if lookahead() ~= "=" then  -- look ahead: expression?
 556         listfield(cc)
 557       else
 558         recfield(cc)
 559       end
 560     elseif c == "[" then  -- constructor_item -> recfield
 561       recfield(cc)
 562     else  -- constructor_part -> listfield
 563       listfield(cc)
 564     end
 565   until not testnext(",") and not testnext(";")
 566   check_match("}", "{", line)
 567   -- lastlistfield(cc) here
 568 end
 569
 570 ----------------------------------------------------------------------
 571 -- parse the arguments (parameters) of a function declaration
 572 -- * used in body()
 573 ----------------------------------------------------------------------
 574
 575 local function parlist()
 576   -- parlist -> [ param { ',' param } ]
 577   local nparams = 0
 578   if tok ~= ")" then  -- is 'parlist' not empty?
 579     repeat
 580       local c = tok
 581       if c == "<name>" then  -- param -> NAME
 582         new_localvar(str_checkname())
 583         nparams = nparams + 1
 584       elseif c == "..." then
 585         nextt()
 586         fs.is_vararg = true
 587       else
 588         syntaxerror("<name> or '...' expected")
 589       end
 590     until fs.is_vararg or not testnext(",")
 591   end--if
 592   adjustlocalvars(nparams)
 593 end
 594
 595 ----------------------------------------------------------------------
 596 -- parse the parameters of a function call
 597 -- * contrast with parlist(), used in function declarations
 598 -- * used in primaryexp()
 599 ----------------------------------------------------------------------
 600
 601 local function funcargs(f)
 602   local args = {}
 603   local line = ln
 604   local c = tok
 605   if c == "(" then  -- funcargs -> '(' [ explist1 ] ')'
 606     if line ~= lastln then
 607       syntaxerror("ambiguous syntax (function call x new statement)")
 608     end
 609     nextt()
 610     if tok == ")" then  -- arg list is empty?
 611       args.k = "VVOID"
 612     else
 613       explist1(args)
 614     end
 615     check_match(")", "(", line)
 616   elseif c == "{" then  -- funcargs -> constructor
 617     constructor(args)
 618   elseif c == "<string>" then  -- funcargs -> STRING
 619     codestring(args, seminfo)
 620     nextt()  -- must use 'seminfo' before 'next'
 621   else
 622     syntaxerror("function arguments expected")
 623     return
 624   end--if c
 625   f.k = "VCALL"
 626 end
 627
 628 --[[--------------------------------------------------------------------
 629 -- mostly expression functions
 630 ----------------------------------------------------------------------]]
 631
 632 ----------------------------------------------------------------------
 633 -- parses an expression in parentheses or a single variable
 634 -- * used in primaryexp()
 635 ----------------------------------------------------------------------
 636
 637 local function prefixexp(v)
 638   -- prefixexp -> NAME | '(' expr ')'
 639   local c = tok
 640   if c == "(" then
 641     local line = ln
 642     nextt()
 643     expr(v)
 644     check_match(")", "(", line)
 645   elseif c == "<name>" then
 646     singlevar(v)
 647   else
 648     syntaxerror("unexpected symbol")
 649   end--if c
 650 end
 651
 652 ----------------------------------------------------------------------
 653 -- parses a prefixexp (an expression in parentheses or a single
 654 -- variable) or a function call specification
 655 -- * used in simpleexp(), assignment(), expr_stat()
 656 ----------------------------------------------------------------------
 657
 658 local function primaryexp(v)
 659   -- primaryexp ->
 660   --    prefixexp { '.' NAME | '[' exp ']' | ':' NAME funcargs | funcargs }
 661   prefixexp(v)
 662   while true do
 663     local c = tok
 664     if c == "." then  -- field
 665       field(v)
 666     elseif c == "[" then  -- '[' exp1 ']'
 667       local key = {}
 668       yindex(key)
 669     elseif c == ":" then  -- ':' NAME funcargs
 670       local key = {}
 671       nextt()
 672       checkname(key)
 673       funcargs(v)
 674     elseif c == "(" or c == "<string>" or c == "{" then  -- funcargs
 675       funcargs(v)
 676     else
 677       return
 678     end--if c
 679   end--while
 680 end
 681
 682 ----------------------------------------------------------------------
 683 -- parses general expression types, constants handled here
 684 -- * used in subexpr()
 685 ----------------------------------------------------------------------
 686
 687 local function simpleexp(v)
 688   -- simpleexp -> NUMBER | STRING | NIL | TRUE | FALSE | ... |
 689   --              constructor | FUNCTION body | primaryexp
 690   local c = tok
 691   if c == "<number>" then
 692     v.k = "VKNUM"
 693   elseif c == "<string>" then
 694     codestring(v, seminfo)
 695   elseif c == "nil" then
 696     v.k = "VNIL"
 697   elseif c == "true" then
 698     v.k = "VTRUE"
 699   elseif c == "false" then
 700     v.k = "VFALSE"
 701   elseif c == "..." then  -- vararg
 702     check_condition(fs.is_vararg == true,
 703                     "cannot use '...' outside a vararg function");
 704     v.k = "VVARARG"
 705   elseif c == "{" then  -- constructor
 706     constructor(v)
 707     return
 708   elseif c == "function" then
 709     nextt()
 710     body(v, false, ln)
 711     return
 712   else
 713     primaryexp(v)
 714     return
 715   end--if c
 716   nextt()
 717 end
 718
 719 ------------------------------------------------------------------------
 720 -- Parse subexpressions. Includes handling of unary operators and binary
 721 -- operators. A subexpr is given the rhs priority level of the operator
 722 -- immediately left of it, if any (limit is -1 if none,) and if a binop
 723 -- is found, limit is compared with the lhs priority level of the binop
 724 -- in order to determine which executes first.
 725 -- * recursively called
 726 -- * used in expr()
 727 ------------------------------------------------------------------------
 728
 729 local function subexpr(v, limit)
 730   -- subexpr -> (simpleexp | unop subexpr) { binop subexpr }
 731   --   * where 'binop' is any binary operator with a priority
 732   --     higher than 'limit'
 733   local op = tok
 734   local uop = unopr[op]
 735   if uop then
 736     nextt()
 737     subexpr(v, UNARY_PRIORITY)
 738   else
 739     simpleexp(v)
 740   end
 741   -- expand while operators have priorities higher than 'limit'
 742   op = tok
 743   local binop = binopr_left[op]
 744   while binop and binop > limit do
 745     local v2 = {}
 746     nextt()
 747     -- read sub-expression with higher priority
 748     local nextop = subexpr(v2, binopr_right[op])
 749     op = nextop
 750     binop = binopr_left[op]
 751   end
 752   return op  -- return first untreated operator
 753 end
 754
 755 ----------------------------------------------------------------------
 756 -- Expression parsing starts here. Function subexpr is entered with the
 757 -- left operator (which is non-existent) priority of -1, which is lower
 758 -- than all actual operators. Expr information is returned in parm v.
 759 -- * used in cond(), explist1(), index(), recfield(), listfield(),
 760 --   prefixexp(), while_stat(), exp1()
 761 ----------------------------------------------------------------------
 762
 763 -- this is a forward-referenced local
 764 function expr(v)
 765   -- expr -> subexpr
 766   subexpr(v, 0)
 767 end
 768
 769 --[[--------------------------------------------------------------------
 770 -- third level parsing functions
 771 ----------------------------------------------------------------------]]
 772
 773 ------------------------------------------------------------------------
 774 -- parse a variable assignment sequence
 775 -- * recursively called
 776 -- * used in expr_stat()
 777 ------------------------------------------------------------------------
 778
 779 local function assignment(v)
 780   local e = {}
 781   local c = v.v.k
 782   check_condition(c == "VLOCAL" or c == "VUPVAL" or c == "VGLOBAL"
 783                   or c == "VINDEXED", "syntax error")
 784   if testnext(",") then  -- assignment -> ',' primaryexp assignment
 785     local nv = {}  -- expdesc
 786     nv.v = {}
 787     primaryexp(nv.v)
 788     -- lparser.c deals with some register usage conflict here
 789     assignment(nv)
 790   else  -- assignment -> '=' explist1
 791     checknext("=")
 792     explist1(e)
 793     return  -- avoid default
 794   end
 795   e.k = "VNONRELOC"
 796 end
 797
 798 ----------------------------------------------------------------------
 799 -- parse a for loop body for both versions of the for loop
 800 -- * used in fornum(), forlist()
 801 ----------------------------------------------------------------------
 802
 803 local function forbody(nvars, isnum)
 804   -- forbody -> DO block
 805   checknext("do")
 806   enterblock(false)  -- scope for declared variables
 807   adjustlocalvars(nvars)
 808   block()
 809   leaveblock()  -- end of scope for declared variables
 810 end
 811
 812 ----------------------------------------------------------------------
 813 -- parse a numerical for loop, calls forbody()
 814 -- * used in for_stat()
 815 ----------------------------------------------------------------------
 816
 817 local function fornum(varname)
 818   -- fornum -> NAME = exp1, exp1 [, exp1] DO body
 819   local line = line
 820   new_localvarliteral("(for index)")
 821   new_localvarliteral("(for limit)")
 822   new_localvarliteral("(for step)")
 823   new_localvar(varname)
 824   checknext("=")
 825   exp1()  -- initial value
 826   checknext(",")
 827   exp1()  -- limit
 828   if testnext(",") then
 829     exp1()  -- optional step
 830   else
 831     -- default step = 1
 832   end
 833   forbody(1, true)
 834 end
 835
 836 ----------------------------------------------------------------------
 837 -- parse a generic for loop, calls forbody()
 838 -- * used in for_stat()
 839 ----------------------------------------------------------------------
 840
 841 local function forlist(indexname)
 842   -- forlist -> NAME {, NAME} IN explist1 DO body
 843   local e = {}
 844   -- create control variables
 845   new_localvarliteral("(for generator)")
 846   new_localvarliteral("(for state)")
 847   new_localvarliteral("(for control)")
 848   -- create declared variables
 849   new_localvar(indexname)
 850   local nvars = 1
 851   while testnext(",") do
 852     new_localvar(str_checkname())
 853     nvars = nvars + 1
 854   end
 855   checknext("in")
 856   local line = line
 857   explist1(e)
 858   forbody(nvars, false)
 859 end
 860
 861 ----------------------------------------------------------------------
 862 -- parse a function name specification
 863 -- * used in func_stat()
 864 ----------------------------------------------------------------------
 865
 866 local function funcname(v)
 867   -- funcname -> NAME {field} [':' NAME]
 868   local needself = false
 869   singlevar(v)
 870   while tok == "." do
 871     field(v)
 872   end
 873   if tok == ":" then
 874     needself = true
 875     field(v)
 876   end
 877   return needself
 878 end
 879
 880 ----------------------------------------------------------------------
 881 -- parse the single expressions needed in numerical for loops
 882 -- * used in fornum()
 883 ----------------------------------------------------------------------
 884
 885 -- this is a forward-referenced local
 886 function exp1()
 887   -- exp1 -> expr
 888   local e = {}
 889   expr(e)
 890 end
 891
 892 ----------------------------------------------------------------------
 893 -- parse condition in a repeat statement or an if control structure
 894 -- * used in repeat_stat(), test_then_block()
 895 ----------------------------------------------------------------------
 896
 897 local function cond()
 898   -- cond -> expr
 899   local v = {}
 900   expr(v)  -- read condition
 901 end
 902
 903 ----------------------------------------------------------------------
 904 -- parse part of an if control structure, including the condition
 905 -- * used in if_stat()
 906 ----------------------------------------------------------------------
 907
 908 local function test_then_block()
 909   -- test_then_block -> [IF | ELSEIF] cond THEN block
 910   nextt()  -- skip IF or ELSEIF
 911   cond()
 912   checknext("then")
 913   block()  -- 'then' part
 914 end
 915
 916 ----------------------------------------------------------------------
 917 -- parse a local function statement
 918 -- * used in local_stat()
 919 ----------------------------------------------------------------------
 920
 921 local function localfunc()
 922   -- localfunc -> NAME body
 923   local v, b = {}
 924   new_localvar(str_checkname())
 925   v.k = "VLOCAL"
 926   adjustlocalvars(1)
 927   body(b, false, ln)
 928 end
 929
 930 ----------------------------------------------------------------------
 931 -- parse a local variable declaration statement
 932 -- * used in local_stat()
 933 ----------------------------------------------------------------------
 934
 935 local function localstat()
 936   -- localstat -> NAME {',' NAME} ['=' explist1]
 937   local nvars = 0
 938   local e = {}
 939   repeat
 940     new_localvar(str_checkname())
 941     nvars = nvars + 1
 942   until not testnext(",")
 943   if testnext("=") then
 944     explist1(e)
 945   else
 946     e.k = "VVOID"
 947   end
 948   adjustlocalvars(nvars)
 949 end
 950
 951 ----------------------------------------------------------------------
 952 -- parse a list of comma-separated expressions
 953 -- * used in return_stat(), localstat(), funcargs(), assignment(),
 954 --   forlist()
 955 ----------------------------------------------------------------------
 956
 957 -- this is a forward-referenced local
 958 function explist1(e)
 959   -- explist1 -> expr { ',' expr }
 960   expr(e)
 961   while testnext(",") do
 962     expr(e)
 963   end
 964 end
 965
 966 ----------------------------------------------------------------------
 967 -- parse function declaration body
 968 -- * used in simpleexp(), localfunc(), func_stat()
 969 ----------------------------------------------------------------------
 970
 971 -- this is a forward-referenced local
 972 function body(e, needself, line)
 973   -- body ->  '(' parlist ')' chunk END
 974   open_func()
 975   checknext("(")
 976   if needself then
 977     new_localvarliteral("self", true)
 978     adjustlocalvars(1)
 979   end
 980   parlist()
 981   checknext(")")
 982   chunk()
 983   check_match("end", "function", line)
 984   close_func()
 985 end
 986
 987 ----------------------------------------------------------------------
 988 -- parse a code block or unit
 989 -- * used in do_stat(), while_stat(), forbody(), test_then_block(),
 990 --   if_stat()
 991 ----------------------------------------------------------------------
 992
 993 -- this is a forward-referenced local
 994 function block()
 995   -- block -> chunk
 996   enterblock(false)
 997   chunk()
 998   leaveblock()
 999 end
1000
1001 --[[--------------------------------------------------------------------
1002 -- second level parsing functions, all with '_stat' suffix
1003 -- * since they are called via a table lookup, they cannot be local
1004 --   functions (a lookup table of local functions might be smaller...)
1005 -- * stat() -> *_stat()
1006 ----------------------------------------------------------------------]]
1007
1008 ----------------------------------------------------------------------
1009 -- initial parsing for a for loop, calls fornum() or forlist()
1010 -- * removed 'line' parameter (used to set debug information only)
1011 -- * used in stat()
1012 ----------------------------------------------------------------------
1013
1014 function for_stat()
1015   -- stat -> for_stat -> FOR (fornum | forlist) END
1016   local line = line
1017   enterblock(true)  -- scope for loop and control variables
1018   nextt()  -- skip 'for'
1019   local varname = str_checkname()  -- first variable name
1020   local c = tok
1021   if c == "=" then
1022     fornum(varname)
1023   elseif c == "," or c == "in" then
1024     forlist(varname)
1025   else
1026     syntaxerror("'=' or 'in' expected")
1027   end
1028   check_match("end", "for", line)
1029   leaveblock()  -- loop scope (`break' jumps to this point)
1030 end
1031
1032 ----------------------------------------------------------------------
1033 -- parse a while-do control structure, body processed by block()
1034 -- * used in stat()
1035 ----------------------------------------------------------------------
1036
1037 function while_stat()
1038   -- stat -> while_stat -> WHILE cond DO block END
1039   local line = line
1040   nextt()  -- skip WHILE
1041   cond()  -- parse condition
1042   enterblock(true)
1043   checknext("do")
1044   block()
1045   check_match("end", "while", line)
1046   leaveblock()
1047 end
1048
1049 ----------------------------------------------------------------------
1050 -- parse a repeat-until control structure, body parsed by chunk()
1051 -- * originally, repeatstat() calls breakstat() too if there is an
1052 --   upvalue in the scope block; nothing is actually lexed, it is
1053 --   actually the common code in breakstat() for closing of upvalues
1054 -- * used in stat()
1055 ----------------------------------------------------------------------
1056
1057 function repeat_stat()
1058   -- stat -> repeat_stat -> REPEAT block UNTIL cond
1059   local line = line
1060   enterblock(true)  -- loop block
1061   enterblock(false)  -- scope block
1062   nextt()  -- skip REPEAT
1063   chunk()
1064   check_match("until", "repeat", line)
1065   cond()
1066   -- close upvalues at scope level below
1067   leaveblock()  -- finish scope
1068   leaveblock()  -- finish loop
1069 end
1070
1071 ----------------------------------------------------------------------
1072 -- parse an if control structure
1073 -- * used in stat()
1074 ----------------------------------------------------------------------
1075
1076 function if_stat()
1077   -- stat -> if_stat -> IF cond THEN block
1078   --                    {ELSEIF cond THEN block} [ELSE block] END
1079   local line = line
1080   local v = {}
1081   test_then_block()  -- IF cond THEN block
1082   while tok == "elseif" do
1083     test_then_block()  -- ELSEIF cond THEN block
1084   end
1085   if tok == "else" then
1086     nextt()  -- skip ELSE
1087     block()  -- 'else' part
1088   end
1089   check_match("end", "if", line)
1090 end
1091
1092 ----------------------------------------------------------------------
1093 -- parse a return statement
1094 -- * used in stat()
1095 ----------------------------------------------------------------------
1096
1097 function return_stat()
1098   -- stat -> return_stat -> RETURN explist
1099   local e = {}
1100   nextt()  -- skip RETURN
1101   local c = tok
1102   if block_follow[c] or c == ";" then
1103     -- return no values
1104   else
1105     explist1(e)  -- optional return values
1106   end
1107 end
1108
1109 ----------------------------------------------------------------------
1110 -- parse a break statement
1111 -- * used in stat()
1112 ----------------------------------------------------------------------
1113
1114 function break_stat()
1115   -- stat -> break_stat -> BREAK
1116   local bl = fs.bl
1117   nextt()  -- skip BREAK
1118   while bl and not bl.isbreakable do -- find a breakable block
1119     bl = bl.prev
1120   end
1121   if not bl then
1122     syntaxerror("no loop to break")
1123   end
1124 end
1125
1126 ----------------------------------------------------------------------
1127 -- parse a function call with no returns or an assignment statement
1128 -- * the struct with .prev is used for name searching in lparse.c,
1129 --   so it is retained for now; present in assignment() also
1130 -- * used in stat()
1131 ----------------------------------------------------------------------
1132
1133 function expr_stat()
1134   -- stat -> expr_stat -> func | assignment
1135   local v = {}
1136   v.v = {}
1137   primaryexp(v.v)
1138   if v.v.k == "VCALL" then  -- stat -> func
1139     -- call statement uses no results
1140   else  -- stat -> assignment
1141     v.prev = nil
1142     assignment(v)
1143   end
1144 end
1145
1146 ----------------------------------------------------------------------
1147 -- parse a function statement
1148 -- * used in stat()
1149 ----------------------------------------------------------------------
1150
1151 function function_stat()
1152   -- stat -> function_stat -> FUNCTION funcname body
1153   local line = line
1154   local v, b = {}, {}
1155   nextt()  -- skip FUNCTION
1156   local needself = funcname(v)
1157   body(b, needself, line)
1158 end
1159
1160 ----------------------------------------------------------------------
1161 -- parse a simple block enclosed by a DO..END pair
1162 -- * used in stat()
1163 ----------------------------------------------------------------------
1164
1165 function do_stat()
1166   -- stat -> do_stat -> DO block END
1167   local line = line
1168   nextt()  -- skip DO
1169   block()
1170   check_match("end", "do", line)
1171 end
1172
1173 ----------------------------------------------------------------------
1174 -- parse a statement starting with LOCAL
1175 -- * used in stat()
1176 ----------------------------------------------------------------------
1177
1178 function local_stat()
1179   -- stat -> local_stat -> LOCAL FUNCTION localfunc
1180   --                    -> LOCAL localstat
1181   nextt()  -- skip LOCAL
1182   if testnext("function") then  -- local function?
1183     localfunc()
1184   else
1185     localstat()
1186   end
1187 end
1188
1189 --[[--------------------------------------------------------------------
1190 -- main functions, top level parsing functions
1191 -- * accessible functions are: init(lexer), parser()
1192 -- * [entry] -> parser() -> chunk() -> stat()
1193 ----------------------------------------------------------------------]]
1194
1195 ----------------------------------------------------------------------
1196 -- initial parsing for statements, calls '_stat' suffixed functions
1197 -- * used in chunk()
1198 ----------------------------------------------------------------------
1199
1200 local function stat()
1201   -- stat -> if_stat while_stat do_stat for_stat repeat_stat
1202   --         function_stat local_stat return_stat break_stat
1203   --         expr_stat
1204   line = ln  -- may be needed for error messages
1205   local c = tok
1206   local fn = stat_call[c]
1207   -- handles: if while do for repeat function local return break
1208   if fn then
1209     _G[fn]()
1210     -- return or break must be last statement
1211     if c == "return" or c == "break" then return true end
1212   else
1213     expr_stat()
1214   end
1215   return false
1216 end
1217
1218 ----------------------------------------------------------------------
1219 -- parse a chunk, which consists of a bunch of statements
1220 -- * used in parser(), body(), block(), repeat_stat()
1221 ----------------------------------------------------------------------
1222
1223 -- this is a forward-referenced local
1224 function chunk()
1225   -- chunk -> { stat [';'] }
1226   local islast = false
1227   while not islast and not block_follow[tok] do
1228     islast = stat()
1229     testnext(";")
1230   end
1231 end
1232
1233 ----------------------------------------------------------------------
1234 -- performs parsing, returns parsed data structure
1235 ----------------------------------------------------------------------
1236
1237 function parser()
1238   open_func()
1239   fs.is_vararg = true  -- main func. is always vararg
1240   nextt()  -- read first token
1241   chunk()
1242   check("<eof>")
1243   close_func()
1244   return globalinfo, localinfo
1245 end
1246
1247 ----------------------------------------------------------------------
1248 -- initialization function
1249 ----------------------------------------------------------------------
1250
1251 function init(tokorig, seminfoorig, toklnorig)
1252   tpos = 1                      -- token position
1253   top_fs = {}                   -- reset top level function state
1254   ------------------------------------------------------------------
1255   -- set up grammar-only token tables; impedance-matching...
1256   -- note that constants returned by the lexer is source-level, so
1257   -- for now, fake(!) constant tokens (TK_NUMBER|TK_STRING|TK_LSTRING)
1258   ------------------------------------------------------------------
1259   local j = 1
1260   toklist, seminfolist, toklnlist, xreflist = {}, {}, {}, {}
1261   for i = 1, #tokorig do
1262     local tok = tokorig[i]
1263     local yep = true
1264     if tok == "TK_KEYWORD" or tok == "TK_OP" then
1265       tok = seminfoorig[i]
1266     elseif tok == "TK_NAME" then
1267       tok = "<name>"
1268       seminfolist[j] = seminfoorig[i]
1269     elseif tok == "TK_NUMBER" then
1270       tok = "<number>"
1271       seminfolist[j] = 0  -- fake!
1272     elseif tok == "TK_STRING" or tok == "TK_LSTRING" then
1273       tok = "<string>"
1274       seminfolist[j] = ""  -- fake!
1275     elseif tok == "TK_EOS" then
1276       tok = "<eof>"
1277     else
1278       -- non-grammar tokens; ignore them
1279       yep = false
1280     end
1281     if yep then  -- set rest of the information
1282       toklist[j] = tok
1283       toklnlist[j] = toklnorig[i]
1284       xreflist[j] = i
1285       j = j + 1
1286     end
1287   end--for
1288   ------------------------------------------------------------------
1289   -- initialize data structures for variable tracking
1290   ------------------------------------------------------------------
1291   globalinfo, globallookup, localinfo = {}, {}, {}
1292   ilocalinfo, ilocalrefs = {}, {}
1293 end
1294
1295 return _G