1 ----------------------------------------------------------------------
4 -- Summary: parser generator. Collection of higher order functors,
5 -- which allow to build and combine parsers. Relies on a lexer
6 -- that supports the same API as the one exposed in mll.lua.
8 ----------------------------------------------------------------------
10 -- Copyright (c) 2006-2008, Fabien Fleutot <metalua@gmail.com>.
12 -- This software is released under the MIT Licence, see licence.txt
15 ----------------------------------------------------------------------
17 --------------------------------------------------------------------------------
23 -- * [gg.multisequence()]
27 -- * [gg.optkeyword()]
30 -- * [gg.parse_error()]
31 -- * [gg.make_parser()]
34 --------------------------------------------------------------------------------
36 module("gg", package.seeall)
38 -------------------------------------------------------------------------------
39 -- parser metatable, which maps __call to method parse, and adds some
40 -- error tracing boilerplate.
41 -------------------------------------------------------------------------------
42 local parser_metatable = { }
43 function parser_metatable.__call (parser, lx, ...)
44 --printf ("Call parser %q of type %q", parser.name or "?", parser.kind)
46 return parser:parse (lx, ...)
47 --local x = parser:parse (lx, ...)
48 --printf ("Result of parser %q: %s",
49 -- parser.name or "?",
50 -- _G.table.tostring(x, "nohash", 80))
53 local li = lx:lineinfo_right() or { "?", "?", "?", "?" }
54 local status, ast = pcall (parser.parse, parser, lx, ...)
55 if status then return ast else
56 -- Try to replace the gg.lua location, in the error msg, with
57 -- the place where the current parser started handling the
59 -- Since the error is rethrown, these places are stacked.
60 error (string.format ("%s\n - (l.%s, c.%s, k.%s) in parser %s",
61 ast :strmatch "gg.lua:%d+: (.*)" or ast,
62 li[1], li[2], li[3], parser.name or parser.kind))
67 -------------------------------------------------------------------------------
68 -- Turn a table into a parser, mainly by setting the metatable.
69 -------------------------------------------------------------------------------
70 function make_parser(kind, p)
72 if not p.transformers then p.transformers = { } end
73 function p.transformers:add (x)
74 table.insert (self, x)
76 setmetatable (p, parser_metatable)
80 -------------------------------------------------------------------------------
81 -- Return true iff [x] is a parser.
82 -- If it's a gg-generated parser, return the name of its kind.
83 -------------------------------------------------------------------------------
84 function is_parser (x)
85 return type(x)=="function" or getmetatable(x)==parser_metatable and x.kind
88 -------------------------------------------------------------------------------
89 -- Parse a sequence, without applying builder nor transformers
90 -------------------------------------------------------------------------------
91 local function raw_parse_sequence (lx, p)
95 if type(e) == "string" then
96 if not lx:is_keyword (lx:next(), e) then
97 parse_error (lx, "A keyword was expected, probably `%s'.", e) end
98 elseif is_parser (e) then
99 table.insert (r, e (lx))
101 gg.parse_error (lx,"Sequence `%s': element #%i is neither a string "..
103 p.name, i, table.tostring(e))
109 -------------------------------------------------------------------------------
110 -- Parse a multisequence, without applying multisequence transformers.
111 -- The sequences are completely parsed.
112 -------------------------------------------------------------------------------
113 local function raw_parse_multisequence (lx, sequence_table, default)
114 local seq_parser = sequence_table[lx:is_keyword(lx:peek())]
115 if seq_parser then return seq_parser (lx)
116 elseif default then return default (lx)
117 else return false end
120 -------------------------------------------------------------------------------
121 -- Applies all transformers listed in parser on ast.
122 -------------------------------------------------------------------------------
123 local function transform (ast, parser, fli, lli)
124 if parser.transformers then
125 for _, t in ipairs (parser.transformers) do ast = t(ast) or ast end
127 if type(ast) == 'table'then
128 local ali = ast.lineinfo
129 if not ali or ali.first~=fli or ali.last~=lli then
130 ast.lineinfo = { first = fli, last = lli }
136 -------------------------------------------------------------------------------
137 -- Generate a tracable parsing error (not implemented yet)
138 -------------------------------------------------------------------------------
139 function parse_error(lx, fmt, ...)
140 local li = lx:lineinfo_left() or {-1,-1,-1, "<unknown file>"}
141 local msg = string.format("line %i, char %i: "..fmt, li[1], li[2], ...)
143 if li[3]>0 and src then
144 local i, j = li[3], li[3]
145 while src:sub(i,i) ~= '\n' and i>=0 do i=i-1 end
146 while src:sub(j,j) ~= '\n' and j<=#src do j=j+1 end
147 local srcline = src:sub (i+1, j-1)
148 local idx = string.rep (" ", li[2]).."^"
149 msg = string.format("%s\n>>> %s\n>>> %s", msg, srcline, idx)
154 -------------------------------------------------------------------------------
156 -- Sequence parser generator
158 -------------------------------------------------------------------------------
161 -- * [builder]: how to build an AST out of sequence parts. let [x] be the list
162 -- of subparser results (keywords are simply omitted). [builder] can be:
163 -- - [nil], in which case the result of parsing is simply [x]
164 -- - a string, which is then put as a tag on [x]
165 -- - a function, which takes [x] as a parameter and returns an AST.
167 -- * [name]: the name of the parser. Used for debug messages
169 -- * [transformers]: a list of AST->AST functions, applied in order on ASTs
170 -- returned by the parser.
172 -- * Table-part entries corresponds to keywords (strings) and subparsers
173 -- (function and callable objects).
175 -- After creation, the following fields are added:
176 -- * [parse] the parsing function lexer->AST
177 -- * [kind] == "sequence"
178 -- * [name] is set, if it wasn't in the input.
180 -------------------------------------------------------------------------------
181 function sequence (p)
182 make_parser ("sequence", p)
184 -------------------------------------------------------------------
186 -------------------------------------------------------------------
187 function p:parse (lx)
189 local fli = lx:lineinfo_right()
190 local seq = raw_parse_sequence (lx, self)
191 local lli = lx:lineinfo_left()
193 -- Builder application:
194 local builder, tb = self.builder, type (self.builder)
195 if tb == "string" then seq.tag = builder
196 elseif tb == "function" or builder and builder.__call then seq = builder(seq)
197 elseif builder == nil then -- nothing
198 else error ("Invalid builder of type "..tb.." in sequence") end
199 seq = transform (seq, self, fli, lli)
200 assert (not seq or seq.lineinfo)
204 -------------------------------------------------------------------
206 -------------------------------------------------------------------
207 -- Try to build a proper name
209 -- don't touch existing name
210 elseif type(p[1])=="string" then -- find name based on 1st keyword
211 if #p==1 then p.name=p[1]
212 elseif type(p[#p])=="string" then
213 p.name = p[1] .. " ... " .. p[#p]
214 else p.name = p[1] .. " ..." end
215 else -- can't find a decent name
216 p.name = "<anonymous>"
223 -------------------------------------------------------------------------------
225 -- Multiple, keyword-driven, sequence parser generator
227 -------------------------------------------------------------------------------
228 -- in [p], useful fields are:
230 -- * [transformers]: as usual
232 -- * [name]: as usual
234 -- * Table-part entries must be sequence parsers, or tables which can
235 -- be turned into a sequence parser by [gg.sequence]. These
236 -- sequences must start with a keyword, and this initial keyword
237 -- must be different for each sequence. The table-part entries will
238 -- be removed after [gg.multisequence] returns.
240 -- * [default]: the parser to run if the next keyword in the lexer is
241 -- none of the registered initial keywords. If there's no default
242 -- parser and no suitable initial keyword, the multisequence parser
243 -- simply returns [false].
245 -- After creation, the following fields are added:
247 -- * [parse] the parsing function lexer->AST
249 -- * [sequences] the table of sequences, indexed by initial keywords.
251 -- * [add] method takes a sequence parser or a config table for
252 -- [gg.sequence], and adds/replaces the corresponding sequence
253 -- parser. If the keyword was already used, the former sequence is
254 -- removed and a warning is issued.
256 -- * [get] method returns a sequence by its initial keyword
258 -- * [kind] == "multisequence"
260 -------------------------------------------------------------------------------
261 function multisequence (p)
262 make_parser ("multisequence", p)
264 -------------------------------------------------------------------
265 -- Add a sequence (might be just a config table for [gg.sequence])
266 -------------------------------------------------------------------
268 -- compile if necessary:
269 local keyword = type(s)=='table' and s[1]
270 if type(s)=='table' and not is_parser(s) then sequence(s) end
271 if is_parser(s)~='sequence' or type(keyword)~='string' then
272 if self.default then -- two defaults
273 error ("In a multisequence parser, all but one sequences "..
274 "must start with a keyword")
275 else self.default = s end -- first default
276 elseif self.sequences[keyword] then -- duplicate keyword
277 eprintf (" *** Warning: keyword %q overloaded in multisequence ***",
279 self.sequences[keyword] = s
280 else -- newly caught keyword
281 self.sequences[keyword] = s
283 end -- </multisequence.add>
285 -------------------------------------------------------------------
286 -- Get the sequence starting with this keyword. [kw :: string]
287 -------------------------------------------------------------------
288 function p:get (kw) return self.sequences [kw] end
290 -------------------------------------------------------------------
291 -- Remove the sequence starting with keyword [kw :: string]
292 -------------------------------------------------------------------
294 if not self.sequences[kw] then
295 eprintf("*** Warning: trying to delete sequence starting "..
296 "with %q from a multisequence having no such "..
298 local removed = self.sequences[kw]
299 self.sequences[kw] = nil
303 -------------------------------------------------------------------
305 -------------------------------------------------------------------
306 function p:parse (lx)
307 local fli = lx:lineinfo_right()
308 local x = raw_parse_multisequence (lx, self.sequences, self.default)
309 local lli = lx:lineinfo_left()
310 return transform (x, self, fli, lli)
313 -------------------------------------------------------------------
315 -------------------------------------------------------------------
316 -- Register the sequences passed to the constructor. They're going
317 -- from the array part of the parser to the hash part of field
320 for i=1, #p do p:add (p[i]); p[i] = nil end
322 -- FIXME: why is this commented out?
323 --if p.default and not is_parser(p.default) then sequence(p.default) end
325 end --</multisequence>
328 -------------------------------------------------------------------------------
330 -- Expression parser generator
332 -------------------------------------------------------------------------------
334 -- Expression configuration relies on three tables: [prefix], [infix]
335 -- and [suffix]. Moreover, the primary parser can be replaced by a
336 -- table: in this case the [primary] table will be passed to
337 -- [gg.multisequence] to create a parser.
339 -- Each of these tables is a modified multisequence parser: the
340 -- differences with respect to regular multisequence config tables are:
342 -- * the builder takes specific parameters:
343 -- - for [prefix], it takes the result of the prefix sequence parser,
344 -- and the prefixed expression
345 -- - for [infix], it takes the left-hand-side expression, the results
346 -- of the infix sequence parser, and the right-hand-side expression.
347 -- - for [suffix], it takes the suffixed expression, and theresult
348 -- of the suffix sequence parser.
350 -- * the default field is a list, with parameters:
351 -- - [parser] the raw parsing function
352 -- - [transformers], as usual
353 -- - [prec], the operator's precedence
354 -- - [assoc] for [infix] table, the operator's associativity, which
355 -- can be "left", "right" or "flat" (default to left)
357 -- In [p], useful fields are:
358 -- * [transformers]: as usual
359 -- * [name]: as usual
360 -- * [primary]: the atomic expression parser, or a multisequence config
362 -- * [prefix]: prefix operators config table, see above.
363 -- * [infix]: infix operators config table, see above.
364 -- * [suffix]: suffix operators config table, see above.
366 -- After creation, these fields are added:
367 -- * [kind] == "expr"
368 -- * [parse] as usual
369 -- * each table is turned into a multisequence, and therefore has an
372 -------------------------------------------------------------------------------
374 make_parser ("expr", p)
376 -------------------------------------------------------------------
378 -- In addition to the lexer, it takes an optional precedence:
379 -- it won't read expressions whose precedence is lower or equal
381 -------------------------------------------------------------------
382 function p:parse (lx, prec)
385 ------------------------------------------------------
386 -- Extract the right parser and the corresponding
387 -- options table, for (pre|in|suff)fix operators.
388 -- Options include prec, assoc, transformers.
389 ------------------------------------------------------
390 local function get_parser_info (tab)
391 local p2 = tab:get (lx:is_keyword (lx:peek()))
392 if p2 then -- keyword-based sequence found
393 local function parser(lx) return raw_parse_sequence(lx, p2) end
395 else -- Got to use the default parser
396 local d = tab.default
397 if d then return d.parse or d.parser, d
398 else return false, false end
402 ------------------------------------------------------
403 -- Look for a prefix sequence. Multiple prefixes are
404 -- handled through the recursive [p.parse] call.
405 -- Notice the double-transform: one for the primary
406 -- expr, and one for the one with the prefix op.
407 ------------------------------------------------------
408 local function handle_prefix ()
409 local fli = lx:lineinfo_right()
410 local p2_func, p2 = get_parser_info (self.prefix)
411 local op = p2_func and p2_func (lx)
412 if op then -- Keyword-based sequence found
413 local ili = lx:lineinfo_right() -- Intermediate LineInfo
414 local e = p2.builder (op, self:parse (lx, p2.prec))
415 local lli = lx:lineinfo_left()
416 return transform (transform (e, p2, ili, lli), self, fli, lli)
417 else -- No prefix found, get a primary expression
418 local e = self.primary(lx)
419 local lli = lx:lineinfo_left()
420 return transform (e, self, fli, lli)
422 end --</expr.parse.handle_prefix>
424 ------------------------------------------------------
425 -- Look for an infix sequence+right-hand-side operand.
426 -- Return the whole binary expression result,
427 -- or false if no operator was found.
428 ------------------------------------------------------
429 local function handle_infix (e)
430 local p2_func, p2 = get_parser_info (self.infix)
431 if not p2 then return false end
433 -----------------------------------------
434 -- Handle flattening operators: gather all operands
435 -- of the series in [list]; when a different operator
436 -- is found, stop, build from [list], [transform] and
438 -----------------------------------------
439 if (not p2.prec or p2.prec>prec) and p2.assoc=="flat" then
440 local fli = lx:lineinfo_right()
441 local pflat, list = p2, { e }
443 local op = p2_func(lx)
444 if not op then break end
445 table.insert (list, self:parse (lx, p2.prec))
446 local _ -- We only care about checking that p2==pflat
447 _, p2 = get_parser_info (self.infix)
449 local e2 = pflat.builder (list)
450 local lli = lx:lineinfo_left()
451 return transform (transform (e2, pflat, fli, lli), self, fli, lli)
453 -----------------------------------------
454 -- Handle regular infix operators: [e] the LHS is known,
455 -- just gather the operator and [e2] the RHS.
456 -- Result goes in [e3].
457 -----------------------------------------
458 elseif p2.prec and p2.prec>prec or
459 p2.prec==prec and p2.assoc=="right" then
460 local fli = e.lineinfo.first -- lx:lineinfo_right()
461 local op = p2_func(lx)
462 if not op then return false end
463 local e2 = self:parse (lx, p2.prec)
464 local e3 = p2.builder (e, op, e2)
465 local lli = lx:lineinfo_left()
466 return transform (transform (e3, p2, fli, lli), self, fli, lli)
468 -----------------------------------------
469 -- Check for non-associative operators, and complain if applicable.
470 -----------------------------------------
471 elseif p2.assoc=="none" and p2.prec==prec then
472 parse_error (lx, "non-associative operator!")
474 -----------------------------------------
475 -- No infix operator suitable at that precedence
476 -----------------------------------------
477 else return false end
479 end --</expr.parse.handle_infix>
481 ------------------------------------------------------
482 -- Look for a suffix sequence.
483 -- Return the result of suffix operator on [e],
484 -- or false if no operator was found.
485 ------------------------------------------------------
486 local function handle_suffix (e)
487 -- FIXME bad fli, must take e.lineinfo.first
488 local p2_func, p2 = get_parser_info (self.suffix)
489 if not p2 then return false end
490 if not p2.prec or p2.prec>=prec then
491 --local fli = lx:lineinfo_right()
492 local fli = e.lineinfo.first
493 local op = p2_func(lx)
494 if not op then return false end
495 local lli = lx:lineinfo_left()
496 e = p2.builder (e, op)
497 e = transform (transform (e, p2, fli, lli), self, fli, lli)
501 end --</expr.parse.handle_suffix>
503 ------------------------------------------------------
504 -- Parser body: read suffix and (infix+operand)
505 -- extensions as long as we're able to fetch more at
506 -- this precedence level.
507 ------------------------------------------------------
508 local e = handle_prefix()
510 local x = handle_suffix (e); e = x or e
511 local y = handle_infix (e); e = y or e
514 -- No transform: it already happened in operators handling
518 -------------------------------------------------------------------
520 -------------------------------------------------------------------
521 if not p.primary then p.primary=p[1]; p[1]=nil end
522 for _, t in ipairs{ "primary", "prefix", "infix", "suffix" } do
523 if not p[t] then p[t] = { } end
524 if not is_parser(p[t]) then multisequence(p[t]) end
526 function p:add(...) return self.primary:add(...) end
531 -------------------------------------------------------------------------------
533 -- List parser generator
535 -------------------------------------------------------------------------------
536 -- In [p], the following fields can be provided in input:
538 -- * [builder]: takes list of subparser results, returns AST
539 -- * [transformers]: as usual
540 -- * [name]: as usual
542 -- * [terminators]: list of strings representing the keywords which
543 -- might mark the end of the list. When non-empty, the list is
544 -- allowed to be empty. A string is treated as a single-element
545 -- table, whose element is that string, e.g. ["do"] is the same as
548 -- * [separators]: list of strings representing the keywords which can
549 -- separate elements of the list. When non-empty, one of these
550 -- keyword has to be found between each element. Lack of a separator
551 -- indicates the end of the list. A string is treated as a
552 -- single-element table, whose element is that string, e.g. ["do"]
553 -- is the same as [{"do"}]. If [terminators] is empty/nil, then
554 -- [separators] has to be non-empty.
556 -- After creation, the following fields are added:
557 -- * [parse] the parsing function lexer->AST
558 -- * [kind] == "list"
560 -------------------------------------------------------------------------------
562 make_parser ("list", p)
564 -------------------------------------------------------------------
566 -------------------------------------------------------------------
567 function p:parse (lx)
569 ------------------------------------------------------
570 -- Used to quickly check whether there's a terminator
571 -- or a separator immediately ahead
572 ------------------------------------------------------
573 local function peek_is_in (keywords)
574 return keywords and lx:is_keyword(lx:peek(), unpack(keywords)) end
577 local fli = lx:lineinfo_right()
579 -- if there's a terminator to start with, don't bother trying
580 if not peek_is_in (self.terminators) then
581 repeat table.insert (x, self.primary (lx)) -- read one element
583 -- First reason to stop: There's a separator list specified,
584 -- and next token isn't one. Otherwise, consume it with [lx:next()]
585 self.separators and not(peek_is_in (self.separators) and lx:next()) or
586 -- Other reason to stop: terminator token ahead
587 peek_is_in (self.terminators) or
588 -- Last reason: end of file reached
592 local lli = lx:lineinfo_left()
594 -- Apply the builder. It can be a string, or a callable value,
595 -- or simply nothing.
596 local b = self.builder
598 if type(b)=="string" then x.tag = b -- b is a string, use it as a tag
599 elseif type(b)=="function" then x=b(x)
601 local bmt = getmetatable(b)
602 if bmt and bmt.__call then x=b(x) end
605 return transform (x, self, fli, lli)
608 -------------------------------------------------------------------
610 -------------------------------------------------------------------
611 if not p.primary then p.primary = p[1]; p[1] = nil end
612 if type(p.terminators) == "string" then p.terminators = { p.terminators }
613 elseif p.terminators and #p.terminators == 0 then p.terminators = nil end
614 if type(p.separators) == "string" then p.separators = { p.separators }
615 elseif p.separators and #p.separators == 0 then p.separators = nil end
621 -------------------------------------------------------------------------------
623 -- Keyword-conditionned parser generator
625 -------------------------------------------------------------------------------
627 -- Only apply a parser if a given keyword is found. The result of
628 -- [gg.onkeyword] parser is the result of the subparser (modulo
629 -- [transformers] applications).
631 -- lineinfo: the keyword is *not* included in the boundaries of the
632 -- resulting lineinfo. A review of all usages of gg.onkeyword() in the
633 -- implementation of metalua has shown that it was the appropriate choice
638 -- * [name]: as usual
640 -- * [transformers]: as usual
642 -- * [peek]: if non-nil, the conditionning keyword is left in the lexeme
643 -- stream instead of being consumed.
645 -- * [primary]: the subparser.
647 -- * [keywords]: list of strings representing triggering keywords.
649 -- * Table-part entries can contain strings, and/or exactly one parser.
650 -- Strings are put in [keywords], and the parser is put in [primary].
652 -- After the call, the following fields will be set:
654 -- * [parse] the parsing method
655 -- * [kind] == "onkeyword"
659 -------------------------------------------------------------------------------
660 function onkeyword (p)
661 make_parser ("onkeyword", p)
663 -------------------------------------------------------------------
665 -------------------------------------------------------------------
667 if lx:is_keyword (lx:peek(), unpack(self.keywords)) then
668 --local fli = lx:lineinfo_right()
669 if not self.peek then lx:next() end
670 local content = self.primary (lx)
671 --local lli = lx:lineinfo_left()
672 local fli, lli = content.lineinfo.first, content.lineinfo.last
673 return transform (content, p, fli, lli)
674 else return false end
677 -------------------------------------------------------------------
679 -------------------------------------------------------------------
680 if not p.keywords then p.keywords = { } end
681 for _, x in ipairs(p) do
682 if type(x)=="string" then table.insert (p.keywords, x)
683 else assert (not p.primary and is_parser (x)); p.primary = x end
685 if not next (p.keywords) then
686 eprintf("Warning, no keyword to trigger gg.onkeyword") end
687 assert (p.primary, 'no primary parser in gg.onkeyword')
692 -------------------------------------------------------------------------------
694 -- Optional keyword consummer pseudo-parser generator
696 -------------------------------------------------------------------------------
698 -- This doesn't return a real parser, just a function. That function parses
699 -- one of the keywords passed as parameters, and returns it. It returns
700 -- [false] if no matching keyword is found.
702 -- Notice that tokens returned by lexer already carry lineinfo, therefore
703 -- there's no need to add them, as done usually through transform() calls.
704 -------------------------------------------------------------------------------
705 function optkeyword (...)
707 if type (args[1]) == "table" then
711 for _, v in ipairs(args) do assert (type(v)=="string") end
713 local x = lx:is_keyword (lx:peek(), unpack (args))
714 if x then lx:next(); return x
715 else return false end
720 -------------------------------------------------------------------------------
722 -- Run a parser with a special lexer
724 -------------------------------------------------------------------------------
726 -- This doesn't return a real parser, just a function.
727 -- First argument is the lexer class to be used with the parser,
728 -- 2nd is the parser itself.
729 -- The resulting parser returns whatever the argument parser does.
731 -------------------------------------------------------------------------------
732 function with_lexer(new_lexer, parser)
734 -------------------------------------------------------------------
735 -- Most gg functions take their parameters in a table, so it's
736 -- better to silently accept when with_lexer{ } is called with
737 -- its arguments in a list:
738 -------------------------------------------------------------------
739 if not parser and #new_lexer==2 and type(new_lexer[1])=='table' then
740 return with_lexer(unpack(new_lexer))
743 -------------------------------------------------------------------
744 -- Save the current lexer, switch it for the new one, run the parser,
745 -- restore the previous lexer, even if the parser caused an error.
746 -------------------------------------------------------------------
748 local old_lexer = getmetatable(lx)
750 setmetatable(lx, new_lexer)
751 local status, result = pcall(parser, lx)
753 setmetatable(lx, old_lexer)
754 if status then return result else error(result) end