6 // Static precedence table, from low (loose binding, do first) to high
7 // (tight binding, do last).
8 #define MAX_PREC_TOKS 9
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,
18 TOK_BIT_ANDEQ, TOK_BIT_OREQ,
19 TOK_BIT_XOREQ }, PREC_REVERSE },
20 { { TOK_COLON, TOK_QUESTION }, PREC_REVERSE },
21 { { TOK_VAR }, PREC_PREFIX },
22 { { TOK_BIT_OR }, PREC_BINARY },
23 { { TOK_BIT_XOR }, PREC_BINARY },
24 { { TOK_BIT_AND }, PREC_BINARY },
25 { { TOK_OR }, PREC_BINARY },
26 { { TOK_AND }, PREC_BINARY },
27 { { TOK_EQ, TOK_NEQ }, PREC_BINARY },
28 { { TOK_LT, TOK_LTE, TOK_GT, TOK_GTE }, PREC_BINARY },
29 { { TOK_PLUS, TOK_MINUS, TOK_CAT }, PREC_BINARY },
30 { { TOK_MUL, TOK_DIV }, PREC_BINARY },
31 { { TOK_MINUS, TOK_NEG, TOK_NOT,
32 TOK_CAT, TOK_BIT_NEG }, PREC_PREFIX },
33 { { TOK_LPAR, TOK_LBRA }, PREC_SUFFIX },
34 { { TOK_DOT }, PREC_BINARY },
36 #define PRECEDENCE_LEVELS (sizeof(PRECEDENCE)/sizeof(struct precedence))
38 void naParseError(struct Parser* p, char* msg, int line)
40 if(line > 0) p->errLine = line;
42 longjmp(p->jumpHandle, 1);
45 static void oops(struct Parser* p) { naParseError(p, "parse error", -1); }
47 void naParseInit(struct Parser* p)
49 memset(p, 0, sizeof(*p));
50 p->tree.type = TOK_TOP;
54 void naParseDestroy(struct Parser* p)
57 for(i=0; i<p->nChunks; i++) naFree(p->chunks[i]);
59 naFree(p->chunkSizes);
63 void* naParseAlloc(struct Parser* p, int bytes)
66 bytes = (bytes+7) & (~7); // Round up to 8 byte chunks for alignment
68 if(p->leftInChunk < bytes) {
75 if(sz < bytes) sz = bytes;
76 newChunk = naAlloc(sz);
80 newChunks = naAlloc(p->nChunks * sizeof(void*));
81 for(i=1; i<p->nChunks; i++) newChunks[i] = p->chunks[i-1];
82 newChunks[0] = newChunk;
84 p->chunks = newChunks;
86 newChunkSizes = naAlloc(p->nChunks * sizeof(int));
87 for(i=1; i<p->nChunks; i++) newChunkSizes[i] = p->chunkSizes[i-1];
88 newChunkSizes[0] = sz;
89 naFree(p->chunkSizes);
90 p->chunkSizes = newChunkSizes;
95 result = (char *)p->chunks[0] + p->chunkSizes[0] - p->leftInChunk;
96 p->leftInChunk -= bytes;
100 static void addChild(struct Token *par, struct Token *ch)
103 ch->prev = par->lastChild;
104 par->lastChild->next = ch;
110 static int endBrace(int tok)
112 if(tok == TOK_LBRA) return TOK_RBRA;
113 if(tok == TOK_LPAR) return TOK_RPAR;
114 if(tok == TOK_LCURL) return TOK_RCURL;
118 static int isOpenBrace(int t)
120 return t==TOK_LPAR || t==TOK_LBRA || t==TOK_LCURL;
123 static int isLoopoid(int t)
125 return t==TOK_FOR || t==TOK_FOREACH || t==TOK_WHILE || t==TOK_FORINDEX;
128 static int isBlockoid(int t)
130 return isLoopoid(t)||t==TOK_IF||t==TOK_ELSIF||t==TOK_ELSE||t==TOK_FUNC;
133 /* Yes, a bare else or elsif ends a block; it means we've reached the
134 * end of the previous if/elsif clause. */
135 static int isBlockEnd(int t)
137 return t==TOK_RPAR||t==TOK_RBRA||t==TOK_RCURL||t==TOK_ELSIF||t==TOK_ELSE;
140 /* To match C's grammar, "blockoid" expressions sometimes need
141 * synthesized terminating semicolons to make them act like
142 * "statements" in C. Always add one after "loopoid"
143 * (for/foreach/while) expressions. Add one after a func if it
144 * immediately follows an assignment, and add one after an
145 * if/elsif/else if it is the first token in an expression list */
146 static int needsSemi(struct Token* t, struct Token* next)
148 if(!next || next->type == TOK_SEMI || isBlockEnd(next->type)) return 0;
149 if(t->type == TOK_IF) return !t->prev || t->prev->type == TOK_SEMI;
150 if(t->type == TOK_FUNC) return t->prev && t->prev->type == TOK_ASSIGN;
151 if(isLoopoid(t->type)) return 1;
155 static struct Token* newToken(struct Parser* p, int type)
157 struct Token* t = naParseAlloc(p, sizeof(struct Token));
158 memset(t, 0, sizeof(*t));
164 static struct Token* parseToken(struct Parser* p, struct Token** list);
166 static void parseBlock(struct Parser* p, struct Token *top,
167 int end, struct Token** list)
171 if(isBlockEnd((*list)->type) && (*list)->type != end) break;
172 if(end == TOK_SEMI && (*list)->type == TOK_COMMA) break;
173 t = parseToken(p, list);
174 if(t->type == end) return; /* drop end token on the floor */
176 if(needsSemi(t, *list))
177 addChild(top, newToken(p, TOK_SEMI));
179 /* Context dependency: end of block is a parse error UNLESS we're
180 * looking for a statement terminator (a braceless block) or a -1
182 if(end != TOK_SEMI && end != -1) oops(p);
185 static struct Token* parseToken(struct Parser* p, struct Token** list)
187 struct Token *t = *list;
189 if(t->next) t->next->prev = 0;
190 t->next = t->prev = 0;
191 p->errLine = t->line;
194 if(isOpenBrace(t->type)) {
195 parseBlock(p, t, endBrace(t->type), list);
196 } else if(isBlockoid(t->type)) {
197 /* Read an optional paren expression */
199 if((*list)->type == TOK_LPAR)
200 addChild(t, parseToken(p, list));
202 /* And the code block, which might be implicit/braceless */
204 if((*list)->type == TOK_LCURL) {
205 addChild(t, parseToken(p, list));
207 /* Context dependency: if we're reading a braceless block,
208 * and the first (!) token is itself a "blockoid"
209 * expression, it is parsed alone, otherwise, read to the
210 * terminating semicolon. */
211 struct Token *blk = newToken(p, TOK_LCURL);
212 if(isBlockoid((*list)->type)) addChild(blk, parseToken(p, list));
213 else parseBlock(p, blk, TOK_SEMI, list);
217 /* Read the elsif/else chain */
218 if(t->type == TOK_IF) {
219 while(*list && ((*list)->type == TOK_ELSIF))
220 addChild(t, parseToken(p, list));
221 if(*list && (*list)->type == TOK_ELSE)
222 addChild(t, parseToken(p, list));
225 /* Finally, check for proper usage */
226 if(t->type != TOK_FUNC) {
227 if(t->type == TOK_ELSE && t->children->type != TOK_LCURL) oops(p);
228 if(t->type != TOK_ELSE && t->children->type != TOK_LPAR) oops(p);
234 // True if the token's type exists in the precedence level.
235 static int tokInLevel(struct Token* tok, int level)
238 for(i=0; i<MAX_PREC_TOKS; i++)
239 if(PRECEDENCE[level].toks[i] == tok->type)
244 static struct Token* parsePrecedence(struct Parser* p, struct Token* start,
245 struct Token* end, int level);
247 static void precChildren(struct Parser* p, struct Token* t)
249 struct Token* top = parsePrecedence(p, t->children, t->lastChild, 0);
254 // Run a "block structure" node (if/elsif/else/for/while/foreach)
255 // through the precedence parser. The funny child structure makes
256 // this a little more complicated than it should be.
257 static void precBlock(struct Parser* p, struct Token* block)
259 struct Token* t = block->children;
261 if(isOpenBrace(t->type))
263 else if(isBlockoid(t->type))
269 /* Binary tokens that get empties synthesized if one side is missing */
270 static int oneSidedBinary(int t)
271 { return t == TOK_SEMI || t == TOK_COMMA || t == TOK_COLON; }
273 static struct Token* parsePrecedence(struct Parser* p,
274 struct Token* start, struct Token* end,
278 struct Token *t, *top, *left, *right;
279 struct Token *a, *b, *c, *d; // temporaries
281 // This is an error. No "siblings" are allowed at the bottom level.
282 if(level >= PRECEDENCE_LEVELS && start != end)
283 naParseError(p, "parse error", start->line);
285 // Synthesize an empty token if necessary
286 if(end == 0 && start == 0)
287 return newToken(p, TOK_EMPTY);
289 // Sanify the list. This is OK, since we're recursing into the
290 // list structure; stuff to the left and right has already been
291 // handled somewhere above.
292 if(end == 0) end = start;
293 if(start == 0) start = end;
294 if(start->prev) start->prev->next = 0;
295 if(end->next) end->next->prev = 0;
296 start->prev = end->next = 0;
298 // Single tokens parse as themselves. Recurse into braces, and
299 // parse children of block structure.
301 if (isOpenBrace(start->type)) precChildren(p, start);
302 else if(isBlockoid(start->type)) precBlock(p, start);
306 if(oneSidedBinary(start->type)) {
307 t = newToken(p, TOK_EMPTY);
312 if(oneSidedBinary(end->type)) {
313 t = newToken(p, TOK_EMPTY);
319 // Another one: the "." and (postfix) "[]/()" operators should
320 // really be the same precendence level, but the existing
321 // implementation doesn't allow for it. Bump us up a level if we
322 // are parsing for DOT but find a LPAR/LBRA at the end of the
324 if(PRECEDENCE[level].toks[0] == TOK_DOT)
325 if(end->type == TOK_LPAR || end->type == TOK_LBRA)
328 top = left = right = 0;
329 rule = PRECEDENCE[level].rule;
332 if(tokInLevel(start, level) && start->next) {
334 b = start->lastChild;
338 if(a) left = parsePrecedence(p, a, b, 0);
339 right = parsePrecedence(p, c, d, level);
343 if(tokInLevel(end, level) && end->prev) {
349 left = parsePrecedence(p, a, b, level);
350 if(c) right = parsePrecedence(p, c, d, 0);
356 if(tokInLevel(t, level)) {
357 a = t->prev ? start : 0;
360 d = t->next ? end : 0;
362 left = parsePrecedence(p, a, b, level);
363 right = parsePrecedence(p, c, d, level+1);
372 if(tokInLevel(t, level)) {
373 a = t->prev ? start : 0;
376 d = t->next ? end : 0;
378 left = parsePrecedence(p, a, b, level+1);
379 right = parsePrecedence(p, c, d, level);
387 // Found nothing, try the next level
389 return parsePrecedence(p, start, end, level+1);
397 top->children = left;
403 top->lastChild = right;
405 top->next = top->prev = 0;
409 naRef naParseCode(struct Context* c, naRef srcFile, int firstLine,
410 char* buf, int len, int* errLine)
416 // Protect from garbage collection
417 naTempSave(c, srcFile);
421 // Catch parser errors here.
422 p.errLine = *errLine = 1;
423 if(setjmp(p.jumpHandle)) {
424 strncpy(c->error, p.err, sizeof(c->error));
425 *errLine = p.errLine;
432 p.firstLine = firstLine;
436 // Lexify, match brace structure, fixup if/for/etc...
439 // Run the block parser, make sure everything was eaten
441 p.tree.children = p.tree.lastChild = 0;
442 parseBlock(&p, &p.tree, -1, &t);
445 // Recursively run the precedence parser, and fixup the treetop
446 t = parsePrecedence(&p, p.tree.children, p.tree.lastChild, 0);
447 t->prev = t->next = 0;
449 p.tree.lastChild = t;
452 codeObj = naCodeGen(&p, &(p.tree), 0);
456 naTempSave(c, codeObj);