src/compiler/gg.lua

   1 ----------------------------------------------------------------------\r
   2 -- Metalua.\r
   3 --\r
   4 -- Summary: parser generator. Collection of higher order functors,\r
   5 --   which allow to build and combine parsers. Relies on a lexer\r
   6 --   that supports the same API as the one exposed in mll.lua.\r
   7 --\r
   8 ----------------------------------------------------------------------\r
   9 --\r
  10 -- Copyright (c) 2006-2008, Fabien Fleutot <metalua@gmail.com>.\r
  11 --\r
  12 -- This software is released under the MIT Licence, see licence.txt\r
  13 -- for details.\r
  14 --\r
  15 ----------------------------------------------------------------------\r
  16 \r
  17 --------------------------------------------------------------------------------\r
  18 --\r
  19 -- Exported API:\r
  20 --\r
  21 -- Parser generators:\r
  22 -- * [gg.sequence()]\r
  23 -- * [gg.multisequence()]\r
  24 -- * [gg.expr()]\r
  25 -- * [gg.list()]\r
  26 -- * [gg.onkeyword()]\r
  27 -- * [gg.optkeyword()]\r
  28 --\r
  29 -- Other functions: \r
  30 -- * [gg.parse_error()]\r
  31 -- * [gg.make_parser()]\r
  32 -- * [gg.is_parser()]\r
  33 --\r
  34 --------------------------------------------------------------------------------\r
  35 \r
  36 module("gg", package.seeall)\r
  37 \r
  38 -------------------------------------------------------------------------------\r
  39 -- parser metatable, which maps __call to method parse, and adds some\r
  40 -- error tracing boilerplate.\r
  41 -------------------------------------------------------------------------------\r
  42 local parser_metatable = { }\r
  43 function parser_metatable.__call (parser, lx, ...)\r
  44    --printf ("Call parser %q of type %q", parser.name or "?", parser.kind)\r
  45    if mlc.metabugs then \r
  46       return parser:parse (lx, ...) \r
  47       --local x = parser:parse (lx, ...) \r
  48       --printf ("Result of parser %q: %s", \r
  49       --        parser.name or "?",\r
  50       --        _G.table.tostring(x, "nohash", 80))\r
  51       --return x\r
  52    else\r
  53       local li = lx:lineinfo_right() or { "?", "?", "?", "?" }\r
  54       local status, ast = pcall (parser.parse, parser, lx, ...)      \r
  55       if status then return ast else\r
  56          error (string.format ("%s\n - (l.%s, c.%s, k.%s) in parser %s", \r
  57                                ast:strmatch "gg.lua:%d+: (.*)" or ast,\r
  58                                li[1], li[2], li[3], parser.name or parser.kind))\r
  59       end\r
  60    end\r
  61 end\r
  62 \r
  63 -------------------------------------------------------------------------------\r
  64 -- Turn a table into a parser, mainly by setting the metatable.\r
  65 -------------------------------------------------------------------------------\r
  66 function make_parser(kind, p)\r
  67    p.kind = kind\r
  68    if not p.transformers then p.transformers = { } end\r
  69    function p.transformers:add (x)\r
  70       table.insert (self, x)\r
  71    end\r
  72    setmetatable (p, parser_metatable)\r
  73    return p\r
  74 end\r
  75 \r
  76 -------------------------------------------------------------------------------\r
  77 -- Return true iff [x] is a parser.\r
  78 -- If it's a gg-generated parser, reutrn the name of its kind.\r
  79 -------------------------------------------------------------------------------\r
  80 function is_parser (x)\r
  81    return type(x)=="function" or getmetatable(x)==parser_metatable and x.kind\r
  82 end\r
  83 \r
  84 -------------------------------------------------------------------------------\r
  85 -- Parse a sequence, without applying builder nor transformers\r
  86 -------------------------------------------------------------------------------\r
  87 local function raw_parse_sequence (lx, p)\r
  88    local r = { }\r
  89    for i=1, #p do\r
  90       e=p[i]\r
  91       if type(e) == "string" then \r
  92          if not lx:is_keyword (lx:next(), e) then\r
  93             parse_error (lx, "Keyword '%s' expected", e) end\r
  94       elseif is_parser (e) then\r
  95          table.insert (r, e (lx)) \r
  96       else \r
  97          gg.parse_error (lx,"Sequence `%s': element #%i is not a string "..\r
  98                          "nor a parser: %s", \r
  99                          p.name, i, table.tostring(e))\r
 100       end\r
 101    end\r
 102    return r\r
 103 end\r
 104 \r
 105 -------------------------------------------------------------------------------\r
 106 -- Parse a multisequence, without applying multisequence transformers.\r
 107 -- The sequences are completely parsed.\r
 108 -------------------------------------------------------------------------------\r
 109 local function raw_parse_multisequence (lx, sequence_table, default)\r
 110    local seq_parser = sequence_table[lx:is_keyword(lx:peek())]\r
 111    if seq_parser  then return seq_parser (lx)\r
 112    elseif default then return default (lx)\r
 113    else return false end\r
 114 end\r
 115 \r
 116 -------------------------------------------------------------------------------\r
 117 -- Applies all transformers listed in parser on ast.\r
 118 -------------------------------------------------------------------------------\r
 119 local function transform (ast, parser, fli, lli)\r
 120    if parser.transformers then\r
 121       for _, t in ipairs (parser.transformers) do ast = t(ast) or ast end\r
 122    end\r
 123    if type(ast) == 'table'then\r
 124       local ali = ast.lineinfo\r
 125       if not ali or ali.first~=fli or ali.last~=lli then\r
 126          ast.lineinfo = { first = fli, last = lli }\r
 127       end\r
 128    end\r
 129    return ast\r
 130 end\r
 131 \r
 132 -------------------------------------------------------------------------------\r
 133 -- Generate a tracable parsing error (not implemented yet)\r
 134 -------------------------------------------------------------------------------\r
 135 function parse_error(lx, fmt, ...)\r
 136    local li = lx:lineinfo_left() or {-1,-1,-1, "<unknown file>"}\r
 137    local msg  = string.format("line %i, char %i: "..fmt, li[1], li[2], ...)   \r
 138    local src = lx.src\r
 139    if li[3]>0 and src then\r
 140       local i, j = li[3], li[3]\r
 141       while src:sub(i,i) ~= '\n' and i>=0    do i=i-1 end\r
 142       while src:sub(j,j) ~= '\n' and j<=#src do j=j+1 end      \r
 143       local srcline = src:sub (i+1, j-1)\r
 144       local idx  = string.rep (" ", li[2]).."^"\r
 145       msg = string.format("%s\n>>> %s\n>>> %s", msg, srcline, idx)\r
 146    end\r
 147    error(msg)\r
 148 end\r
 149    \r
 150 -------------------------------------------------------------------------------\r
 151 --\r
 152 -- Sequence parser generator\r
 153 --\r
 154 -------------------------------------------------------------------------------\r
 155 -- Input fields:\r
 156 --\r
 157 -- * [builder]: how to build an AST out of sequence parts. let [x] be the list\r
 158 --   of subparser results (keywords are simply omitted). [builder] can be:\r
 159 --    - [nil], in which case the result of parsing is simply [x]\r
 160 --    - a string, which is then put as a tag on [x]\r
 161 --    - a function, which takes [x] as a parameter and returns an AST.\r
 162 --\r
 163 -- * [name]: the name of the parser. Used for debug messages\r
 164 --\r
 165 -- * [transformers]: a list of AST->AST functions, applied in order on ASTs\r
 166 --   returned by the parser.\r
 167 --\r
 168 -- * Table-part entries corresponds to keywords (strings) and subparsers \r
 169 --   (function and callable objects).\r
 170 --\r
 171 -- After creation, the following fields are added:\r
 172 -- * [parse] the parsing function lexer->AST\r
 173 -- * [kind] == "sequence"\r
 174 -- * [name] is set, if it wasn't in the input.\r
 175 --\r
 176 -------------------------------------------------------------------------------\r
 177 function sequence (p)\r
 178    make_parser ("sequence", p)\r
 179 \r
 180    -------------------------------------------------------------------\r
 181    -- Parsing method\r
 182    -------------------------------------------------------------------\r
 183    function p:parse (lx)\r
 184       -- Raw parsing:\r
 185       local fli = lx:lineinfo_right()\r
 186       local seq = raw_parse_sequence (lx, self)\r
 187       local lli = lx:lineinfo_left()\r
 188 \r
 189       -- Builder application:\r
 190       local builder, tb = self.builder, type (self.builder)\r
 191       if tb == "string" then seq.tag = builder\r
 192       elseif tb == "function" or builder and builder.__call then seq = builder(seq)\r
 193       elseif builder == nil then -- nothing\r
 194       else error ("Invalid builder of type "..tb.." in sequence") end\r
 195       seq = transform (seq, self, fli, lli)\r
 196       assert (not seq or seq.lineinfo)\r
 197       return seq\r
 198    end\r
 199 \r
 200    -------------------------------------------------------------------\r
 201    -- Construction\r
 202    -------------------------------------------------------------------\r
 203    -- Try to build a proper name\r
 204    if not p.name and type(p[1])=="string" then \r
 205       p.name = p[1].." ..." \r
 206       if type(p[#p])=="string" then p.name = p.name .. " " .. p[#p] end\r
 207    else\r
 208       p.name = "<anonymous>"\r
 209    end\r
 210 \r
 211    return p\r
 212 end --</sequence>\r
 213 \r
 214 \r
 215 -------------------------------------------------------------------------------\r
 216 --\r
 217 -- Multiple, keyword-driven, sequence parser generator\r
 218 --\r
 219 -------------------------------------------------------------------------------\r
 220 -- in [p], useful fields are:\r
 221 --\r
 222 -- * [transformers]: as usual\r
 223 --\r
 224 -- * [name]: as usual\r
 225 --\r
 226 -- * Table-part entries must be sequence parsers, or tables which can\r
 227 --   be turned into a sequence parser by [gg.sequence]. These\r
 228 --   sequences must start with a keyword, and this initial keyword\r
 229 --   must be different for each sequence.  The table-part entries will\r
 230 --   be removed after [gg.multisequence] returns.\r
 231 --\r
 232 -- * [default]: the parser to run if the next keyword in the lexer is\r
 233 --   none of the registered initial keywords. If there's no default\r
 234 --   parser and no suitable initial keyword, the multisequence parser\r
 235 --   simply returns [false].\r
 236 --\r
 237 -- After creation, the following fields are added:\r
 238 --\r
 239 -- * [parse] the parsing function lexer->AST\r
 240 --\r
 241 -- * [sequences] the table of sequences, indexed by initial keywords.\r
 242 --\r
 243 -- * [add] method takes a sequence parser or a config table for\r
 244 --   [gg.sequence], and adds/replaces the corresponding sequence\r
 245 --   parser. If the keyword was already used, the former sequence is\r
 246 --   removed and a warning is issued.\r
 247 --\r
 248 -- * [get] method returns a sequence by its initial keyword\r
 249 --\r
 250 -- * [kind] == "multisequence"\r
 251 --\r
 252 -------------------------------------------------------------------------------\r
 253 function multisequence (p)   \r
 254    make_parser ("multisequence", p)\r
 255 \r
 256    -------------------------------------------------------------------\r
 257    -- Add a sequence (might be just a config table for [gg.sequence])\r
 258    -------------------------------------------------------------------\r
 259    function p:add (s)\r
 260       -- compile if necessary:\r
 261       if not is_parser(s) then sequence(s) end\r
 262       if type(s[1]) ~= "string" then \r
 263          error "Invalid sequence for multiseq"\r
 264       elseif self.sequences[s[1]] then \r
 265          eprintf (" *** Warning: keyword %q overloaded in multisequence ***", s[1])\r
 266       end\r
 267       self.sequences[s[1]] = s\r
 268    end -- </multisequence.add>\r
 269 \r
 270    -------------------------------------------------------------------\r
 271    -- Get the sequence starting with this keyword. [kw :: string]\r
 272    -------------------------------------------------------------------\r
 273    function p:get (kw) return self.sequences [kw] end\r
 274 \r
 275    -------------------------------------------------------------------\r
 276    -- Remove the sequence starting with keyword [kw :: string]\r
 277    -------------------------------------------------------------------\r
 278    function p:del (kw) \r
 279       if not self.sequences[kw] then \r
 280          eprintf("*** Warning: trying to delete sequence starting "..\r
 281                  "with %q from a multisequence having no such "..\r
 282                  "entry ***", kw) end\r
 283       local removed = self.sequences[kw]\r
 284       self.sequences[kw] = nil \r
 285       return removed\r
 286    end\r
 287 \r
 288    -------------------------------------------------------------------\r
 289    -- Parsing method\r
 290    -------------------------------------------------------------------\r
 291    function p:parse (lx)\r
 292       local fli = lx:lineinfo_right()\r
 293       local x = raw_parse_multisequence (lx, self.sequences, self.default)\r
 294       local lli = lx:lineinfo_left()\r
 295       return transform (x, self, fli, lli)\r
 296    end\r
 297 \r
 298    -------------------------------------------------------------------\r
 299    -- Construction\r
 300    -------------------------------------------------------------------\r
 301    -- Register the sequences passed to the constructor. They're going\r
 302    -- from the array part of the parser to the hash part of field\r
 303    -- [sequences]\r
 304    p.sequences = { }\r
 305    for i=1, #p do p:add (p[i]); p[i] = nil end\r
 306 \r
 307    -- FIXME: why is this commented out?\r
 308    --if p.default and not is_parser(p.default) then sequence(p.default) end\r
 309    return p\r
 310 end --</multisequence>\r
 311 \r
 312 \r
 313 -------------------------------------------------------------------------------\r
 314 --\r
 315 -- Expression parser generator\r
 316 --\r
 317 -------------------------------------------------------------------------------\r
 318 --\r
 319 -- Expression configuration relies on three tables: [prefix], [infix]\r
 320 -- and [suffix]. Moreover, the primary parser can be replaced by a\r
 321 -- table: in this case the [primary] table will be passed to\r
 322 -- [gg.multisequence] to create a parser.\r
 323 --\r
 324 -- Each of these tables is a modified multisequence parser: the\r
 325 -- differences with respect to regular multisequence config tables are:\r
 326 --\r
 327 -- * the builder takes specific parameters:\r
 328 --   - for [prefix], it takes the result of the prefix sequence parser,\r
 329 --     and the prefixed expression\r
 330 --   - for [infix], it takes the left-hand-side expression, the results \r
 331 --     of the infix sequence parser, and the right-hand-side expression.\r
 332 --   - for [suffix], it takes the suffixed expression, and theresult \r
 333 --     of the suffix sequence parser.\r
 334 --\r
 335 -- * the default field is a list, with parameters:\r
 336 --   - [parser] the raw parsing function\r
 337 --   - [transformers], as usual\r
 338 --   - [prec], the operator's precedence\r
 339 --   - [assoc] for [infix] table, the operator's associativity, which\r
 340 --     can be "left", "right" or "flat" (default to left)\r
 341 --\r
 342 -- In [p], useful fields are:\r
 343 -- * [transformers]: as usual\r
 344 -- * [name]: as usual\r
 345 -- * [primary]: the atomic expression parser, or a multisequence config \r
 346 --   table (mandatory)\r
 347 -- * [prefix]:  prefix  operators config table, see above.\r
 348 -- * [infix]:   infix   operators config table, see above.\r
 349 -- * [suffix]: suffix operators config table, see above.\r
 350 --\r
 351 -- After creation, these fields are added:\r
 352 -- * [kind] == "expr"\r
 353 -- * [parse] as usual\r
 354 -- * each table is turned into a multisequence, and therefore has an \r
 355 --   [add] method\r
 356 --\r
 357 -------------------------------------------------------------------------------\r
 358 function expr (p)\r
 359    make_parser ("expr", p)\r
 360 \r
 361    -------------------------------------------------------------------\r
 362    -- parser method.\r
 363    -- In addition to the lexer, it takes an optional precedence:\r
 364    -- it won't read expressions whose precedence is lower or equal\r
 365    -- to [prec].\r
 366    -------------------------------------------------------------------\r
 367    function p:parse (lx, prec)\r
 368       prec = prec or 0\r
 369 \r
 370       ------------------------------------------------------\r
 371       -- Extract the right parser and the corresponding\r
 372       -- options table, for (pre|in|suff)fix operators.\r
 373       -- Options include prec, assoc, transformers.\r
 374       ------------------------------------------------------\r
 375       local function get_parser_info (tab)\r
 376          local p2 = tab:get (lx:is_keyword (lx:peek()))\r
 377          if p2 then -- keyword-based sequence found\r
 378             local function parser(lx) return raw_parse_sequence(lx, p2) end\r
 379             return parser, p2\r
 380          else -- Got to use the default parser\r
 381             local d = tab.default\r
 382             if d then return d.parse or d.parser, d\r
 383             else return false, false end\r
 384          end\r
 385       end\r
 386 \r
 387       ------------------------------------------------------\r
 388       -- Look for a prefix sequence. Multiple prefixes are\r
 389       -- handled through the recursive [p.parse] call.\r
 390       -- Notice the double-transform: one for the primary\r
 391       -- expr, and one for the one with the prefix op.\r
 392       ------------------------------------------------------\r
 393       local function handle_prefix ()\r
 394          local fli = lx:lineinfo_right()\r
 395          local p2_func, p2 = get_parser_info (self.prefix)\r
 396          local op = p2_func and p2_func (lx)\r
 397          if op then -- Keyword-based sequence found\r
 398             local ili = lx:lineinfo_right() -- Intermediate LineInfo\r
 399             local e = p2.builder (op, self:parse (lx, p2.prec))\r
 400             local lli = lx:lineinfo_left()\r
 401             return transform (transform (e, p2, ili, lli), self, fli, lli)\r
 402          else -- No prefix found, get a primary expression         \r
 403             local e = self.primary(lx)\r
 404             local lli = lx:lineinfo_left()\r
 405             return transform (e, self, fli, lli)\r
 406          end\r
 407       end --</expr.parse.handle_prefix>\r
 408 \r
 409       ------------------------------------------------------\r
 410       -- Look for an infix sequence+right-hand-side operand.\r
 411       -- Return the whole binary expression result,\r
 412       -- or false if no operator was found.\r
 413       ------------------------------------------------------\r
 414       local function handle_infix (e)\r
 415          local p2_func, p2 = get_parser_info (self.infix)\r
 416          if not p2 then return false end\r
 417 \r
 418          -----------------------------------------\r
 419          -- Handle flattening operators: gather all operands\r
 420          -- of the series in [list]; when a different operator \r
 421          -- is found, stop, build from [list], [transform] and\r
 422          -- return.\r
 423          -----------------------------------------\r
 424          if (not p2.prec or p2.prec>prec) and p2.assoc=="flat" then\r
 425             local fli = lx:lineinfo_right()\r
 426             local pflat, list = p2, { e }\r
 427             repeat\r
 428                local op = p2_func(lx)\r
 429                if not op then break end\r
 430                table.insert (list, self:parse (lx, p2.prec))\r
 431                local _ -- We only care about checking that p2==pflat\r
 432                _, p2 = get_parser_info (self.infix)\r
 433             until p2 ~= pflat\r
 434             local e2 = pflat.builder (list)\r
 435             local lli = lx:lineinfo_left()\r
 436             return transform (transform (e2, pflat, fli, lli), self, fli, lli)\r
 437  \r
 438          -----------------------------------------\r
 439          -- Handle regular infix operators: [e] the LHS is known,\r
 440          -- just gather the operator and [e2] the RHS.\r
 441          -- Result goes in [e3].\r
 442          -----------------------------------------\r
 443          elseif p2.prec and p2.prec>prec or \r
 444                 p2.prec==prec and p2.assoc=="right" then\r
 445             local fli = e.lineinfo.first -- lx:lineinfo_right()\r
 446             local op = p2_func(lx)\r
 447             if not op then return false end\r
 448             local e2 = self:parse (lx, p2.prec)\r
 449             local e3 = p2.builder (e, op, e2)\r
 450             local lli = lx:lineinfo_left()\r
 451             return transform (transform (e3, p2, fli, lli), self, fli, lli)\r
 452 \r
 453          -----------------------------------------\r
 454          -- Check for non-associative operators, and complain if applicable. \r
 455          -----------------------------------------\r
 456          elseif p2.assoc=="none" and p2.prec==prec then\r
 457             parser_error (lx, "non-associative operator!")\r
 458 \r
 459          -----------------------------------------\r
 460          -- No infix operator suitable at that precedence\r
 461          -----------------------------------------\r
 462          else return false end\r
 463 \r
 464       end --</expr.parse.handle_infix>\r
 465 \r
 466       ------------------------------------------------------\r
 467       -- Look for a suffix sequence.\r
 468       -- Return the result of suffix operator on [e],\r
 469       -- or false if no operator was found.\r
 470       ------------------------------------------------------\r
 471       local function handle_suffix (e)\r
 472          -- FIXME bad fli, must take e.lineinfo.first\r
 473          local p2_func, p2 = get_parser_info (self.suffix)\r
 474          if not p2 then return false end\r
 475          if not p2.prec or p2.prec>=prec then\r
 476             --local fli = lx:lineinfo_right()\r
 477             local fli = e.lineinfo.first\r
 478             local op = p2_func(lx)\r
 479             if not op then return false end\r
 480             local lli = lx:lineinfo_left()\r
 481             e = p2.builder (e, op)\r
 482             e = transform (transform (e, p2, fli, lli), self, fli, lli)\r
 483             return e\r
 484          end\r
 485          return false\r
 486       end --</expr.parse.handle_suffix>\r
 487 \r
 488       ------------------------------------------------------\r
 489       -- Parser body: read suffix and (infix+operand) \r
 490       -- extensions as long as we're able to fetch more at\r
 491       -- this precedence level.\r
 492       ------------------------------------------------------\r
 493       local e = handle_prefix()\r
 494       repeat\r
 495          local x = handle_suffix (e); e = x or e\r
 496          local y = handle_infix   (e); e = y or e\r
 497       until not (x or y)\r
 498 \r
 499       -- No transform: it already happened in operators handling\r
 500       return e\r
 501    end --</expr.parse>\r
 502 \r
 503    -------------------------------------------------------------------\r
 504    -- Construction\r
 505    -------------------------------------------------------------------\r
 506    if not p.primary then p.primary=p[1]; p[1]=nil end\r
 507    for _, t in ipairs{ "primary", "prefix", "infix", "suffix" } do\r
 508       if not p[t] then p[t] = { } end\r
 509       if not is_parser(p[t]) then multisequence(p[t]) end\r
 510    end\r
 511    function p:add(...) return self.primary:add(...) end\r
 512    return p\r
 513 end --</expr>\r
 514 \r
 515 \r
 516 -------------------------------------------------------------------------------\r
 517 --\r
 518 -- List parser generator\r
 519 --\r
 520 -------------------------------------------------------------------------------\r
 521 -- In [p], the following fields can be provided in input:\r
 522 --\r
 523 -- * [builder]: takes list of subparser results, returns AST\r
 524 -- * [transformers]: as usual\r
 525 -- * [name]: as usual\r
 526 --\r
 527 -- * [terminators]: list of strings representing the keywords which\r
 528 --   might mark the end of the list. When non-empty, the list is\r
 529 --   allowed to be empty. A string is treated as a single-element\r
 530 --   table, whose element is that string, e.g. ["do"] is the same as\r
 531 --   [{"do"}].\r
 532 --\r
 533 -- * [separators]: list of strings representing the keywords which can\r
 534 --   separate elements of the list. When non-empty, one of these\r
 535 --   keyword has to be found between each element. Lack of a separator\r
 536 --   indicates the end of the list. A string is treated as a\r
 537 --   single-element table, whose element is that string, e.g. ["do"]\r
 538 --   is the same as [{"do"}]. If [terminators] is empty/nil, then\r
 539 --   [separators] has to be non-empty.\r
 540 --\r
 541 -- After creation, the following fields are added:\r
 542 -- * [parse] the parsing function lexer->AST\r
 543 -- * [kind] == "list"\r
 544 --\r
 545 -------------------------------------------------------------------------------\r
 546 function list (p)\r
 547    make_parser ("list", p)\r
 548 \r
 549    -------------------------------------------------------------------\r
 550    -- Parsing method\r
 551    -------------------------------------------------------------------\r
 552    function p:parse (lx)\r
 553 \r
 554       ------------------------------------------------------\r
 555       -- Used to quickly check whether there's a terminator \r
 556       -- or a separator immediately ahead\r
 557       ------------------------------------------------------\r
 558       local function peek_is_in (keywords) \r
 559          return keywords and lx:is_keyword(lx:peek(), unpack(keywords)) end\r
 560 \r
 561       local x = { }\r
 562       local fli = lx:lineinfo_right()\r
 563 \r
 564       -- if there's a terminator to start with, don't bother trying\r
 565       if not peek_is_in (self.terminators) then \r
 566          repeat table.insert (x, self.primary (lx)) -- read one element\r
 567          until\r
 568             -- First reason to stop: There's a separator list specified,\r
 569             -- and next token isn't one. Otherwise, consume it with [lx:next()]\r
 570             self.separators and not(peek_is_in (self.separators) and lx:next()) or\r
 571             -- Other reason to stop: terminator token ahead\r
 572             peek_is_in (self.terminators) or\r
 573             -- Last reason: end of file reached\r
 574             lx:peek().tag=="Eof"\r
 575       end\r
 576 \r
 577       local lli = lx:lineinfo_left()\r
 578       \r
 579       -- Apply the builder. It can be a string, or a callable value, \r
 580       -- or simply nothing.\r
 581       local b = self.builder\r
 582       if b then\r
 583          if type(b)=="string" then x.tag = b -- b is a string, use it as a tag\r
 584          elseif type(b)=="function" then x=b(x)\r
 585          else\r
 586             local bmt = getmetatable(b)\r
 587             if bmt and bmt.__call then x=b(x) end\r
 588          end\r
 589       end\r
 590       return transform (x, self, fli, lli)\r
 591    end --</list.parse>\r
 592 \r
 593    -------------------------------------------------------------------\r
 594    -- Construction\r
 595    -------------------------------------------------------------------\r
 596    if not p.primary then p.primary = p[1]; p[1] = nil end\r
 597    if type(p.terminators) == "string" then p.terminators = { p.terminators }\r
 598    elseif p.terminators and #p.terminators == 0 then p.terminators = nil end\r
 599    if type(p.separators) == "string" then p.separators = { p.separators }\r
 600    elseif p.separators and #p.separators == 0 then p.separators = nil end\r
 601 \r
 602    return p\r
 603 end --</list>\r
 604 \r
 605 \r
 606 -------------------------------------------------------------------------------\r
 607 --\r
 608 -- Keyword-conditionned parser generator\r
 609 --\r
 610 -------------------------------------------------------------------------------\r
 611 -- \r
 612 -- Only apply a parser if a given keyword is found. The result of\r
 613 -- [gg.onkeyword] parser is the result of the subparser (modulo\r
 614 -- [transformers] applications).\r
 615 --\r
 616 -- lineinfo: the keyword is *not* included in the boundaries of the\r
 617 -- resulting lineinfo. A review of all usages of gg.onkeyword() in the\r
 618 -- implementation of metalua has shown that it was the appropriate choice\r
 619 -- in every case.\r
 620 --\r
 621 -- Input fields:\r
 622 --\r
 623 -- * [name]: as usual\r
 624 --\r
 625 -- * [transformers]: as usual\r
 626 --\r
 627 -- * [peek]: if non-nil, the conditionning keyword is left in the lexeme\r
 628 --   stream instead of being consumed.\r
 629 --\r
 630 -- * [primary]: the subparser. \r
 631 --\r
 632 -- * [keywords]: list of strings representing triggering keywords.\r
 633 --\r
 634 -- * Table-part entries can contain strings, and/or exactly one parser.\r
 635 --   Strings are put in [keywords], and the parser is put in [primary].\r
 636 --\r
 637 -- After the call, the following fields will be set:\r
 638 --   \r
 639 -- * [parse] the parsing method\r
 640 -- * [kind] == "onkeyword"\r
 641 -- * [primary]\r
 642 -- * [keywords]\r
 643 --\r
 644 -------------------------------------------------------------------------------\r
 645 function onkeyword (p)\r
 646    make_parser ("onkeyword", p)\r
 647 \r
 648    -------------------------------------------------------------------\r
 649    -- Parsing method\r
 650    -------------------------------------------------------------------\r
 651    function p:parse(lx)\r
 652       if lx:is_keyword (lx:peek(), unpack(self.keywords)) then\r
 653          --local fli = lx:lineinfo_right()\r
 654          if not self.peek then lx:next() end\r
 655          local content = self.primary (lx)\r
 656          --local lli = lx:lineinfo_left()\r
 657          local fli, lli = content.lineinfo.first, content.lineinfo.last\r
 658          return transform (content, p, fli, lli)\r
 659       else return false end\r
 660    end\r
 661 \r
 662    -------------------------------------------------------------------\r
 663    -- Construction\r
 664    -------------------------------------------------------------------\r
 665    if not p.keywords then p.keywords = { } end\r
 666    for _, x in ipairs(p) do\r
 667       if type(x)=="string" then table.insert (p.keywords, x)\r
 668       else assert (not p.primary and is_parser (x)); p.primary = x end\r
 669    end\r
 670    assert (p.primary, 'no primary parser in gg.onkeyword')\r
 671    return p\r
 672 end --</onkeyword>\r
 673 \r
 674 \r
 675 -------------------------------------------------------------------------------\r
 676 --\r
 677 -- Optional keyword consummer pseudo-parser generator\r
 678 --\r
 679 -------------------------------------------------------------------------------\r
 680 --\r
 681 -- This doesn't return a real parser, just a function. That function parses\r
 682 -- one of the keywords passed as parameters, and returns it. It returns \r
 683 -- [false] if no matching keyword is found.\r
 684 --\r
 685 -- Notice that tokens returned by lexer already carry lineinfo, therefore\r
 686 -- there's no need to add them, as done usually through transform() calls.\r
 687 -------------------------------------------------------------------------------\r
 688 function optkeyword (...)\r
 689    local args = {...}\r
 690    if type (args[1]) == "table" then \r
 691       assert (#args == 1)\r
 692       args = args[1]\r
 693    end\r
 694    for _, v in ipairs(args) do assert (type(v)=="string") end\r
 695    return function (lx)\r
 696       local x = lx:is_keyword (lx:peek(), unpack (args))\r
 697       if x then lx:next(); return x\r
 698       else return false end\r
 699    end\r
 700 end\r
 701 \r
 702 \r
 703 -------------------------------------------------------------------------------\r
 704 --\r
 705 -- Run a parser with a special lexer\r
 706 --\r
 707 -------------------------------------------------------------------------------\r
 708 --\r
 709 -- This doesn't return a real parser, just a function.\r
 710 -- First argument is the lexer class to be used with the parser,\r
 711 -- 2nd is the parser itself.\r
 712 -- The resulting parser returns whatever the argument parser does.\r
 713 --\r
 714 -------------------------------------------------------------------------------\r
 715 function with_lexer(new_lexer, parser)\r
 716 \r
 717    -------------------------------------------------------------------\r
 718    -- Most gg functions take their parameters in a table, so it's \r
 719    -- better to silently accept when with_lexer{ } is called with\r
 720    -- its arguments in a list:\r
 721    -------------------------------------------------------------------\r
 722    if not parser and #new_lexer==2 and type(new_lexer[1])=='table' then\r
 723       return with_lexer(unpack(new_lexer))\r
 724    end\r
 725 \r
 726    -------------------------------------------------------------------\r
 727    -- Save the current lexer, switch it for the new one, run the parser,\r
 728    -- restore the previous lexer, even if the parser caused an error.\r
 729    -------------------------------------------------------------------\r
 730    return function (lx)\r
 731       local old_lexer = getmetatable(lx)\r
 732       lx:sync()\r
 733       setmetatable(lx, new_lexer)\r
 734       local status, result = pcall(parser, lx)\r
 735       lx:sync()\r
 736       setmetatable(lx, old_lexer)\r
 737       if status then return result else error(result) end\r
 738    end\r
 739 end\r