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