C   79

tokenise.c

Guest on 26th July 2022 01:07:51 AM

  1. /*
  2.  *  Assembler Tokeniser:
  3.  */
  4.  
  5. #include "compiler.h"
  6.  
  7. /*
  8.  *  Input file line number, starts from 1 each time.
  9.  */
  10.   static long line_number = 1;
  11.  
  12. /*
  13.  *  Allow buffering of Tokens for lookahead:
  14.  */
  15.  
  16.   static Token current_token = NULL;
  17.   static Token cached_token = NULL;
  18.  
  19. /*
  20.  *  Table of keywords
  21.  */
  22.   char * TokenNames[] = {
  23.         "#ERROR#", "#EOF#", "#\\n#", "#IDENT#",
  24.         "int", "real", "string", "#INT#", "#DBL#", "#STR#",
  25.         "<<",   ">>",   "(",    ")",
  26.         "{",    "}",    "[",    "]",
  27.         "==",   "!=",   "<=",   ">=",   "<",    ">",    "=",
  28.         ",",    ";",    "*",    "/",    "%",    "+",    "-",
  29.         "&",    "|",    "^",    "~",
  30.         "\\",   "\"",   ".",    ":",
  31.         "eof",  "print",
  32.         "readint",      "readline",     "readreal",
  33.         "function",
  34.         "and",  "or",   "not",
  35.         "abs",  "chr",  "ord",  "find", "sort", "size",
  36.         "if",   "else", "for",  "to",   "while",
  37.         "break",        "continue",     "pass",
  38.         "return",       "exit",
  39.   };
  40.  
  41. /*
  42.  *  Symbol Table (for storing all Tokens)
  43.  *
  44.  *  All keywords, punctuation and identifiers are placed
  45.  *  into the symbol table. Pointers to Tokens are returned
  46.  *  by the tokeniser, but the memory is entirely managed
  47.  *  within the symbol table, so the rest of the program
  48.  *  need never free memory. Tokens can simply be discarded.
  49.  *
  50.  *  One function manages the symbol table memory: initTokeniser
  51.  *  must be called every time a new file is being parsed.
  52.  */
  53.  
  54. enum {
  55.         NHASH=1024,
  56.         MAXTOKEN = 1024,
  57. };
  58.  
  59.  
  60. static int hash_table_used = 0;
  61. static Token hash_table[NHASH];
  62.  
  63. Token newToken(void)
  64. {
  65.         Token t;
  66.  
  67.         t = (Token) zalloc(sizeof(struct Token));
  68.         t->next = NULL;
  69.         t->line = line_number;
  70.         t->kind = ERROR;
  71.         t->num = 0;
  72.         t->real = 0.0;
  73.         t->name = NULL;
  74.         return t;
  75. }
  76.  
  77. static void delToken(Token t)
  78. {
  79.         zfree(t->name);
  80.         zfree(t);
  81. }
  82.  
  83. static int hash(char *name)
  84. {
  85.         unsigned long h;
  86.  
  87.         for(h=0; *name; name++)
  88.                 h = h*31 + *name;
  89.         return h%NHASH;
  90. }
  91.  
  92. /*
  93.  *  Set the hash table to all NULL.
  94.  */
  95. static void initHashTable(void)
  96. {
  97.         int i;
  98.  
  99.         for (i=0; i < NHASH; i++)
  100.                 hash_table[i] = NULL;
  101. }
  102.  
  103. /*
  104.  *  Hash lookup
  105.  */
  106. static Token findToken(char *name)
  107. {
  108.         Token t;
  109.  
  110.         for (t = hash_table[hash(name)]; t; t=t->next)
  111.                 if (!strcmp(name, t->name))
  112.                         return t;
  113.         return NULL;
  114. }
  115.  
  116. /*
  117.  *  Hash insert (ensures uniqueness)
  118.  */
  119. Token addToken(Token t)
  120. {
  121.         int h;
  122.         Token prev;
  123.  
  124.         prev = findToken(t->name);
  125.         if (prev) {
  126.                 if (prev != t)
  127.                         delToken(t);
  128.                 return prev;
  129.         }
  130.         else {
  131.                 h = hash(t->name);
  132.                 t->next = hash_table[h];
  133.                 hash_table[h] = t;
  134.                 return t;
  135.         }
  136. }
  137.  
  138. /*
  139.  *  Debug printing:
  140.  */
  141.  
  142. void printToken(Token t)
  143. {
  144.         char *name;
  145.  
  146.         fprintf(stderr, "token: ");
  147.         if (t->kind == EOF)
  148.                 name = TokenNames[ENDOFFILE];
  149.         else
  150.                 name = TokenNames[t->kind];
  151.         fprintf(stderr, "line=%ld\t", t->line);
  152.         fprintf(stderr, "kind=%2d %s\t", t->kind, name);
  153.         fprintf(stderr, "int=%ld\t", t->num);
  154.         fprintf(stderr, "real=%f\t", t->real);
  155.         fprintf(stderr, "str=\"%s\"", t->name ? t->name : "");
  156.         fprintf(stderr, "\n");
  157. }
  158.  
  159. void printAllTokens(void)
  160. {
  161.         int i;
  162.         Token t;
  163.  
  164.         for (i=0; i<NHASH; i++) {
  165.                 fprintf(stderr, "hash value %d:\n", i);
  166.                 for (t = hash_table[i]; t; t=t->next)
  167.                         printToken(t);
  168.         }
  169. }
  170.  
  171. /*
  172.  *  Remove all identifiers from the hash table, but leave keywords.
  173.  */
  174. static int isKeyword(Token t)
  175. {
  176.         return (t->line > 0);
  177. }
  178.  
  179. static void clearIdentifiers(void)
  180. {
  181.         int i;
  182.         Token t, next;
  183.  
  184.         for (i=0; i < NHASH; i++) {
  185.                 t = hash_table[i];
  186.                 while (t && isKeyword(t)) {
  187.                         hash_table[i] = t->next;
  188.                         next = t->next;
  189.                         delToken(t);
  190.                         t = next;
  191.                 }
  192.         }
  193. }
  194.  
  195. /*
  196.  *  Add all keywords to the hash table.
  197.  */
  198. static void addKeywords(void)
  199. {
  200.         int i;
  201.         Token t;
  202.         char buf[30];
  203.  
  204.         /* add keywords */
  205.         for (i=0; i < (sizeof(TokenNames)/sizeof(TokenNames[0])); i++) {
  206.                 if (TokenNames[i] == NULL)
  207.                         continue;
  208.                 t = newToken();
  209.                 t->line = 0; /* keyword */
  210.                 t->kind = i;
  211.                 if (i == ENDOFFILE)
  212.                         t->kind = EOF;
  213.                 t->name = zstrdup(TokenNames[i]);
  214.                 addToken(t);
  215.         }
  216.         //printAllTokens();
  217. }
  218.  
  219. /*
  220.  *  Error handler: prints the error + line number and stops parsing.
  221.  */
  222. void parserError(Program p, char *msg)
  223. {
  224.         if (++(p->error_count) > MAX_ERRORS)
  225.                 return;
  226.         if (msg)
  227.                 fprintf(stderr, "error: %s near line %ld\n", msg, line_number);
  228. /*
  229.         if (current_token) {
  230.                 fprintf(stderr, "this ");
  231.                 printToken(current_token);
  232.         }
  233.         if (cached_token) {
  234.                 fprintf(stderr, "next ");
  235.                 printToken(cached_token);
  236.         }
  237. */
  238. }
  239.  
  240. /*
  241.  *  Low-level file input (reads binary or text, Dos, Unix or Mac):
  242.  */
  243. static int getChar(Program p)
  244. {
  245.         int ch;
  246.  
  247.         if (p->error_count > MAX_ERRORS)
  248.                 return EOF;
  249.         ch = getc(p->file);
  250.         if (ch == '\r') {
  251.                 ch = getc(p->file);
  252.                 if (ch != '\n')
  253.                         ungetc(ch, p->file);
  254.                 ch = '\n';
  255.         }
  256.         if (ch == '\n')
  257.                 line_number++;
  258.         return ch;
  259. }
  260.  
  261. static int ungetChar(int ch, Program p)
  262. {
  263.         int value = ch;
  264.         if (ch != EOF)
  265.                 value = ungetc(ch, p->file);
  266.         if (ch == '\n')
  267.                 line_number--;
  268.         return value;
  269. }
  270.  
  271. static int peekChar(Program p)
  272. {
  273.         int ch = getChar(p);
  274.         ungetChar(ch, p);
  275.         return ch;
  276. }
  277.  
  278. /*
  279.  *  Handle spacing:
  280.  *  Note: newlines are not counted as spaces by this tokeniser;
  281.  *  rather, they are tokens in their own right.
  282.  */
  283. static void skipSpaces(Program p)
  284. {
  285.         int ch;
  286.  
  287.         while ((ch=getChar(p)) != EOF) {
  288.                 if ((ch == '\n') || (! isspace(ch))) {
  289.                         ungetChar(ch, p);
  290.                         break;
  291.                 }
  292.         }
  293. }
  294.  
  295. /*
  296.  *  Handle # comments:
  297.  *  Assume we are about to read the start of a comment.
  298.  */
  299. static void skipComment(Program p)
  300. {
  301.         int ch = getChar(p);
  302.  
  303.         if (ch == '#') {        // skip until end of line
  304.                 while ((ch = getChar(p)) != EOF) {
  305.                         if (ch == '\n') {
  306.                                 ungetChar(ch, p);
  307.                                 break;
  308.                         }
  309.                 }
  310.         }
  311.         else {
  312.                 ungetChar(ch, p);
  313.         }
  314. }
  315.  
  316. static int ishexdigit(int ch)
  317. {
  318.         if (isdigit(ch))    return 1;
  319.         ch = tolower(ch);
  320.         if (ch == 'a')      return 1;
  321.         else if (ch == 'b') return 1;
  322.         else if (ch == 'c') return 1;
  323.         else if (ch == 'd') return 1;
  324.         else if (ch == 'e') return 1;
  325.         else if (ch == 'f') return 1;
  326.         return 0;
  327. }
  328.  
  329. static Token getNumberToken(Program p, char *buf)
  330. {
  331.         Token t;
  332.         int ch, i=0;
  333.         int base=10;
  334.  
  335.         // read in a plain number
  336.         t = newToken();
  337.  
  338.         while ((ch = peekChar(p)) != EOF) {
  339.                 if ((i == 0) && (ch == '0')) {
  340.                         t->kind = INTVAL;
  341.                         buf[i++] = getChar(p);
  342.                         ch = peekChar(p);
  343.                         if ((ch == 'x') || (ch == 'X')) {
  344.                                 buf[i++] = getChar(p);
  345.                                 base=16;
  346.                         }
  347.                 }
  348.                 else if ((base == 16) && (ishexdigit(ch))) {
  349.                         t->kind = INTVAL;
  350.                         buf[i++] = getChar(p);
  351.                 }
  352.                 else if ((base == 16) && (ch == '.')) {
  353.                         break;  /* found 0x1f7. */
  354.                 }
  355.                 else if (isdigit(ch)) {
  356.                         t->kind = INTVAL;
  357.                         buf[i++] = getChar(p);
  358.                 }
  359.                 else if (ch == '.') {
  360.                         t->kind = DOUBLEVAL;
  361.                         buf[i++] = getChar(p);
  362.                         if (! isdigit(ch = peekChar(p)))
  363.                                 break; /* found 123.x */
  364.                         while (isdigit(ch = peekChar(p)))
  365.                                 buf[i++] = getChar(p);
  366.                         if (toupper(ch = peekChar(p)) == 'E') {
  367.                                 buf[i++] = getChar(p);
  368.                                 ch = peekChar(p);
  369.                                 if ((ch == '+') || (ch == '-'))
  370.                                         buf[i++] = getChar(p);
  371.                                 while (isdigit(ch = peekChar(p)))
  372.                                         buf[i++] = getChar(p);
  373.                         }
  374.                         break;
  375.                 }
  376.                 else {
  377.                         break;
  378.                 }
  379.         }
  380.         buf[i] = '\0';
  381.         sscanf(buf, "%li", &t->num);
  382.         sscanf(buf, "%lf", &t->real);
  383.  
  384.         return t;
  385. }
  386.  
  387. /*
  388.  *  Read an identifier: an instruction, keyword, label,
  389.  *  register identifier (r0 ... r63) etc
  390.  */
  391. static Token getIdentToken(Program p, char *buf)
  392. {
  393.         Token t;
  394.         int ch, i=0;
  395.  
  396.         t = newToken();
  397.         t->kind = IDENT;
  398.  
  399.         // read in an identifier
  400.         while ((ch = getChar(p)) != EOF) {
  401.                 if (isalpha(ch) || (ch == '_') || isdigit(ch))
  402.                         buf[i++] = ch;
  403.                 else {
  404.                         ungetChar(ch, p);
  405.                         break;
  406.                 }
  407.         }
  408.         buf[i] = '\0';
  409.  
  410.         return t;
  411. }
  412.  
  413. /*
  414.  *  Read in punctuation marks, including memory cell identifiers
  415.  *  such as [r7], [r4], [sp] etc. '[' followed by non-alphabetics is
  416.  *  returned as separate tokens '[' then  whatever then ']' etc.
  417.  */
  418. static Token getPunctToken(Program p, char *buf)
  419. {
  420.         Token t;
  421.         int ch, i=0;
  422.  
  423.         t = newToken();
  424.  
  425.         // read in a punctuation mark
  426.         if ((ch = getChar(p)) != EOF) {
  427.                 if (ispunct(ch) && (ch != '_')) {
  428.                         buf[i++] = ch;
  429.  
  430.                         switch (ch) {
  431.                          case '[':
  432.                                 ch = peekChar(p);
  433.                                 if (! isalpha(ch))
  434.                                         break;
  435.                                 while (ch != ']') {
  436.                                         ch = peekChar(p);
  437.                                         if ((! isalpha(ch)) && (! isdigit(ch)))
  438.                                                 break;
  439.                                         buf[i++] = getChar(p);
  440.                                 }
  441.                                 if (ch == ']')
  442.                                         buf[i++] = getChar(p);
  443.                                 break;
  444.  
  445.                          case '<':
  446.                                 ch = getChar(p);
  447.                                 if ((ch == '<') || (ch == '='))
  448.                                         buf[i++] = ch;
  449.                                 else
  450.                                         ungetChar(ch, p);
  451.                                 break;
  452.  
  453.                          case '>':
  454.                                 ch = getChar(p);
  455.                                 if ((ch == '>') || (ch == '='))
  456.                                         buf[i++] = ch;
  457.                                 else
  458.                                         ungetChar(ch, p);
  459.                                 break;
  460.  
  461.                          case '=': case '!':
  462.                                 ch = getChar(p);
  463.                                 if (ch == '=')
  464.                                         buf[i++] = ch;
  465.                                 else
  466.                                         ungetChar(ch, p);
  467.                                 break;
  468.  
  469.                          default:
  470.                                 break;
  471.                         }
  472.                 }
  473.                 else {
  474.                         ungetChar(ch, p);
  475.                 }
  476.         }
  477.         buf[i] = '\0';
  478.  
  479.         return t;
  480. }
  481.  
  482. static Token getStringToken(Program p, char *buf)
  483. {
  484.         Token t;
  485.         int ch, prev, i=0;
  486.  
  487.         t = newToken();
  488.         t->kind = STRINGVAL;
  489.  
  490.         // read in the string until we hit a quote char
  491.         ch = getChar(p);
  492.         if (ch != '\"') {
  493.                 t->kind = ERROR;
  494.                 ungetChar(ch, p);       // error
  495.                 return t;
  496.         }
  497.         buf[i++] = ch;  // keep quote char
  498.         prev = '\0';
  499.         while ((ch = getChar(p)) != EOF) {
  500.                 if (ch == '\"') {
  501.                         if (prev == '\\') {
  502.                                 buf[i-1] = ch;
  503.                         }
  504.                         else {
  505.                                 buf[i++] = ch;  // keep quote char
  506.                                 break;
  507.                         }
  508.                 } else if (ch == '\\') {
  509.                         if (prev == '\\')
  510.                                 prev = ' ';     /* avoid carry-over */
  511.                         buf[i++] = ch;
  512.                         continue;
  513.                 } else if (ch == '\t') {
  514.                         buf[i++] = '\\';
  515.                         buf[i++] = 't';
  516.                 } else if (ch == '\n') {
  517.                         parserError(p, "newline within string");
  518.                 } else {
  519.                         buf[i++] = ch;
  520.                 }
  521.                 prev = ch;
  522.         }
  523.         buf[i] = '\0';
  524.  
  525.         return t;
  526. }
  527.  
  528. static Token fetchToken(Program p)      /* fetch token from file */
  529. {
  530.         static char buf[MAXTOKEN];
  531.         int ch;
  532.         Token t = NULL;
  533.  
  534.         buf[0] = '\0';
  535.  
  536.         // find next token
  537.         while ((ch=getChar(p)) != EOF) {
  538.                 // find token
  539.                 if (ch == '\n') {
  540.                         t = findToken(TokenNames[NEWLINE]);
  541.                         break;
  542.                 }
  543.                 else if (isspace(ch)) {
  544.                         ungetChar(ch, p);
  545.                         skipSpaces(p);
  546.                         continue;       // loop
  547.                 }
  548.                 else if (ch == '#') {
  549.                         ungetChar(ch, p);
  550.                         skipComment(p);
  551.                         continue;       // loop
  552.                 }
  553.                 else if (isdigit(ch)) {
  554.                         ungetChar(ch, p);
  555.                         t = getNumberToken(p, buf);
  556.                         t->name = zstrdup(buf);
  557.                 }
  558.                 else if (isalpha(ch)) {
  559.                         ungetChar(ch, p);
  560.                         t = getIdentToken(p, buf);
  561.                         t->name = zstrdup(buf);
  562.                 }
  563.                 else if (ch == '\"') {
  564.                         ungetChar(ch, p);
  565.                         t = getStringToken(p, buf);
  566.                         t->name = zstrdup(buf);
  567.                 }
  568.                 else if (ispunct(ch)) {
  569.                         ungetChar(ch, p);
  570.                         t = getPunctToken(p, buf);
  571.                         t->name = zstrdup(buf);
  572.                 }
  573.                 else {
  574.                         t = findToken(TokenNames[ERROR]);
  575.                         break;
  576.                 }
  577.                 // always break, except for comments and spaces
  578.                 break;
  579.         }
  580.         if ((ch == EOF) && (t == NULL)) {
  581.                 t = findToken(TokenNames[ENDOFFILE]);
  582.         }
  583.         t = addToken(t);
  584.         printToken(t);
  585.         return t;
  586. }
  587.  
  588. /*
  589.  *  Initialise (or re-initialise) the tokeniser hash table.
  590.  */
  591. void initTokeniser(void)
  592. {
  593.         if (hash_table_used)
  594.                 clearIdentifiers();
  595.         else {
  596.                 initHashTable();
  597.                 addKeywords();
  598.                 hash_table_used = 1;
  599.         }
  600.         line_number = 1;
  601.         current_token = NULL;
  602.         cached_token = NULL;
  603. }
  604.  
  605. Token getToken(Program p)       /* fetch next token from the file */
  606. {
  607.         current_token = cached_token;
  608.         cached_token = NULL;
  609.         if (! current_token)
  610.                 current_token = fetchToken(p);
  611.         if (current_token->kind == ERROR)
  612.                 parserError(p, "some weird error");
  613.         return current_token;
  614. }
  615.  
  616. Token peekToken(Program p)      /* peek ahead at next token */
  617. {
  618.         if (! cached_token)
  619.                 cached_token = fetchToken(p);
  620.         return cached_token;
  621. }
  622.  
  623. int eatToken(Program p, int kind, char *msg)
  624. {
  625.         Token t = getToken(p);
  626.         if (t->kind != kind) {
  627.                 parserError(p, msg);
  628.                 return 0;
  629.         }
  630.         return 1;
  631. }

Raw Paste


Login or Register to edit or fork this paste. It's free.