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 --
  22 -- Copyright (c) 2006, Fabien Fleutot <metalua@gmail.com>.
  23 --
  24 -- This software is released under the MIT Licence, see licence.txt
  25 -- for details.
  26 --
  27 ----------------------------------------------------------------------
  28
  29 module ("lexer", package.seeall)
  30
  31 require 'metalua.runtime'
  32
  33
  34 lexer = { alpha={ }, sym={ } }
  35 lexer.__index=lexer
  36
  37 local debugf = function() end
  38 --local debugf=printf
  39
  40 ----------------------------------------------------------------------
  41 -- Patterns used by [lexer:extract] to decompose the raw string into
  42 -- correctly tagged tokens.
  43 ----------------------------------------------------------------------
  44 lexer.patterns = {
  45    spaces              = "^[ \r\n\t]*()",
  46    short_comment       = "^%-%-([^\n]*)()\n",
  47    final_short_comment = "^%-%-([^\n]*)()$",
  48    long_comment        = "^%-%-%[(=*)%[\n?(.-)%]%1%]()",
  49    long_string         = "^%[(=*)%[\n?(.-)%]%1%]()",
  50    number_mantissa     = {
  51       "^%d+%.?%d*()",
  52       "^%d*%d%.%d+()" },
  53    number_exponant = "^[eE][%+%-]?%d+()",
  54    word            = "^([%a_][%w_]*)()"
  55 }
  56
  57 ----------------------------------------------------------------------
  58 -- Take a letter [x], and returns the character represented by the
  59 -- sequence ['\\'..x], e.g. [unesc_letter "n" == "\n"].
  60 ----------------------------------------------------------------------
  61 local function unesc_letter(x)
  62    local t = {
  63       a = "\a", b = "\b", f = "\f",
  64       n = "\n", r = "\r", t = "\t", v = "\v",
  65       ["\\"] = "\\", ["'"] = "'", ['"'] = '"' }
  66    return t[x] or error("Unknown escape sequence \\"..x)
  67 end
  68
  69 ----------------------------------------------------------------------
  70 -- Turn the digits of an escape sequence into the corresponding
  71 -- character, e.g. [unesc_digits("123") == string.char(123)].
  72 ----------------------------------------------------------------------
  73 local function unesc_digits (x)
  74    local k, j, i = x:reverse():byte(1, 3)
  75    local z = _G.string.byte "0"
  76    return _G.string.char ((k or z) + 10*(j or z) + 100*(i or z) - 111*z)
  77 end
  78
  79 ----------------------------------------------------------------------
  80 -- unescape a whole string, applying [unesc_digits] and [unesc_letter]
  81 -- as many times as required.
  82 ----------------------------------------------------------------------
  83 local function unescape_string (s)
  84    return s:gsub("\\([0-9]+)", unesc_digits):gsub("\\(.)",unesc_letter)
  85 end
  86
  87 lexer.extractors = {
  88    "skip_whitespaces_and_comments",
  89    "extract_short_string", "extract_word", "extract_number",
  90    "extract_long_string", "extract_symbol" }
  91
  92 lexer.token_metatable = {
  93 --         __tostring = function(a)
  94 --            return string.format ("`%s{'%s'}",a.tag, a[1])
  95 --         end
  96       }
  97
  98 ----------------------------------------------------------------------
  99 -- Really extract next token fron the raw string
 100 -- (and update the index).
 101 ----------------------------------------------------------------------
 102 function lexer:extract ()
 103    local previous_i = self.i
 104    local loc, eof, token = self.i
 105
 106    local function tk (tag, content)
 107       assert (tag and content)
 108       local i, ln = previous_i, self.line
 109       -- update line numbers
 110       while true do
 111          i = self.src:find("\n", i+1, true)
 112          if not i then break end
 113          if loc and i <= loc then ln = ln+1 end
 114          if i <= self.i then self.line = self.line+1 else break end
 115       end
 116       local a = { tag      = tag,
 117                   char     = loc,
 118                   lineinfo = { first = ln, last = self.line },
 119                   line     = self.line,
 120                   content }
 121       -- FIXME [EVE] make lineinfo passing less memory consuming
 122       -- FIXME [Fabien] suppress line/lineinfo.line redundancy.
 123       if #self.attached_comments > 0 then
 124          a.comments = self.attached_comments
 125          self.attached_comments = nil
 126       end
 127       return setmetatable (a, self.token_metatable)
 128    end
 129
 130    self.attached_comments = { }
 131
 132    for ext_idx, extractor in ipairs(self.extractors) do
 133       -- printf("method = %s", method)
 134       local tag, content = self[extractor](self)
 135       -- [loc] is placed just after the leading whitespaces and comments,
 136       -- and the whitespace extractor is at index 1.
 137       if ext_idx==1 then loc = self.i end
 138
 139       if tag then
 140          --printf("`%s{ %q }\t%i", tag, content, loc);
 141          return tk (tag, content)
 142       end
 143    end
 144
 145    error "Cant extract anything!"
 146 end
 147
 148 ----------------------------------------------------------------------
 149 -- skip whites and comments
 150 -- FIXME: doesn't take into account:
 151 -- - unterminated long comments
 152 -- - short comments without a final \n
 153 ----------------------------------------------------------------------
 154 function lexer:skip_whitespaces_and_comments()
 155    local attached_comments = { }
 156    repeat
 157       local _, j
 158       local again = false
 159       local last_comment_content = nil
 160       -- skip spaces
 161       self.i = self.src:match (self.patterns.spaces, self.i)
 162       -- skip a long comment if any
 163       _, last_comment_content, j = self.src:match (self.patterns.long_comment, self.i)
 164       if j then
 165          _G.table.insert(self.attached_comments,
 166                          {last_comment_content, self.i, j, "long"})
 167          self.i=j; again=true
 168       end
 169       -- skip a short comment if any
 170       last_comment_content, j = self.src:match (self.patterns.short_comment, self.i)
 171       if j then
 172          _G.table.insert(attached_comments,
 173                          {last_comment_content, self.i, j, "short"})
 174          self.i=j; again=true
 175       end
 176       if self.i>#self.src then return "Eof", "eof" end
 177    until not again
 178
 179    if self.src:match (self.patterns.final_short_comment, self.i) then
 180       return "Eof", "eof" end
 181    --assert (not self.src:match(self.patterns.short_comment, self.i))
 182    --assert (not self.src:match(self.patterns.long_comment, self.i))
 183    -- --assert (not self.src:match(self.patterns.spaces, self.i))
 184    return
 185 end
 186
 187 ----------------------------------------------------------------------
 188 --
 189 ----------------------------------------------------------------------
 190 function lexer:extract_short_string()
 191    -- [k] is the first unread char, [self.i] points to [k] in [self.src]
 192    local j, k = self.i, self.src:sub (self.i,self.i)
 193    if k=="'" or k=='"' then
 194       -- short string
 195       repeat
 196          self.i=self.i+1;
 197          local kk = self.src:sub (self.i, self.i)
 198          if kk=="\\" then
 199             self.i=self.i+1;
 200             kk = self.src:sub (self.i, self.i)
 201          end
 202          if self.i > #self.src then error "Unterminated string" end
 203          if self.i == "\r" or self.i == "\n" then error "no \\n in short strings!" end
 204       until self.src:sub (self.i, self.i) == k
 205          and ( self.src:sub (self.i-1, self.i-1) ~= '\\'
 206          or self.src:sub (self.i-2, self.i-2) == '\\')
 207       self.i=self.i+1
 208       return "String", unescape_string (self.src:sub (j+1,self.i-2))
 209    end
 210 end
 211
 212 ----------------------------------------------------------------------
 213 --
 214 ----------------------------------------------------------------------
 215 function lexer:extract_word()
 216    -- Id / keyword
 217    local word, j = self.src:match (self.patterns.word, self.i)
 218    if word then
 219       self.i = j
 220       if self.alpha [word] then return "Keyword", word
 221       else return "Id", word end
 222    end
 223 end
 224
 225 ----------------------------------------------------------------------
 226 --
 227 ----------------------------------------------------------------------
 228 function lexer:extract_number()
 229    -- Number
 230    local j = self.src:match (self.patterns.number_mantissa[1], self.i) or
 231              self.src:match (self.patterns.number_mantissa[2], self.i)
 232    if j then
 233       j = self.src:match (self.patterns.number_exponant, j) or j;
 234       local n = tonumber (self.src:sub (self.i, j-1))
 235       self.i = j
 236       return "Number", n
 237    end
 238 end
 239
 240 ----------------------------------------------------------------------
 241 --
 242 ----------------------------------------------------------------------
 243 function lexer:extract_long_string()
 244    -- Long string
 245    local _, content, j = self.src:match (self.patterns.long_string, self.i)
 246    if j then self.i = j; return "String", content end
 247 end
 248
 249 ----------------------------------------------------------------------
 250 --
 251 ----------------------------------------------------------------------
 252 function lexer:extract_symbol()
 253    -- compound symbol
 254    local k = self.src:sub (self.i,self.i)
 255    local symk = self.sym [k]
 256    if not symk then
 257       self.i = self.i + 1
 258       return "Keyword", k
 259    end
 260    for _, sym in pairs (symk) do
 261       if sym == self.src:sub (self.i, self.i + #sym - 1) then
 262          self.i = self.i + #sym;
 263          return "Keyword", sym
 264       end
 265    end
 266    -- single char symbol
 267    self.i = self.i+1
 268    return "Keyword", k
 269 end
 270
 271 ----------------------------------------------------------------------
 272 -- Add a keyword to the list of keywords recognized by the lexer.
 273 ----------------------------------------------------------------------
 274 function lexer:add (w, ...)
 275    assert(not ..., "lexer:add() takes only one arg, although possibly a table")
 276    if type (w) == "table" then
 277       for _, x in ipairs (w) do self:add (x) end
 278    else
 279       if w:match (self.patterns.word .. "$") then self.alpha [w] = true
 280       elseif w:match "^%p%p+$" then
 281          local k = w:sub(1,1)
 282          local list = self.sym [k]
 283          if not list then list = { }; self.sym [k] = list end
 284          _G.table.insert (list, w)
 285       elseif w:match "^%p$" then return
 286       else error "Invalid keyword" end
 287    end
 288 end
 289
 290 ----------------------------------------------------------------------
 291 -- Return the [n]th next token, without consumming it.
 292 -- [n] defaults to 1. If it goes pass the end of the stream, an EOF
 293 -- token is returned.
 294 ----------------------------------------------------------------------
 295 function lexer:peek (n)
 296    assert(self)
 297    if not n then n=1 end
 298    if n > #self.peeked then
 299       for i = #self.peeked+1, n do
 300          self.peeked [i] = self:extract()
 301       end
 302    end
 303   return self.peeked [n]
 304 end
 305
 306 ----------------------------------------------------------------------
 307 -- Return the [n]th next token, removing it as well as the 0..n-1
 308 -- previous tokens. [n] defaults to 1. If it goes pass the end of the
 309 -- stream, an EOF token is returned.
 310 ----------------------------------------------------------------------
 311 function lexer:next (n)
 312    if not n then n=1 end
 313    self:peek (n)
 314    local a
 315    for i=1,n do
 316       a = _G.table.remove (self.peeked, 1)
 317       if a then
 318         debugf ("[L:%i K:%i T:%s %q]", a.line or -1, a.char or -1,
 319                 a.tag or '<none>', a[1]) end
 320         self.lastline = a.lineinfo.last
 321       end
 322    end
 323    return a or eof_token
 324 end
 325
 326 ----------------------------------------------------------------------
 327 -- Returns an object which saves the stream's current state.
 328 ----------------------------------------------------------------------
 329 function lexer:save () return { self.i; _G.table.cat(self.peeked) } end
 330
 331 ----------------------------------------------------------------------
 332 -- Restore the stream's state, as saved by method [save].
 333 ----------------------------------------------------------------------
 334 function lexer:restore (s) self.i=s[1]; self.peeked=s[2] end
 335
 336 ----------------------------------------------------------------------
 337 --
 338 ----------------------------------------------------------------------
 339 function lexer:sync()
 340    local p1 = self.peeked[1]
 341    if p1 then
 342       self.i, self.line, self.peeked = p1.char, p1.line, { }
 343    end
 344 end
 345
 346 ----------------------------------------------------------------------
 347 -- Take over an old lexer.
 348 ----------------------------------------------------------------------
 349 function lexer:takeover(old)
 350    self:sync()
 351    self.i, self.line, self.src = old.i, old.line, old.src
 352    return self
 353 end
 354
 355 ----------------------------------------------------------------------
 356 -- Create a new lexstream.
 357 ----------------------------------------------------------------------
 358 function lexer:newstream (src_or_stream)
 359    if type(src_or_stream)=='table' then -- it's a stream
 360       return setmetatable({ }, self):takeover(src_or_stream)
 361    elseif type(src_or_stream)=='string' then -- it's a source string
 362       local stream = {
 363          src    = src_or_stream; -- The source, as a single string
 364          peeked = { };           -- Already peeked, but not discarded yet, tokens
 365          i      = 1;             -- Character offset in src
 366          line   = 1;             -- Current line number
 367       }
 368       setmetatable (stream, self)
 369
 370       -- skip initial sharp-bang for unix scripts
 371       if src and src:match "^#!" then stream.i = src:find "\n" + 1 end
 372       return stream
 373    else
 374       assert(false, ":newstream() takes a source string or a stream, not a "..
 375                     type(src_or_stream))
 376    end
 377 end
 378
 379 ----------------------------------------------------------------------
 380 -- if there's no ... args, return the token a (whose truth value is
 381 -- true) if it's a `Keyword{ }, or nil.  If there are ... args, they
 382 -- have to be strings. if the token a is a keyword, and it's content
 383 -- is one of the ... args, then returns it (it's truth value is
 384 -- true). If no a keyword or not in ..., return nil.
 385 ----------------------------------------------------------------------
 386 function lexer:is_keyword (a, ...)
 387    if not a or a.tag ~= "Keyword" then return false end
 388    local words = {...}
 389    if #words == 0 then return a[1] end
 390    for _, w in ipairs (words) do
 391       if w == a[1] then return w end
 392    end
 393    return false
 394 end
 395
 396 ----------------------------------------------------------------------
 397 -- Cause an error if the next token isn't a keyword whose content
 398 -- is listed among ... args (which have to be strings).
 399 ----------------------------------------------------------------------
 400 function lexer:check (...)
 401    local words = {...}
 402    local a = self:next()
 403    local function err ()
 404       error ("Got " .. tostring (a) ..
 405              ", expected one of these keywords : '" ..
 406              _G.table.concat (words,"', '") .. "'") end
 407
 408    if not a or a.tag ~= "Keyword" then err () end
 409    if #words == 0 then return a[1] end
 410    for _, w in ipairs (words) do
 411        if w == a[1] then return w end
 412    end
 413    err ()
 414 end
 415
 416 ----------------------------------------------------------------------
 417 --
 418 ----------------------------------------------------------------------
 419 function lexer:clone()
 420    local clone = {
 421       alpha = table.deep_copy(self.alpha),
 422       sym   = table.deep_copy(self.sym) }
 423    setmetatable(clone, self)
 424    clone.__index = clone
 425    return clone
 426 end