src/compiler/lexer.lua

   1 ----------------------------------------------------------------------
   2 -- Metalua:  $Id: mll.lua,v 1.3 2006/11/15 09:07:50 fab13n Exp $
   3 --
   4 -- Summary: generic Lua-style lexer definition. You need this plus
   5 -- some keyword additions to create the complete Lua lexer,
   6 -- as is done in mlp_lexer.lua.
   7 --
   8 -- TODO:
   9 --
  10 -- * Make it possible to change lexer on the fly. This implies the
  11 --   ability to easily undo any pre-extracted tokens;
  12 --
  13 -- * Make it easy to define new flavors of strings. Replacing the
  14 --   lexer.patterns.long_string regexp by an extensible list, with
  15 --   customizable token tag, would probably be enough. Maybe add:
  16 --   + an index of capture for the regexp, that would specify
  17 --     which capture holds the content of the string-like token
  18 --   + a token tag
  19 --   + or a string->string transformer function.
  20 --
  21 -- * There are some _G.table to prevent a namespace clash which has
  22 --   now disappered. remove them.
  23 ----------------------------------------------------------------------
  24 --
  25 -- Copyright (c) 2006, Fabien Fleutot <metalua@gmail.com>.
  26 --
  27 -- This software is released under the MIT Licence, see licence.txt
  28 -- for details.
  29 --
  30 ----------------------------------------------------------------------
  31
  32 module ("lexer", package.seeall)
  33
  34 require 'metalua.runtime'
  35
  36
  37 lexer = { alpha={ }, sym={ } }
  38 lexer.__index=lexer
  39
  40 local debugf = function() end
  41 --local debugf=printf
  42
  43 ----------------------------------------------------------------------
  44 -- Patterns used by [lexer:extract] to decompose the raw string into
  45 -- correctly tagged tokens.
  46 ----------------------------------------------------------------------
  47 lexer.patterns = {
  48    spaces              = "^[ \r\n\t]*()",
  49    short_comment       = "^%-%-([^\n]*)()\n",
  50    final_short_comment = "^%-%-([^\n]*)()$",
  51    long_comment        = "^%-%-%[(=*)%[\n?(.-)%]%1%]()",
  52    long_string         = "^%[(=*)%[\n?(.-)%]%1%]()",
  53    number_mantissa     = {
  54       "^%d+%.?%d*()",
  55       "^%d*%.%d+()" },
  56    number_exponant = "^[eE][%+%-]?%d+()",
  57    number_hex      = "^0[xX]%x+()",
  58    word            = "^([%a_][%w_]*)()"
  59 }
  60
  61 ----------------------------------------------------------------------
  62 -- unescape a whole string, applying [unesc_digits] and
  63 -- [unesc_letter] as many times as required.
  64 ----------------------------------------------------------------------
  65 local function unescape_string (s)
  66
  67    -- Turn the digits of an escape sequence into the corresponding
  68    -- character, e.g. [unesc_digits("123") == string.char(123)].
  69    local function unesc_digits (backslashes, digits)
  70       if #backslashes%2==0 then
  71          -- Even number of backslashes, they escape each other, not the digits.
  72          -- Return them so that unesc_letter() can treaat them
  73          return backslashes..digits
  74       else
  75          -- Remove the odd backslash, which escapes the number sequence.
  76          -- The rest will be returned and parsed by unesc_letter()
  77          backslashes = backslashes :sub (1,-2)
  78       end
  79       local k, j, i = digits:reverse():byte(1, 3)
  80       local z = _G.string.byte "0"
  81       local code = (k or z) + 10*(j or z) + 100*(i or z) - 111*z
  82       if code > 255 then
  83          error ("Illegal escape sequence '\\"..digits.."' in string: ASCII codes must be in [0..255]")
  84       end
  85       return backslashes .. string.char (code)
  86    end
  87
  88    -- Take a letter [x], and returns the character represented by the
  89    -- sequence ['\\'..x], e.g. [unesc_letter "n" == "\n"].
  90    local function unesc_letter(x)
  91       local t = {
  92          a = "\a", b = "\b", f = "\f",
  93          n = "\n", r = "\r", t = "\t", v = "\v",
  94          ["\\"] = "\\", ["'"] = "'", ['"'] = '"', ["\n"] = "\n" }
  95       return t[x] or error([[Unknown escape sequence '\]]..x..[[']])
  96    end
  97
  98    return s
  99       :gsub ("(\\+)([0-9][0-9]?[0-9]?)", unesc_digits)
 100       :gsub ("\\(%D)",unesc_letter)
 101 end
 102
 103 lexer.extractors = {
 104    "skip_whitespaces_and_comments",
 105    "extract_short_string", "extract_word", "extract_number",
 106    "extract_long_string", "extract_symbol" }
 107
 108 lexer.token_metatable = {
 109 --         __tostring = function(a)
 110 --            return string.format ("`%s{'%s'}",a.tag, a[1])
 111 --         end
 112 }
 113
 114 lexer.lineinfo_metatable = { }
 115 --[[
 116 -- The presence of this function prevents serialization by Pluto,
 117 -- I can't figure out why :(
 118 function lexer.lineinfo_metatable:__tostring()
 119    local txt = string.format("%s:%i(%i,%i)", self[4], self[3], self[1], self[2])
 120    if self.comments then
 121       acc = { }
 122       for comment in ivalues(self.comments) do
 123          local content, loc1, loc2, kind = unpack(comment)
 124          table.insert (acc, string.format ("%s@%i..%i:%q", kind, loc1, loc2, content))
 125       end
 126       txt = txt.."["..table.concat(acc,"; ").."]"
 127    end
 128    return txt
 129 end
 130 --]]
 131
 132 ----------------------------------------------------------------------
 133 -- Really extract next token fron the raw string
 134 -- (and update the index).
 135 -- loc: offset of the position just after spaces and comments
 136 -- previous_i: offset in src before extraction began
 137 ----------------------------------------------------------------------
 138 function lexer:extract ()
 139    local previous_i = self.i
 140    local loc = self.i
 141    local eof, token
 142
 143    -- Put line info, comments and metatable arount the tag and content
 144    -- provided by extractors, thus returning a complete lexer token.
 145    -- first_line: line # at the beginning of token
 146    -- first_column_offset: char # of the last '\n' before beginning of token
 147    -- i: scans from beginning of prefix spaces/comments to end of token.
 148    local function build_token (tag, content)
 149       assert (tag and content)
 150       local i, first_line, first_column_offset, previous_line_length =
 151          previous_i, self.line, self.column_offset, nil
 152
 153       -- update self.line and first_line. i := indexes of '\n' chars
 154       while true do
 155          i = self.src :find ("\n", i+1, true)
 156          if not i or i>self.i then break end -- no more '\n' until end of token
 157          previous_line_length = i - self.column_offset
 158          if loc and i <= loc then -- '\n' before beginning of token
 159             first_column_offset = i
 160             first_line = first_line+1
 161          end
 162          self.line   = self.line+1
 163          self.column_offset = i
 164       end
 165
 166       -- lineinfo entries: [1]=line, [2]=column, [3]=char, [4]=filename
 167       local fli = { first_line, loc-first_column_offset, loc, self.src_name }
 168       local lli = { self.line, self.i-self.column_offset-1, self.i-1, self.src_name }
 169       --Pluto barfes when the metatable is set:(
 170       setmetatable(fli, lexer.lineinfo_metatable)
 171       setmetatable(lli, lexer.lineinfo_metatable)
 172       local a = { tag = tag, lineinfo = { first=fli, last=lli }, content }
 173       if lli[2]==-1 then lli[1], lli[2] = lli[1]-1, previous_line_length-1 end
 174       if #self.attached_comments > 0 then
 175          a.lineinfo.comments = self.attached_comments
 176          fli.comments = self.attached_comments
 177          if self.lineinfo_last then
 178             self.lineinfo_last.comments = self.attached_comments
 179          end
 180       end
 181       self.attached_comments = { }
 182       return setmetatable (a, self.token_metatable)
 183    end --</function build_token>
 184
 185    for ext_idx, extractor in ipairs(self.extractors) do
 186       -- printf("method = %s", method)
 187       local tag, content = self [extractor] (self)
 188       -- [loc] is placed just after the leading whitespaces and comments;
 189       -- for this to work, the whitespace extractor *must be* at index 1.
 190       if ext_idx==1 then loc = self.i end
 191
 192       if tag then
 193          --printf("`%s{ %q }\t%i", tag, content, loc);
 194          return build_token (tag, content)
 195       end
 196    end
 197
 198    error "None of the lexer extractors returned anything!"
 199 end
 200
 201 ----------------------------------------------------------------------
 202 -- skip whites and comments
 203 -- FIXME: doesn't take into account:
 204 -- - unterminated long comments
 205 -- - short comments at last line without a final \n
 206 ----------------------------------------------------------------------
 207 function lexer:skip_whitespaces_and_comments()
 208    local table_insert = _G.table.insert
 209    repeat -- loop as long as a space or comment chunk is found
 210       local _, j
 211       local again = false
 212       local last_comment_content = nil
 213       -- skip spaces
 214       self.i = self.src:match (self.patterns.spaces, self.i)
 215       -- skip a long comment if any
 216       _, last_comment_content, j =
 217          self.src :match (self.patterns.long_comment, self.i)
 218       if j then
 219          table_insert(self.attached_comments,
 220                          {last_comment_content, self.i, j, "long"})
 221          self.i=j; again=true
 222       end
 223       -- skip a short comment if any
 224       last_comment_content, j = self.src:match (self.patterns.short_comment, self.i)
 225       if j then
 226          table_insert(self.attached_comments,
 227                          {last_comment_content, self.i, j, "short"})
 228          self.i=j; again=true
 229       end
 230       if self.i>#self.src then return "Eof", "eof" end
 231    until not again
 232
 233    if self.src:match (self.patterns.final_short_comment, self.i) then
 234       return "Eof", "eof" end
 235    --assert (not self.src:match(self.patterns.short_comment, self.i))
 236    --assert (not self.src:match(self.patterns.long_comment, self.i))
 237    -- --assert (not self.src:match(self.patterns.spaces, self.i))
 238    return
 239 end
 240
 241 ----------------------------------------------------------------------
 242 -- extract a '...' or "..." short string
 243 ----------------------------------------------------------------------
 244 function lexer:extract_short_string()
 245    -- [k] is the first unread char, [self.i] points to [k] in [self.src]
 246    local j, k = self.i, self.src :sub (self.i,self.i)
 247    if k~="'" and k~='"' then return end
 248    local i = self.i + 1
 249    local j = i
 250    while true do
 251       -- k = opening char: either simple-quote or double-quote
 252       -- i = index of beginning-of-string
 253       -- x = next "interesting" character
 254       -- j = position after interesting char
 255       -- y = char just after x
 256       local x, y
 257       x, j, y = self.src :match ("([\\\r\n"..k.."])()(.?)", j)
 258       if x == '\\' then j=j+1  -- don't parse escaped char
 259       elseif x == k then break -- unescaped end of string
 260       else -- eof or '\r' or '\n' reached before end of string
 261          assert (not x or x=="\r" or x=="\n")
 262          error "Unterminated string"
 263       end
 264    end
 265    self.i = j
 266
 267    return "String", unescape_string (self.src:sub (i,j-2))
 268 end
 269
 270 ----------------------------------------------------------------------
 271 --
 272 ----------------------------------------------------------------------
 273 function lexer:extract_word()
 274    -- Id / keyword
 275    local word, j = self.src:match (self.patterns.word, self.i)
 276    if word then
 277       self.i = j
 278       if self.alpha [word] then return "Keyword", word
 279       else return "Id", word end
 280    end
 281 end
 282
 283 ----------------------------------------------------------------------
 284 --
 285 ----------------------------------------------------------------------
 286 function lexer:extract_number()
 287    -- Number
 288    local j = self.src:match(self.patterns.number_hex, self.i)
 289    if not j then
 290       j = self.src:match (self.patterns.number_mantissa[1], self.i) or
 291           self.src:match (self.patterns.number_mantissa[2], self.i)
 292       if j then
 293          j = self.src:match (self.patterns.number_exponant, j) or j;
 294       end
 295    end
 296    if not j then return end
 297    -- Number found, interpret with tonumber() and return it
 298    local n = tonumber (self.src:sub (self.i, j-1))
 299    self.i = j
 300    return "Number", n
 301 end
 302
 303 ----------------------------------------------------------------------
 304 --
 305 ----------------------------------------------------------------------
 306 function lexer:extract_long_string()
 307    -- Long string
 308    local _, content, j = self.src:match (self.patterns.long_string, self.i)
 309    if j then self.i = j; return "String", content end
 310 end
 311
 312 ----------------------------------------------------------------------
 313 --
 314 ----------------------------------------------------------------------
 315 function lexer:extract_symbol()
 316    -- compound symbol
 317    local k = self.src:sub (self.i,self.i)
 318    local symk = self.sym [k]
 319    if not symk then
 320       self.i = self.i + 1
 321       return "Keyword", k
 322    end
 323    for _, sym in pairs (symk) do
 324       if sym == self.src:sub (self.i, self.i + #sym - 1) then
 325          self.i = self.i + #sym;
 326          return "Keyword", sym
 327       end
 328    end
 329    -- single char symbol
 330    self.i = self.i+1
 331    return "Keyword", k
 332 end
 333
 334 ----------------------------------------------------------------------
 335 -- Add a keyword to the list of keywords recognized by the lexer.
 336 ----------------------------------------------------------------------
 337 function lexer:add (w, ...)
 338    assert(not ..., "lexer:add() takes only one arg, although possibly a table")
 339    if type (w) == "table" then
 340       for _, x in ipairs (w) do self:add (x) end
 341    else
 342       if w:match (self.patterns.word .. "$") then self.alpha [w] = true
 343       elseif w:match "^%p%p+$" then
 344          local k = w:sub(1,1)
 345          local list = self.sym [k]
 346          if not list then list = { }; self.sym [k] = list end
 347          _G.table.insert (list, w)
 348       elseif w:match "^%p$" then return
 349       else error "Invalid keyword" end
 350    end
 351 end
 352
 353 ----------------------------------------------------------------------
 354 -- Return the [n]th next token, without consumming it.
 355 -- [n] defaults to 1. If it goes pass the end of the stream, an EOF
 356 -- token is returned.
 357 ----------------------------------------------------------------------
 358 function lexer:peek (n)
 359    if not n then n=1 end
 360    if n > #self.peeked then
 361       for i = #self.peeked+1, n do
 362          self.peeked [i] = self:extract()
 363       end
 364    end
 365   return self.peeked [n]
 366 end
 367
 368 ----------------------------------------------------------------------
 369 -- Return the [n]th next token, removing it as well as the 0..n-1
 370 -- previous tokens. [n] defaults to 1. If it goes pass the end of the
 371 -- stream, an EOF token is returned.
 372 ----------------------------------------------------------------------
 373 function lexer:next (n)
 374    n = n or 1
 375    self:peek (n)
 376    local a
 377    for i=1,n do
 378       a = _G.table.remove (self.peeked, 1)
 379       if a then
 380          --debugf ("lexer:next() ==> %s %s",
 381          --        table.tostring(a), tostring(a))
 382       end
 383       self.lastline = a.lineinfo.last[1]
 384    end
 385    self.lineinfo_last = a.lineinfo.last
 386    return a or eof_token
 387 end
 388
 389 ----------------------------------------------------------------------
 390 -- Returns an object which saves the stream's current state.
 391 ----------------------------------------------------------------------
 392 -- FIXME there are more fields than that to save
 393 function lexer:save () return { self.i; _G.table.cat(self.peeked) } end
 394
 395 ----------------------------------------------------------------------
 396 -- Restore the stream's state, as saved by method [save].
 397 ----------------------------------------------------------------------
 398 -- FIXME there are more fields than that to restore
 399 function lexer:restore (s) self.i=s[1]; self.peeked=s[2] end
 400
 401 ----------------------------------------------------------------------
 402 -- Resynchronize: cancel any token in self.peeked, by emptying the
 403 -- list and resetting the indexes
 404 ----------------------------------------------------------------------
 405 function lexer:sync()
 406    local p1 = self.peeked[1]
 407    if p1 then
 408       li = p1.lineinfo.first
 409       self.line, self.i = li[1], li[3]
 410       self.column_offset = self.i - li[2]
 411       self.peeked = { }
 412       self.attached_comments = p1.lineinfo.first.comments or { }
 413    end
 414 end
 415
 416 ----------------------------------------------------------------------
 417 -- Take the source and offset of an old lexer.
 418 ----------------------------------------------------------------------
 419 function lexer:takeover(old)
 420    self:sync()
 421    self.line, self.column_offset, self.i, self.src, self.attached_comments =
 422       old.line, old.column_offset, old.i, old.src, old.attached_comments
 423    return self
 424 end
 425
 426 -- function lexer:lineinfo()
 427 --      if self.peeked[1] then return self.peeked[1].lineinfo.first
 428 --     else return { self.line, self.i-self.column_offset, self.i } end
 429 -- end
 430
 431
 432 ----------------------------------------------------------------------
 433 -- Return the current position in the sources. This position is between
 434 -- two tokens, and can be within a space / comment area, and therefore
 435 -- have a non-null width. :lineinfo_left() returns the beginning of the
 436 -- separation area, :lineinfo_right() returns the end of that area.
 437 --
 438 --    ____ last consummed token    ____ first unconsummed token
 439 --   /                            /
 440 -- XXXXX  <spaces and comments> YYYYY
 441 --      \____                    \____
 442 --           :lineinfo_left()         :lineinfo_right()
 443 ----------------------------------------------------------------------
 444 function lexer:lineinfo_right()
 445    return self:peek(1).lineinfo.first
 446 end
 447
 448 function lexer:lineinfo_left()
 449    return self.lineinfo_last
 450 end
 451
 452 ----------------------------------------------------------------------
 453 -- Create a new lexstream.
 454 ----------------------------------------------------------------------
 455 function lexer:newstream (src_or_stream, name)
 456    name = name or "?"
 457    if type(src_or_stream)=='table' then -- it's a stream
 458       return setmetatable ({ }, self) :takeover (src_or_stream)
 459    elseif type(src_or_stream)=='string' then -- it's a source string
 460       local src = src_or_stream
 461       local stream = {
 462          src_name      = name;   -- Name of the file
 463          src           = src;    -- The source, as a single string
 464          peeked        = { };    -- Already peeked, but not discarded yet, tokens
 465          i             = 1;      -- Character offset in src
 466          line          = 1;      -- Current line number
 467          column_offset = 0;      -- distance from beginning of file to last '\n'
 468          attached_comments = { },-- comments accumulator
 469          lineinfo_last = { 1, 1, 1, name }
 470       }
 471       setmetatable (stream, self)
 472
 473       -- skip initial sharp-bang for unix scripts
 474       -- FIXME: redundant with mlp.chunk()
 475       if src and src :match "^#" then stream.i = src :find "\n" + 1 end
 476       return stream
 477    else
 478       assert(false, ":newstream() takes a source string or a stream, not a "..
 479                     type(src_or_stream))
 480    end
 481 end
 482
 483 ----------------------------------------------------------------------
 484 -- if there's no ... args, return the token a (whose truth value is
 485 -- true) if it's a `Keyword{ }, or nil.  If there are ... args, they
 486 -- have to be strings. if the token a is a keyword, and it's content
 487 -- is one of the ... args, then returns it (it's truth value is
 488 -- true). If no a keyword or not in ..., return nil.
 489 ----------------------------------------------------------------------
 490 function lexer:is_keyword (a, ...)
 491    if not a or a.tag ~= "Keyword" then return false end
 492    local words = {...}
 493    if #words == 0 then return a[1] end
 494    for _, w in ipairs (words) do
 495       if w == a[1] then return w end
 496    end
 497    return false
 498 end
 499
 500 ----------------------------------------------------------------------
 501 -- Cause an error if the next token isn't a keyword whose content
 502 -- is listed among ... args (which have to be strings).
 503 ----------------------------------------------------------------------
 504 function lexer:check (...)
 505    local words = {...}
 506    local a = self:next()
 507    local function err ()
 508       error ("Got " .. tostring (a) ..
 509              ", expected one of these keywords : '" ..
 510              _G.table.concat (words,"', '") .. "'") end
 511
 512    if not a or a.tag ~= "Keyword" then err () end
 513    if #words == 0 then return a[1] end
 514    for _, w in ipairs (words) do
 515        if w == a[1] then return w end
 516    end
 517    err ()
 518 end
 519
 520 ----------------------------------------------------------------------
 521 --
 522 ----------------------------------------------------------------------
 523 function lexer:clone()
 524    local clone = {
 525       alpha = table.deep_copy(self.alpha),
 526       sym   = table.deep_copy(self.sym) }
 527    setmetatable(clone, self)
 528    clone.__index = clone
 529    return clone
 530 end