6 // Static precedence table, from low (loose binding, do first) to high
7 // (tight binding, do last).
8 #define MAX_PREC_TOKS 6
9 static const struct precedence {
10 int toks[MAX_PREC_TOKS];
13 { { TOK_SEMI, TOK_COMMA }, PREC_REVERSE },
14 { { TOK_ELLIPSIS }, PREC_SUFFIX },
15 { { TOK_RETURN, TOK_BREAK, TOK_CONTINUE }, PREC_PREFIX },
16 { { TOK_ASSIGN, TOK_PLUSEQ, TOK_MINUSEQ,
17 TOK_MULEQ, TOK_DIVEQ, TOK_CATEQ }, 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)
34 if(line > 0) p->errLine = line;
36 longjmp(p->jumpHandle, 1);
39 static void oops(struct Parser* p) { naParseError(p, "parse error", -1); }
41 void naParseInit(struct Parser* p)
43 memset(p, 0, sizeof(*p));
44 p->tree.type = TOK_TOP;
48 void naParseDestroy(struct Parser* p)
51 for(i=0; i<p->nChunks; i++) naFree(p->chunks[i]);
53 naFree(p->chunkSizes);
57 void* naParseAlloc(struct Parser* p, int bytes)
60 bytes = (bytes+7) & (~7); // Round up to 8 byte chunks for alignment
62 if(p->leftInChunk < bytes) {
69 if(sz < bytes) sz = bytes;
70 newChunk = naAlloc(sz);
74 newChunks = naAlloc(p->nChunks * sizeof(void*));
75 for(i=1; i<p->nChunks; i++) newChunks[i] = p->chunks[i-1];
76 newChunks[0] = newChunk;
78 p->chunks = newChunks;
80 newChunkSizes = naAlloc(p->nChunks * sizeof(int));
81 for(i=1; i<p->nChunks; i++) newChunkSizes[i] = p->chunkSizes[i-1];
82 newChunkSizes[0] = sz;
83 naFree(p->chunkSizes);
84 p->chunkSizes = newChunkSizes;
89 result = (char *)p->chunks[0] + p->chunkSizes[0] - p->leftInChunk;
90 p->leftInChunk -= bytes;
94 static void addChild(struct Token *par, struct Token *ch)
97 ch->prev = par->lastChild;
98 par->lastChild->next = ch;
104 static int endBrace(int tok)
106 if(tok == TOK_LBRA) return TOK_RBRA;
107 if(tok == TOK_LPAR) return TOK_RPAR;
108 if(tok == TOK_LCURL) return TOK_RCURL;
112 static int isOpenBrace(int t)
114 return t==TOK_LPAR || t==TOK_LBRA || t==TOK_LCURL;
117 static int isLoopoid(int t)
119 return t==TOK_FOR || t==TOK_FOREACH || t==TOK_WHILE || t==TOK_FORINDEX;
122 static int isBlockoid(int t)
124 return isLoopoid(t)||t==TOK_IF||t==TOK_ELSIF||t==TOK_ELSE||t==TOK_FUNC;
127 /* Yes, a bare else or elsif ends a block; it means we've reached the
128 * end of the previous if/elsif clause. */
129 static int isBlockEnd(int t)
131 return t==TOK_RPAR||t==TOK_RBRA||t==TOK_RCURL||t==TOK_ELSIF||t==TOK_ELSE;
134 /* To match C's grammar, "blockoid" expressions sometimes need
135 * synthesized terminating semicolons to make them act like
136 * "statements" in C. Always add one after "loopoid"
137 * (for/foreach/while) expressions. Add one after a func if it
138 * immediately follows an assignment, and add one after an
139 * if/elsif/else if it is the first token in an expression list */
140 static int needsSemi(struct Token* t, struct Token* next)
142 if(!next || next->type == TOK_SEMI || isBlockEnd(next->type)) return 0;
143 if(t->type == TOK_IF) return !t->prev || t->prev->type == TOK_SEMI;
144 if(t->type == TOK_FUNC) return t->prev && t->prev->type == TOK_ASSIGN;
145 if(isLoopoid(t->type)) return 1;
149 static struct Token* newToken(struct Parser* p, int type)
151 struct Token* t = naParseAlloc(p, sizeof(struct Token));
152 memset(t, 0, sizeof(*t));
158 static struct Token* parseToken(struct Parser* p, struct Token** list);
160 static void parseBlock(struct Parser* p, struct Token *top,
161 int end, struct Token** list)
165 if(isBlockEnd((*list)->type) && (*list)->type != end) break;
166 if(end == TOK_SEMI && (*list)->type == TOK_COMMA) break;
167 t = parseToken(p, list);
168 if(t->type == end) return; /* drop end token on the floor */
170 if(needsSemi(t, *list))
171 addChild(top, newToken(p, TOK_SEMI));
173 /* Context dependency: end of block is a parse error UNLESS we're
174 * looking for a statement terminator (a braceless block) or a -1
176 if(end != TOK_SEMI && end != -1) oops(p);
179 static struct Token* parseToken(struct Parser* p, struct Token** list)
181 struct Token *t = *list;
183 if(t->next) t->next->prev = 0;
184 t->next = t->prev = 0;
185 p->errLine = t->line;
188 if(isOpenBrace(t->type)) {
189 parseBlock(p, t, endBrace(t->type), list);
190 } else if(isBlockoid(t->type)) {
191 /* Read an optional paren expression */
193 if((*list)->type == TOK_LPAR)
194 addChild(t, parseToken(p, list));
196 /* And the code block, which might be implicit/braceless */
198 if((*list)->type == TOK_LCURL) {
199 addChild(t, parseToken(p, list));
201 /* Context dependency: if we're reading a braceless block,
202 * and the first (!) token is itself a "blockoid"
203 * expression, it is parsed alone, otherwise, read to the
204 * terminating semicolon. */
205 struct Token *blk = newToken(p, TOK_LCURL);
206 if(isBlockoid((*list)->type)) addChild(blk, parseToken(p, list));
207 else parseBlock(p, blk, TOK_SEMI, list);
211 /* Read the elsif/else chain */
212 if(t->type == TOK_IF) {
213 while(*list && ((*list)->type == TOK_ELSIF))
214 addChild(t, parseToken(p, list));
215 if(*list && (*list)->type == TOK_ELSE)
216 addChild(t, parseToken(p, list));
219 /* Finally, check for proper usage */
220 if(t->type != TOK_FUNC) {
221 if(t->type == TOK_ELSE && t->children->type != TOK_LCURL) oops(p);
222 if(t->type != TOK_ELSE && t->children->type != TOK_LPAR) oops(p);
228 // True if the token's type exists in the precedence level.
229 static int tokInLevel(struct Token* tok, int level)
232 for(i=0; i<MAX_PREC_TOKS; i++)
233 if(PRECEDENCE[level].toks[i] == tok->type)
238 static struct Token* parsePrecedence(struct Parser* p, struct Token* start,
239 struct Token* end, int level);
241 static void precChildren(struct Parser* p, struct Token* t)
243 struct Token* top = parsePrecedence(p, t->children, t->lastChild, 0);
248 // Run a "block structure" node (if/elsif/else/for/while/foreach)
249 // through the precedence parser. The funny child structure makes
250 // this a little more complicated than it should be.
251 static void precBlock(struct Parser* p, struct Token* block)
253 struct Token* t = block->children;
255 if(isOpenBrace(t->type))
257 else if(isBlockoid(t->type))
263 /* Binary tokens that get empties synthesized if one side is missing */
264 static int oneSidedBinary(int t)
265 { return t == TOK_SEMI || t == TOK_COMMA || t == TOK_COLON; }
267 static struct Token* parsePrecedence(struct Parser* p,
268 struct Token* start, struct Token* end,
272 struct Token *t, *top, *left, *right;
273 struct Token *a, *b, *c, *d; // temporaries
275 // This is an error. No "siblings" are allowed at the bottom level.
276 if(level >= PRECEDENCE_LEVELS && start != end)
277 naParseError(p, "parse error", start->line);
279 // Synthesize an empty token if necessary
280 if(end == 0 && start == 0)
281 return newToken(p, TOK_EMPTY);
283 // Sanify the list. This is OK, since we're recursing into the
284 // list structure; stuff to the left and right has already been
285 // handled somewhere above.
286 if(end == 0) end = start;
287 if(start == 0) start = end;
288 if(start->prev) start->prev->next = 0;
289 if(end->next) end->next->prev = 0;
290 start->prev = end->next = 0;
292 // Single tokens parse as themselves. Recurse into braces, and
293 // parse children of block structure.
295 if (isOpenBrace(start->type)) precChildren(p, start);
296 else if(isBlockoid(start->type)) precBlock(p, start);
300 if(oneSidedBinary(start->type)) {
301 t = newToken(p, TOK_EMPTY);
306 if(oneSidedBinary(end->type)) {
307 t = newToken(p, TOK_EMPTY);
313 // Another one: the "." and (postfix) "[]/()" operators should
314 // really be the same precendence level, but the existing
315 // implementation doesn't allow for it. Bump us up a level if we
316 // are parsing for DOT but find a LPAR/LBRA at the end of the
318 if(PRECEDENCE[level].toks[0] == TOK_DOT)
319 if(end->type == TOK_LPAR || end->type == TOK_LBRA)
322 top = left = right = 0;
323 rule = PRECEDENCE[level].rule;
326 if(tokInLevel(start, level) && start->next) {
328 b = start->lastChild;
332 if(a) left = parsePrecedence(p, a, b, 0);
333 right = parsePrecedence(p, c, d, level);
337 if(tokInLevel(end, level) && end->prev) {
343 left = parsePrecedence(p, a, b, level);
344 if(c) right = parsePrecedence(p, c, d, 0);
350 if(tokInLevel(t, level)) {
351 a = t->prev ? start : 0;
354 d = t->next ? end : 0;
356 left = parsePrecedence(p, a, b, level);
357 right = parsePrecedence(p, c, d, level+1);
366 if(tokInLevel(t, level)) {
367 a = t->prev ? start : 0;
370 d = t->next ? end : 0;
372 left = parsePrecedence(p, a, b, level+1);
373 right = parsePrecedence(p, c, d, level);
381 // Found nothing, try the next level
383 return parsePrecedence(p, start, end, level+1);
391 top->children = left;
397 top->lastChild = right;
399 top->next = top->prev = 0;
403 naRef naParseCode(struct Context* c, naRef srcFile, int firstLine,
404 char* buf, int len, int* errLine)
410 // Protect from garbage collection
411 naTempSave(c, srcFile);
415 // Catch parser errors here.
416 p.errLine = *errLine = 1;
417 if(setjmp(p.jumpHandle)) {
418 strncpy(c->error, p.err, sizeof(c->error));
419 *errLine = p.errLine;
426 p.firstLine = firstLine;
430 // Lexify, match brace structure, fixup if/for/etc...
433 // Run the block parser, make sure everything was eaten
435 p.tree.children = p.tree.lastChild = 0;
436 parseBlock(&p, &p.tree, -1, &t);
439 // Recursively run the precedence parser, and fixup the treetop
440 t = parsePrecedence(&p, p.tree.children, p.tree.lastChild, 0);
441 t->prev = t->next = 0;
443 p.tree.lastChild = t;
446 codeObj = naCodeGen(&p, &(p.tree), 0);
450 naTempSave(c, codeObj);