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