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