helm/DEVEL/pxp/pxp/m2parsergen/README

   1 ----------------------------------------------------------------------
   2 m2parsergen
   3 ----------------------------------------------------------------------
   4
   5 This is a parser generator for top-down (or recursively descending) parsers.
   6 The input file must be structured as follows:
   7
   8 ---------------------------------------- Begin of file
   9
  10 <OCAML TEXT ("preamble")>
  11
  12 %%
  13
  14 <DECLARATIONS>
  15
  16 %%
  17
  18 <RULES>
  19
  20 %%
  21
  22 <OCAML TEXT ("postamble")>
  23
  24 ---------------------------------------- End of file
  25
  26 The two-character combination %% separates the various sections. The
  27 text before the first %% and after the last %% will be copied verbatim
  28 to the output file.
  29
  30 Within the declarations and rules sections you must use /* ... */ as
  31 comment braces.
  32
  33 There are two types of declarations:
  34
  35 %token Name
  36
  37 declares that Name is a token without associated value, and
  38
  39 %token <> Name
  40
  41 declares that Name is a token with associated value (i.e. Name x).
  42
  43 In contrast to ocamlyacc, you need not to specify a type. This is a
  44 fundamental difference, because m2parsergen will not generate a type
  45 declaration for a "token" type; you must do this yourself.
  46
  47 You need not to declare start symbols; every grammar rule may be used
  48 as start symbol.
  49
  50 The rules look like:
  51
  52 name_of_rule(arg1, arg2, ...):
  53   label1:symbol1 label2:symbol2 ... {{ CODE }}
  54 | label1:symbol1 label2:symbol2 ... {{ CODE }}
  55 ...
  56 | label1:symbol1 label2:symbol2 ... {{ CODE }}
  57
  58 The rules may have arguments (note that you must write the
  59 parantheses, even if the rule does not have arguments). Here, arg1,
  60 arg2, ... are the formal names of the arguments; you may refer to them
  61 in OCaml code.
  62
  63 Furthermore, the symbols may have labels (you can leave the labels
  64 out). You can refer to the value associated with a symbol by its
  65 label, i.e. there is an OCaml variable with the same name as the label
  66 prescribes, and this variable contains the value.
  67
  68 The OCaml code must be embraced by {{ and }}, and these separators
  69 must not occur within the code.
  70
  71 EXAMPLE:
  72
  73 prefix_term():
  74   Plus_symbol Left_paren v1:prefix_term() Comma v2:prefix_term() Right_paren
  75     {{ v1 + v2 }}
  76 | Times_symbol Left_paren v1:prefix_term() Comma v2:prefix_term() Right_paren
  77     {{ v1 * v2 }}
  78 | n:Number
  79     {{ n }}
  80
  81 As you can see in the example, you must pass values for the arguments
  82 if you call non-terminal symbols (here, the argument list is empty: ()).
  83
  84 The generated parsers behave as follows:
  85
  86 - A rule is applicable to a token sequence if the first token is
  87   matched by the rule.
  88
  89   In the example: prefix_term is applicable if the first token of a
  90   sequence is either Plus_symbol, Times_symbol, or Number.
  91
  92 - One branch of the applicable rule is selected: it is the first
  93   branch that matches the first token. THE OTHER TOKENS DO NOT HAVE
  94   ANY EFFECT ON BRANCH SELECTION!
  95
  96   For instance, in the following rule the second branch is never
  97   selected, because only the A is used to select the branch:
  98
  99   a():
 100     A B {{ ... }}
 101   | A C {{ ... }}
 102
 103 - Once a branch is selected, it is checked whether the branch matches
 104   the token sequence. If this check succeeds, the code section of the
 105   branch is executed, and the resulting value is returned to the
 106   caller.
 107   If the check fails, the exception Parsing.Parse_error is raised.
 108   Normally, this exception is not caught, and will force the parser
 109   to stop.
 110
 111   The check in detail:
 112
 113   If the rule demands a terminal, there a must be exactly this
 114   terminal at the corresponding location in the token sequence.
 115
 116   If the rule demands a non-terminal, it is checked whether the rule
 117   for to this non-terminal is applicable. If so, the branch
 118   is selected, and recursively checked. If the rule is not applicable,
 119   the check fails immediately.
 120
 121 - THERE IS NO BACKTRACKING!
 122
 123   Note that the following works (but the construction is resolved at
 124   generation time):
 125
 126   rule1() =
 127      rule2() A B ... {{ ... }}
 128
 129   rule2() =
 130      C {{ ... }}
 131    | D {{ ... }}
 132
 133   In this case, the (only) branch of rule1 is selected if the next
 134   token is C or D.
 135
 136 ---
 137
 138
 139
 140 *** Options and repetitions ***
 141
 142 Symbols can be tagged as being optional, or to occur repeatedly:
 143
 144 rule():
 145   Name whitespace()* Question_mark?
 146
 147 - "*": The symbol matches zero or more occurrences.
 148
 149 - "?": The symbol matches zero or one occurrence.
 150
 151 This is done as follows:
 152
 153 - terminal*: The maximum number of consecutive tokens <terminal> are
 154              matched.
 155 - non-terminal*: The maximum number of the subsequences matching
 156                  <non-terminal> are matched. Before another
 157                  subsequence is matched, it is checked whether the
 158                  rule for <non-terminal> is applicable. If so, the
 159                  rule is invoked and must succeed (otherwise Parsing.
 160                  Parse_error). If not, the loop is exited.
 161
 162 - terminal?: If the next token is <terminal>, it is matched. If not,
 163              no token is matched.
 164
 165 - non-terminal?: It is checked whether the rule for <non-terminal>
 166                  is applicable. If so, the rule is invoked, and
 167                  matches a sequence of tokens. If not, no token is
 168                  matched.
 169
 170 You may refer to repeated or optional symbols by labels. In this case,
 171 the label is associated with lists of values, or optional values,
 172 respectively:
 173
 174 rule():
 175   A  lab:other()*  lab':unlikely()?
 176     {{ let n = List.length lab in ...
 177        match lab' with
 178          None -> ...
 179        | Some v -> ...
 180     }}
 181
 182 A different scheme is applied if the symbol is a token without
 183 associated value (%token Name, and NOT %token <> Name):
 184
 185 rule():
 186   A lab:B* lab':C?
 187
 188 Here, "lab" becomes an integer variable counting the number of Bs, and
 189 "lab'" becomes a boolean variable denoting whether there is a C or not.
 190
 191
 192 *** Early let-binding ***
 193
 194 You may put some OCaml code directly after the first symbol of a
 195 branch:
 196
 197 rule():
 198   A $ {{ let-binding }} C D ... {{ ... }}
 199
 200 The code brace {{ let-binding }} must be preceded by a dollar
 201 sign. You can put "let ... = ... in" statements into this brace:
 202
 203 rule1():
 204   n:A $ {{ let twice = 2 * n in }} rule2(twice) {{ ... }}
 205
 206 This code is executed once the branch is selected.
 207
 208
 209 *** Very early let-binding ***
 210
 211 This is also possible:
 212
 213 rule():
 214   $ {{ CODE }}
 215   A
 216   ...
 217
 218 The CODE is executed right when the branch is selected, and before any
 219 other happens. (Only for hacks!)
 220
 221
 222
 223 *** Computed rules ***
 224
 225 rule():
 226   A $ {{ let followup = ... some function ... in }} [ followup ]()
 227     {{ ... }}
 228
 229 Between [ and ], you can refer to the O'Caml name of *any* function.
 230 Here, the function "followup" is bound in the let-binding.
 231
 232
 233 *** Error handling ***
 234
 235 If a branch is already selected, but the check fails whether the other
 236 symbols of the branch match, it is possible to catch the resulting
 237 exception and to find out at which position the failure has occurred.
 238
 239 rule():
 240   x:A y:B z:C {{ ... }} ? {{ ERROR-CODE }}
 241
 242 After a question mark, it is allowed to append another code
 243 brace. This code is executed if the branch check fails (but not if the
 244 branch is not selected nor if no branches are selected). The string
 245 variable !yy_position contains the label of the symbol that caused the
 246 failure (or it contains the empty string if the symbol does not have a
 247 label).
 248
 249 Example:
 250
 251 rule():
 252   x:A y:B z:C {{ print_endline "SUCCESS" }} ? {{ print_endline !yy_position }}
 253
 254 If the token sequence is A B C, "SUCCESS" will be printed. If the
 255 sequence is A C, the second symbol fails, and "y" will be printed. If
 256 the sequence is A B D, the third symbol fails, and "z" will be
 257 printed. If the sequence is B, the rule will be never selected because
 258 it is not applicable.
 259
 260
 261
 262 *** Error recovery ***
 263
 264 You may call the functions yy_current, yy_get_next, or one of the
 265 parse_* functions in the error brace to recover from the error
 266 (e.g. to move ahead until a certain token is reached). See below.
 267
 268
 269
 270 *** How to call the parser ***
 271
 272 The rules are rewritten into a OCaml let-binding:
 273
 274 let rec parse_<rule1> ... = ...
 275     and parse_<rule2> ... = ...
 276     ...
 277     and parse_<ruleN> ... = ...
 278 in
 279
 280 i.e. there are lots of functions, and the name of the functions are
 281 "parse_" plus the name of the rules. You can call every function.
 282
 283 The first two arguments of the functions have a special meaning; the
 284 other arguments are the arguments coming from the rule description:
 285
 286 rule(a,b):
 287   ...
 288
 289 ===>
 290
 291 let rec parse_rule yy_current yy_get_next a b = ...
 292
 293 The first argument, yy_current, is a function that returns the current
 294 token. The second arguments, yy_get_next, is a function that switches
 295 to the next token, and returns it.
 296
 297 If the tokens are stored in a list, this may be a definition:
 298
 299 let input = ref [ Token1; Token2; ... ] in
 300 let yy_current() = List.hd !input in
 301 let yy_get_next () =
 302   input := List.tl !input;
 303   List.hd !input
 304
 305 When you call one of the parser functions, the current token must
 306 already be loaded, i.e. yy_current returns the first token to match by
 307 the function.
 308
 309 After the functions has returned, the current token is the token
 310 following the sequence of tokens that have been matched by the
 311 function.
 312
 313 The function returns the value computed by the OCaml code brace of the
 314 rule (or the value of the error brace).
 315
 316 If the rule is not applicable, the exception Not_found is raised.
 317
 318 If the rule is applicable, but it does not match, the exception
 319 Parsing.Parse_error is raised.