README-parser.md

   1 Metalua Parser
   2 ==============
   3
   4 `metalua-parser` is a subset of the Metalua compiler, which turns
   5 valid Lua source files and strings into abstract syntax trees
   6 (AST). This README includes a description of this AST format. People
   7 interested by Lua code analysis and generation are encouraged to
   8 produce and/or consume this format to represent ASTs.
   9
  10 It has been designed for Lua 5.1. It hasn't been tested against
  11 Lua 5.2, but should be easily ported.
  12
  13 ## Usage
  14
  15 Module `metalua.compiler` has a `new()` function, which returns a
  16 compiler instance. This instance has a set of methods of the form
  17 `:xxx_to_yyy(input)`, where `xxx` and `yyy` must be one of the
  18 following:
  19
  20 * `srcfile` the name of a Lua source file;
  21 * `src` a string containing the Lua sources of a list of statements;
  22 * `lexstream` a lexical tokens stream;
  23 * `ast` an abstract syntax tree;
  24 * `bytecode` a chunk of Lua bytecode that can be loaded in a Lua 5.1
  25   VM (not available if you only installed the parser);
  26 * `function` an executable Lua function.
  27
  28 Compiling into bytecode or executable functions requires the whole
  29 Metalua compiler, not only the parser. The most frequently used
  30 functions are `:src_to_ast(source_string)` and
  31 `:srcfile_to_ast("path/to/source/file.lua")`.
  32
  33     mlc = require 'metalua.compiler'.new()
  34     ast = mlc :src_to_ast[[ return 123 ]]
  35
  36 A compiler instance can be reused as much as you want; it's only
  37 interesting to work with more than one compiler instance when you
  38 start extending their grammars.
  39
  40 ## Abstract Syntax Trees definition
  41
  42 ### Notation
  43
  44 Trees are written below with some Metalua syntax sugar, which
  45 increases their readability. the backquote symbol introduces a `tag`,
  46 i.e. a string stored in the `"tag"` field of a table:
  47
  48 * `` `Foo{ 1, 2, 3 }`` is a shortcut for `{tag="Foo", 1, 2, 3}`;
  49 * `` `Foo`` is a shortcut for `{tag="Foo"}`;
  50 * `` `Foo 123`` is a shortcut for `` `Foo{ 123 }``, and therefore
  51   `{tag="Foo", 123 }`; the expression after the tag must be a literal
  52   number or string.
  53
  54 When using a Metalua interpreter or compiler, the backtick syntax is
  55 supported and can be used directly. Metalua's pretty-printing helpers
  56 also try to use backtick syntax whenever applicable.
  57
  58 ### Tree elements
  59
  60 Tree elements are mainly categorized into statements `stat`,
  61 expressions `expr` and lists of statements `block`. Auxiliary
  62 definitions include function applications/method invocation `apply`,
  63 are both valid statements and expressions, expressions admissible on
  64 the left-hand-side of an assignment statement `lhs`.
  65
  66     block: { stat* }
  67
  68     stat:
  69       `Do{ stat* }
  70     | `Set{ {lhs+} {expr+} }                    -- lhs1, lhs2... = e1, e2...
  71     | `While{ expr block }                      -- while e do b end
  72     | `Repeat{ block expr }                     -- repeat b until e
  73     | `If{ (expr block)+ block? }               -- if e1 then b1 [elseif e2 then b2] ... [else bn] end
  74     | `Fornum{ ident expr expr expr? block }    -- for ident = e, e[, e] do b end
  75     | `Forin{ {ident+} {expr+} block }          -- for i1, i2... in e1, e2... do b end
  76     | `Local{ {ident+} {expr+}? }               -- local i1, i2... = e1, e2...
  77     | `Localrec{ ident expr }                   -- only used for 'local function'
  78     | `Goto{ <string> }                         -- goto str
  79     | `Label{ <string> }                        -- ::str::
  80     | `Return{ <expr*> }                        -- return e1, e2...
  81     | `Break                                    -- break
  82     | apply
  83
  84     expr:
  85       `Nil  |  `Dots  |  `True  |  `False
  86     | `Number{ <number> }
  87     | `String{ <string> }
  88     | `Function{ { `Id{ <string> }* `Dots? } block }
  89     | `Table{ ( `Pair{ expr expr } | expr )* }
  90     | `Op{ opid expr expr? }
  91     | `Paren{ expr }       -- significant to cut multiple values returns
  92     | apply
  93     | lhs
  94
  95     apply:
  96       `Call{ expr expr* }
  97     | `Invoke{ expr `String{ <string> } expr* }
  98
  99     lhs: `Id{ <string> } | `Index{ expr expr }
 100
 101     opid: 'add'   | 'sub'   | 'mul'   | 'div'
 102         | 'mod'   | 'pow'   | 'concat'| 'eq'
 103         | 'lt'    | 'le'    | 'and'   | 'or'
 104         | 'not'   | 'len'
 105
 106 ### Meta-data (lineinfo)
 107
 108
 109 ASTs also embed some metadata, allowing to map them to their source
 110 representation. Those informations are stored in a `"lineinfo"` field
 111 in each tree node, which points to the range of characters in the
 112 source string which represents it, and to the content of any comment
 113 that would appear immediately before or after that node.
 114
 115 Lineinfo objects have two fields, `"first"` and `"last"`, describing
 116 respectively the beginning and the end of the subtree in the
 117 sources. For instance, the sub-node ``Number{123}` produced by parsing
 118 `[[return 123]]` will have `lineinfo.first` describing offset 8, and
 119 `lineinfo.last` describing offset 10:
 120
 121
 122     > mlc = require 'metalua.compiler'.new()
 123     > ast = mlc :src_to_ast "return 123 -- comment"
 124     > print(ast[1][1].lineinfo)
 125     <?|L1|C8-10|K8-10|C>
 126     >
 127
 128 A lineinfo keeps track of character offsets relative to the beginning
 129 of the source string/file ("K8-10" above), line numbers (L1 above; a
 130 lineinfo spanning on several lines would read something like "L1-10"),
 131 columns i.e. offset within the line ("C8-10" above), and a filename if
 132 available (the "?" mark above indicating that we have no file name, as
 133 the AST comes from a string). The final "|C>" indicates that there's a
 134 comment immediately after the node; an initial "<C|" would have meant
 135 that there was a comment immediately before the node.
 136
 137 Positions represent either the end of a token and the beginning of an
 138 inter-token space (`"last"` fields) or the beginning of a token, and
 139 the end of an inter-token space (`"first"` fields). Inter-token spaces
 140 might be empty. They can also contain comments, which might be useful
 141 to link with surrounding tokens and AST subtrees.
 142
 143 Positions are chained with their "dual" one: a position at the
 144 beginning of and inter-token space keeps a refernce to the position at
 145 the end of that inter-token space in its `"facing"` field, and
 146 conversly, end-of-inter-token positions keep track of the inter-token
 147 space beginning, also in `"facing"`. An inter-token space can be
 148 empty, e.g. in `"2+2"`, in which case `lineinfo==lineinfo.facing`.
 149
 150 Comments are also kept in the `"comments"` field. If present, this
 151 field contains a list of comments, with a `"lineinfo"` field
 152 describing the span between the first and last comment. Each comment
 153 is represented by a list of one string, with a `"lineinfo"` describing
 154 the span of this comment only. Consecutive lines of `--` comments are
 155 considered as one comment: `"-- foo\n-- bar\n"` parses as one comment
 156 whose text is `"foo\nbar"`, whereas `"-- foo\n\n-- bar\n"` parses as
 157 two comments `"foo"` and `"bar"`.
 158
 159 So for instance, if `f` is the AST of a function and I want to
 160 retrieve the comment before the function, I'd do:
 161
 162     f_comment = f.lineinfo.first.comments[1][1]
 163
 164 The informations in lineinfo positions, i.e. in each `"first"` and
 165 `"last"` field, are held in the following fields:
 166
 167 * `"source"` the filename (optional);
 168 * `"offset"` the 1-based offset relative to the beginning of the string/file;
 169 * `"line"` the 1-based line number;
 170 * `"column"` the 1-based offset within the line;
 171 * `"facing"` the position at the opposite end of the inter-token space.
 172 * `"comments"` the comments in the associated inter-token space (optional).
 173 * `"id"` an arbitrary number, which uniquely identifies an inter-token
 174   space within a given tokens stream.
 175