ocean-lang.org Git - ocean/blob - csrc/scanner.mdc

   1 # Lexical Scanner #
   2
   3 ## The Task at Hand ##
   4
   5 The main task of the lexical scanner is to convert a stream of
   6 characters into a stream of tokens.  The tokens are then typically
   7 used by a parser to extract the syntactic structure.
   8
   9 The stream of characters are assumed to be in memory identified by a
  10 linked list of blocks, such as provided by the "[mdcode][]" literate
  11 program extractor.  A single token may never cross a block boundary.
  12
  13 [mdcode]: mdcode.html
  14
  15 ###### includes
  16         #include "mdcode.h"
  17
  18 The text is assumed to be UTF-8 though some matching assumes the
  19 ASCII subset.  If the text provided does not conform to UTF-8 an error
  20 will be reported and some number of bytes will be skipped.
  21
  22 ###### public types
  23         #include <wchar.h>
  24         #include <wctype.h>
  25         #include <unicode/uchar.h>
  26
  27 Tokens are returned by successive calls to the main interface
  28 function: `token_next()` which has a `state` structure to keep track
  29 of where it is up to.  Each token carries not just a numeric
  30 identifier but also the code block, the line and character within that
  31 block, and the actual start and length using the `struct text` from
  32 "mdcode".
  33
  34 ###### public types
  35         struct token {
  36                 int               num;
  37                 struct code_node *node;
  38                 struct text       txt;
  39                 int               line, col;
  40         };
  41         struct token_state;
  42
  43 ###### private types
  44         struct token_state {
  45                 ## state fields
  46         };
  47
  48 ###### exported functions
  49         struct token token_next(struct token_state *state);
  50
  51 ###### main functions
  52         struct token token_next(struct token_state *state)
  53         {
  54                 ## token_next init
  55                 while (1) {
  56                         wint_t ch;
  57                         struct token tk;
  58
  59                         ## one token
  60                 }
  61         }
  62
  63 The `line` and `col` offsets are useful for reporting errors.
  64 The `txt` provides the content when that is important.
  65
  66 ### Token types and configuration ##
  67
  68 The scanner is not completely general, yet not completely specified.
  69 There are a fixed set of token types, though particular tokens within
  70 those types can be distinguish via configuration.
  71
  72 Most token types may be explicitly ignored, as typically comments
  73 would be.  The exact consequence of ignoring each token type varies
  74 from token to token.
  75
  76 ###### public types
  77         struct token_config {
  78                 int ignored;    // bit set of ignored tokens.
  79                 ## token config parameters
  80         };
  81
  82 ###### state fields
  83         struct token_config *conf;
  84
  85 ###### token_next init
  86         int ignored = state->conf->ignored;
  87
  88 The different tokens are numbers, words, marks, strings, comments,
  89 newlines, EOF, and indents, each of which is examined in detail below.
  90
  91 There are various cases where no token can be found in part of the
  92 input.  All of these will be reported as a `TK_error` token.
  93
  94 It is possible to declare a number of strings which form distinct
  95 tokens (rather than being grouped as e.g. 'word').  These are given
  96 token numbers from `TK_reserved` upwards.
  97
  98 ###### public types
  99         enum token_num {
 100                 TK_error,
 101                 ## token types
 102                 TK_reserved
 103         };
 104
 105 ### Numbers
 106
 107 Numbers are the messiest tokens to parse, primarily because they can
 108 contain characters that also have meaning outside of numbers and,
 109 particularly, immediately after numbers.
 110
 111 The obvious example is the '`-`' sign.  It can come inside a number for
 112 a negative exponent, or after a number as a subtraction operator.  To
 113 be sure we have parsed as best as possible we need to only allow the
 114 '`-`' inside a number if it is after an exponent character.  This can be
 115 `e` or `p` (for hex exponents), but `e` can also be a hexadecimal
 116 digit, so we don't allow '`-`' after just any `e`.
 117
 118 To make matters worse, our language designer has decided to experiment
 119 with allowing commas to be used as the decimal indicator, and spaces
 120 to be used to separate groups of digits in large numbers.  Both of
 121 these can reasonably be restricted to appear between two digits, so we
 122 have to add that condition to our tests.  For consistency we require
 123 every non-alpha-numeric to appear between two hex digits, with the
 124 exception that a sign can appear only after a 'p' or 'e', and a space
 125 can only appear between decimal digits.  Allowing a space before a
 126 letter easily leads to confusion, such a in `a < 3 and b < 4`.
 127
 128 So we cannot just treat numbers as starting with a digit and being
 129 followed by some set of characters.  We need more structure than that.
 130
 131 So:
 132
 133 - Numbers must start with a digit.
 134 - If the first digit is zero, the next character should be a base
 135   signifier (one of `xob`) or a decimal marker (`.` or `,`) (though this isn't
 136   enforced at this stage)
 137   In the first case the only first `p` or `P` may be followed by a sign.
 138 - If the number doesn't start with `0` followed by one of `xob`, the
 139   first `e` may be followed by a sign.
 140 - A sign must always be followed by a digit.
 141 - Any digit may be followed by a space or underscore and any hex digit
 142   maybe followed by an underscore, providing that the subsequence character
 143   is also a digit (for space) or hex digit (for underscore).
 144   This rule will require an extra level of 'unget' to be
 145   supported when handling characters.
 146 - Otherwise any digits or ASCII letters are allowed.  We do not at
 147   this point check that the digits given are permitted by the base.
 148   That will happen when the token is converted to a number.
 149
 150 To allow easy configuration, the various non alphanumeric characters
 151 are only permitted if they are listed in a configuration parameter.
 152
 153 ###### token config parameters
 154         char *number_chars;
 155
 156 Note that numbers may not start with a period, so `.75` is not a
 157 number.  This is not the norm, but is not unheard of.  Excluding these
 158 numbers simplifies the rule at very little cost.
 159
 160 ###### token types
 161         TK_number,
 162
 163 If TK_number is ignored, digits will result in an error unless they
 164 are declared to be a start character for words.
 165
 166 ###### includes
 167
 168         #include <string.h>
 169
 170 ###### parse number
 171
 172         if (iswdigit(ch) && !(ignored & (1<<TK_number))) {
 173                 int prev = 0;
 174                 int expect_p = 0;
 175                 int decimal_mark = 0;
 176                 if (ch == '0') {
 177                         wchar_t ch2 = get_char(state);
 178                         if (strchr("xobXOB", ch2) != NULL)
 179                                 expect_p = 1;
 180                         unget_char(state);
 181                 }
 182                 while (1) {
 183                         int sign_ok = 0;
 184                         switch(expect_p) {
 185                         case 0:
 186                                 if (ch == 'e' || ch == 'E') {
 187                                         sign_ok = 1;
 188                                         decimal_mark = 1;
 189                                 }
 190                                 break;
 191                         case 1:
 192                                 if (ch == 'p' || ch == 'P') {
 193                                         sign_ok = 1;
 194                                         decimal_mark = 1;
 195                                 }
 196                                 break;
 197                         }
 198                         save_unget_state(state);
 199                         prev = ch;
 200                         ch = get_char(state);
 201
 202                         if (!iswalnum(prev)) {
 203                                 /* special characters, like separators and decimal marks
 204                                  * and signs, must be followed by a hexdigit, and the
 205                                  * space and signs must be followed by a decimal digit.
 206                                  */
 207                                 if (!iswxdigit(ch) ||
 208                                    ((prev == '-' || prev == '+') && !iswdigit(ch)) ||
 209                                    (prev == ' ' && !iswdigit(ch))) {
 210                                         /* don't want the new char or the special */
 211                                         restore_unget_state(state);
 212                                         break;
 213                                 }
 214                         }
 215                         if (iswalnum(ch))
 216                                 continue;
 217
 218                         if (!strchr(state->conf->number_chars, ch)) {
 219                                 /* non-number char */
 220                                 break;
 221                         }
 222                         if (ch == '+' || ch == '-') {
 223                                 /* previous must be 'e' or 'p' in appropraite context */
 224                                 if (!sign_ok)
 225                                         break;
 226                                 expect_p = -1;
 227                         } else if (ch == ' ') {
 228                                 /* previous must be a digit */
 229                                 if (!iswdigit(prev))
 230                                         break;
 231                         } else {
 232                                 /* previous must be a hex digit */
 233                                 if (!iswxdigit(prev))
 234                                         break;
 235                         }
 236                         if (ch == '.' || ch == ',') {
 237                                 /* only one of these permitted */
 238                                 if (decimal_mark)
 239                                         break;
 240                                 decimal_mark = 1;
 241                         }
 242                 }
 243                 /* We seem to have a "number" token */
 244                 unget_char(state);
 245                 close_token(state, &tk);
 246                 tk.num = TK_number;
 247                 return tk;
 248         }
 249
 250 ### Words
 251 Words start with a "start" character followed by the longest
 252 sequence of "continue" characters.  The Unicode ID_START and
 253 ID_CONTINUE sets are always permitted, but other ASCII characters
 254 can be added to these sets.
 255
 256 ###### token config parameters
 257         char *word_start;
 258         char *word_cont;
 259
 260 ###### internal functions
 261         static int is_word_start(wchar_t ch, struct token_config *conf)
 262         {
 263                 return iswalpha(ch) ||
 264                        strchr(conf->word_start, ch) != NULL ||
 265                        u_hasBinaryProperty(ch, UCHAR_ID_START);
 266         }
 267
 268         static int is_word_continue(wchar_t ch, struct token_config *conf)
 269         {
 270                 return iswalnum(ch) ||
 271                        strchr(conf->word_cont, ch) != NULL ||
 272                        u_hasBinaryProperty(ch, UCHAR_ID_CONTINUE);
 273         }
 274
 275 Words can be either known or unknown.  Known words are referred to as
 276 "reserved words" and get a unique token number.  Unknown words are
 277 "identifiers" and are syntactically a single token.
 278
 279 ###### token types
 280         TK_ident,
 281
 282 A list of known words must be provided.  This list is shared with the
 283 "marks" which are described next.  The list must be lexically sorted
 284 and the length of the list must be given (`known_count`).
 285 Tokens matching these known words are reported as the index of the
 286 list added to `TK_reserved`.
 287
 288 If identifiers are ignored, then any word which is not listed as a
 289 known word results in an error.
 290
 291 ###### token config parameters
 292         const char **words_marks;
 293         int known_count;
 294
 295 ###### parse word
 296
 297         if (is_word_start(ch, state->conf)) {
 298                 int n;
 299                 /* A word: identifier or reserved */
 300                 do
 301                         ch = get_char(state);
 302                 while (is_word_continue(ch, state->conf));
 303                 unget_char(state);
 304                 close_token(state, &tk);
 305                 tk.num = TK_ident;
 306                 if (ignored & (1<<TK_ident))
 307                         tk.num = TK_error;
 308                 n = find_known(state->conf, tk.txt);
 309                 if (n >= 0)
 310                         tk.num = TK_reserved + n;
 311                 return tk;
 312         }
 313
 314 ### Marks
 315
 316 Marks are generally one or more punctuation marks joined together.  It
 317 would be nice to use the term "symbol" for these, but that causes
 318 confusion in a subsequent discussion of the grammar, which has terminal
 319 symbols and non-terminal symbols which are conceptually quite
 320 different.  So strings of punctuation characters will be marks.
 321
 322 A "mark" consists of ASCII characters that are not white space, are not
 323 "start" characters for words, and are not digits.
 324 These will collectively be called mark characters.
 325
 326 ###### internal functions
 327         static int is_mark(wchar_t ch, struct token_config *conf)
 328         {
 329                 return ch > ' ' &&
 330                        ch < 0x7f &&
 331                        !iswalnum(ch) &&
 332                        strchr(conf->word_start, ch) == NULL;
 333         }
 334
 335 As with words, there can be known and unknown marks, though the rules
 336 are slightly different.
 337
 338 Two marks do not need to be separated by a non-mark characters.  This
 339 is different from words which do need to be separated by at least one
 340 non-continue character.
 341
 342 The scanner will normally prefer longer sequences of mark characters,
 343 but will more strongly prefer known marks over unknown marks.  So if
 344 it finds a known mark where adding one more character does not result
 345 in a known mark, it will return that first known mark.
 346
 347 If no known mark is found we will test against strings and comments
 348 below before giving up and assuming an unknown mark.
 349
 350 If an unknown mark contains a quote character or a comment marker, and
 351 that token is not being ignored, then we terminate the unknown mark
 352 before that quote or comment.  This ensures that an unknown mark
 353 immediately before a string is handled correctly.
 354
 355 If the first character of a comment marker (i.e. '/') is a known mark,
 356 the above rules would suggest that the start of a comment would be
 357 parsed as that mark, which is not what is wanted.  So the introductory
 358 sequences for a comment ("//" and "/*") are treated as
 359 partially-known.  They prevent the leading "/" from being a mark by
 360 itself, but do not actually constitute a stand-alone mark.
 361
 362 If `TK_mark` is ignored, then unknown marks are returned as errors.
 363
 364 ###### token types
 365         TK_mark,
 366
 367 Known marks are included in the same list as the list of known words.
 368
 369 ###### parse mark
 370         tk.num = TK_error;
 371         while (is_mark(ch, state->conf)) {
 372                 int n;
 373                 wchar_t prev;
 374                 close_token(state, &tk);
 375                 n = find_known(state->conf, tk.txt);
 376                 if (n >= 0)
 377                         tk.num = TK_reserved + n;
 378                 else if (tk.num != TK_error) {
 379                         /* found a longest-known-mark, still need to
 380                          * check for comments
 381                          */
 382                         if (tk.txt.len == 2 && tk.txt.txt[0] == '/' &&
 383                             (ch == '/' || ch == '*')) {
 384                                 /* Yes, this is a comment, not a '/' */
 385                                 restore_unget_state(state);
 386                                 tk.num = TK_error;
 387                                 break;
 388                         }
 389                         unget_char(state);
 390                         close_token(state, &tk);
 391                         return tk;
 392                 }
 393                 prev = ch;
 394                 save_unget_state(state);
 395                 ch = get_char(state);
 396                 if (!(ignored & (1<<TK_string)) && n < 0 &&is_quote(ch) && !is_quote(prev))
 397                         /* If strings are allowed, a quote (Which isn't a known mark)
 398                          * mustn't be treated as part of an unknown mark.  It can be
 399                          * part of a multi-line srtings though.
 400                          */
 401                         break;
 402                 if (prev == '#' && n < 0)
 403                         /* '#' is not a known mark, so assume it is a comment */
 404                         break;
 405                 if (prev == '/' && ch == '/' && tk.txt.len == 1 && n < 0) {
 406                         close_token(state, &tk);
 407                         restore_unget_state(state);
 408                         break;
 409                 }
 410                 if (prev == '/' && ch == '*' && tk.txt.len == 1 && n < 0) {
 411                         close_token(state, &tk);
 412                         restore_unget_state(state);
 413                         break;
 414                 }
 415         }
 416         unget_char(state);
 417         if (tk.num != TK_error) {
 418                 close_token(state, &tk);
 419                 return tk;
 420         }
 421
 422 If we don't find a known mark, we will check for strings and comments
 423 before assuming that we have an unknown mark
 424
 425 ###### parse mark
 426         ## parse string
 427         ## parse comment
 428         ## unknown mark
 429
 430 ### Strings
 431
 432 Strings start with one of single quote, double quote, or back quote
 433 and continue until a matching character on the same line.  Any of
 434 these characters can be included in the list of known marks and then
 435 they will not be used for identifying strings.
 436
 437 Immediately following the close quote, one or two ASCII letters may
 438 appear.  These are somewhat like the arbitrary letters allowed in
 439 "Numbers" above.  They can be used by the language in various ways.
 440
 441 If 3 identical quote characters appear in a row and are
 442 followed by a newline, then this forms a multi-line string which
 443 continues until an identical triple quote appears on a line preceded
 444 only by whitespace and followed immediately by 0-2 ASCII letters and a newline.
 445
 446 Multi-line strings may not extend beyond the end of the `code_node` in
 447 which they start.
 448
 449 Normal strings and multi-line strings are encoded as two different
 450 token types.
 451
 452 ###### token types
 453         TK_string,
 454         TK_multi_string,
 455
 456 ###### internal functions
 457         static int is_quote(wchar_t ch)
 458         {
 459                 return ch == '\'' || ch == '"' || ch == '`'; // "
 460         }
 461
 462 #### Multi-line strings
 463
 464 The multi-line string is checked for first.  If they are being
 465 ignored, we fall through and treat a triple quote as an empty string
 466 followed by the start of a new string.
 467
 468 ###### parse string
 469         if (tk.txt.len == 3 &&
 470             !(ignored & (1 << TK_multi_string)) &&
 471             is_quote(tk.txt.txt[0]) &&
 472             memcmp(tk.txt.txt, tk.txt.txt+1, 2) == 0 &&
 473             is_newline(tk.txt.txt[3])) {
 474                 // triple quote
 475                 wchar_t first = tk.txt.txt[0];
 476                 int qseen = 0;
 477                 int at_sol = 1;
 478                 while (!at_eon(state) && qseen < 3) {
 479                         ch = get_char(state);
 480                         if (is_newline(ch)) {
 481                                 at_sol = 1;
 482                                 qseen = 0;
 483                         } else if (at_sol && ch == first) {
 484                                 qseen += 1;
 485                         } else if (ch != ' ' && ch != '\t') {
 486                                 at_sol = 0;
 487                                 qseen = 0;
 488                         }
 489                 }
 490                 if (qseen != 3) {
 491                         /* Hit end of node - error.
 492                          * unget so the newline is seen,
 493                          * but return rest of string as an error.
 494                          */
 495                         if (is_newline(ch))
 496                                 unget_char(state);
 497                         close_token(state, &tk);
 498                         tk.num = TK_error;
 499                         return tk;
 500                 }
 501                 /* 2 letters are allowed */
 502                 ch = get_char(state);
 503                 if (iswalpha(ch))
 504                         ch = get_char(state);
 505                 if (iswalpha(ch))
 506                         ch = get_char(state);
 507                 /* Now we must have a newline, but we don't return it
 508                  * whatever it is.*/
 509                 unget_char(state);
 510                 close_token(state, &tk);
 511                 tk.num = TK_multi_string;
 512                 if (!is_newline(ch))
 513                         tk.num = TK_error;
 514                 return tk;
 515         }
 516
 517 #### Single-line strings
 518
 519 The sequence of marks collected may be more than a single-line
 520 string, so we reset to the start and collect characters until
 521 we find a close quote or a newline.
 522
 523 If `TK_string` is ignored, then quote characters will appear as `TK_mark`s.
 524
 525 ###### parse string
 526         if (tk.txt.len && is_quote(tk.txt.txt[0]) &&
 527             !(ignored & (1<<TK_string))) {
 528                 wchar_t first = tk.txt.txt[0];
 529                 reset_token(state, &tk);
 530                 ch = get_char(state);
 531                 tk.num = TK_error;
 532                 while (!at_eon(state) && !is_newline(ch)) {
 533                         ch = get_char(state);
 534                         if (ch == first) {
 535                                 tk.num = TK_string;
 536                                 break;
 537                         }
 538                         if (is_newline(ch)) {
 539                                 unget_char(state);
 540                                 break;
 541                         }
 542                 }
 543                 while (!at_eon(state) && (ch = get_char(state)) &&
 544                                           iswalpha(ch))
 545                         ;
 546                 unget_char(state);
 547                 close_token(state, &tk);
 548                 return tk;
 549         }
 550
 551 ### Comments
 552
 553 Single line comments may start with '`//`' or '`#`' providing that these
 554 are not known marks.  They continue to the end of the line.
 555
 556 Block comments start with '`/*`' if this is not a known mark.  They
 557 continue to the first occurrence of '`*/`' and may not contain any
 558 occurrence of '`/*`'.
 559
 560 Block comments can be wholly within one line or can continue over
 561 multiple lines.  The multi-line version should be followed immediately
 562 by a newline.  The Linux kernel contains over 285000 multi-line
 563 comments are only 34 are followed by characters other than white space
 564 (which should be removed) or a backslash (only needed in macros).  So
 565 it would not suffer from this rule.
 566
 567 These two comment types are reported as two separate token types, and
 568 consequently can be ignored separately.  When ignored a comment is
 569 still parsed, but is discarded.
 570
 571 ###### token types
 572         TK_line_comment,
 573         TK_block_comment,
 574
 575 ###### internal functions
 576         static int is_line_comment(struct text txt)
 577         {
 578                 return (txt.len >= 1 && txt.txt[0] == '#') ||
 579                        (txt.len >= 2 && txt.txt[0] == '/' &&
 580                                         txt.txt[1] == '/');
 581         }
 582
 583         static int is_block_comment(struct text txt)
 584         {
 585                 return txt.len >= 2 && txt.txt[0] == '/' &&
 586                        txt.txt[1] == '*';
 587         }
 588
 589 #### Single line comments
 590
 591 A single-line comment continues up to, but not including the newline
 592 or end of node.
 593
 594 ###### parse comment
 595
 596         if (is_line_comment(tk.txt)) {
 597                 while (!is_newline(ch) && !at_eon(state))
 598                         ch = get_char(state);
 599                 if (is_newline(ch))
 600                         unget_char(state);
 601                 close_token(state, &tk);
 602                 tk.num = TK_line_comment;
 603                 if (ignored & (1 << TK_line_comment))
 604                         continue;
 605                 return tk;
 606         }
 607
 608 #### Block comments
 609
 610 The token text collected so far could exceed the comment, so we need
 611 to reset it first.
 612
 613 If we find an embedded `/*` we reset to just before the '/' and report
 614 an error.  That way the next thing to be parsed will be the rest of
 615 the comment.  This requires a double unget, so we need to save/restore
 616 the unget state (explained later).
 617
 618 ###### parse comment
 619
 620         if (is_block_comment(tk.txt)) {
 621                 wchar_t prev;
 622                 int newlines = 0;
 623                 reset_token(state, &tk);
 624                 get_char(state);
 625                 get_char(state);
 626                 save_unget_state(state);
 627                 ch = get_char(state);
 628                 prev = 0;
 629                 while (!at_eon(state) &&
 630                        (prev != '/' || ch != '*') &&
 631                        (prev != '*' || ch != '/')) {
 632                         if (is_newline(ch))
 633                                 newlines = 1;
 634                         prev = ch;
 635                         save_unget_state(state);
 636                         ch = get_char(state);
 637                 }
 638                 close_token(state, &tk);
 639                 if (at_eon(state)) {
 640                         tk.num = TK_error;
 641                         return tk;
 642                 }
 643                 if (prev == '/') {
 644                         /* embedded.  Need to unget twice! */
 645                         restore_unget_state(state);
 646                         unget_char(state);
 647                         tk.num = TK_error;
 648                         return tk;
 649                 }
 650                 tk.num = TK_block_comment;
 651                 if (newlines && !(ignored & (1<<TK_newline))) {
 652                         /* next char must be newline */
 653                         ch = get_char(state);
 654                         unget_char(state);
 655                         if (!is_newline(ch))
 656                                 tk.num = TK_error;
 657                 }
 658                 if (tk.num == TK_error ||
 659                     !(ignored & (1 << TK_block_comment)))
 660                         return tk;
 661                 continue;
 662         }
 663
 664 ### Indents, Newlines, and White Space.
 665
 666 Normally white space is ignored.  However newlines can be important as
 667 can indents, which are either after a newline or at the start of a
 668 node (detected by `at_son()`);
 669
 670 ###### exported functions
 671         static inline int is_newline(wchar_t ch)
 672         {
 673                 return ch == '\n' || ch == '\f' || ch == '\v';
 674         }
 675
 676 ###### white space
 677         if (ch <= ' ' && !is_newline(ch)
 678             && ! at_son(state))
 679                 continue;
 680
 681 If a line starts with more white-space than the previous non-blank
 682 line - or if the first non-blank line in the document starts with any
 683 white-space - then an "IN" is reported at the start of the line.
 684
 685 Before the next non-blank line which starts with less white space, or
 686 at the latest at the end of the document, a matching "OUT" token
 687 is reported.  There will always be an exact match between "IN" and
 688 "OUT" tokens.
 689
 690 It is possible for "OUT" to be followed (almost) immediately by an
 691 "IN".  This happens if, for example, the indent of three consecutive
 692 lines are 0, 8, 4 spaces.  Before the second line we report an
 693 "IN".  Before the third line we must report an "OUT", as 4 is less
 694 than 8, then also an Ident as 4 is greater than 0.
 695
 696 ###### token types
 697         TK_in,
 698         TK_out,
 699
 700 For the purpose of measuring the length of white space, a tab adds at
 701 least one space, and rounds up to a multiple of 8.
 702
 703 ###### exported functions
 704         static inline int indent_tab(int indent)
 705         {
 706                 return (indent|7)+1;
 707         }
 708
 709 We need to track the current levels of indent.  This requires some
 710 sort of stack as indent levels are pushed on and popped off.  In
 711 practice this stack is unlikely to often exceed 5 so we will used a
 712 fixed stack of 20 indent levels.  More than this will be silently
 713 ignored.
 714
 715 ###### state fields
 716         int     indent_level;
 717         int     indent_sizes[20];
 718
 719 #### Newlines
 720
 721 Newlines can optionally be reported.  Newlines within a block comment
 722 or a multi-line string are not reported separately, but each of these
 723 must be followed immediately by a newline so these constructs cannot
 724 hide the fact that a newline was present.
 725
 726 When indents are being reported, the Newline which would normally be
 727 reported immediately before the "IN" is delayed until after the
 728 matching "OUT".  This makes an indented section act like a
 729 continuation of the previous line to some extent.
 730
 731 A blank line would normally be reported simply as two consecutive Newline
 732 tokens.  However if the subsequent line is indented (and indents are being
 733 reported) then the right thing to do is less obvious as Newlines should be
 734 delayed - but how many Newlines?
 735
 736 The approach we will take is to report the extra Newlines immediately after
 737 the IN token, so the blank line is treated as though it were an indented
 738 blank line.
 739
 740 ###### token types
 741         TK_newline,
 742
 743 If we find a newline or white space at the start of a block, we keep
 744 collecting spaces, tabs, and newlines until we find some real text.
 745 Then depending on the indent we generate some number of tokens.  These
 746 will be a sequence of "Newline OUT" pairs representing a decrease
 747 in indent, then either a Newline or an IN depending on whether the
 748 next line is indented, then zero or more Newlines representing all the
 749 blank lines that have been skipped.
 750
 751 When a Newline leads to the next block of code there is a question of
 752 whether the various Newline and OUT/IN tokens should appear to
 753 pbelong to the earlier or later block.  This is addressed by processing
 754 the tokens in two stages based on the relative indent levels of the
 755 two blocks (each block has a base indent to which the actual indents
 756 are added).
 757
 758 Any "Newline OUT" pairs needed to reduce the current indent to the
 759 maximum of the base indents of the old and new blocks are generated
 760 against the old block.  Then if the next block does not have an
 761 increased indent, one more "Newline" is generated.
 762
 763 If further "Newline OUT" pairs are needed to get to the indent
 764 level of the 'next' block, they are generated against that block,
 765 though the first Newline is suppressed (it having already been
 766 generated).
 767
 768 Finally the Newline or IN for the first line of the new block is
 769 generated, unless the Newline needs to be suppressed because it
 770 appeared at the end of the previous block.
 771
 772 This means that a block may start with an OUT or an IN, but
 773 will only start with a Newline if it actually starts with a blank
 774 line.
 775
 776 We will need to represent in the `token_state` where in this sequence
 777 of delayed tokens we are.  As `state.col` records the target indent we
 778 don't need to record how many OUTs or INs are needed.  We do
 779 need to record the number of blank lines, and which of Newline and
 780 OUT is needed next in the initial sequence of pairs.
 781
 782 For this we store one more than the number of blank lines as
 783 `delayed_lines` and a flag for `out_next`.
 784
 785 ###### state fields
 786         int check_indent;
 787         int delayed_lines;
 788         int out_next;
 789
 790 Generating these tokens involve two separate pieces of code.
 791
 792 Firstly we need to recognise white space and count the indents and
 793 newlines.  These are recorded in the above state fields.
 794
 795 Separately we need, on each call to `token_next`, we need to check if
 796 there are some delayed tokens and if so we need to advance the state
 797 information and return one token.
 798
 799 ###### white space
 800         if (is_newline(ch) || (at_son(state) && ch <= ' ')) {
 801                 int newlines = 0;
 802                 int was_son = at_son(state);
 803                 if (ignored & (1<<TK_in)) {
 804                         if (!is_newline(ch))
 805                                 continue;
 806                         if (ignored & (1<<TK_newline))
 807                                 continue;
 808                         tk.num = TK_newline;
 809                         close_token(state, &tk);
 810                         return tk;
 811                 }
 812                 // Indents are needed, so check all white space.
 813                 while (ch <= ' ' && !at_eon(state)) {
 814                         if (is_newline(ch))
 815                                 newlines += 1;
 816                         ch = get_char(state);
 817                 }
 818                 if (at_eon(state)) {
 819                         newlines += 1;
 820                         if (state->node->next &&
 821                             state->node->next->indent > state->node->indent)
 822                                 state->col = state->node->next->indent;
 823                         else
 824                                 state->col = state->node->indent;
 825                 } else
 826                         unget_char(state);
 827                 state->delayed_lines = newlines;
 828                 state->out_next = was_son;
 829                 state->check_indent = 1;
 830                 continue;
 831         }
 832
 833 ###### delayed tokens
 834
 835         if (state->check_indent || state->delayed_lines) {
 836                 if (state->col < state->indent_sizes[state->indent_level]) {
 837                         if (!state->out_next &&
 838                             !(ignored & (1<<TK_newline))) {
 839                                 state->out_next = 1;
 840                                 tk.num = TK_newline;
 841                                 return tk;
 842                         }
 843                         state->indent_level -= 1;
 844                         state->out_next = 0;
 845                         tk.num = TK_out;
 846                         return tk;
 847                 }
 848                 if (state->col > state->indent_sizes[state->indent_level] &&
 849                     state->indent_level < sizeof(state->indent_sizes)-1) {
 850                         state->indent_level += 1;
 851                         state->indent_sizes[state->indent_level] = state->col;
 852                         state->delayed_lines -= 1;
 853                         tk.num = TK_in;
 854                         return tk;
 855                 }
 856                 state->check_indent = 0;
 857                 if (state->delayed_lines && !(ignored & (1<<TK_newline))) {
 858                         tk.num = TK_newline;
 859                         state->delayed_lines -= 1;
 860                         return tk;
 861                 }
 862                 state->delayed_lines = 0;
 863                 continue;
 864         }
 865
 866 ### End of File
 867
 868 After the last newline in the file has been processed, a special
 869 end-of-file token will be returned.  any further attempts to get more
 870 tokens will continue to return the same end-of-file token.
 871
 872 ###### token types
 873         TK_eof,
 874
 875 ###### white space
 876         if (ch == WEOF) {
 877                 if (state->col) {
 878                         state->col = 0;
 879                         state->check_indent = 1;
 880                         continue;
 881                 }
 882                 tk.num = TK_eof;
 883                 return tk;
 884         }
 885
 886 ### Unknown Marks, or errors.
 887
 888 We have now handled all the possible known mark-like tokens.
 889 If the token we have is not empty and `TK_mark` is allowed,
 890 we have an unknown mark, otherwise this must be an error.
 891
 892 ###### unknown mark
 893
 894         /* one unknown mark character */
 895         if (tk.txt.len) {
 896                 close_token(state, &tk);
 897                 if (ignored & (1<<TK_mark))
 898                         tk.num = TK_error;
 899                 else
 900                         tk.num = TK_mark;
 901                 return tk;
 902         }
 903         /* Completely unrecognised character is next, possibly
 904          * a digit and we are ignoring numbers.
 905          * What ever it is, make it an error.
 906          */
 907         get_char(state);
 908         close_token(state, &tk);
 909         tk.num = TK_error;
 910         return tk;
 911
 912 ## Tools For The Task
 913
 914 You may have noticed that are few gaps we left in the above -
 915 functions used without first defining them.  Doing so above would have
 916 broken the flow.
 917
 918 ### Character by character
 919
 920 As we walk through the various `code_node`s we need to process whole
 921 Unicode codepoints, and keep track of which line and column we are on.
 922 We will assume for now that any printing character uses one column,
 923 though that is not true in general.
 924
 925 As the text in a `code_node` may include an indent that identifies it as
 926 being code, we need to be careful to strip that.  The `code_node` has
 927 a flag that tells us whether or not we need to strip.
 928
 929 ###### includes
 930         #include <memory.h>
 931
 932 ###### state fields
 933         struct code_node *node;
 934         int    offset;
 935         int    line;
 936         int    col;
 937
 938 ###### internal functions
 939
 940         static int do_strip(struct token_state *state)
 941         {
 942                 int indent = 0;
 943                 if (state->node->needs_strip) {
 944                         int n = 4;
 945                         while (n && state->node->code.txt[state->offset] == ' ') {
 946                                 indent += 1;
 947                                 state->offset += 1;
 948                                 n -= 1;
 949                         }
 950                         while (n == 4 && state->node->code.txt[state->offset] == '\t') {
 951                                 indent = indent_tab(indent);
 952                                 state->offset += 1;
 953                                 n -= 4;
 954                         }
 955                 }
 956                 return indent;
 957         }
 958
 959         static wint_t get_char(struct token_state *state)
 960         {
 961                 wchar_t next;
 962                 size_t n;
 963                 mbstate_t mbstate;
 964
 965                 if (state->node == NULL)
 966                         return WEOF;
 967                 if (state->node->code.len <= state->offset) {
 968                         do
 969                                 state->node = state->node->next;
 970                         while (state->node && state->node->code.txt == NULL);
 971                         state->offset = 0;
 972                         if (state->node == NULL)
 973                                 return WEOF;
 974                         state->line = state->node->line_no;
 975                         state->col = do_strip(state);
 976                 }
 977
 978                 ## before get_char
 979
 980                 memset(&mbstate, 0, sizeof(mbstate));
 981
 982                 n = mbrtowc(&next, state->node->code.txt + state->offset,
 983                             state->node->code.len - state->offset,
 984                             &mbstate);
 985                 if (n == -2 || n == 0) {
 986                         /* Not enough bytes - not really possible */
 987                         next = '\n';
 988                         state->offset = state->node->code.len;
 989                 } else if (n == -1) {
 990                         /* error */
 991                         state->offset += 1;
 992                         next = 0x7f; // an illegal character
 993                 } else
 994                         state->offset += n;
 995
 996                 if (next >= ' ') {
 997                         state->col += 1;
 998                 } else if (is_newline(next)) {
 999                         state->line += 1;
1000                         state->col = do_strip(state);
1001                 } else if (next == '\t') {
1002                         state->col = indent_tab(state->col);
1003                 }
1004                 return next;
1005         }
1006
1007 We will sometimes want to "unget" the last character as it needs to be
1008 considered again as part of the next token.  So we need to store a
1009 'previous' version of all metadata.
1010
1011 ###### state fields
1012         int    prev_offset;
1013         int    prev_line;
1014         int    prev_col;
1015
1016 ###### before get_char
1017         state->prev_offset = state->offset;
1018         state->prev_line   = state->line;
1019         state->prev_col    = state->col;
1020
1021 ###### internal functions
1022
1023         static void unget_char(struct token_state *state)
1024         {
1025                 if (state->node) {
1026                         state->offset = state->prev_offset;
1027                         state->line   = state->prev_line;
1028                         state->col    = state->prev_col;
1029                 }
1030         }
1031
1032 We occasionally need a double-unget, particularly for numbers and
1033 block comments.  We don't impose this cost on all scanning, but
1034 require those code sections that need it to call `save_unget_state`
1035 before each `get_char`, and then `restore_unget_state` when a
1036 double-unget is needed.
1037
1038 ###### state fields
1039         int     prev_offset2;
1040         int     prev_line2;
1041         int     prev_col2;
1042
1043 ###### internal functions
1044         static void save_unget_state(struct token_state *state)
1045         {
1046                 state->prev_offset2 = state->prev_offset;
1047                 state->prev_line2 = state->prev_line;
1048                 state->prev_col2 = state->prev_col;
1049         }
1050
1051         static void restore_unget_state(struct token_state *state)
1052         {
1053                 state->prev_offset = state->prev_offset2;
1054                 state->prev_line = state->prev_line2;
1055                 state->prev_col = state->prev_col2;
1056         }
1057
1058 At the start of a token we don't want to be at the end of a code block
1059 if we can help it.  To avoid this possibility, we 'get' and 'unget' a
1060 single character.  This will move into the next non-empty code block
1061 and leave the current pointer at the start of it.
1062
1063 This has to happen _after_ dealing with delayed tokens as some of them
1064 must appear in the previous node.  When we do this, we need to reset
1065 the data in the token.
1066
1067 ###### delayed tokens
1068         if (at_eon(state)) {
1069                 get_char(state);
1070                 unget_char(state);
1071                 tk.node = state->node;
1072                 if (state->node)
1073                         tk.txt.txt = state->node->code.txt + state->offset;
1074                 tk.line = state->line;
1075                 tk.col = state->col;
1076                 tk.txt.len = 0;
1077         }
1078
1079 ### Managing tokens
1080
1081 The current token is initialized to line up with the first character
1082 that we 'get' for each token.  When we have, or might have, a full
1083 token we can call `close_token` to set the `len` of the token
1084 appropriately.  This can safely be called multiple times.
1085
1086 Finally we occasionally (for single-line strings and block comments)
1087 need to reset to the beginning of the current token as we might have
1088 parsed too much already.  For that there is `reset_token`.
1089
1090 ###### one token
1091         tk.node = state->node;
1092         if (state->node)
1093                 tk.txt.txt = state->node->code.txt + state->offset;
1094         tk.line = state->line;
1095         tk.col = state->col;
1096         tk.txt.len = 0;
1097
1098 ###### internal functions
1099
1100         static void close_token(struct token_state *state,
1101                                 struct token *tk)
1102         {
1103                 if (state->node != tk->node)
1104                         tk->txt.len = tk->node->code.len - (tk->txt.txt - tk->node->code.txt);
1105                 else
1106                         tk->txt.len = (state->node->code.txt + state->offset)
1107                                       - tk->txt.txt;
1108         }
1109
1110         static void reset_token(struct token_state *state, struct token *tok)
1111         {
1112                 state->prev_line = tok->line;
1113                 state->prev_col = tok->col;
1114                 state->prev_offset = tok->txt.txt - state->node->code.txt;
1115                 unget_char(state);
1116                 tok->txt.len = 0;
1117         }
1118
1119 Tokens make not cross into the next `code_node`, and some tokens can
1120 include the newline at the and of a `code_node`, we must be able to
1121 easily check if we have reached the end.  Equally we need to know if
1122 we are at the start of a node, as white space is treated a little
1123 differently there.
1124
1125 ###### internal functions
1126
1127         static int at_son(struct token_state *state)
1128         {
1129                 return state->offset == 0;
1130         }
1131
1132         static int at_eon(struct token_state *state)
1133         {
1134                 // at end-of-node ??
1135                 return state->node == NULL ||
1136                        state->offset >= state->node->code.len;
1137         }
1138
1139 ### Find a known word
1140
1141 As the known-word list is sorted we can use a simple binary search.
1142 Following the pattern established in "mdcode", we will use a `struct
1143 text` with start and length to represent the code fragment we are
1144 searching for.
1145
1146 ###### internal functions
1147         static int find_known(struct token_config *conf, struct text txt)
1148         {
1149                 int lo = 0;
1150                 int hi = conf->known_count;
1151
1152                 while (lo + 1 < hi) {
1153                         int mid = (lo + hi) / 2;
1154                         int cmp = strncmp(conf->words_marks[mid],
1155                                           txt.txt, txt.len);
1156                         if (cmp == 0 && conf->words_marks[mid][txt.len])
1157                                 cmp = 1;
1158                         if (cmp <= 0)
1159                                 lo = mid;
1160                         else
1161                                 hi = mid;
1162                 }
1163                 if (strncmp(conf->words_marks[lo],
1164                            txt.txt, txt.len) == 0
1165                     && conf->words_marks[lo][txt.len] == 0)
1166                         return lo;
1167                 else
1168                         return -1;
1169         }
1170
1171 ### Bringing it all together
1172
1173 Now we have all the bits there is just one section missing:  combining
1174 all the token parsing code into one block.
1175
1176 The handling of delayed tokens (Newlines, INs, OUTs) must come
1177 first before we try getting another character.
1178
1179 Then we parse all the test, making sure that we check for known marks
1180 before strings and comments, but unknown marks after strings and comments.
1181
1182 This block of code will either return a token, or will choose to
1183 ignore one, in which case it will `continue` around to the top of the
1184 loop.
1185
1186 ###### one token
1187         ## delayed tokens
1188
1189         ch = get_char(state);
1190
1191         ## white space
1192         ## parse number
1193         ## parse word
1194         ## parse mark
1195
1196 ### Start and stop
1197
1198 As well as getting tokens, we need to be able to create the
1199 `token_state` to start with, and discard it later.
1200
1201 ###### includes
1202         #include <malloc.h>
1203
1204 ###### main functions
1205         struct token_state *token_open(struct code_node *code, struct
1206                                        token_config *conf)
1207         {
1208                 struct token_state *state = malloc(sizeof(*state));
1209                 memset(state, 0, sizeof(*state));
1210                 state->node = code;
1211                 state->line = code->line_no;
1212                 state->col = do_strip(state);
1213                 state->conf = conf;
1214                 return state;
1215         }
1216         void token_close(struct token_state *state)
1217         {
1218                 free(state);
1219         }
1220
1221 ###### exported functions
1222         struct token_state *token_open(struct code_node *code, struct
1223                                        token_config *conf);
1224         void token_close(struct token_state *state);
1225
1226 ### Trace tokens
1227
1228 Getting tokens is the main thing but it is also useful to be able to
1229 print out token information, particularly for tracing and testing.
1230
1231 Known tokens are printed verbatim.  Other tokens are printed as
1232 `type(content)` where content is truncated to a given number of characters.
1233
1234 The function for printing a truncated string (`text_dump`) is also exported
1235 so that it can be used to tracing processed strings too.
1236
1237 ###### includes
1238         #include <stdio.h>
1239
1240 ###### exported functions
1241         void token_trace(FILE *f, struct token tok, int max);
1242         void text_dump(FILE *f, struct text t, int max);
1243
1244 ###### main functions
1245
1246         void text_dump(FILE *f, struct text txt, int max)
1247         {
1248                 int i;
1249                 if (txt.len > max)
1250                         max -= 2;
1251                 else
1252                         max = txt.len;
1253                 for (i = 0; i < max; i++) {
1254                         char c = txt.txt[i];
1255                         if (c < ' ' || c > '~')
1256                                 fprintf(f, "\\x%02x", c & 0xff);
1257                         else if (c == '\\')
1258                                 fprintf(f, "\\\\");
1259                         else
1260                                 fprintf(f, "%c", c);
1261                 }
1262                 if (i < txt.len)
1263                         fprintf(f, "..");
1264         }
1265
1266         void token_trace(FILE *f, struct token tok, int max)
1267         {
1268                 static char *types[] = {
1269                         [TK_ident] = "ident",
1270                         [TK_mark] = "mark",
1271                         [TK_number] = "number",
1272                         [TK_string] = "string",
1273                         [TK_multi_string] = "mstring",
1274                         [TK_line_comment] = "lcomment",
1275                         [TK_block_comment] = "bcomment",
1276                         [TK_in] = "in",
1277                         [TK_out] = "out",
1278                         [TK_newline] = "newline",
1279                         [TK_eof] = "eof",
1280                         [TK_error] = "ERROR",
1281                         };
1282
1283                 switch (tok.num) {
1284                 default: /* known word or mark */
1285                         fprintf(f, "%.*s", tok.txt.len, tok.txt.txt);
1286                         break;
1287                 case TK_in:
1288                 case TK_out:
1289                 case TK_newline:
1290                 case TK_eof:
1291                         /* No token text included */
1292                         fprintf(f, "%s()", types[tok.num]);
1293                         break;
1294                 case TK_ident:
1295                 case TK_mark:
1296                 case TK_number:
1297                 case TK_string:
1298                 case TK_multi_string:
1299                 case TK_line_comment:
1300                 case TK_block_comment:
1301                 case TK_error:
1302                         fprintf(f, "%s(", types[tok.num]);
1303                         text_dump(f, tok.txt, max);
1304                         fprintf(f, ")");
1305                         break;
1306                 }
1307         }
1308
1309 ### And there we have it
1310
1311 We now have all the library functions defined for reading and printing
1312 tokens.  Now we just need C files to store them, and a mk file to make them.
1313
1314 ###### File: scanner.h
1315         ## public types
1316         ## exported functions
1317
1318 ###### File: libscanner.c
1319         ## includes
1320         #include "scanner.h"
1321         ## private types
1322         ## internal functions
1323         ## main functions
1324
1325 ###### File: scanner.mk
1326
1327         CFLAGS += -Wall -g
1328         all ::
1329         scanner.mk scanner.h libscanner.c : scanner.mdc
1330                 ./md2c scanner.mdc
1331         all :: libscanner.o
1332         libscanner.o : libscanner.c
1333                 $(CC) $(CFLAGS) -c libscanner.c
1334
1335 ## Processing numbers
1336
1337 Converting a `TK_number` token to a numerical value is a slightly
1338 higher level task than lexical analysis, and slightly lower than
1339 grammar parsing, so put it here - as an appendix if you like.
1340
1341 Importantly it will be used by the same testing rig that is used for
1342 testing the token scanner.
1343
1344 The numeric value that we will convert all numbers into is the `mpq_t`
1345 from the GNU high precision number library "libgmp".
1346
1347 ###### number includes
1348         #include <gmp.h>
1349         #include "mdcode.h"
1350
1351 Firstly we need to be able to parse a string of digits in a given base
1352 and possibly with a decimal marker.  We store this in an `mpz_t`
1353 integer and report the number of digits after the decimal mark.
1354
1355 On error we return zero and ensure that the 'mpz_t' has been freed, or
1356 had never been initialised.
1357
1358 ###### number functions
1359
1360         static int parse_digits(mpz_t num, struct text tok, int base,
1361                                 int *placesp)
1362         {
1363                 /* Accept digits up to 'base', ignore '_' and
1364                  * (for base 10) ' ' if they appear between two
1365                  * legal digits, and if `placesp` is not NULL,
1366                  * allow a single '.' or ',' and report the number
1367                  * of digits beyond there.
1368                  * Return number of characters processed (p),
1369                  * or 0 if something illegal was found.
1370                  */
1371                 int p;
1372                 int decimal = -1; // digits after marker
1373                 enum {Digit, Space, Other} prev = Other;
1374                 int digits = 0;
1375
1376                 for (p = 0; p < tok.len; p++) {
1377                         int dig;
1378                         char c = tok.txt[p];
1379
1380                         if (c == '_' || (c == ' ' && base == 10)) {
1381                                 if (prev != Digit)
1382                                         goto bad;
1383                                 prev = Space;
1384                                 continue;
1385                         }
1386                         if (c == '.' || c == ',') {
1387                                 if (prev != Digit)
1388                                         goto bad;
1389                                 if (!placesp || decimal >= 0)
1390                                         return p-1;
1391                                 decimal = 0;
1392                                 prev = Other;
1393                                 continue;
1394                         }
1395                         if (isdigit(c))
1396                                 dig = c - '0';
1397                         else if (isupper(c))
1398                                 dig = 10 + c - 'A';
1399                         else if (islower(c))
1400                                 dig = 10 + c - 'a';
1401                         else
1402                                 dig = base;
1403                         if (dig >= base) {
1404                                 if (prev == Space)
1405                                         p--;
1406                                 break;
1407                         }
1408                         prev = Digit;
1409                         if (digits)
1410                                 mpz_mul_ui(num, num, base);
1411                         else
1412                                 mpz_init(num);
1413                         digits += 1;
1414                         mpz_add_ui(num, num, dig);
1415                         if (decimal >= 0)
1416                                 decimal++;
1417                 }
1418                 if (digits == 0)
1419                         return 0;
1420                 if (placesp) {
1421                         if (decimal >= 0)
1422                                 *placesp = decimal;
1423                         else
1424                                 *placesp = 0;
1425                 }
1426                 return p;
1427         bad:
1428                 if (digits)
1429                         mpz_clear(num);
1430                 return 0;
1431         }
1432
1433 ###### number includes
1434         #include <ctype.h>
1435
1436 To parse a full number we need to consider the optional base, the
1437 mantissa, and the optional exponent.  We will treat these one at a
1438 time.
1439
1440 The base is indicated by a letter after a leading zero, which must be
1441 followed by a base letter or a period.  The base also determines the
1442 character which will mark an exponent.
1443
1444 ###### number vars
1445         int base = 10;
1446         char expc = 'e';
1447
1448 ###### parse base
1449
1450         if (tok.txt[0] == '0' && tok.len > 1) {
1451                 int skip = 0;
1452                 switch(tok.txt[1]) {
1453                 case 'x':
1454                 case 'X':
1455                         base = 16;
1456                         skip = 2;
1457                         expc = 'p';
1458                         break;
1459                 case 'o':
1460                 case 'O':
1461                         base = 8;
1462                         skip = 2;
1463                         expc = 'p';
1464                         break;
1465                 case 'b':
1466                 case 'B':
1467                         base = 2;
1468                         skip = 2;
1469                         expc = 'p';
1470                         break;
1471                 case '0':
1472                 case '1':
1473                 case '2':
1474                 case '3':
1475                 case '4':
1476                 case '5':
1477                 case '6':
1478                 case '7':
1479                 case '8':
1480                 case '9':
1481                 case '_':
1482                 case ' ':
1483                         // another digit is not permitted
1484                         // after a zero.
1485                         return 0;
1486                 default:
1487                         // must be decimal marker or trailing
1488                         // letter, which are OK;
1489                         break;
1490                 }
1491                 tok.txt += skip;
1492                 tok.len -= skip;
1493         }
1494
1495 After the base is the mantissa, which may contain a decimal mark, so
1496 we need to record the number of places.  We won't impose the number of
1497 places until we have the exponent as well.
1498
1499 ###### number vars
1500         int places = 0;
1501         mpz_t mant;
1502         int d;
1503
1504 ###### parse mantissa
1505
1506         d = parse_digits(mant, tok, base, &places);
1507         if (d == 0)
1508                 return 0;
1509         tok.txt += d;
1510         tok.len -= d;
1511         mpq_init(num);
1512         mpq_set_z(num, mant);
1513         mpz_clear(mant);
1514
1515 After the mantissa number may come an exponent which may be positive
1516 or negative.  We assume at this point that we have seen the exponent
1517 character `expc`.
1518
1519 ###### number vars
1520         long lexp = 0;
1521         mpz_t exp;
1522         int esign = 1;
1523
1524 ###### parse exponent
1525         if (tok.len > 1) {
1526                 if (tok.txt[0] == '+') {
1527                         tok.txt++;
1528                         tok.len--;
1529                 } else if (tok.txt[0] == '-') {
1530                         esign = -1;
1531                         tok.txt++;
1532                         tok.len--;
1533                 }
1534         }
1535         d = parse_digits(exp, tok, 10, NULL);
1536         if (d == 0) {
1537                 mpq_clear(num);
1538                 return 0;
1539         }
1540         if (!mpz_fits_slong_p(exp)) {
1541                 mpq_clear(num);
1542                 mpz_clear(exp);
1543                 return 0;
1544         }
1545         lexp = mpz_get_si(exp) * esign;
1546         mpz_clear(exp);
1547         tok.txt += d;
1548         tok.len -= d;
1549
1550 Now that we have the mantissa and the exponent we can multiply them
1551 together, also allowing for the number of digits after the decimal
1552 mark.
1553
1554 For base 10, we simply subtract the decimal places from the exponent.
1555 For the other bases, as the exponent is alway based on 2, even for
1556 octal and hex, we need a bit more detail.
1557 We then recover the sign from the exponent, as division is quite
1558 different from multiplication.
1559
1560 ###### calc exponent
1561         switch (base) {
1562         case 10:
1563         case 2:
1564                 lexp -= places;
1565                 break;
1566         case 16:
1567                 lexp -= 4*places;
1568                 break;
1569         case 8:
1570                 lexp -= 3*places;
1571                 break;
1572         }
1573         if (lexp < 0) {
1574                 lexp = -lexp;
1575                 esign = -1;
1576         } else
1577                 esign = 1;
1578
1579 Imposing the exponent on the number is also very different for base 10
1580 than for the others.  For the binary shift `gmp` provides a simple
1581 function.  For base 10 we use something like Russian Peasant
1582 Multiplication.
1583
1584 ###### calc exponent
1585         if (expc == 'e') {
1586                 mpq_t tens;
1587                 mpq_init(tens);
1588                 mpq_set_ui(tens, 10, 1);
1589                 while (1) {
1590                         if (lexp & 1) {
1591                                 if (esign > 0)
1592                                         mpq_mul(num, num, tens);
1593                                 else
1594                                         mpq_div(num, num, tens);
1595                         }
1596                         lexp >>= 1;
1597                         if (lexp == 0)
1598                                 break;
1599                         mpq_mul(tens, tens, tens);
1600                 }
1601                 mpq_clear(tens);
1602         } else {
1603                 if (esign > 0)
1604                         mpq_mul_2exp(num, num, lexp);
1605                 else
1606                         mpq_div_2exp(num, num, lexp);
1607         }
1608
1609 Now we are ready to parse a number: the base, mantissa, and exponent.
1610 If all goes well we check for the possible trailing letters and
1611 return.  Return value is 1 for success and 0 for failure.
1612
1613 ###### number functions
1614         int number_parse(mpq_t num, char tail[3], struct text tok)
1615         {
1616                 ## number vars
1617                 int i;
1618
1619                 ## parse base
1620                 ## parse mantissa
1621                 if (tok.len > 1 && (tok.txt[0] == expc ||
1622                                     tok.txt[0] == toupper(expc))) {
1623                         tok.txt++;
1624                         tok.len--;
1625                         ## parse exponent
1626                 }
1627                 ## calc exponent
1628
1629                 for (i = 0; i < 2; i++) {
1630                         if (tok.len <= i)
1631                                 break;
1632                         if (!isalpha(tok.txt[i]))
1633                                 goto err;
1634                         tail[i] = tok.txt[i];
1635                 }
1636                 tail[i] = 0;
1637                 if (i == tok.len)
1638                         return 1;
1639         err:
1640                 mpq_clear(num);
1641                 return 0;
1642         }
1643
1644 Number parsing goes in `libnumber.c`
1645
1646 ###### File: libnumber.c
1647
1648         #include <unistd.h>
1649         #include <stdlib.h>
1650
1651         ## number includes
1652         ## number functions
1653
1654 ###### File: number.h
1655         int number_parse(mpq_t num, char tail[3], struct text tok);
1656
1657 ###### File: scanner.mk
1658         all :: libnumber.o
1659         libnumber.o : libnumber.c
1660                 $(CC) $(CFLAGS) -c libnumber.c
1661
1662 ## Processing strings
1663
1664 Both `TK_string` and `TK_multi_string` require post-processing which
1665 can be one of two types: literal or with escapes processed.
1666 Even literal processing is non-trivial as the file may contain indents
1667 which need to be stripped.
1668
1669 Errors can only occur when processing escapes.  Any unrecognised
1670 character following the escape character will cause an error.
1671
1672 Processing escapes and striping indents can only make the string
1673 shorter, not longer, so we allocate a buffer which is the same size as
1674 the string and process into that.
1675
1676 To request escape processing, we pass the character we want to use for
1677 quoting, usually '`\`'.  To avoid escape processing we pass a zero.
1678
1679 ###### string main
1680         int string_parse(struct token *tok, char escape,
1681                          struct text *str, char tail[3])
1682         {
1683                 ## string vars
1684                 struct text t = tok->txt;
1685
1686                 str->txt = NULL;
1687                 ## strip tail
1688                 if (tok->num == TK_string) {
1689                         ## strip single
1690                 } else {
1691                         ## strip multi
1692                 }
1693                 str->txt = malloc(t.len);
1694                 str->len = 0;
1695
1696                 ## process string
1697                 return 1;
1698         err:
1699                 free(str->txt);
1700                 str->txt = NULL;
1701                 return 0;
1702         }
1703
1704 ### strip tail
1705
1706 The tail of the string can be 0, 1, or 2 letters
1707
1708         i = t.len;
1709         if (i >= 0 && isalpha(t.txt[i-1]))
1710                 i -= 1;
1711         if (i >= 0 && isalpha(t.txt[i-1]))
1712                 i -= 1;
1713         strncpy(tail, t.txt+i, t.len-i);
1714         tail[t.len-i] = 0;
1715         t.len = i;
1716
1717 ###### string vars
1718         int i;
1719
1720 ### strip single
1721
1722 Stripping the quote of a single-line string is trivial.
1723 The only part that is at all interesting is that quote character must
1724 be remembered.
1725
1726         quote = t.txt[0];
1727         if (t.txt[t.len-1] != quote)
1728                 goto err;
1729         t.txt += 1;
1730         t.len -= 2;
1731
1732 ###### string vars
1733         char quote;
1734
1735 ### strip multi
1736
1737 For a multi-line string we have a little more work to do.  We need to
1738 remove 3 quotes, not 1, and need to count the indent of the close
1739 quote as it will need to be stripped from all lines.
1740
1741         quote = t.txt[0];
1742         if (t.len < 7 ||
1743             t.txt[1] != quote || t.txt[2] != quote ||
1744             !is_newline(t.txt[3]))
1745                 goto err;
1746         t.txt += 4;
1747         t.len -= 4;
1748         i = t.len;
1749         if (i <= 0 || t.txt[i-1] != quote)
1750                 goto err;
1751         i -= 1;
1752         if (i <= 0 || t.txt[i-1] != quote)
1753                 goto err;
1754         i -= 1;
1755         if (i <= 0 || t.txt[i-1] != quote)
1756                 goto err;
1757         i -= 1;
1758         t.len = i;
1759         while (i > 0 && !is_newline(t.txt[i-1]))
1760                 i--;
1761         indent = 0;
1762         while (i < t.len) {
1763                 if (t.txt[i] == ' ')
1764                         indent += 1;
1765                 if (t.txt[i] == '\t')
1766                         indent = indent_tab(indent);
1767                 i++;
1768         }
1769
1770 ###### string vars
1771         int indent = 0;
1772
1773 ### process string
1774
1775 Now we just take one byte at a time. trans-ASCII unicode won't look
1776 like anything we are interested in so it will just be copied byte by
1777 byte.
1778
1779         cp = str->txt;
1780         at_sol = 1;
1781         for (i = 0; i < t.len; i++) {
1782                 char c;
1783                 if (at_sol) {
1784                         at_sol = 0;
1785                         ## strip indent
1786                         if (i >= t.len)
1787                                 break;
1788                 }
1789                 c = t.txt[i];
1790                 if (c != escape) {
1791                         *cp = c;
1792                         cp += 1;
1793                         if (is_newline(c))
1794                                 at_sol = 1;
1795                 } else if (i+1 >= t.len) {
1796                         // escape and end of string
1797                         goto err;
1798                 } else {
1799                         i += 1;
1800                         c = t.txt[i];
1801                         ## parse escape
1802                 }
1803         }
1804         str->len = cp - str->txt;
1805
1806 ###### string vars
1807         char *cp;
1808         int at_sol;
1809
1810 ### strip indent
1811
1812 Every time we find a start of line, we strip spaces and tabs until the
1813 required indent is found.
1814
1815         int skipped = 0;
1816         while (i < t.len && skipped < indent) {
1817                 c = t.txt[i];
1818                 if (c == ' ')
1819                         skipped += 1;
1820                 else if (c == '\t')
1821                         skipped = indent_tab(skipped);
1822                 else
1823                         break;
1824                 i+= 1;
1825         }
1826
1827 ### parse escape
1828         switch (c) {
1829         case 'n':
1830                 *cp++ = '\n'; break;
1831         case 'r':
1832                 *cp++ = '\r'; break;
1833         case 't':
1834                 *cp++ = '\t'; break;
1835         case 'b':
1836                 *cp++ = '\b'; break;
1837         case 'q':
1838                 *cp++ = quote; break;
1839         case 'f':
1840                 *cp++ = '\f'; break;
1841         case 'v':
1842                 *cp++ = '\v'; break;
1843         case 'a':
1844                 *cp++ = '\a'; break;
1845         case '0':
1846         case '1':
1847         case '2':
1848         case '3':
1849                 // 3 digit octal number
1850                 if (i+2 >= t.len)
1851                         goto err;
1852                 if (t.txt[i+1] < '0' || t.txt[i+1] > '7' ||
1853                     t.txt[i+2] < '0' || t.txt[i+1] > '7')
1854                         goto err;
1855                 n = (t.txt[i  ]-'0') * 64 +
1856                     (t.txt[i+1]-'0') *  8 +
1857                     (t.txt[i+2]-'0') *  1;
1858                 *cp++ = n;
1859                 i += 2;
1860                 break;
1861         case 'x':
1862                 // 2 hex digits
1863                 n = take_hex(2, t.txt+i+1, t.len-i-1);
1864                 if (n < 0)
1865                         goto err;
1866                 *cp++ = n;
1867                 i += 2;
1868                 break;
1869         case 'u':
1870         case 'U':
1871                 // 4 or 8 hex digits for unicode
1872                 n = take_hex(c == 'u'?4:8, t.txt+i+1, t.len-i-1);
1873                 if (n < 0)
1874                         goto err;
1875                 memset(&pstate, 0, sizeof(pstate));
1876                 n = wcrtomb(cp, n, &pstate);
1877                 if (n <= 0)
1878                         goto err;
1879                 cp += n;
1880                 i += c == 'u' ? 4 : 8;
1881                 break;
1882         default:
1883                 if (c == escape)
1884                         *cp++ = c;
1885                 else if (is_newline(c))
1886                         at_sol = 1;
1887                 else
1888                         goto err;
1889         }
1890
1891 ###### string vars
1892         long n;
1893         mbstate_t pstate;
1894
1895 For `\x` `\u` and `\U` we need to collect a specific number of
1896 hexadecimal digits
1897
1898 ###### string functions
1899
1900         static long take_hex(int digits, char *cp, int l)
1901         {
1902                 long n = 0;
1903                 if (l < digits)
1904                         return -1;
1905                 while (digits) {
1906                         char  c = *cp;
1907                         int d;
1908                         if (!isxdigit(c))
1909                                 return -1;
1910                         if (isdigit(c))
1911                                 d = c - '0';
1912                         else if (isupper(c))
1913                                 d = 10 + c - 'A';
1914                         else
1915                                 d = 10 + c - 'a';
1916                         n = n * 16 + d;
1917                         digits--;
1918                         cp++;
1919                 }
1920                 return n;
1921         }
1922
1923 #### File: libstring.c
1924
1925 String parsing goes in `libstring.c`
1926
1927         #include <unistd.h>
1928         #include <stdlib.h>
1929         #include <stdio.h>
1930         #include <string.h>
1931         #include <ctype.h>
1932         #include <wchar.h>
1933         #include "mdcode.h"
1934         #include "scanner.h"
1935         ## string functions
1936         ## string main
1937
1938 ###### File: string.h
1939         int string_parse(struct token *tok, char escape,
1940                          struct text *str, char tail[3]);
1941
1942 ###### File: scanner.mk
1943         all :: libstring.o
1944         libstring.o : libstring.c
1945                 $(CC) $(CFLAGS) -c libstring.c
1946
1947 ## Testing
1948
1949 As "untested code is buggy code" we need a program to easily test
1950 the scanner library.  This will simply parse a given file and report
1951 the tokens one per line.
1952
1953 ###### File: scanner.c
1954
1955         #include <unistd.h>
1956         #include <stdlib.h>
1957         #include <fcntl.h>
1958         #include <errno.h>
1959         #include <sys/mman.h>
1960         #include <string.h>
1961         #include <stdio.h>
1962         #include <gmp.h>
1963         #include <locale.h>
1964         #include <getopt.h>
1965         #include "mdcode.h"
1966         #include "scanner.h"
1967         #include "number.h"
1968         #include "string.h"
1969
1970         static int errs;
1971         static void pr_err(char *msg)
1972         {
1973                 errs++;
1974                 fprintf(stderr, "%s\n", msg);
1975         }
1976
1977         static int kcmp(const void *ap, const void *bp)
1978         {
1979                 char * const *a = ap;
1980                 char * const *b = bp;
1981                 return strcmp(*a, *b);
1982         }
1983
1984         int main(int argc, char *argv[])
1985         {
1986                 int fd;
1987                 int len;
1988                 char *file;
1989                 char *filename = NULL;
1990                 struct token_state *state;
1991                 const char *known[] = {
1992                         "==",
1993                         "else",
1994                         "if",
1995                         "then",
1996                         "while",
1997                         "{",
1998                         "}",
1999                 };
2000                 struct token_config conf = {
2001                         .word_start = "_$",
2002                         .word_cont = "",
2003                         .words_marks = known,
2004                         .number_chars = "., _+-",
2005                         .known_count = sizeof(known)/sizeof(known[0]),
2006                         .ignored = 0,
2007                 };
2008                 static const struct option long_options[] = {
2009                         { "word-start",         1, NULL, 'W'},
2010                         { "word-cont",          1, NULL, 'w'},
2011                         { "number-chars",       1, NULL, 'n'},
2012                         { "ignore-numbers",     0, NULL, 'N'},
2013                         { "ignore-ident",       0, NULL, 'I'},
2014                         { "ignore-marks",       0, NULL, 'M'},
2015                         { "ignore-strings",     0, NULL, 'S'},
2016                         { "ignore-multi-strings",0, NULL, 'z'},
2017                         { "ignore-line-comment",0, NULL, 'c'},
2018                         { "ignore-newline",     0, NULL, 'l'},
2019                         { "ignore-block-comment", 0, NULL, 'C'},
2020                         { "ignore-indent",      0, NULL, 'i'},
2021                         { "file",               1, NULL, 'f'},
2022                         { NULL,                 0, NULL, 0},
2023                 };
2024                 static const char options[] = "W:w:n:NIMSzclCif:";
2025
2026                 struct section *table, *s, *prev;
2027                 int opt;
2028
2029                 setlocale(LC_ALL,"");
2030                 while ((opt = getopt_long(argc, argv, options, long_options, NULL))
2031                        != -1) {
2032                         switch(opt) {
2033                         case 'W': conf.word_start = optarg; break;
2034                         case 'w': conf.word_cont = optarg; break;
2035                         case 'n': conf.number_chars = optarg; break;
2036                         case 'N': conf.ignored |= 1 << TK_number; break;
2037                         case 'I': conf.ignored |= 1 << TK_ident; break;
2038                         case 'M': conf.ignored |= 1 << TK_mark; break;
2039                         case 'S': conf.ignored |= 1 << TK_string; break;
2040                         case 'z': conf.ignored |= 1 << TK_multi_string; break;
2041                         case 'c': conf.ignored |= 1 << TK_line_comment; break;
2042                         case 'C': conf.ignored |= 1 << TK_block_comment; break;
2043                         case 'l': conf.ignored |= 1 << TK_newline; break;
2044                         case 'i': conf.ignored |= 1 << TK_in; break;
2045                         case 'f': filename = optarg; break;
2046                         default: fprintf(stderr, "scanner: unknown option '%c'.\n",
2047                                          opt);
2048                                 exit(1);
2049                         }
2050                 }
2051
2052                 if (optind < argc) {
2053                         const char **wm = calloc(argc - optind, sizeof(char*));
2054                         int i;
2055                         for (i = optind; i < argc; i++)
2056                                 wm[i - optind] = argv[i];
2057                         qsort(wm, argc-optind, sizeof(char*), kcmp);
2058                         conf.words_marks = wm;
2059                         conf.known_count = argc - optind;
2060                 }
2061
2062                 if (filename)
2063                         fd = open(filename, O_RDONLY);
2064                 else
2065                         fd = 0;
2066                 if (fd < 0) {
2067                         fprintf(stderr, "scanner: cannot open %s: %s\n",
2068                                 filename, strerror(errno));
2069                         exit(1);
2070                 }
2071                 len = lseek(fd, 0, 2);
2072                 if (len <= 0) {
2073                         fprintf(stderr,"scanner: %s is empty or not seekable\n",
2074                                 filename ?: "stdin");
2075                         exit(1);
2076                 }
2077                 file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
2078                 table = code_extract(file, file+len, pr_err);
2079
2080                 for (s = table; s;
2081                         (code_free(s->code), prev = s, s = s->next, free(prev))) {
2082                         printf("Tokenizing: %.*s\n", s->section.len,
2083                                 s->section.txt);
2084                         state = token_open(s->code, &conf);
2085                         while(1) {
2086                                 struct token tk = token_next(state);
2087                                 printf("%d:%d ", tk.line, tk.col);
2088                                 token_trace(stdout, tk, 20);
2089                                 if (tk.num == TK_number) {
2090                                         mpq_t num;
2091                                         char tail[3];
2092                                         if (number_parse(num, tail,tk.txt)) {
2093                                                 printf(" %s ", tail);
2094                                                 mpq_out_str(stdout, 10, num);
2095                                                 mpq_clear(num);
2096                                         } else
2097                                                 printf(" BAD NUMBER");
2098                                 }
2099                                 if (tk.num == TK_string ||
2100                                     tk.num == TK_multi_string) {
2101                                         char esc = '\\';
2102                                         struct text str;
2103                                         char tail[3];
2104                                         if (tk.txt.txt[0] == '`')
2105                                                 esc = 0;
2106                                         if (string_parse(&tk, esc,
2107                                                          &str, tail)) {
2108                                                 printf(" %s ", tail);
2109                                                 text_dump(stdout, str, 20);
2110                                                 free(str.txt);
2111                                         } else
2112                                                 printf(" BAD STRING");
2113                                 }
2114                                 printf("\n");
2115                                 if (tk.num == TK_error)
2116                                         errs = 1;
2117                                 if (tk.num == TK_eof)
2118                                         break;
2119                         }
2120                         token_close(state);
2121                 }
2122                 if (conf.words_marks != known)
2123                         free(conf.words_marks);
2124                 exit(!!errs);
2125         }
2126 ###### File: scanner.mk
2127         scanner.c : scanner.mdc
2128                 ./md2c scanner.mdc
2129         all :: scanner
2130         scanner : scanner.o scanner.h libscanner.o libmdcode.o mdcode.h
2131                 $(CC) $(CFLAGS) -o scanner scanner.o libscanner.o \
2132                         libmdcode.o libnumber.o libstring.o -licuuc -lgmp
2133         scanner.o : scanner.c
2134                 $(CC) $(CFLAGS) -c scanner.c