simgear/nasal/lex.c

   1 #include "parse.h"
   2
   3 // Static table of recognized lexemes in the language
   4 static const struct Lexeme {
   5     char* str;
   6     int   tok;
   7 } LEXEMES[] = {
   8     {"and", TOK_AND},
   9     {"or",  TOK_OR},
  10     {"!",   TOK_NOT},
  11     {"(", TOK_LPAR},
  12     {")", TOK_RPAR},
  13     {"[", TOK_LBRA},
  14     {"]", TOK_RBRA},
  15     {"{", TOK_LCURL},
  16     {"}", TOK_RCURL},
  17     {"*", TOK_MUL},
  18     {"+", TOK_PLUS},
  19     {"-", TOK_MINUS},
  20     {"/", TOK_DIV},
  21     {"~", TOK_CAT},
  22     {":", TOK_COLON},
  23     {".", TOK_DOT},
  24     {",", TOK_COMMA},
  25     {";", TOK_SEMI},
  26     {"=", TOK_ASSIGN},
  27     {"<",  TOK_LT},
  28     {"<=", TOK_LTE},
  29     {"==", TOK_EQ},
  30     {"!=", TOK_NEQ},
  31     {">",  TOK_GT},
  32     {">=", TOK_GTE},
  33     {"nil", TOK_NIL},
  34     {"if",    TOK_IF},
  35     {"elsif", TOK_ELSIF},
  36     {"else",  TOK_ELSE},
  37     {"for",     TOK_FOR},
  38     {"foreach", TOK_FOREACH},
  39     {"while",   TOK_WHILE},
  40     {"return",   TOK_RETURN},
  41     {"break",    TOK_BREAK},
  42     {"continue", TOK_CONTINUE},
  43     {"func", TOK_FUNC},
  44     {"...", TOK_ELLIPSIS},
  45     {"?", TOK_QUESTION},
  46     {"var", TOK_VAR},
  47     {"+=", TOK_PLUSEQ},
  48     {"-=", TOK_MINUSEQ},
  49     {"*=", TOK_MULEQ},
  50     {"/=", TOK_DIVEQ},
  51     {"~=", TOK_CATEQ},
  52     {"forindex", TOK_FORINDEX},
  53 };
  54
  55 // Build a table of where each line ending is
  56 static int* findLines(struct Parser* p)
  57 {
  58     char* buf = p->buf;
  59     int sz = p->len/10 + 16;
  60     int* lines = naParseAlloc(p, (sizeof(int) * sz));
  61     int i, j, n=0;
  62
  63     for(i=0; i<p->len; i++) {
  64         // Not a line ending at all
  65         if(buf[i] != '\n' && buf[i] != '\r')
  66             continue;
  67
  68         // Skip over the \r of a \r\n pair.
  69         if(buf[i] == '\r' && (i+1)<p->len && buf[i+1] == '\n') {
  70             continue;
  71         }
  72         // Reallocate if necessary
  73         if(n == sz) {
  74             int* nl;
  75             sz *= 2;
  76             nl = naParseAlloc(p, sizeof(int) * sz);
  77             for(j=0; j<n; j++) nl[j] = lines[j];
  78             lines = nl;
  79         }
  80         lines[n++] = i;
  81     }
  82     p->lines = lines;
  83     p->nLines = n;
  84     return lines;
  85 }
  86
  87 // What line number is the index on?
  88 static int getLine(struct Parser* p, int index)
  89 {
  90     int i;
  91     for(i=0; i<p->nLines; i++)
  92         if(p->lines[i] > index)
  93             return (p->firstLine-1) + i+1;
  94     return (p->firstLine-1) + p->nLines+1;
  95 }
  96
  97 static void error(struct Parser* p, char* msg, int index)
  98 {
  99     naParseError(p, msg, getLine(p, index));
 100 }
 101
 102 // End index (the newline character) of the given line
 103 static int lineEnd(struct Parser* p, int line)
 104 {
 105     if(line > p->nLines) return p->len;
 106     return p->lines[line-1];
 107 }
 108
 109 static void newToken(struct Parser* p, int pos, int type,
 110                      char* str, int slen, double num)
 111 {
 112     struct Token *tok, *last = p->tree.lastChild;
 113
 114     /* Adjacent string literals get concatenated */
 115     if(type == TOK_LITERAL && str) {
 116         if(last && last->type == TOK_LITERAL) {
 117             int i, len1 = last->strlen;
 118             char* str2 = naParseAlloc(p, len1 + slen);
 119             for(i=0; i<len1; i++) str2[i] = last->str[i];
 120             for(i=0; i<slen; i++) str2[i+len1] = str[i];
 121             last->str = str2;
 122             last->strlen += slen;
 123             return;
 124         }
 125     }
 126
 127     tok = naParseAlloc(p, sizeof(struct Token));
 128     tok->type = type;
 129     tok->line = getLine(p, pos);
 130     tok->str = str;
 131     tok->strlen = slen;
 132     tok->num = num;
 133     tok->next = 0;
 134     tok->prev = last;
 135     tok->children = 0;
 136     tok->lastChild = 0;
 137     tok->rule = 0;
 138
 139     // Context sensitivity hack: a "-" following a binary operator of
 140     // equal or higher precedence must be a unary negation.  Needed to
 141     // get precedence right in the parser for expressiong like "a * -2"
 142     if(type == TOK_MINUS && tok->prev) {
 143         int pt = tok->prev->type;
 144         if(pt==TOK_PLUS||pt==TOK_MINUS||pt==TOK_CAT||pt==TOK_MUL||pt==TOK_DIV)
 145             tok->type = type = TOK_NEG;
 146     }
 147
 148     if(!p->tree.children) p->tree.children = tok;
 149     if(p->tree.lastChild) p->tree.lastChild->next = tok;
 150     p->tree.lastChild = tok;
 151 }
 152
 153 static int hex(char c)
 154 {
 155     if(c >= '0' && c <= '9') return c - '0';
 156     if(c >= 'A' && c <= 'F') return c - 'A' + 10;
 157     if(c >= 'a' && c <= 'f') return c - 'a' + 10;
 158     return -1;
 159 }
 160
 161 static int hexc(char c, struct Parser* p, int index)
 162 {
 163     int n = hex(c);
 164     if(n < 0) error(p, "bad hex constant", index);
 165     return n;
 166 }
 167
 168 // Escape and returns a single backslashed expression in a single
 169 // quoted string.  Trivial, just escape \' and leave everything else
 170 // alone.
 171 static void sqEscape(char* buf, int len, int index, struct Parser* p,
 172                      char* cOut, int* eatenOut)
 173 {
 174     if(len < 2) error(p, "unterminated string", index);
 175     if(buf[1] == '\'') {
 176         *cOut = '\'';
 177         *eatenOut = 2;
 178     } else {
 179         *cOut = '\\';
 180         *eatenOut = 1;
 181     }
 182 }
 183
 184 // Ditto, but more complicated for double quotes.
 185 /* FIXME: need to handle \b (8), \f (12), and \uXXXX for JSON compliance */
 186 static void dqEscape(char* buf, int len, int index, struct Parser* p,
 187                      char* cOut, int* eatenOut)
 188 {
 189     if(len < 2) error(p, "unterminated string", index);
 190     *eatenOut = 2;
 191     switch(buf[1]) {
 192     case '"': *cOut = '"'; break;
 193     case 'r': *cOut = '\r'; break;
 194     case 'n': *cOut = '\n'; break;
 195     case 't': *cOut = '\t'; break;
 196     case '\\': *cOut = '\\'; break;
 197     case '`': *cOut = '`'; break;
 198     case 'x':
 199         if(len < 4) error(p, "unterminated string", index);
 200         *cOut = (char)((hexc(buf[2], p, index)<<4) | hexc(buf[3], p, index));
 201         *eatenOut = 4;
 202         break;
 203     default:
 204         // Unhandled, put the backslash back
 205         *cOut = '\\';
 206         *eatenOut = 1;
 207     }
 208 }
 209
 210 static void charLiteral(struct Parser* p, int index, char* s, int len)
 211 {
 212     int n, c;
 213     c = naLexUtf8C(s, len, &n);
 214     if(c < 0 || n != len) error(p, "invalid utf8 character constant", index);
 215     newToken(p, index, TOK_LITERAL, 0, 0, c);
 216 }
 217
 218 // Read in a string literal
 219 static int lexStringLiteral(struct Parser* p, int index, char q)
 220 {
 221     int i, j, len, iteration;
 222     char* out = 0;
 223     char* buf = p->buf;
 224
 225     for(iteration = 0; iteration<2; iteration++) {
 226         i = index+1;
 227         j = len = 0;
 228         while(i < p->len) {
 229             char c = buf[i];
 230             int eaten = 1;
 231             if(c == q) break;
 232             if(c == '\\') {
 233                 if(q == '\'') sqEscape(buf+i, p->len-i, i, p, &c, &eaten);
 234                 else          dqEscape(buf+i, p->len-i, i, p, &c, &eaten);
 235             }
 236             if(iteration == 1) out[j++] = c;
 237             i += eaten;
 238             len++;
 239         }
 240         // Finished stage one -- allocate the buffer for stage two
 241         if(iteration == 0) out = naParseAlloc(p, len);
 242     }
 243     if(q == '`') charLiteral(p, index, out, len);
 244     else         newToken(p, index, TOK_LITERAL, out, len, 0);
 245     return i+1;
 246 }
 247
 248 static int lexHexLiteral(struct Parser* p, int index)
 249 {
 250     int nib, i = index;
 251     double d = 0;
 252     while(i < p->len && (nib = hex(p->buf[i])) >= 0) {
 253         d = d*16 + nib;
 254         i++;
 255     }
 256     newToken(p, index, TOK_LITERAL, 0, 0, d);
 257     return i;
 258 }
 259
 260 #define ISNUM(c) ((c) >= '0' && (c) <= '9')
 261 #define ISHEX(c) (ISNUM(c) || ((c)>='a' && (c)<='f') || ((c)>='A' && (c)<='F'))
 262 #define NUMSTART(c) (ISNUM(c) || (c) == '+' || (c) == '-')
 263 static int lexNumLiteral(struct Parser* p, int index)
 264 {
 265     int len = p->len, i = index;
 266     unsigned char* buf = (unsigned char*)p->buf;
 267     double d;
 268
 269     if(buf[i] == '0' && i+2<len && buf[i+1] == 'x' && ISHEX(buf[i+2]))
 270        return lexHexLiteral(p, index+2);
 271
 272     while(i<len && ISNUM(buf[i])) i++;
 273     if(i<len && buf[i] == '.') {
 274         i++;
 275         while(i<len && ISNUM(buf[i])) i++;
 276     }
 277     if(i+1<len && (buf[i] == 'e' || buf[i] == 'E') && NUMSTART(buf[i+1])) {
 278         i++;
 279         if(buf[i] == '-' || buf[i] == '+') i++;
 280         while(i<len && ISNUM(buf[i])) i++;
 281     }
 282     naStr_parsenum(p->buf + index, i - index, &d);
 283     newToken(p, index, TOK_LITERAL, 0, 0, d);
 284     return i;
 285 }
 286
 287 static int trySymbol(struct Parser* p, int start)
 288 {
 289     int i = start;
 290     while((i < p->len) &&
 291           ((p->buf[i] == '_') ||
 292            (p->buf[i] >= 'A' && p->buf[i] <= 'Z') ||
 293            (p->buf[i] >= 'a' && p->buf[i] <= 'z') ||
 294            (p->buf[i] >= '0' && p->buf[i] <= '9')))
 295     { i++; }
 296     return i-start;
 297 }
 298
 299 // Returns the length of lexeme l if the buffer prefix matches, or
 300 // else zero.
 301 static int matchLexeme(char* buf, int len, char* l)
 302 {
 303     int i;
 304     for(i=0; i<len; i++) {
 305         if(l[i] == 0)      return i;
 306         if(l[i] != buf[i]) return 0;
 307     }
 308     // Ran out of buffer.  This is still OK if we're also at the end
 309     // of the lexeme.
 310     if(l[i] == 0) return i;
 311     return 0;
 312 }
 313
 314 // This is dumb and algorithmically slow.  It would be much more
 315 // elegant to sort and binary search the lexeme list, but that's a lot
 316 // more code and this really isn't very slow in practice; it checks
 317 // every byte of every lexeme for each input byte.  There are less
 318 // than 100 bytes of lexemes in the grammar.  Returns the number of
 319 // bytes in the lexeme read (or zero if none was recognized)
 320 static int tryLexemes(struct Parser* p, int index, int* lexemeOut)
 321 {
 322     int i, n, best, bestIndex=-1;
 323     char* start = p->buf + index;
 324     int len = p->len - index;
 325
 326     n = sizeof(LEXEMES) / sizeof(struct Lexeme);
 327     best = 0;
 328     for(i=0; i<n; i++) {
 329         int l = matchLexeme(start, len, LEXEMES[i].str);
 330         if(l > best) {
 331             best = l;
 332             bestIndex = i;
 333         }
 334     }
 335     if(best > 0) *lexemeOut = bestIndex;
 336     return best;
 337 }
 338
 339 void naLex(struct Parser* p)
 340 {
 341     int i = 0;
 342     findLines(p);
 343     while(i<p->len) {
 344         char c = p->buf[i];
 345
 346         // Whitespace, comments and string literals have obvious
 347         // markers and can be handled by a switch:
 348         int handled = 1;
 349         switch(c) {
 350         case ' ': case '\t': case '\n': case '\r': case '\f': case '\v':
 351             i++;
 352             break;
 353         case '#':
 354             i = lineEnd(p, getLine(p, i));
 355             break;
 356         case '\'': case '"': case '`':
 357             i = lexStringLiteral(p, i, c);
 358             break;
 359         default:
 360             if(ISNUM(c) || (c == '.' && (i+1)<p->len && ISNUM(p->buf[i+1])))
 361                 i = lexNumLiteral(p, i);
 362             else handled = 0;
 363         }
 364
 365         // Lexemes and symbols are a little more complicated.  Pick
 366         // the longest one that matches.  Since some lexemes look like
 367         // symbols (e.g. "or") they need a higher precedence, but we
 368         // don't want a lexeme match to clobber the beginning of a
 369         // symbol (e.g. "orchid").  If neither match, we have a bad
 370         // character in the mix.
 371         if(!handled) {
 372             int symlen=0, lexlen=0, lexeme=-1;
 373             lexlen = tryLexemes(p, i, &lexeme);
 374             if((c>='A' && c<='Z') || (c>='a' && c<='z') || (c=='_'))
 375                 symlen = trySymbol(p, i);
 376             if(lexlen && lexlen >= symlen) {
 377                 newToken(p, i, LEXEMES[lexeme].tok, 0, 0, 0);
 378                 i += lexlen;
 379             } else if(symlen) {
 380                 newToken(p, i, TOK_SYMBOL, p->buf+i, symlen, 0);
 381                 i += symlen;
 382             } else {
 383                 error(p, "illegal character", i);
 384             }
 385         }
 386     }
 387 }