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 5
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 }, PREC_REVERSE },
18 { { TOK_COLON, TOK_QUESTION }, PREC_REVERSE },
19 { { TOK_VAR }, PREC_PREFIX },
20 { { TOK_OR }, PREC_BINARY },
21 { { TOK_AND }, PREC_BINARY },
22 { { TOK_EQ, TOK_NEQ }, PREC_BINARY },
23 { { TOK_LT, TOK_LTE, TOK_GT, TOK_GTE }, PREC_BINARY },
24 { { TOK_PLUS, TOK_MINUS, TOK_CAT }, PREC_BINARY },
25 { { TOK_MUL, TOK_DIV }, PREC_BINARY },
26 { { TOK_MINUS, TOK_NEG, TOK_NOT }, PREC_PREFIX },
27 { { TOK_LPAR, TOK_LBRA }, PREC_SUFFIX },
28 { { TOK_DOT }, PREC_BINARY },
30 #define PRECEDENCE_LEVELS (sizeof(PRECEDENCE)/sizeof(struct precedence))
32 void naParseError(struct Parser* p, char* msg, int line)
36 longjmp(p->jumpHandle, 1);
39 // A "generic" (too obfuscated to describe) parser error
40 static void oops(struct Parser* p, struct Token* t)
42 naParseError(p, "parse error", t->line);
45 void naParseInit(struct Parser* p)
57 p->tree.type = TOK_TOP;
65 p->tree.lastChild = 0;
68 void naParseDestroy(struct Parser* p)
71 for(i=0; i<p->nChunks; i++) naFree(p->chunks[i]);
73 naFree(p->chunkSizes);
77 void* naParseAlloc(struct Parser* p, int bytes)
81 // Round up to 8 byte chunks for alignment
82 if(bytes & 0x7) bytes = ((bytes>>3) + 1) << 3;
85 if(p->leftInChunk < bytes) {
92 if(sz < bytes) sz = bytes;
93 newChunk = naAlloc(sz);
97 newChunks = naAlloc(p->nChunks * sizeof(void*));
98 for(i=1; i<p->nChunks; i++) newChunks[i] = p->chunks[i-1];
99 newChunks[0] = newChunk;
101 p->chunks = newChunks;
103 newChunkSizes = naAlloc(p->nChunks * sizeof(int));
104 for(i=1; i<p->nChunks; i++) newChunkSizes[i] = p->chunkSizes[i-1];
105 newChunkSizes[0] = sz;
106 naFree(p->chunkSizes);
107 p->chunkSizes = newChunkSizes;
112 result = (char *)p->chunks[0] + p->chunkSizes[0] - p->leftInChunk;
113 p->leftInChunk -= bytes;
114 return (void*)result;
117 // Remove the child from the list where it exists, and insert it at
118 // the end of the parents child list.
119 static void addNewChild(struct Token* p, struct Token* c)
121 if(c->prev) c->prev->next = c->next;
122 if(c->next) c->next->prev = c->prev;
123 if(c == c->parent->children)
124 c->parent->children = c->next;
125 if(c == c->parent->lastChild)
126 c->parent->lastChild = c->prev;
129 c->prev = p->lastChild;
130 if(p->lastChild) p->lastChild->next = c;
131 if(!p->children) p->children = c;
135 // Follows the token list from start (which must be a left brace of
136 // some type), placing all tokens found into start's child list until
137 // it reaches the matching close brace.
138 static void collectBrace(struct Parser* p, struct Token* start)
142 if(start->type == TOK_LPAR) closer = TOK_RPAR;
143 if(start->type == TOK_LBRA) closer = TOK_RBRA;
144 if(start->type == TOK_LCURL) closer = TOK_RCURL;
150 case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
153 case TOK_RPAR: case TOK_RBRA: case TOK_RCURL:
154 if(t->type != closer)
155 naParseError(p, "mismatched closing brace", t->line);
157 // Drop this node on the floor, stitch up the list and return
158 if(start->parent->lastChild == t)
159 start->parent->lastChild = t->prev;
160 start->next = t->next;
161 if(t->next) t->next->prev = start;
164 // Snip t out of the existing list, and append it to start's
167 addNewChild(start, t);
170 naParseError(p, "unterminated brace", start->line);
173 // Recursively find the contents of all matching brace pairs in the
174 // token list and turn them into children of the left token. The
175 // right token disappears.
176 static void braceMatch(struct Parser* p, struct Token* start)
178 struct Token* t = start;
181 case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
184 case TOK_RPAR: case TOK_RBRA: case TOK_RCURL:
185 if(start->type != TOK_LBRA)
186 naParseError(p, "stray closing brace", t->line);
193 // Allocate and return an "empty" token as a parsing placeholder.
194 static struct Token* emptyToken(struct Parser* p)
196 struct Token* t = naParseAlloc(p, sizeof(struct Token));
202 t->next = t->prev = t->children = t->lastChild = 0;
207 // Fixes up parenting for obvious parsing situations, like code blocks
208 // being the child of a func keyword, etc...
209 static void fixBlockStructure(struct Parser* p, struct Token* start)
216 // Slurp an optional paren block containing an arglist, then
217 // fall through to parse the curlies...
218 if(t->next && t->next->type == TOK_LPAR) {
221 fixBlockStructure(p, c);
223 case TOK_ELSE: // and TOK_FUNC!
224 // These guys precede a single curly block
225 if(!t->next || t->next->type != TOK_LCURL) oops(p, t);
228 fixBlockStructure(p, c);
230 case TOK_FOR: case TOK_FOREACH: case TOK_WHILE:
231 case TOK_IF: case TOK_ELSIF:
232 // Expect a paren and then a curly
233 if(!t->next || t->next->type != TOK_LPAR) oops(p, t);
236 fixBlockStructure(p, c);
238 if(!t->next || t->next->type != TOK_LCURL) oops(p, t);
241 fixBlockStructure(p, c);
243 case TOK_LPAR: case TOK_LBRA: case TOK_LCURL:
244 fixBlockStructure(p, t->children);
250 // Another pass to hook up the elsif/else chains.
253 if(t->type == TOK_IF) {
254 while(t->next && t->next->type == TOK_ELSIF)
255 addNewChild(t, t->next);
256 if(t->next && t->next->type == TOK_ELSE)
257 addNewChild(t, t->next);
262 // And a final one to add semicolons. Always add one after
263 // for/foreach/while expressions. Add one after a function lambda
264 // if it immediately follows an assignment, and add one after an
265 // if/elsif/else if it is the first token in an expression list
266 // (i.e has no previous token, or is preceded by a ';' or '{').
267 // This mimicks common usage and avoids a conspicuous difference
268 // between this grammar and more common languages. It can be
269 // "escaped" with extra parenthesis if necessary, e.g.:
270 // a = (func { join(" ", arg) })(1, 2, 3, 4);
277 || t->prev->type == TOK_SEMI
278 || t->prev->type == TOK_LCURL)
281 case TOK_FOR: case TOK_FOREACH: case TOK_WHILE:
285 if(t->prev && t->prev->type == TOK_ASSIGN)
289 if(t->next && t->next->type == TOK_SEMI)
290 addSemi = 0; // don't bother if it's already there!
292 struct Token* semi = emptyToken(p);
293 semi->type = TOK_SEMI;
294 semi->line = t->line;
295 semi->next = t->next;
297 semi->parent = t->parent;
298 if(semi->next) semi->next->prev = semi;
300 t = semi; // don't bother checking the new one
307 // True if the token's type exists in the precedence level.
308 static int tokInLevel(struct Token* tok, int level)
311 for(i=0; i<MAX_PREC_TOKS; i++)
312 if(PRECEDENCE[level].toks[i] == tok->type)
317 static int isBrace(int type)
319 return type == TOK_LPAR || type == TOK_LBRA || type == TOK_LCURL;
322 static int isBlock(int t)
324 return t == TOK_IF || t == TOK_ELSIF || t == TOK_ELSE
325 || t == TOK_FOR || t == TOK_FOREACH || t == TOK_WHILE
329 static void precChildren(struct Parser* p, struct Token* t);
330 static void precBlock(struct Parser* p, struct Token* t);
332 static struct Token* parsePrecedence(struct Parser* p,
333 struct Token* start, struct Token* end,
337 struct Token *t, *top, *left, *right;
338 struct Token *a, *b, *c, *d; // temporaries
340 // This is an error. No "siblings" are allowed at the bottom level.
341 if(level >= PRECEDENCE_LEVELS && start != end)
344 // Synthesize an empty token if necessary
345 if(end == 0 && start == 0)
346 return emptyToken(p);
348 // Sanify the list. This is OK, since we're recursing into the
349 // list structure; stuff to the left and right has already been
350 // handled somewhere above.
351 if(end == 0) end = start;
352 if(start == 0) start = end;
353 if(start->prev) start->prev->next = 0;
354 if(end->next) end->next->prev = 0;
355 start->prev = end->next = 0;
357 // Single tokens parse as themselves. Recurse into braces, and
358 // parse children of block structure.
360 if(isBrace(start->type)) {
361 precChildren(p, start);
362 } else if(isBlock(start->type)) {
368 // A context-sensitivity: we want to parse ';' and ',' as binary
369 // operators, but want them to be legal at the beginning and end
370 // of a list (unlike, say, '+' where we want a parse error).
371 // Generate empties as necessary.
372 if(start->type == TOK_SEMI || start->type == TOK_COMMA) {
378 if(end->type == TOK_SEMI || end->type == TOK_COMMA) {
385 // Another one: the "." and (postfix) "[]/()" operators should
386 // really be the same precendence level, but the existing
387 // implementation doesn't allow for it. Bump us up a level if we
388 // are parsing for DOT but find a LPAR/LBRA at the end of the
390 if(PRECEDENCE[level].toks[0] == TOK_DOT)
391 if(end->type == TOK_LPAR || end->type == TOK_LBRA)
394 top = left = right = 0;
395 rule = PRECEDENCE[level].rule;
398 if(tokInLevel(start, level) && start->next) {
400 b = start->lastChild;
404 if(a) left = parsePrecedence(p, a, b, 0);
405 right = parsePrecedence(p, c, d, level);
409 if(tokInLevel(end, level) && end->prev) {
415 left = parsePrecedence(p, a, b, level);
416 if(c) right = parsePrecedence(p, c, d, 0);
422 if(tokInLevel(t, level)) {
423 a = t->prev ? start : 0;
426 d = t->next ? end : 0;
428 left = parsePrecedence(p, a, b, level);
429 right = parsePrecedence(p, c, d, level+1);
438 if(tokInLevel(t, level)) {
439 a = t->prev ? start : 0;
442 d = t->next ? end : 0;
444 left = parsePrecedence(p, a, b, level+1);
445 right = parsePrecedence(p, c, d, level);
453 // Found nothing, try the next level
455 return parsePrecedence(p, start, end, level+1);
462 top->children = left;
469 top->lastChild = right;
471 top->next = top->prev = 0;
475 static void precChildren(struct Parser* p, struct Token* t)
477 struct Token* top = parsePrecedence(p, t->children, t->lastChild, 0);
482 // Run a "block structure" node (if/elsif/else/for/while/foreach)
483 // through the precedence parser. The funny child structure makes
484 // this a little more complicated than it should be.
485 static void precBlock(struct Parser* p, struct Token* block)
487 struct Token* t = block->children;
491 else if(isBlock(t->type))
497 naRef naParseCode(struct Context* c, naRef srcFile, int firstLine,
498 char* buf, int len, int* errLine)
504 // Protect from garbage collection
505 naVec_append(c->temps, srcFile);
507 // Catch parser errors here.
509 if(setjmp(p.jumpHandle)) {
511 *errLine = p.errLine;
518 p.firstLine = firstLine;
522 // Lexify, match brace structure, fixup if/for/etc...
524 braceMatch(&p, p.tree.children);
525 fixBlockStructure(&p, p.tree.children);
527 // Recursively run the precedence parser, and fixup the treetop
528 t = parsePrecedence(&p, p.tree.children, p.tree.lastChild, 0);
529 t->prev = t->next = 0;
531 p.tree.lastChild = t;
534 codeObj = naCodeGen(&p, &(p.tree), 0);
538 naVec_append(c->temps, codeObj);