5 // Static precedence table, from low (loose binding, do first) to high
6 // (tight binding, do last).
7 enum { PREC_BINARY, PREC_REVERSE, PREC_PREFIX, PREC_SUFFIX };
9 #define MAX_PREC_TOKS 6
11 int toks[MAX_PREC_TOKS];
14 { { TOK_SEMI, TOK_COMMA }, PREC_REVERSE },
15 { { TOK_ELLIPSIS }, PREC_SUFFIX },
16 { { TOK_RETURN, TOK_BREAK, TOK_CONTINUE }, PREC_PREFIX },
17 { { TOK_ASSIGN, TOK_PLUSEQ, TOK_MINUSEQ,
18 TOK_MULEQ, TOK_DIVEQ, TOK_CATEQ }, PREC_REVERSE },
19 { { TOK_COLON, TOK_QUESTION }, PREC_REVERSE },
20 { { TOK_VAR }, PREC_PREFIX },
21 { { TOK_OR }, PREC_BINARY },
22 { { TOK_AND }, PREC_BINARY },
23 { { TOK_EQ, TOK_NEQ }, PREC_BINARY },
24 { { TOK_LT, TOK_LTE, TOK_GT, TOK_GTE }, PREC_BINARY },
25 { { TOK_PLUS, TOK_MINUS, TOK_CAT }, PREC_BINARY },
26 { { TOK_MUL, TOK_DIV }, PREC_BINARY },
27 { { TOK_MINUS, TOK_NEG, TOK_NOT }, PREC_PREFIX },
28 { { TOK_LPAR, TOK_LBRA }, PREC_SUFFIX },
29 { { TOK_DOT }, PREC_BINARY },
31 #define PRECEDENCE_LEVELS (sizeof(PRECEDENCE)/sizeof(struct precedence))
33 void naParseError(struct Parser* p, char* msg, int line)
37 longjmp(p->jumpHandle, 1);
40 // A "generic" (too obfuscated to describe) parser error
41 static void oops(struct Parser* p, struct Token* t)
43 naParseError(p, "parse error", t->line);
46 void naParseInit(struct Parser* p)
58 p->tree.type = TOK_TOP;
66 p->tree.lastChild = 0;
69 void naParseDestroy(struct Parser* p)
72 for(i=0; i<p->nChunks; i++) naFree(p->chunks[i]);
74 naFree(p->chunkSizes);
78 void* naParseAlloc(struct Parser* p, int bytes)
82 // Round up to 8 byte chunks for alignment
83 if(bytes & 0x7) bytes = ((bytes>>3) + 1) << 3;
86 if(p->leftInChunk < bytes) {
93 if(sz < bytes) sz = bytes;
94 newChunk = naAlloc(sz);
98 newChunks = naAlloc(p->nChunks * sizeof(void*));
99 for(i=1; i<p->nChunks; i++) newChunks[i] = p->chunks[i-1];
100 newChunks[0] = newChunk;
102 p->chunks = newChunks;
104 newChunkSizes = naAlloc(p->nChunks * sizeof(int));
105 for(i=1; i<p->nChunks; i++) newChunkSizes[i] = p->chunkSizes[i-1];
106 newChunkSizes[0] = sz;
107 naFree(p->chunkSizes);
108 p->chunkSizes = newChunkSizes;
113 result = (char *)p->chunks[0] + p->chunkSizes[0] - p->leftInChunk;
114 p->leftInChunk -= bytes;
115 return (void*)result;
118 // Remove the child from the list where it exists, and insert it at
119 // the end of the parents child list.
120 static void addNewChild(struct Token* p, struct Token* c)
122 if(c->prev) c->prev->next = c->next;
123 if(c->next) c->next->prev = c->prev;
124 if(c == c->parent->children)
125 c->parent->children = c->next;
126 if(c == c->parent->lastChild)
127 c->parent->lastChild = c->prev;
130 c->prev = p->lastChild;
131 if(p->lastChild) p->lastChild->next = c;
132 if(!p->children) p->children = c;
136 // Follows the token list from start (which must be a left brace of
137 // some type), placing all tokens found into start's child list until
138 // it reaches the matching close brace.
139 static void collectBrace(struct Parser* p, struct Token* start)
143 if(start->type == TOK_LPAR) closer = TOK_RPAR;
144 if(start->type == TOK_LBRA) closer = TOK_RBRA;
145 if(start->type == TOK_LCURL) closer = TOK_RCURL;
151 case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
154 case TOK_RPAR: case TOK_RBRA: case TOK_RCURL:
155 if(t->type != closer)
156 naParseError(p, "mismatched closing brace", t->line);
158 // Drop this node on the floor, stitch up the list and return
159 if(start->parent->lastChild == t)
160 start->parent->lastChild = t->prev;
161 start->next = t->next;
162 if(t->next) t->next->prev = start;
165 // Snip t out of the existing list, and append it to start's
168 addNewChild(start, t);
171 naParseError(p, "unterminated brace", start->line);
174 // Recursively find the contents of all matching brace pairs in the
175 // token list and turn them into children of the left token. The
176 // right token disappears.
177 static void braceMatch(struct Parser* p, struct Token* start)
179 struct Token* t = start;
182 case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
185 case TOK_RPAR: case TOK_RBRA: case TOK_RCURL:
186 if(start->type != TOK_LBRA)
187 naParseError(p, "stray closing brace", t->line);
194 // Allocate and return an "empty" token as a parsing placeholder.
195 static struct Token* emptyToken(struct Parser* p)
197 struct Token* t = naParseAlloc(p, sizeof(struct Token));
203 t->next = t->prev = t->children = t->lastChild = 0;
208 // Fixes up parenting for obvious parsing situations, like code blocks
209 // being the child of a func keyword, etc...
210 static void fixBlockStructure(struct Parser* p, struct Token* start)
217 // Slurp an optional paren block containing an arglist, then
218 // fall through to parse the curlies...
219 if(t->next && t->next->type == TOK_LPAR) {
222 fixBlockStructure(p, c);
224 case TOK_ELSE: // and TOK_FUNC!
225 // These guys precede a single curly block
226 if(!t->next || t->next->type != TOK_LCURL) oops(p, t);
229 fixBlockStructure(p, c);
231 case TOK_FOR: case TOK_FOREACH: case TOK_FORINDEX: case TOK_WHILE:
232 case TOK_IF: case TOK_ELSIF:
233 // Expect a paren and then a curly
234 if(!t->next || t->next->type != TOK_LPAR) oops(p, t);
237 fixBlockStructure(p, c);
239 if(!t->next || t->next->type != TOK_LCURL) oops(p, t);
242 fixBlockStructure(p, c);
244 case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
245 fixBlockStructure(p, t->children);
251 // Another pass to hook up the elsif/else chains.
254 if(t->type == TOK_IF) {
255 while(t->next && t->next->type == TOK_ELSIF)
256 addNewChild(t, t->next);
257 if(t->next && t->next->type == TOK_ELSE)
258 addNewChild(t, t->next);
263 // And a final one to add semicolons. Always add one after
264 // for/foreach/while expressions. Add one after a function lambda
265 // if it immediately follows an assignment, and add one after an
266 // if/elsif/else if it is the first token in an expression list
267 // (i.e has no previous token, or is preceded by a ';' or '{').
268 // This mimicks common usage and avoids a conspicuous difference
269 // between this grammar and more common languages. It can be
270 // "escaped" with extra parenthesis if necessary, e.g.:
271 // a = (func { join(" ", arg) })(1, 2, 3, 4);
278 || t->prev->type == TOK_SEMI
279 || t->prev->type == TOK_LCURL)
282 case TOK_FOR: case TOK_FOREACH: case TOK_FORINDEX: case TOK_WHILE:
286 if(t->prev && t->prev->type == TOK_ASSIGN)
290 if(t->next && t->next->type == TOK_SEMI)
291 addSemi = 0; // don't bother if it's already there!
293 struct Token* semi = emptyToken(p);
294 semi->type = TOK_SEMI;
295 semi->line = t->line;
296 semi->next = t->next;
298 semi->parent = t->parent;
299 if(semi->next) semi->next->prev = semi;
301 t = semi; // don't bother checking the new one
308 // True if the token's type exists in the precedence level.
309 static int tokInLevel(struct Token* tok, int level)
312 for(i=0; i<MAX_PREC_TOKS; i++)
313 if(PRECEDENCE[level].toks[i] == tok->type)
318 static int isBrace(int type)
320 return type == TOK_LPAR || type == TOK_LBRA || type == TOK_LCURL;
323 static int isBlock(int t)
325 return t == TOK_IF || t == TOK_ELSIF || t == TOK_ELSE
326 || t == TOK_FOR || t == TOK_FOREACH || t == TOK_WHILE
327 || t == TOK_FUNC || t == TOK_FORINDEX;
330 static void precChildren(struct Parser* p, struct Token* t);
331 static void precBlock(struct Parser* p, struct Token* t);
333 static struct Token* parsePrecedence(struct Parser* p,
334 struct Token* start, struct Token* end,
338 struct Token *t, *top, *left, *right;
339 struct Token *a, *b, *c, *d; // temporaries
341 // This is an error. No "siblings" are allowed at the bottom level.
342 if(level >= PRECEDENCE_LEVELS && start != end)
345 // Synthesize an empty token if necessary
346 if(end == 0 && start == 0)
347 return emptyToken(p);
349 // Sanify the list. This is OK, since we're recursing into the
350 // list structure; stuff to the left and right has already been
351 // handled somewhere above.
352 if(end == 0) end = start;
353 if(start == 0) start = end;
354 if(start->prev) start->prev->next = 0;
355 if(end->next) end->next->prev = 0;
356 start->prev = end->next = 0;
358 // Single tokens parse as themselves. Recurse into braces, and
359 // parse children of block structure.
361 if(isBrace(start->type)) {
362 precChildren(p, start);
363 } else if(isBlock(start->type)) {
369 // A context-sensitivity: we want to parse ';' and ',' as binary
370 // operators, but want them to be legal at the beginning and end
371 // of a list (unlike, say, '+' where we want a parse error).
372 // Generate empties as necessary.
373 if(start->type == TOK_SEMI || start->type == TOK_COMMA) {
379 if(end->type == TOK_SEMI || end->type == TOK_COMMA) {
386 // Another one: the "." and (postfix) "[]/()" operators should
387 // really be the same precendence level, but the existing
388 // implementation doesn't allow for it. Bump us up a level if we
389 // are parsing for DOT but find a LPAR/LBRA at the end of the
391 if(PRECEDENCE[level].toks[0] == TOK_DOT)
392 if(end->type == TOK_LPAR || end->type == TOK_LBRA)
395 top = left = right = 0;
396 rule = PRECEDENCE[level].rule;
399 if(tokInLevel(start, level) && start->next) {
401 b = start->lastChild;
405 if(a) left = parsePrecedence(p, a, b, 0);
406 right = parsePrecedence(p, c, d, level);
410 if(tokInLevel(end, level) && end->prev) {
416 left = parsePrecedence(p, a, b, level);
417 if(c) right = parsePrecedence(p, c, d, 0);
423 if(tokInLevel(t, level)) {
424 a = t->prev ? start : 0;
427 d = t->next ? end : 0;
429 left = parsePrecedence(p, a, b, level);
430 right = parsePrecedence(p, c, d, level+1);
439 if(tokInLevel(t, level)) {
440 a = t->prev ? start : 0;
443 d = t->next ? end : 0;
445 left = parsePrecedence(p, a, b, level+1);
446 right = parsePrecedence(p, c, d, level);
454 // Found nothing, try the next level
456 return parsePrecedence(p, start, end, level+1);
463 top->children = left;
470 top->lastChild = right;
472 top->next = top->prev = 0;
476 static void precChildren(struct Parser* p, struct Token* t)
478 struct Token* top = parsePrecedence(p, t->children, t->lastChild, 0);
483 // Run a "block structure" node (if/elsif/else/for/while/foreach)
484 // through the precedence parser. The funny child structure makes
485 // this a little more complicated than it should be.
486 static void precBlock(struct Parser* p, struct Token* block)
488 struct Token* t = block->children;
492 else if(isBlock(t->type))
498 naRef naParseCode(struct Context* c, naRef srcFile, int firstLine,
499 char* buf, int len, int* errLine)
505 // Protect from garbage collection
506 naVec_append(c->temps, srcFile);
508 // Catch parser errors here.
510 if(setjmp(p.jumpHandle)) {
512 *errLine = p.errLine;
519 p.firstLine = firstLine;
523 // Lexify, match brace structure, fixup if/for/etc...
525 braceMatch(&p, p.tree.children);
526 fixBlockStructure(&p, p.tree.children);
528 // Recursively run the precedence parser, and fixup the treetop
529 t = parsePrecedence(&p, p.tree.children, p.tree.lastChild, 0);
530 t->prev = t->next = 0;
532 p.tree.lastChild = t;
535 codeObj = naCodeGen(&p, &(p.tree), 0);
539 naVec_append(c->temps, codeObj);