| /* | |
| Copyright 2002-2003 John Plevyak, All Rights Reserved | |
| */ | |
| #include "d.h" | |
| /* tunables */ | |
| #define DEFAULT_COMMIT_ACTIONS_INTERVAL 100 | |
| #define PNODE_HASH_INITIAL_SIZE_INDEX 10 | |
| #define SNODE_HASH_INITIAL_SIZE_INDEX 8 | |
| #define ERROR_RECOVERY_QUEUE_SIZE 10000 | |
| #define GOTO_STATE(_p, _pn, _ps) \ | |
| ((_p)->t->goto_table[(_pn)->parse_node.symbol - \ | |
| (_ps)->state->goto_table_offset] - 1) | |
| #define GOTO_STATE_INDEX(_p, _symbol, _si) \ | |
| ((_p)->t->goto_table[(_symbol) - (_p)->t->state[_si].goto_table_offset] - 1) | |
| #define is_unreduced_epsilon_PNode(_pn) \ | |
| (is_epsilon_PNode(_pn) && ((_pn)->reduction && (_pn)->reduction->final_code)) | |
| #ifndef USE_GC | |
| static void free_SNode(struct Parser *p, struct SNode *s); | |
| #define ref_pn(_pn) do { (_pn)->refcount++; } while (0) | |
| #define ref_sn(_sn) do { (_sn)->refcount++; } while (0) | |
| #define unref_pn(_p, _pn) do { if (!--(_pn)->refcount) free_PNode(_p, _pn); } while (0) | |
| #define unref_sn(_p, _sn) do { if (!--(_sn)->refcount) free_SNode(_p, _sn); } while (0) | |
| #else | |
| #define ref_pn(_pn) | |
| #define ref_sn(_sn) | |
| #define unref_pn(_p, _pn) | |
| #define unref_sn(_p, _sn) | |
| #endif | |
| typedef Stack(struct PNode*) StackPNode; | |
| typedef Stack(struct SNode*) StackSNode; | |
| typedef Stack(int) StackInt; | |
| static int exhaustive_parse(Parser *p, int state); | |
| void | |
| print_paren(PNode *p) { | |
| int i; | |
| char *c; | |
| if (!p->error_recovery) { | |
| if (p->children.n) { | |
| if (p->children.n > 1) | |
| printf("("); | |
| for (i = 0; i < p->children.n; i++) | |
| print_paren(p->children.v[i]); | |
| if (p->children.n > 1) | |
| printf(")"); | |
| } else if (p->parse_node.start_loc.s != p->parse_node.end_skip) { | |
| printf(" "); | |
| for (c = p->parse_node.start_loc.s; c < p->parse_node.end_skip; c++) | |
| printf("%c", *c); | |
| printf(" "); | |
| } | |
| } | |
| } | |
| void | |
| xprint_paren(Parser *pp, PNode *p) { | |
| int i; | |
| char *c; | |
| if (!p->error_recovery) { | |
| printf("[%s]", pp->t->symbols[p->parse_node.symbol].name); | |
| if (p->children.n) { | |
| printf("("); | |
| for (i = 0; i < p->children.n; i++) | |
| xprint_paren(pp, p->children.v[i]); | |
| printf(")"); | |
| } else if (p->parse_node.start_loc.s != p->parse_node.end_skip) { | |
| printf(" "); | |
| for (c = p->parse_node.start_loc.s; c < p->parse_node.end_skip; c++) | |
| printf("%c", *c); | |
| printf(" "); | |
| } | |
| } | |
| } | |
| void xpp(Parser *pp, PNode *p) { xprint_paren(pp, p); printf("\n"); } | |
| void pp(PNode *p) { print_paren(p); printf("\n"); } | |
| #define D_ParseNode_to_PNode(_apn) \ | |
| ((PNode*)D_PN(_apn, -(int)&((PNode*)(NULL))->parse_node)) | |
| #define PNode_to_D_ParseNode(_apn) \ | |
| ((D_ParseNode*)&((PNode*)(_apn))->parse_node) | |
| D_ParseNode * | |
| d_get_child(D_ParseNode *apn, int child) { | |
| PNode *pn = D_ParseNode_to_PNode(apn); | |
| if (child < 0 || child >= pn->children.n) | |
| return NULL; | |
| return &pn->children.v[child]->parse_node; | |
| } | |
| int | |
| d_get_number_of_children(D_ParseNode *apn) { | |
| PNode *pn = D_ParseNode_to_PNode(apn); | |
| return pn->children.n; | |
| } | |
| D_ParseNode * | |
| d_find_in_tree(D_ParseNode *apn, int symbol) { | |
| PNode *pn = D_ParseNode_to_PNode(apn); | |
| D_ParseNode *res; | |
| int i; | |
| if (pn->parse_node.symbol == symbol) | |
| return apn; | |
| for (i = 0; i < pn->children.n; i++) | |
| if ((res = d_find_in_tree(&pn->children.v[i]->parse_node, symbol))) | |
| return res; | |
| return NULL; | |
| } | |
| char * | |
| d_ws_before(D_Parser *ap, D_ParseNode *apn) { | |
| PNode *pn = D_ParseNode_to_PNode(apn); | |
| return pn->ws_before; | |
| } | |
| char * | |
| d_ws_after(D_Parser *ap, D_ParseNode *apn) { | |
| PNode *pn = D_ParseNode_to_PNode(apn); | |
| return pn->ws_after; | |
| } | |
| #define SNODE_HASH(_s, _sc, _g) ((((uint)(_s)) << 12) + (((uint)(_sc))) + ((uint)(_g))) | |
| SNode * | |
| find_SNode(Parser *p, uint state, D_Scope *sc, void *g) { | |
| SNodeHash *ph = &p->snode_hash; | |
| SNode *sn; | |
| uint h = SNODE_HASH(state, sc, g); | |
| if (ph->v) | |
| for (sn = ph->v[h % ph->m]; sn; sn = sn->bucket_next) | |
| if (sn->state - p->t->state == state && | |
| sn->initial_scope == sc && | |
| sn->initial_globals == g) | |
| return sn; | |
| return NULL; | |
| } | |
| void | |
| insert_SNode_internal(Parser *p, SNode *sn) { | |
| SNodeHash *ph = &p->snode_hash; | |
| uint h = SNODE_HASH(sn->state - p->t->state, sn->initial_scope, sn->initial_globals), i; | |
| SNode *t; | |
| if (ph->n + 1 > ph->m) { | |
| SNode **v = ph->v; | |
| int m = ph->m; | |
| ph->i++; | |
| ph->m = prime2[ph->i]; | |
| ph->v = (SNode**)MALLOC(ph->m * sizeof(*ph->v)); | |
| memset(ph->v, 0, ph->m * sizeof(*ph->v)); | |
| for (i = 0; i < m; i++) | |
| while ((t = v[i])) { | |
| v[i] = v[i]->bucket_next; | |
| insert_SNode_internal(p, t); | |
| } | |
| FREE(v); | |
| } | |
| sn->bucket_next = ph->v[h % ph->m]; | |
| ph->v[h % ph->m] = sn; | |
| ph->n++; | |
| } | |
| static void | |
| insert_SNode(Parser *p, SNode *sn) { | |
| insert_SNode_internal(p, sn); | |
| ref_sn(sn); | |
| sn->all_next = p->snode_hash.all; | |
| p->snode_hash.all = sn; | |
| } | |
| static SNode * | |
| new_SNode(Parser *p, D_State *state, d_loc_t *loc, D_Scope *sc, void *g) { | |
| SNode *sn = p->free_snodes; | |
| if (!sn) | |
| sn = MALLOC(sizeof *sn); | |
| else | |
| p->free_snodes = sn->all_next; | |
| sn->depth = 0; | |
| vec_clear(&sn->zns); | |
| #ifndef USE_GC | |
| sn->refcount = 0; | |
| #endif | |
| sn->all_next = 0; | |
| p->states++; | |
| sn->state = state; | |
| sn->initial_scope = sc; | |
| sn->initial_globals = g; | |
| sn->loc = *loc; | |
| insert_SNode(p, sn); | |
| if (sn->state->accept) { | |
| if (!p->accept) { | |
| ref_sn(sn); | |
| p->accept = sn; | |
| } else if (sn->loc.s > p->accept->loc.s) { | |
| ref_sn(sn); | |
| unref_sn(p, p->accept); | |
| p->accept = sn; | |
| } | |
| } | |
| return sn; | |
| } | |
| static ZNode * | |
| new_ZNode(Parser *p, PNode *pn) { | |
| ZNode *z = p->free_znodes; | |
| if (!z) | |
| z = MALLOC(sizeof *z); | |
| else | |
| p->free_znodes = znode_next(z); | |
| z->pn = pn; | |
| vec_clear(&z->sns); | |
| return z; | |
| } | |
| static void | |
| free_PNode(Parser *p, PNode *pn) { | |
| PNode *amb; | |
| int i; | |
| if (p->user.free_node_fn) | |
| p->user.free_node_fn(&pn->parse_node); | |
| for (i = 0; i < pn->children.n; i++) | |
| unref_pn(p, pn->children.v[i]); | |
| vec_free(&pn->children); | |
| if ((amb = pn->ambiguities)) { | |
| pn->ambiguities = NULL; | |
| free_PNode(p, amb); | |
| } | |
| if (pn->latest != pn) | |
| unref_pn(p, pn->latest); | |
| pn->all_next = p->free_pnodes; | |
| p->free_pnodes = pn; | |
| #ifdef TRACK_PNODES | |
| if (pn->xprev) | |
| pn->xprev->xnext = pn->xnext; | |
| else | |
| p->xall = pn->xnext; | |
| if (pn->xnext) | |
| pn->xnext->xprev = pn->xprev; | |
| pn->xprev = NULL; | |
| pn->xnext = NULL; | |
| #endif | |
| } | |
| #ifndef USE_GC | |
| static void | |
| free_ZNode(Parser *p, ZNode *z, SNode *s) { | |
| int i; | |
| unref_pn(p, z->pn); | |
| for (i = 0; i < z->sns.n; i++) | |
| if (s != z->sns.v[i]) | |
| unref_sn(p, z->sns.v[i]); | |
| vec_free(&z->sns); | |
| znode_next(z) = p->free_znodes; | |
| p->free_znodes = z; | |
| } | |
| static void | |
| free_SNode(Parser *p, struct SNode *s) { | |
| int i; | |
| for (i = 0; i < s->zns.n; i++) | |
| if (s->zns.v[i]) | |
| free_ZNode(p, s->zns.v[i], s); | |
| vec_free(&s->zns); | |
| s->all_next = p->free_snodes; | |
| p->free_snodes = s; | |
| } | |
| #endif | |
| #define PNODE_HASH(_si, _ei, _s, _sc, _g) \ | |
| ((((uint)_si) << 8) + (((uint)_ei) << 16) + (((uint)_s)) + (((uint)_sc)) + (((uint)_g))) | |
| PNode * | |
| find_PNode(Parser *p, char *start, char *end_skip, int symbol, D_Scope *sc, void *g) { | |
| PNodeHash *ph = &p->pnode_hash; | |
| PNode *pn; | |
| uint h = PNODE_HASH(start, end_skip, symbol, sc, g); | |
| if (ph->v) | |
| for (pn = ph->v[h % ph->m]; pn; pn = pn->bucket_next) | |
| if (pn->parse_node.symbol == symbol && | |
| pn->parse_node.start_loc.s == start && | |
| pn->parse_node.end_skip == end_skip && | |
| pn->initial_scope == sc && | |
| pn->initial_globals == g) | |
| return pn; | |
| return NULL; | |
| } | |
| void | |
| insert_PNode_internal(Parser *p, PNode *pn) { | |
| PNodeHash *ph = &p->pnode_hash; | |
| uint h = PNODE_HASH(pn->parse_node.start_loc.s, pn->parse_node.end_skip, | |
| pn->parse_node.symbol, pn->initial_scope, pn->initial_globals), i; | |
| PNode *t; | |
| if (ph->n + 1 > ph->m) { | |
| PNode **v = ph->v; | |
| int m = ph->m; | |
| ph->i++; | |
| ph->m = prime2[ph->i]; | |
| ph->v = (PNode**)MALLOC(ph->m * sizeof(*ph->v)); | |
| memset(ph->v, 0, ph->m * sizeof(*ph->v)); | |
| for (i = 0; i < m; i++) | |
| while ((t = v[i])) { | |
| v[i] = v[i]->bucket_next; | |
| insert_PNode_internal(p, t); | |
| } | |
| FREE(v); | |
| } | |
| pn->bucket_next = ph->v[h % ph->m]; | |
| ph->v[h % ph->m] = pn; | |
| ph->n++; | |
| } | |
| static void | |
| insert_PNode(Parser *p, PNode *pn) { | |
| insert_PNode_internal(p, pn); | |
| ref_pn(pn); | |
| pn->all_next = p->pnode_hash.all; | |
| p->pnode_hash.all = pn; | |
| } | |
| static void | |
| free_old_nodes(Parser *p) { | |
| int i; | |
| uint h; | |
| PNode *pn = p->pnode_hash.all, *tpn, **lpn; | |
| SNode *sn = p->snode_hash.all, *tsn, **lsn; | |
| while (sn) { | |
| h = SNODE_HASH(sn->state - p->t->state, sn->initial_scope, sn->initial_globals); | |
| lsn = &p->snode_hash.v[h % p->snode_hash.m]; | |
| tsn = sn; sn = sn->all_next; | |
| while (*lsn != tsn) lsn = &(*lsn)->bucket_next; | |
| *lsn = (*lsn)->bucket_next; | |
| } | |
| sn = p->snode_hash.last_all; | |
| while (sn) { | |
| tsn = sn; sn = sn->all_next; | |
| unref_sn(p, tsn); | |
| } | |
| p->snode_hash.last_all = p->snode_hash.all; | |
| p->snode_hash.all = NULL; | |
| while (pn) { | |
| for (i = 0; i < pn->children.n; i++) { | |
| if (pn->children.v[i] != pn->children.v[i]->latest) { | |
| ref_pn(pn->children.v[i]->latest); | |
| unref_pn(p, pn->children.v[i]); | |
| pn->children.v[i] = pn->children.v[i]->latest; | |
| } | |
| } | |
| h = PNODE_HASH(pn->parse_node.start_loc.s, pn->parse_node.end_skip, | |
| pn->parse_node.symbol, pn->initial_scope, pn->initial_globals); | |
| lpn = &p->pnode_hash.v[h % p->pnode_hash.m]; | |
| tpn = pn; pn = pn->all_next; | |
| while (*lpn != tpn) lpn = &(*lpn)->bucket_next; | |
| *lpn = (*lpn)->bucket_next; | |
| unref_pn(p, tpn); | |
| } | |
| p->pnode_hash.n = 0; | |
| p->pnode_hash.all = NULL; | |
| } | |
| static void | |
| alloc_parser_working_data(Parser *p) { | |
| p->pnode_hash.i = PNODE_HASH_INITIAL_SIZE_INDEX; | |
| p->pnode_hash.m = prime2[p->pnode_hash.i]; | |
| p->pnode_hash.v = | |
| (PNode**)MALLOC(p->pnode_hash.m * sizeof(*p->pnode_hash.v)); | |
| memset(p->pnode_hash.v, 0, p->pnode_hash.m * sizeof(*p->pnode_hash.v)); | |
| p->snode_hash.i = SNODE_HASH_INITIAL_SIZE_INDEX; | |
| p->snode_hash.m = prime2[p->snode_hash.i]; | |
| p->snode_hash.v = | |
| (SNode**)MALLOC(p->snode_hash.m * sizeof(*p->snode_hash.v)); | |
| memset(p->snode_hash.v, 0, p->snode_hash.m * sizeof(*p->snode_hash.v)); | |
| p->shift_results = MALLOC(p->t->nsymbols * sizeof(ShiftResult)); | |
| } | |
| static void | |
| free_parser_working_data(Parser *p) { | |
| int i; | |
| free_old_nodes(p); | |
| free_old_nodes(p); /* to catch SNodes saved for error repair */ | |
| if (p->pnode_hash.v) | |
| FREE(p->pnode_hash.v); | |
| if (p->snode_hash.v) | |
| FREE(p->snode_hash.v); | |
| memset(&p->pnode_hash, 0, sizeof(p->pnode_hash)); | |
| memset(&p->snode_hash, 0, sizeof(p->snode_hash)); | |
| while (p->reductions_todo) { | |
| Reduction *r = p->free_reductions->next; | |
| unref_sn(p, p->reductions_todo->snode); | |
| FREE(p->free_reductions); p->free_reductions = r; | |
| } | |
| while (p->shifts_todo) { | |
| Shift *s = p->free_shifts->next; | |
| unref_sn(p, p->shifts_todo->snode); | |
| FREE(p->free_shifts); p->free_shifts = s; | |
| } | |
| while (p->free_reductions) { | |
| Reduction *r = p->free_reductions->next; | |
| FREE(p->free_reductions); p->free_reductions = r; | |
| } | |
| while (p->free_shifts) { | |
| Shift *s = p->free_shifts->next; | |
| FREE(p->free_shifts); p->free_shifts = s; | |
| } | |
| while (p->free_pnodes) { | |
| PNode *pn = p->free_pnodes->all_next; | |
| FREE(p->free_pnodes); p->free_pnodes = pn; | |
| } | |
| while (p->free_znodes) { | |
| ZNode *zn = znode_next(p->free_znodes); | |
| FREE(p->free_znodes); p->free_znodes = zn; | |
| } | |
| while (p->free_snodes) { | |
| SNode *sn = p->free_snodes->all_next; | |
| FREE(p->free_snodes); p->free_snodes = sn; | |
| } | |
| for (i = 0; i < p->error_reductions.n; i++) | |
| FREE(p->error_reductions.v[i]); | |
| vec_free(&p->error_reductions); | |
| if (p->whitespace_parser) | |
| free_parser_working_data(p->whitespace_parser); | |
| FREE(p->shift_results); | |
| p->shift_results = NULL; | |
| } | |
| static int | |
| znode_depth(ZNode *z) { | |
| int i, d = 0; | |
| if (!z) | |
| return INT_MAX; | |
| for (i = 0; i < z->sns.n; i++) | |
| d = d < z->sns.v[i]->depth ? z->sns.v[i]->depth : d; | |
| return d; | |
| } | |
| static Reduction * | |
| add_Reduction(Parser *p, ZNode *z, SNode *sn, D_Reduction *reduction) { | |
| Reduction *x, **l = &p->reductions_todo; | |
| int d = znode_depth(z), dd; | |
| for (x = p->reductions_todo; x; l = &x->next, x = x->next) { | |
| if (sn->loc.s < x->snode->loc.s) | |
| break; | |
| dd = znode_depth(x->znode); | |
| if ((sn->loc.s == x->snode->loc.s && d >= dd)) { | |
| if (d == dd) | |
| while (x) { | |
| if (sn == x->snode && z == x->znode && reduction == x->reduction) | |
| return NULL; | |
| x = x->next; | |
| } | |
| break; | |
| } | |
| } | |
| { | |
| Reduction *r = p->free_reductions; | |
| if (!r) | |
| r = MALLOC(sizeof *r); | |
| else | |
| p->free_reductions = r->next; | |
| r->znode = z; | |
| r->snode = sn; | |
| r->new_snode = NULL; | |
| ref_sn(sn); | |
| r->reduction = reduction; | |
| r->next = *l; | |
| *l = r; | |
| return r; | |
| } | |
| } | |
| static void | |
| add_Shift(Parser *p, SNode *snode) { | |
| Shift *x, **l = &p->shifts_todo; | |
| Shift *s = p->free_shifts; | |
| if (!s) | |
| s = MALLOC(sizeof *s); | |
| else | |
| p->free_shifts = s->next; | |
| s->snode = snode; | |
| ref_sn(s->snode); | |
| for (x = p->shifts_todo; x; l = &x->next, x = x->next) | |
| if (snode->loc.s <= x->snode->loc.s) break; | |
| s->next = *l; | |
| *l = s; | |
| } | |
| static SNode * | |
| add_SNode(Parser *p, D_State *state, d_loc_t *loc, D_Scope *sc, void *g) { | |
| int i; | |
| SNode *sn = find_SNode(p, state - p->t->state, sc, g); | |
| if (sn) | |
| return sn; | |
| sn = new_SNode(p, state, loc, sc, g); | |
| if (sn->state->shifts) | |
| add_Shift(p, sn); | |
| for (i = 0; i < sn->state->reductions.n; i++) | |
| if (!sn->state->reductions.v[i]->nelements) | |
| add_Reduction(p, 0, sn, sn->state->reductions.v[i]); | |
| return sn; | |
| } | |
| static int | |
| reduce_actions(Parser *p, PNode *pn, D_Reduction *r) { | |
| int i, height = 0; | |
| PNode *c; | |
| for (i = 0; i < pn->children.n; i++) { | |
| c = pn->children.v[i]; | |
| if (c->op_assoc) { | |
| pn->assoc = c->op_assoc; | |
| pn->priority = c->op_priority; | |
| } | |
| if (c->height >= height) | |
| height = c->height + 1; | |
| } | |
| pn->op_assoc = r->op_assoc; | |
| pn->op_priority = r->op_priority; | |
| pn->height = height; | |
| if (r->rule_assoc) { | |
| pn->assoc = r->rule_assoc; | |
| pn->priority = r->rule_priority; | |
| } | |
| if (r->speculative_code) | |
| return r->speculative_code( | |
| pn, (void**)&pn->children.v[0], pn->children.n, | |
| (int)&((PNode*)(NULL))->parse_node, (D_Parser*)p); | |
| return 0; | |
| } | |
| #define x 666 /* impossible */ | |
| static int child_table[4][3][6] = { | |
| { | |
| /* binary parent, child on left */ | |
| /* priority of child vs parent, or = with child|parent associativity | |
| > < =LL =LR =RL =RR | |
| */ | |
| { 1, 0, 1, 1, 0, 0}, /* binary child */ | |
| { 1, 1, 1, 1, x, x}, /* left unary child */ | |
| { 1, 0, x, x, 1, 1} /* right unary child */ | |
| }, | |
| { /* binary parent, child on right */ | |
| { 1, 0, 0, 0, 1, 1}, /* binary child */ | |
| { 1, 0, 1, 1, x, x}, /* left unary child */ | |
| { 1, 1, x, x, 1, 1} /* right unary child */ | |
| }, | |
| { /* left unary parent */ | |
| { 1, 0, 0, x, 0, x}, /* binary child */ | |
| { 1, 0, 1, x, x, x}, /* left unary child */ | |
| { 1, 1, x, x, 1, x} /* right unary child */ | |
| }, | |
| { /* right unary parent */ | |
| { 1, 0, x, 0, x, 0}, /* binary child */ | |
| { 1, 1, x, 1, x, x}, /* left unary child */ | |
| { 1, 0, x, x, x, 1} /* right unary child */ | |
| } | |
| }; | |
| #undef x | |
| /* returns 1 if legal for child reduction and illegal for child shift */ | |
| static int | |
| check_child(int ppri, AssocKind passoc, int cpri, AssocKind cassoc, | |
| int left, int right) | |
| { | |
| int p = IS_BINARY_NARY_ASSOC(passoc) ? (right ? 1 : 0) : | |
| (passoc == ASSOC_UNARY_LEFT ? 2 : 3); | |
| int c = IS_BINARY_NARY_ASSOC(cassoc) ? 0 : | |
| (cassoc == ASSOC_UNARY_LEFT ? 1 : 2); | |
| int r = | |
| cpri > ppri ? 0 : ( | |
| cpri < ppri ? 1 : ( 2 + ( | |
| (IS_RIGHT_ASSOC(cassoc) ? 2 : 0) + | |
| (IS_RIGHT_ASSOC(passoc) ? 1 : 0)))); | |
| return child_table[p][c][r]; | |
| } | |
| /* check assoc/priority legality, 0 is OK, -1 is bad */ | |
| static int | |
| check_assoc_priority(PNode *pn0, PNode *pn1, PNode *pn2) { | |
| if (!IS_UNARY_BINARY_ASSOC(pn0->op_assoc)) { | |
| if (IS_UNARY_BINARY_ASSOC(pn1->op_assoc)) { /* second token is operator */ | |
| /* check expression pn0 (child of pn1) */ | |
| if (pn0->assoc) { | |
| if (!check_child(pn1->op_priority, pn1->op_assoc, | |
| pn0->priority, pn0->assoc, 0, 1)) | |
| return -1; | |
| } | |
| } | |
| } else { /* pn0 is an operator */ | |
| if (pn1->op_assoc) { | |
| /* check pn0 (child of operator pn1) */ | |
| if (!check_child(pn1->op_priority, pn1->op_assoc, | |
| pn0->op_priority, pn0->op_assoc, 0, 1)) | |
| return -1; | |
| } else if (pn2) { | |
| /* check pn0 (child of operator pn2) */ | |
| if (pn2->op_assoc && | |
| !check_child(pn2->op_priority, pn2->op_assoc, | |
| pn0->op_priority, pn0->op_assoc, 0, 1)) | |
| return -1; | |
| } | |
| /* check expression pn1 (child of pn0) */ | |
| if (pn1->assoc) { | |
| if (!check_child(pn0->op_priority, pn0->op_assoc, | |
| pn1->priority, pn1->assoc, 1, 0)) | |
| return -1; | |
| } | |
| } | |
| return 0; | |
| } | |
| /* check to see if a path is legal with respect to | |
| the associativity and priority of its operators */ | |
| static int | |
| check_path_priorities_internal(VecZNode *path) { | |
| int i = 0, j, k, jj, kk, one = 0; | |
| ZNode *z, *zz, *zzz; | |
| PNode *pn0, *pn1; | |
| if (path->n < i + 1) | |
| return 0; | |
| pn0 = path->v[i]->pn; | |
| if (!pn0->op_assoc) { /* deal with top expression directly */ | |
| i = 1; | |
| if (path->n < i + 1) | |
| return 0; | |
| pn1 = path->v[i]->pn; | |
| if (!pn1->op_assoc) | |
| return 0; | |
| if (pn0->assoc) { | |
| if (!check_child(pn1->op_priority, pn1->op_assoc, | |
| pn0->priority, pn0->assoc, 0, 1)) | |
| return -1; | |
| } | |
| pn0 = pn1; | |
| } | |
| if (path->n > i + 1) { /* entirely in the path */ | |
| pn1 = path->v[i + 1]->pn; | |
| if (path->n > i + 2) | |
| return check_assoc_priority(pn0, pn1, path->v[i + 2]->pn); | |
| else { /* one level from the stack beyond the path */ | |
| z = path->v[i + 1]; | |
| for (k = 0; k < z->sns.n; k++) | |
| for (j = 0; j < z->sns.v[k]->zns.n; j++) { | |
| one = 1; | |
| zz = z->sns.v[k]->zns.v[j]; | |
| if (zz && !check_assoc_priority(pn0, pn1, zz->pn)) | |
| return 0; | |
| } | |
| if (!one) | |
| return check_assoc_priority(pn0, pn1, NULL); | |
| } | |
| } else { /* two levels from the stack beyond the path */ | |
| z = path->v[i]; | |
| for (k = 0; k < z->sns.n; k++) | |
| for (j = 0; j < z->sns.v[k]->zns.n; j++) { | |
| zz = z->sns.v[k]->zns.v[j]; | |
| if (zz) | |
| for (kk = 0; kk < zz->sns.n; kk++) | |
| for (jj = 0; jj < zz->sns.v[kk]->zns.n; jj++) { | |
| one = 1; | |
| zzz = zz->sns.v[kk]->zns.v[jj]; | |
| if (zzz && !check_assoc_priority(pn0, zz->pn, zzz->pn)) | |
| return 0; | |
| } | |
| } | |
| return 0; | |
| } | |
| return -1; | |
| } | |
| /* avoid cases without operator priorities */ | |
| #define check_path_priorities(_p) ((_p)->n > 1 && \ | |
| ((_p)->v[0]->pn->op_assoc || (_p)->v[1]->pn->op_assoc) && \ | |
| check_path_priorities_internal(_p)) | |
| static int | |
| cmp_priorities(int xpri[], int xn, int ypri[], int yn) { | |
| int i = 0; | |
| while (i < xn && i < yn) { | |
| if (xpri[i] > ypri[i]) | |
| return -1; | |
| if (xpri[i] < ypri[i]) | |
| return 1; | |
| i++; | |
| } | |
| return 0; | |
| } | |
| static void | |
| intsort(int *xp, int n) { | |
| int again = 1, i, t; | |
| while (again) { | |
| again = 0; | |
| for (i = 0; i < n - 1; i++) { | |
| if (xp[i] > xp[i+1]) { | |
| t = xp[i]; | |
| xp[i] = xp[i + 1]; | |
| xp[i + 1] = t; | |
| again = 1; | |
| } | |
| } | |
| } | |
| } | |
| /* sort by deepest, then by address */ | |
| static void | |
| priority_insert(StackPNode *psx, PNode *x) { | |
| PNode *t, **start, **cur; | |
| stack_push(psx, x); | |
| start = psx->start; | |
| cur = psx->cur; | |
| for (;cur > start + 1;cur--) { | |
| if (cur[-1]->height > cur[-2]->height) | |
| continue; | |
| if (cur[-1]->height == cur[-2]->height && cur[-1] > cur[-2]) | |
| continue; | |
| t = cur[-1]; | |
| cur[-1] = cur[-2]; | |
| cur[-2] = t; | |
| } | |
| } | |
| static void | |
| get_exp_all(PNode *x, StackInt *psx) { | |
| int i; | |
| if (x->assoc) | |
| stack_push(psx, x->priority); | |
| for (i = 0; i < x->children.n; i++) | |
| get_exp_all(x->children.v[i]->latest, psx); | |
| } | |
| static void | |
| get_exp_one(PNode *x, StackPNode *psx, StackInt *isx) { | |
| int i; | |
| if (!IS_NARY_ASSOC(x->assoc)) | |
| priority_insert(psx, x); | |
| else { | |
| stack_push(isx, x->priority); | |
| for (i = 0; i < x->children.n; i++) | |
| if (x->children.v[i]->assoc) | |
| get_exp_one(x->children.v[i], psx, isx); | |
| } | |
| } | |
| static void | |
| get_exp_one_down(PNode *x, StackPNode *psx, StackInt *isx) { | |
| int i; | |
| stack_push(isx, x->priority); | |
| for (i = 0; i < x->children.n; i++) | |
| if (x->children.v[i]->assoc) | |
| get_exp_one(x->children.v[i], psx, isx); | |
| } | |
| /* get the set of priorities for unshared nodes, | |
| eliminating shared subtrees via priority queues */ | |
| static void | |
| get_unshared_priorities(StackPNode *psx, StackPNode *psy, | |
| StackInt *isx, StackInt *isy) | |
| { | |
| StackPNode *psr; | |
| PNode *t; | |
| while (1) { | |
| if (is_stack_empty(psx)) { | |
| psr = psy; | |
| break; | |
| } else if (is_stack_empty(psy)) { | |
| psr = psx; | |
| break; | |
| } | |
| if (stack_head(psx)->height > stack_head(psy)->height) | |
| psr = psx; | |
| else if (stack_head(psx)->height < stack_head(psy)->height) | |
| psr = psy; | |
| else if (stack_head(psx) > stack_head(psy)) | |
| psr = psx; | |
| else if (stack_head(psx) < stack_head(psy)) | |
| psr = psy; | |
| else { | |
| (void)stack_pop(psx); | |
| (void)stack_pop(psy); | |
| continue; | |
| } | |
| t = stack_pop(psr); | |
| if (psr == psx) | |
| get_exp_one_down(t, psx, isx); | |
| else | |
| get_exp_one_down(t, psy, isy); | |
| } | |
| while (!is_stack_empty(psr)) { | |
| t = stack_pop(psr); | |
| if (psr == psx) | |
| get_exp_all(t, isx); | |
| else | |
| get_exp_all(t, isy); | |
| } | |
| return; | |
| } | |
| static int | |
| cmp_eagerness(PNode *x, PNode *y) { | |
| int i, n; | |
| char *xx, *yy; | |
| n = x->children.n < y->children.n ? x->children.n : y->children.n; | |
| for (i = 0; i < n; i++) { | |
| xx = x->children.v[i]->parse_node.end_skip; | |
| yy = y->children.v[i]->parse_node.end_skip; | |
| /* if the child is a symbol, the end_skip of the last child | |
| will not equal that of the entire parse tree */ | |
| xx = i == x->children.n - 1 ? x->parse_node.end_skip : xx; | |
| yy = i == y->children.n - 1 ? y->parse_node.end_skip : yy; | |
| if (xx > yy) | |
| return -1; | |
| if (xx < yy) | |
| return 1; | |
| } | |
| return 0; | |
| } | |
| static int | |
| cmp_pnodes(Parser *p, PNode *x, PNode *y) { | |
| StackPNode psx, psy; | |
| StackInt isx, isy; | |
| int r = 0; | |
| if (x->assoc && y->assoc) { | |
| /* simple case */ | |
| if (!IS_NARY_ASSOC(x->assoc) && !IS_NARY_ASSOC(y->assoc)) { | |
| if (x->priority > y->priority) | |
| return -1; | |
| if (x->priority < y->priority) | |
| return 1; | |
| } | |
| /* compare the priorities of operators in two trees | |
| while eliminating common subtrees for efficiency. */ | |
| stack_clear(&psx); stack_clear(&psy); stack_clear(&isx); stack_clear(&isy); | |
| get_exp_one(x, &psx, &isx); | |
| get_exp_one(y, &psy, &isy); | |
| get_unshared_priorities(&psx, &psy, &isx, &isy); | |
| intsort(isx.start, stack_depth(&isx)); | |
| intsort(isy.start, stack_depth(&isy)); | |
| r = cmp_priorities(isx.start, stack_depth(&isx), | |
| isy.start, stack_depth(&isy)); | |
| stack_free(&psx); stack_free(&psy); stack_free(&isx); stack_free(&isy); | |
| if (r) | |
| return r; | |
| } | |
| if (!p->user.dont_use_eagerness_for_disambiguation) | |
| if ((r = cmp_eagerness(x, y))) | |
| return r; | |
| if (!p->user.dont_use_height_for_disambiguation) { | |
| if (x->height < y->height) | |
| return -1; | |
| if (x->height > y->height) | |
| return 1; | |
| } | |
| return r; | |
| } | |
| static char * | |
| find_ws_before(Parser *p, ZNode *zn) { | |
| while (zn && is_epsilon_PNode(zn->pn)) { | |
| zn = zn->sns.n ? (zn->sns.v[0]->zns.n ? zn->sns.v[0]->zns.v[0] : NULL) : NULL; | |
| } | |
| if (zn) | |
| return zn->pn->parse_node.end; | |
| else | |
| return p->start; | |
| } | |
| static PNode * | |
| make_PNode(Parser *p, int symbol, d_loc_t *start_loc, char *e, PNode *pn, | |
| D_Reduction *r, VecZNode *path, D_Shift *sh) | |
| { | |
| int i, l = sizeof(PNode) - sizeof(d_voidp) + p->user.sizeof_user_parse_node; | |
| PNode *new_pn = p->free_pnodes; | |
| if (!new_pn) | |
| new_pn = MALLOC(l); | |
| else | |
| p->free_pnodes = new_pn->all_next; | |
| p->pnodes++; | |
| memset(new_pn, 0, l); | |
| #ifdef TRACK_PNODES | |
| new_pn->xnext = p->xall; | |
| if (p->xall) | |
| p->xall->xprev = new_pn; | |
| p->xall = new_pn; | |
| #endif | |
| new_pn->parse_node.symbol = symbol; | |
| new_pn->parse_node.start_loc = *start_loc; | |
| if (!r || !path) { /* end of last parse node of path for non-epsilon reductions */ | |
| new_pn->parse_node.end = e; | |
| new_pn->ws_before = e; | |
| } else { | |
| new_pn->parse_node.end = pn->parse_node.end; | |
| new_pn->ws_before = find_ws_before(p, path->v[path->n-1]->sns.v[0]->zns.v[0]); | |
| } | |
| new_pn->parse_node.end_skip = e; | |
| new_pn->shift = sh; | |
| new_pn->reduction = r; | |
| new_pn->parse_node.scope = pn->parse_node.scope; | |
| new_pn->initial_scope = new_pn->parse_node.scope; | |
| new_pn->parse_node.globals = pn->parse_node.globals; | |
| new_pn->initial_globals = new_pn->parse_node.globals; | |
| new_pn->parse_node.white_space = pn->parse_node.white_space; | |
| new_pn->latest = new_pn; | |
| new_pn->ws_after = e; | |
| if (sh) { | |
| new_pn->op_assoc = sh->op_assoc; | |
| new_pn->op_priority = sh->op_priority; | |
| if (sh->speculative_code) | |
| if (sh->speculative_code( | |
| pn, (void**)&pn->children.v[0], pn->children.n, | |
| (int)&((PNode*)(NULL))->parse_node, (D_Parser*)p)) | |
| { | |
| free_PNode(p, new_pn); | |
| return NULL; | |
| } | |
| } else if (r) { | |
| if (path) | |
| for (i = path->n - 1; i >= 0; i--) { | |
| PNode *latest = path->v[i]->pn->latest; | |
| vec_add(&new_pn->children, latest); | |
| ref_pn(latest); | |
| } | |
| if (reduce_actions(p, new_pn, r)) { | |
| free_PNode(p, new_pn); | |
| return NULL; | |
| } | |
| if (path && path->n > 1) { | |
| int n = path->n; | |
| for (i = 0; i < n; i += n-1) { | |
| PNode *child = new_pn->children.v[i]; | |
| if (child->assoc && | |
| !check_child(new_pn->priority, new_pn->assoc, | |
| child->priority, child->assoc, i == 0, i == n - 1)) | |
| { | |
| free_PNode(p, new_pn); | |
| return NULL; | |
| } | |
| } | |
| } | |
| } | |
| return new_pn; | |
| } | |
| static int | |
| PNode_equal(PNode *pn, D_Reduction *r, VecZNode *path, D_Shift *sh) { | |
| int i, n = pn->children.n; | |
| if (sh) | |
| return sh == pn->shift; | |
| if (r != pn->reduction) | |
| return 0; | |
| if (!path && !n) | |
| return 1; | |
| if (n == path->n) { | |
| for (i = 0; i < n; i++) { | |
| if (pn->children.v[i]->latest != path->v[n - i - 1]->pn->latest) | |
| return 0; | |
| } | |
| return 1; | |
| } | |
| return 0; | |
| } | |
| /* find/create PNode */ | |
| static PNode * | |
| add_PNode(Parser *p, int symbol, d_loc_t *start_loc, char *e, PNode *pn, | |
| D_Reduction *r, VecZNode *path, D_Shift *sh) | |
| { | |
| PNode *old_pn = find_PNode(p, start_loc->s, e, symbol, pn->initial_scope, pn->initial_globals), | |
| *new_pn; | |
| if (old_pn && PNode_equal(old_pn, r, path, sh)) | |
| return old_pn; | |
| new_pn = make_PNode(p, symbol, start_loc, e, pn, r, path, sh); | |
| if (!old_pn) { | |
| old_pn = new_pn; | |
| if (!new_pn) | |
| return NULL; | |
| insert_PNode(p, new_pn); | |
| goto Lreturn; | |
| } | |
| if (!new_pn) | |
| goto Lreturn; | |
| p->compares++; | |
| switch (cmp_pnodes(p, new_pn, old_pn)) { | |
| case 0: | |
| new_pn->ambiguities = old_pn->ambiguities; | |
| old_pn->ambiguities = new_pn; | |
| break; | |
| case -1: | |
| insert_PNode(p, new_pn); | |
| old_pn->latest = new_pn; | |
| ref_pn(new_pn); | |
| old_pn = new_pn; | |
| break; | |
| case 1: | |
| free_PNode(p, new_pn); | |
| break; | |
| } | |
| Lreturn: | |
| return old_pn; | |
| } | |
| /* The set of znodes associated with a state can be very large | |
| because of cascade reductions (for example, large expression trees). | |
| Use an adaptive data structure starting with a short list and | |
| then falling back to a direct map hash table. | |
| */ | |
| static void set_add_znode(VecZNode *v, ZNode *z); | |
| static void | |
| set_union_znode(VecZNode *v, VecZNode *vv) { | |
| int i; | |
| for (i = 0; i < vv->n; i++) | |
| if (vv->v[i]) | |
| set_add_znode(v, vv->v[i]); | |
| } | |
| static ZNode * | |
| set_find_znode(VecZNode *v, PNode *pn) { | |
| uint i, j, n = v->n, h; | |
| if (n <= INTEGRAL_VEC_SIZE) { | |
| for (i = 0; i < n; i++) | |
| if (v->v[i]->pn == pn) | |
| return v->v[i]; | |
| return NULL; | |
| } | |
| h = ((uint)pn) % n; | |
| for (i = h, j = 0; | |
| i < v->n && j < SET_MAX_SEQUENTIAL; | |
| i = ((i + 1) % n), j++) | |
| { | |
| if (!v->v[i]) | |
| return NULL; | |
| else if (v->v[i]->pn == pn) | |
| return v->v[i]; | |
| } | |
| return NULL; | |
| } | |
| static void | |
| set_add_znode_hash(VecZNode *v, ZNode *z) { | |
| VecZNode vv; | |
| int i, j, n = v->n; | |
| if (n) { | |
| uint h = ((uint)z->pn) % n; | |
| for (i = h, j = 0; | |
| i < v->n && j < SET_MAX_SEQUENTIAL; | |
| i = ((i + 1) % n), j++) | |
| { | |
| if (!v->v[i]) { | |
| v->v[i] = z; | |
| return; | |
| } | |
| } | |
| } | |
| if (!n) { | |
| vv.v = NULL; | |
| v->i = INITIAL_SET_SIZE_INDEX; | |
| } else { | |
| vv.v = (void*)v->v; | |
| vv.n = v->n; | |
| v->i = v->i + 2; | |
| } | |
| v->n = prime2[v->i]; | |
| v->v = MALLOC(v->n * sizeof(void *)); | |
| memset(v->v, 0, v->n * sizeof(void *)); | |
| if (vv.v) { | |
| set_union_znode(v, &vv); | |
| FREE(vv.v); | |
| } | |
| set_add_znode(v, z); | |
| } | |
| static void | |
| set_add_znode(VecZNode *v, ZNode *z) { | |
| VecZNode vv; | |
| int i, n = v->n; | |
| if (n < INTEGRAL_VEC_SIZE) { | |
| vec_add(v, z); | |
| return; | |
| } | |
| if (n == INTEGRAL_VEC_SIZE) { | |
| vv = *v; | |
| vec_clear(v); | |
| for (i = 0; i < n; i++) | |
| set_add_znode_hash(v, vv.v[i]); | |
| } | |
| set_add_znode_hash(v, z); | |
| } | |
| static SNode * | |
| goto_PNode(Parser *p, d_loc_t *loc, PNode *pn, SNode *ps) { | |
| SNode *new_ps, *pre_ps; | |
| ZNode *z = NULL; | |
| D_State *state; | |
| int i, j, k, state_index; | |
| if (!IS_BIT_SET(ps->state->goto_valid, pn->parse_node.symbol)) | |
| return NULL; | |
| state_index = GOTO_STATE(p, pn, ps); | |
| state = &p->t->state[state_index]; | |
| new_ps = add_SNode(p, state, loc, pn->initial_scope, pn->initial_globals); | |
| new_ps->last_pn = pn; | |
| DBG(printf("goto %d (%s) -> %d %X\n", | |
| ps->state - p->t->state, | |
| p->t->symbols[pn->parse_node.symbol].name, | |
| state_index, (uint)new_ps)); | |
| if (ps != new_ps && new_ps->depth < ps->depth + 1) | |
| new_ps->depth = ps->depth + 1; | |
| /* find/create ZNode */ | |
| z = set_find_znode(&new_ps->zns, pn); | |
| if (!z) { /* not found */ | |
| set_add_znode(&new_ps->zns, (z = new_ZNode(p, pn))); | |
| ref_pn(pn); | |
| for (j = 0; j < new_ps->state->reductions.n; j++) | |
| if (new_ps->state->reductions.v[j]->nelements) | |
| add_Reduction(p, z, new_ps, new_ps->state->reductions.v[j]); | |
| if (!pn->shift) | |
| for (j = 0; j < new_ps->state->right_epsilon_hints.n; j++) { | |
| D_RightEpsilonHint *h = &new_ps->state->right_epsilon_hints.v[j]; | |
| pre_ps = find_SNode(p, h->preceeding_state, new_ps->initial_scope, new_ps->initial_globals); | |
| if (!pre_ps) continue; | |
| for (k = 0; k < pre_ps->zns.n; k++) | |
| if (pre_ps->zns.v[k]) { | |
| Reduction *r = | |
| add_Reduction(p, pre_ps->zns.v[k], pre_ps, h->reduction); | |
| if (r) { | |
| r->new_snode = new_ps; | |
| r->new_depth = h->depth; | |
| } | |
| } | |
| } | |
| } | |
| for (i = 0; i < z->sns.n; i++) | |
| if (z->sns.v[i] == ps) break; | |
| if (i >= z->sns.n) { /* not found */ | |
| vec_add(&z->sns, ps); | |
| if (new_ps != ps) | |
| ref_sn(ps); | |
| } | |
| return new_ps; | |
| } | |
| static void | |
| parse_whitespace(D_Parser *ap, d_loc_t *loc, void **p_globals) { | |
| Parser *pp = ((Parser*)ap)->whitespace_parser; | |
| pp->start = loc->s; | |
| if (!exhaustive_parse(pp, ((Parser *)ap)->t->whitespace_state)) { | |
| if (pp->accept) { | |
| *loc = pp->accept->loc; | |
| unref_sn(pp, pp->accept); | |
| pp->accept = NULL; | |
| } | |
| } | |
| } | |
| static void | |
| shift_one(Parser *p, Shift *s) { | |
| int i, nshifts = 0; | |
| d_loc_t loc, skip_loc; | |
| D_WhiteSpaceFn skip_fn = NULL; | |
| PNode *new_pn; | |
| D_State *state = s->snode->state; | |
| ShiftResult *r; | |
| loc = s->snode->loc; | |
| skip_loc.s = NULL; | |
| p->scans++; | |
| if (state->scanner_code) { | |
| p->code_shift.term_priority = 0; | |
| p->code_shift.op_assoc = 0; | |
| p->shift_results[nshifts].loc = loc; | |
| if ((state->scanner_code( | |
| &p->shift_results[nshifts].loc.s, | |
| &p->shift_results[nshifts].loc.col, | |
| &p->shift_results[nshifts].loc.line, | |
| &p->code_shift.symbol, &p->code_shift.term_priority, | |
| &p->code_shift.op_assoc, &p->code_shift.op_priority))) | |
| { | |
| p->shift_results[nshifts++].shift = &p->code_shift; | |
| } | |
| } | |
| if (state->scanner_table) | |
| nshifts += scan_buffer(&loc, state, &p->shift_results[nshifts]); | |
| for (i = 0; i < nshifts ;i++) { | |
| r = &p->shift_results[i]; | |
| p->shifts++; | |
| DBG(printf("shift %d %X %d (%s)\n", | |
| s->snode->state - p->t->state, (uint)s->snode, r->shift->symbol, | |
| p->t->symbols[r->shift->symbol].name)); | |
| new_pn = add_PNode(p, r->shift->symbol, &s->snode->loc, r->loc.s, | |
| s->snode->last_pn, NULL, NULL, r->shift); | |
| if (new_pn) { | |
| if (!skip_loc.s || skip_loc.s != r->loc.s || skip_fn != new_pn->parse_node.white_space) { | |
| skip_loc = r->loc; | |
| skip_fn = new_pn->parse_node.white_space; | |
| new_pn->parse_node.white_space( | |
| (D_Parser*)p, &skip_loc, (void**)&new_pn->parse_node.globals); | |
| skip_loc.previous_col = s->snode->loc.col >= 0 ? s->snode->loc.col : | |
| s->snode->loc.previous_col; | |
| new_pn->ws_before = find_ws_before(p, s->snode->zns.v[0]); | |
| new_pn->ws_after = skip_loc.s; | |
| } | |
| goto_PNode(p, &skip_loc, new_pn, s->snode); | |
| } | |
| } | |
| unref_sn(p, s->snode); | |
| s->next = p->free_shifts; | |
| p->free_shifts = s; | |
| } | |
| static VecZNode path1; /* static first path for speed */ | |
| static VecZNode * | |
| new_VecZNode(VecVecZNode *paths, int n, int parent) { | |
| int i; | |
| VecZNode *pv; | |
| if (!paths->n) | |
| pv = &path1; | |
| else | |
| pv = MALLOC(sizeof *pv); | |
| vec_clear(pv); | |
| if (parent >= 0) | |
| for (i = 0; i < n; i++) | |
| vec_add(pv, paths->v[parent]->v[i]); | |
| return pv; | |
| } | |
| static void | |
| build_paths_internal(ZNode *z, VecVecZNode *paths, int parent, | |
| int n, int n_to_go) | |
| { | |
| int j, k, l; | |
| vec_add(paths->v[parent], z); | |
| if (n_to_go <= 1) | |
| return; | |
| for (k = 0; k < z->sns.n; k++) | |
| for (j = 0, l = 0; j < z->sns.v[k]->zns.n; j++) { | |
| if (z->sns.v[k]->zns.v[j]) { | |
| if (k + l) { | |
| vec_add(paths, new_VecZNode(paths, n - (n_to_go - 1), parent)); | |
| parent = paths->n - 1; | |
| } | |
| build_paths_internal(z->sns.v[k]->zns.v[j], paths, parent, | |
| n, n_to_go - 1); | |
| l++; | |
| } | |
| } | |
| } | |
| static void | |
| build_paths(ZNode *z, VecVecZNode *paths, int nchildren_to_go) { | |
| if (!nchildren_to_go) | |
| return; | |
| vec_add(paths, new_VecZNode(paths, 0, -1)); | |
| build_paths_internal(z, paths, 0, nchildren_to_go, nchildren_to_go); | |
| } | |
| static void | |
| free_paths(VecVecZNode *paths) { | |
| int i; | |
| vec_free(&path1); | |
| for (i = 1; i < paths->n; i++) { | |
| vec_free(paths->v[i]); | |
| FREE(paths->v[i]); | |
| } | |
| vec_free(paths); | |
| } | |
| static void | |
| reduce_one(Parser *p, Reduction *r) { | |
| SNode *sn = r->snode; | |
| PNode *pn, *last_pn; | |
| ZNode *first_z; | |
| int i, j, n = r->reduction->nelements; | |
| VecVecZNode paths; | |
| VecZNode *path; | |
| if (!r->znode) { /* epsilon reduction */ | |
| if ((pn = add_PNode(p, r->reduction->symbol, &sn->loc, | |
| sn->loc.s, sn->last_pn, r->reduction, 0, 0))) | |
| goto_PNode(p, &sn->loc, pn, sn); | |
| } else { | |
| DBG(printf("reduce %d %X %d\n", r->snode->state - p->t->state, (uint)sn, n)); | |
| vec_clear(&paths); | |
| build_paths(r->znode, &paths, n); | |
| for (i = 0; i < paths.n; i++) { | |
| path = paths.v[i]; | |
| if (r->new_snode) { /* prune paths by new right epsilon node */ | |
| for (j = 0; j < path->v[r->new_depth]->sns.n; j++) | |
| if (path->v[r->new_depth]->sns.v[j] == r->new_snode) | |
| break; | |
| if (j >= path->v[r->new_depth]->sns.n) | |
| continue; | |
| } | |
| if (check_path_priorities(path)) | |
| continue; | |
| p->reductions++; | |
| last_pn = path->v[0]->pn; | |
| first_z = path->v[n - 1]; | |
| pn = add_PNode(p, r->reduction->symbol, | |
| &first_z->pn->parse_node.start_loc, | |
| sn->loc.s, last_pn, r->reduction, path, NULL); | |
| if (pn) | |
| for (j = 0; j < first_z->sns.n; j++) | |
| goto_PNode(p, &sn->loc, pn, first_z->sns.v[j]); | |
| } | |
| free_paths(&paths); | |
| } | |
| unref_sn(p, sn); | |
| r->next = p->free_reductions; | |
| p->free_reductions = r; | |
| } | |
| static int | |
| VecSNode_equal(VecSNode *vsn1, VecSNode *vsn2) { | |
| int i, j; | |
| if (vsn1->n != vsn2->n) | |
| return 0; | |
| for (i = 0; i < vsn1->n; i++) { | |
| for (j = 0; j < vsn2->n; j++) { | |
| if (vsn1->v[i] == vsn2->v[j]) | |
| break; | |
| } | |
| if (j >= vsn2->n) | |
| return 0; | |
| } | |
| return 1; | |
| } | |
| static ZNode * | |
| binary_op_ZNode(SNode *sn) { | |
| ZNode *z; | |
| if (sn->zns.n != 1) | |
| return NULL; | |
| z = sn->zns.v[0]; | |
| if (z->pn->op_assoc == ASSOC_UNARY_RIGHT) { | |
| if (z->sns.n != 1) | |
| return NULL; | |
| sn = z->sns.v[0]; | |
| if (sn->zns.n != 1) | |
| return NULL; | |
| z = sn->zns.v[0]; | |
| } | |
| if (!IS_BINARY_ASSOC(z->pn->op_assoc)) | |
| return NULL; | |
| return z; | |
| } | |
| static char *spaces = " "; | |
| static void | |
| print_stack(Parser *p, SNode *s, int indent) { | |
| int i,j; | |
| printf("%d", s->state - p->t->state); | |
| indent += 2; | |
| for (i = 0; i < s->zns.n; i++) { | |
| if (!s->zns.v[i]) | |
| continue; | |
| if (s->zns.n > 1) | |
| printf("\n%s[", &spaces[99-indent]); | |
| printf("(%s:", p->t->symbols[s->zns.v[i]->pn->parse_node.symbol].name); | |
| print_paren(s->zns.v[i]->pn); | |
| printf(")"); | |
| for (j = 0; j < s->zns.v[i]->sns.n; j++) { | |
| if (s->zns.v[i]->sns.n > 1) | |
| printf("\n%s[", &spaces[98-indent]); | |
| print_stack(p, s->zns.v[i]->sns.v[j], indent); | |
| if (s->zns.v[i]->sns.n > 1) | |
| printf("]"); | |
| } | |
| if (s->zns.n > 1) | |
| printf("]"); | |
| } | |
| } | |
| /* compare two stacks with operators on top of identical substacks | |
| eliminating the stack with the lower priority binary operator | |
| - used to eliminate unnecessary stacks created by the | |
| (empty) application binary operator | |
| */ | |
| static void | |
| cmp_stacks(Parser *p) { | |
| char *pos; | |
| Shift *a, *b, **al, **bl; | |
| ZNode *az, *bz; | |
| pos = p->shifts_todo->snode->loc.s; | |
| DBG({ | |
| int i = 0; | |
| for (al = &p->shifts_todo, a = *al; a && a->snode->loc.s == pos; | |
| al = &a->next, a = a->next) | |
| { | |
| if (++i < 2) printf("\n"); | |
| print_stack(p, a->snode, 0); | |
| printf("\n"); | |
| }}); | |
| for (al = &p->shifts_todo, a = *al; a && a->snode->loc.s == pos; | |
| al = &a->next, a = a->next) | |
| { | |
| if (!(az = binary_op_ZNode(a->snode))) | |
| continue; | |
| for (bl = &a->next, b = a->next; b && b->snode->loc.s == pos; | |
| bl = &b->next, b = b->next) { | |
| if (!(bz = binary_op_ZNode(b->snode))) | |
| continue; | |
| if (!VecSNode_equal(&az->sns, &bz->sns)) | |
| continue; | |
| if ((a->snode->state->reduces_to != b->snode->state - p->t->state) && | |
| (b->snode->state->reduces_to != a->snode->state - p->t->state)) | |
| continue; | |
| if (az->pn->op_priority > bz->pn->op_priority) { | |
| DBG(printf("DELETE "); | |
| print_stack(p, b->snode, 0); | |
| printf("\n")); | |
| *bl = b->next; | |
| unref_sn(p, b->snode); | |
| FREE(b); | |
| b = *bl; | |
| break; | |
| } | |
| if (az->pn->op_priority < bz->pn->op_priority) { | |
| DBG(printf("DELETE "); | |
| print_stack(p, a->snode, 0); | |
| printf("\n")); | |
| *al = a->next; | |
| unref_sn(p, a->snode); | |
| FREE(a); | |
| a = *al; | |
| goto Lbreak2; | |
| } | |
| } | |
| Lbreak2:; | |
| } | |
| } | |
| static void | |
| free_ParseTreeBelow(Parser *p, PNode *pn) { | |
| int i; | |
| PNode *amb; | |
| for (i = 0; i < pn->children.n; i++) | |
| unref_pn(p, pn->children.v[i]); | |
| vec_free(&pn->children); | |
| if ((amb = pn->ambiguities)) { | |
| pn->ambiguities = NULL; | |
| free_PNode(p, amb); | |
| } | |
| } | |
| void | |
| free_D_ParseTreeBelow(D_Parser *p, D_ParseNode *dpn) { | |
| free_ParseTreeBelow((Parser*)p, DPN_TO_PN(dpn)); | |
| } | |
| D_ParseNode * | |
| ambiguity_count_fn(D_Parser *pp, int n, D_ParseNode **v) { | |
| Parser *p = (Parser*)pp; | |
| p->ambiguities += n - 1; | |
| return v[0]; | |
| } | |
| D_ParseNode * | |
| ambiguity_abort_fn(D_Parser *pp, int n, D_ParseNode **v) { | |
| int i; | |
| if (verbose_level) { | |
| for (i = 0; i < n; i++) { | |
| print_paren(D_ParseNode_to_PNode(v[i])); | |
| printf("\n"); | |
| } | |
| } | |
| d_fail("unresolved ambiguity line %d file %s", v[0]->start_loc.line, | |
| v[0]->start_loc.pathname); | |
| return v[0]; | |
| } | |
| static int | |
| final_actionless(PNode *pn) { | |
| int i; | |
| if (pn->reduction && pn->reduction->final_code) | |
| return 0; | |
| for (i = 0; i < pn->children.n; i++) | |
| if (!final_actionless(pn->children.v[i])) | |
| return 0; | |
| return 1; | |
| } | |
| static PNode * | |
| resolve_ambiguities(Parser *p, PNode *pn) { | |
| PNode *amb; | |
| D_ParseNode *res; | |
| int efa; | |
| Vec(D_ParseNode*) pns; | |
| vec_clear(&pns); | |
| efa = is_epsilon_PNode(pn) && final_actionless(pn); | |
| vec_add(&pns, &pn->parse_node); | |
| for (amb = pn->ambiguities; amb; amb = amb->ambiguities) { | |
| if (!p->user.dont_merge_epsilon_trees) | |
| if (efa && is_epsilon_PNode(amb) && final_actionless(amb)) | |
| continue; | |
| vec_add(&pns, &amb->parse_node); | |
| } | |
| if (pns.n == 1) { | |
| res = pns.v[0]; | |
| goto Ldone; | |
| } | |
| res = p->user.ambiguity_fn((D_Parser *)p, pns.n, pns.v); | |
| Ldone: | |
| vec_free(&pns); | |
| return D_ParseNode_to_PNode(res); | |
| } | |
| static void | |
| fixup_internal_symbol(Parser *p, PNode *pn, int ichild) { | |
| PNode *child = pn->children.v[ichild]; | |
| int j, n, pnn; | |
| n = child->children.n, pnn = pn->children.n; | |
| if (pn == child) | |
| d_fail("circular parse: unable to fixup internal symbol"); | |
| if (n == 0) { | |
| for (j = ichild; j < pnn - 1; j++) | |
| pn->children.v[j] = pn->children.v[j + 1]; | |
| pn->children.n--; | |
| } else if (n == 1) { | |
| ref_pn(child->children.v[0]); | |
| pn->children.v[ichild] = child->children.v[0]; | |
| } else { | |
| for (j = 0; j < n - 1; j++) /* expand children vector */ | |
| vec_add(&pn->children, NULL); | |
| for (j = pnn - 1; j >= ichild + 1; j--) /* move to new places */ | |
| pn->children.v[j - 1 + n] = pn->children.v[j]; | |
| for (j = 0; j < n; j++) { | |
| ref_pn(child->children.v[j]); | |
| pn->children.v[ichild + j] = child->children.v[j]; | |
| } | |
| } | |
| unref_pn(p, child); | |
| } | |
| #define is_symbol_internal(_p, _pn) \ | |
| ((_p)->t->symbols[(_pn)->parse_node.symbol].kind == D_SYMBOL_INTERNAL) | |
| static PNode * | |
| commit_tree(Parser *p, PNode *pn) { | |
| int i, n, fixup = 0, internal; | |
| if (pn->evaluated) | |
| return pn; | |
| if (!is_unreduced_epsilon_PNode(pn)) | |
| pn->evaluated = 1; | |
| if (pn->ambiguities) | |
| pn = resolve_ambiguities(p, pn); | |
| internal = is_symbol_internal(p, pn); | |
| fixup = !p->user.dont_fixup_internal_productions && internal; | |
| for (i = 0; i < pn->children.n; i++) { | |
| pn->children.v[i] = commit_tree(p, pn->children.v[i]); | |
| n = pn->children.v[i]->children.n; | |
| if (fixup && is_symbol_internal(p, pn->children.v[i])) { | |
| fixup_internal_symbol(p, pn, i); | |
| i -= 1; | |
| continue; | |
| } | |
| } | |
| if (pn->reduction && pn->reduction->final_code) | |
| pn->reduction->final_code( | |
| pn, (void**)pn->children.v, pn->children.n, | |
| (int)&((PNode*)(NULL))->parse_node, (D_Parser*)p); | |
| if (pn->evaluated) { | |
| if (!p->user.save_parse_tree && !internal) | |
| free_ParseTreeBelow(p, pn); | |
| } | |
| return pn; | |
| } | |
| static int | |
| commit_stack(Parser *p, SNode *sn) { | |
| int res = 0; | |
| if (sn->zns.n != 1) | |
| return -1; | |
| if (sn->zns.v[0]->sns.n > 1) | |
| return -2; | |
| if (is_unreduced_epsilon_PNode(sn->zns.v[0]->pn)) /* wait till reduced */ | |
| return -3; | |
| if (sn->zns.v[0]->sns.n) | |
| if ((res = commit_stack(p, sn->zns.v[0]->sns.v[0])) < 0) | |
| return res; | |
| sn->zns.v[0]->pn = commit_tree(p, sn->zns.v[0]->pn); | |
| return res; | |
| } | |
| static char * | |
| find_substr(char *str, char *s) { | |
| int len = strlen(s); | |
| if (len == 1) { | |
| while (*str && *str != *s) str++; | |
| if (*str == *s) | |
| return str + 1; | |
| } else | |
| while (*str) { | |
| if (!strncmp(s, str, len)) | |
| return str + len; | |
| str++; | |
| } | |
| return NULL; | |
| } | |
| static void | |
| syntax_error_report_fn(struct D_Parser *p) { | |
| char *fn = d_dup_pathname_str(p->loc.pathname); | |
| fprintf(stderr, "syntax error, '%s' line %d\n", fn, p->loc.line); | |
| FREE(fn); | |
| } | |
| static void | |
| update_line(char *s, char *e, int *line) { | |
| for (;s < e; s++) if (*s == '\n') (*line)++; | |
| } | |
| static int | |
| error_recovery(Parser *p) { | |
| SNode *sn, *best_sn = NULL; | |
| char *best_s = NULL, *ss, *s; | |
| int i, j, head = 0, tail = 0, res = 1; | |
| D_ErrorRecoveryHint *best_er = NULL; | |
| SNode **q = MALLOC(ERROR_RECOVERY_QUEUE_SIZE * sizeof(SNode*)); | |
| PNode *best_pn; | |
| if (!p->snode_hash.last_all) | |
| return res; | |
| p->user.loc = p->snode_hash.last_all->loc; | |
| if (!p->user.error_recovery) | |
| return res; | |
| if (p->user.loc.line > p->last_syntax_error_line) { | |
| p->last_syntax_error_line = p->user.loc.line; | |
| p->user.syntax_errors++; | |
| p->user.syntax_error_fn((D_Parser*)p); | |
| } | |
| for (sn = p->snode_hash.last_all; sn; sn = sn->all_next) { | |
| if (tail < ERROR_RECOVERY_QUEUE_SIZE - 1) | |
| q[tail++] = sn; | |
| } | |
| s = p->snode_hash.last_all->loc.s; | |
| while (tail > head) { | |
| sn = q[head++]; | |
| if (sn->state->error_recovery_hints.n) { | |
| for (i = 0; i < sn->state->error_recovery_hints.n; i++) { | |
| D_ErrorRecoveryHint *er = &sn->state->error_recovery_hints.v[i]; | |
| if ((ss = find_substr(s, er->string))) { | |
| if (!best_sn || ss < best_s || | |
| (best_sn && ss == best_s && | |
| (best_sn->depth < sn->depth || | |
| (best_sn->depth == sn->depth && | |
| best_er->depth < er->depth)))) | |
| { | |
| best_sn = sn; | |
| best_s = ss; | |
| best_er = er; | |
| } | |
| } | |
| } | |
| } | |
| for (i = 0; i < sn->zns.n; i++) | |
| if (sn->zns.v[i]) | |
| for (j = 0; j < sn->zns.v[i]->sns.n; j++) { | |
| if (tail < ERROR_RECOVERY_QUEUE_SIZE - 1) | |
| q[tail++] = sn->zns.v[i]->sns.v[j]; | |
| } | |
| } | |
| if (best_sn) { | |
| D_Reduction *rr = MALLOC(sizeof(*rr)); | |
| Reduction *r = MALLOC(sizeof(*r)); | |
| d_loc_t best_loc = p->user.loc; | |
| PNode *new_pn; | |
| SNode *new_sn; | |
| ZNode *z; | |
| memset(rr, 0, sizeof(*rr)); | |
| vec_add(&p->error_reductions, rr); | |
| rr->nelements = best_er->depth + 1; | |
| rr->symbol = best_er->symbol; | |
| update_line(best_loc.s, best_s, &best_loc.line); | |
| best_loc.s = best_s; | |
| best_pn = best_sn->zns.v[0]->pn; | |
| best_pn->parse_node.white_space( | |
| (D_Parser*)p, &best_loc, (void**)&best_pn->parse_node.globals); | |
| ref_sn(best_sn); | |
| new_pn = add_PNode(p, 0, &p->user.loc, best_loc.s, best_pn, 0, 0, 0); | |
| new_sn = new_SNode(p, best_sn->state, &best_loc, new_pn->initial_scope, new_pn->initial_globals); | |
| new_sn->last_pn = new_pn; | |
| set_add_znode(&new_sn->zns, (z = new_ZNode(p, new_pn))); | |
| ref_pn(new_pn); | |
| vec_add(&z->sns, best_sn); | |
| r->znode = z; | |
| r->snode = new_sn; | |
| ref_sn(best_sn); | |
| r->reduction = rr; | |
| r->new_snode = NULL; | |
| r->next = NULL; | |
| free_old_nodes(p); | |
| reduce_one(p, r); | |
| for (i = 0; i < p->t->nstates; i++) | |
| for (sn = p->snode_hash.v[i]; sn; sn = sn->bucket_next) | |
| for (j = 0; j < sn->zns.n; j++) | |
| if ((z = sn->zns.v[j])) | |
| if (z->pn->reduction == rr) { | |
| z->pn->evaluated = 1; | |
| z->pn->error_recovery = 1; | |
| } | |
| if (p->shifts_todo || p->reductions_todo) | |
| res = 0; | |
| } | |
| FREE(q); | |
| return res; | |
| } | |
| #define PASS_CODE_FOUND(_p, _pn) ((_pn)->reduction && (_pn)->reduction->npass_code > (_p)->index && \ | |
| (_pn)->reduction->pass_code[(_p)->index]) | |
| static void | |
| pass_call(Parser *p, D_Pass *pp, PNode *pn) { | |
| if (PASS_CODE_FOUND(pp, pn)) | |
| pn->reduction->pass_code[pp->index]( | |
| pn, (void**)&pn->children.v[0], pn->children.n, | |
| (int)&((PNode*)(NULL))->parse_node, (D_Parser*)p); | |
| } | |
| static void | |
| pass_preorder(Parser *p, D_Pass *pp, PNode *pn) { | |
| int found = PASS_CODE_FOUND(pp, pn), i; | |
| pass_call(p, pp, pn); | |
| if ((pp->kind & D_PASS_FOR_ALL) || | |
| ((pp->kind & D_PASS_FOR_UNDEFINED) && !found)) | |
| for (i = 0; i < pn->children.n; i++) | |
| pass_preorder(p, pp, pn->children.v[i]); | |
| } | |
| static void | |
| pass_postorder(Parser *p, D_Pass *pp, PNode *pn) { | |
| int found = PASS_CODE_FOUND(pp, pn), i; | |
| if ((pp->kind & D_PASS_FOR_ALL) || | |
| ((pp->kind & D_PASS_FOR_UNDEFINED) && !found)) | |
| for (i = 0; i < pn->children.n; i++) | |
| pass_postorder(p, pp, pn->children.v[i]); | |
| pass_call(p, pp, pn); | |
| } | |
| void | |
| d_pass(D_Parser *ap, D_ParseNode *apn, int pass_number) { | |
| PNode *pn = D_ParseNode_to_PNode(apn); | |
| Parser *p = (Parser*)ap; | |
| D_Pass *pp; | |
| if (pass_number >= p->t->npasses) | |
| d_fail("bad pass number: %d\n", pass_number); | |
| pp = &p->t->passes[pass_number]; | |
| if (pp->kind & D_PASS_MANUAL) | |
| pass_call(p, pp, pn); | |
| else if (pp->kind & D_PASS_PRE_ORDER) | |
| pass_preorder(p, pp, pn); | |
| else if (pp->kind & D_PASS_POST_ORDER) | |
| pass_postorder(p, pp, pn); | |
| } | |
| static int | |
| exhaustive_parse(Parser *p, int state) { | |
| Reduction *r; | |
| Shift *s; | |
| char *pos, *epos = NULL; | |
| PNode *pn, tpn; | |
| SNode *sn; | |
| ZNode *z; | |
| int progress = 0, ready = 0; | |
| d_loc_t loc; | |
| pos = p->user.loc.s = p->start; | |
| loc = p->user.loc; | |
| p->user.initial_white_space_fn((D_Parser*)p, &loc, &p->user.initial_globals); | |
| /* initial state */ | |
| sn = add_SNode(p, &p->t->state[state], &loc, p->top_scope, p->user.initial_globals); | |
| memset(&tpn, 0, sizeof(tpn)); | |
| tpn.parse_node.white_space = p->user.initial_white_space_fn; | |
| tpn.parse_node.globals = p->user.initial_globals; | |
| tpn.initial_scope = tpn.parse_node.scope = p->top_scope; | |
| tpn.parse_node.end = loc.s; | |
| pn = add_PNode(p, 0, &loc, loc.s, &tpn, 0, 0, 0); | |
| sn->last_pn = pn; | |
| set_add_znode(&sn->zns, (z = new_ZNode(p, pn))); | |
| ref_pn(pn); | |
| while (1) { | |
| /* reduce all */ | |
| while (p->reductions_todo) { | |
| pos = p->reductions_todo->snode->loc.s; | |
| if (p->shifts_todo && p->shifts_todo->snode->loc.s < pos) | |
| break; | |
| if (pos > epos) { | |
| epos = pos; | |
| free_old_nodes(p); | |
| } | |
| for (;(r = p->reductions_todo) && r->snode->loc.s == pos;) { | |
| p->reductions_todo = p->reductions_todo->next; | |
| reduce_one(p, r); | |
| } | |
| } | |
| /* done? */ | |
| if (!p->shifts_todo) { | |
| if (p->accept && | |
| (p->accept->loc.s == p->end || p->user.partial_parses)) | |
| return 0; | |
| else { | |
| if (error_recovery(p)) | |
| return 1; | |
| continue; | |
| } | |
| } else if (!p->user.dont_compare_stacks && p->shifts_todo->next) | |
| cmp_stacks(p); | |
| /* shift all */ | |
| pos = p->shifts_todo->snode->loc.s; | |
| if (pos > epos) { | |
| epos = pos; | |
| free_old_nodes(p); | |
| } | |
| progress++; | |
| ready = progress > p->user.commit_actions_interval; | |
| if (ready && !p->shifts_todo->next) { | |
| commit_stack(p, p->shifts_todo->snode); | |
| ready = progress = 0; | |
| } | |
| for (; (s = p->shifts_todo) && s->snode->loc.s == pos;) { | |
| p->shifts_todo = p->shifts_todo->next; | |
| shift_one(p, s); | |
| } | |
| if (ready && p->reductions_todo && !p->reductions_todo->next) { | |
| commit_stack(p, p->reductions_todo->snode); | |
| progress = 0; | |
| } | |
| } | |
| } | |
| /* doesn't include nl */ | |
| char _wspace[256] = { | |
| 0, 0, 0, 0, 0, 0, 0, 0, | |
| 0, 1, 0, 1, 1, 1, 0, 0, | |
| 0, 0, 0, 0, 0, 0, 0, 0, | |
| 0, 0, 0, 0, 0, 0, 0, 0, | |
| 1, 0, 0, 0, 0, 0, 0, 0 /* zero padded */ | |
| }; | |
| #define wspace(_x) (_wspace[(unsigned char)_x]) | |
| static void | |
| white_space(D_Parser *p, d_loc_t *loc, void **p_user_globals) { | |
| int rec = 0; | |
| char *s = loc->s, *scol; | |
| if (p->loc.s == s) | |
| scol = s; | |
| else | |
| scol = 0; | |
| if (*s == '#' && loc->previous_col == 0) { | |
| Ldirective: | |
| { | |
| char *save = s; | |
| s++; | |
| while (wspace(*s)) s++; | |
| if (!strncmp("line", s, 4)) { | |
| if (wspace(s[4])) { | |
| s += 5; | |
| while (wspace(*s)) s++; | |
| } | |
| } | |
| if (isdigit(*s)) { | |
| loc->line = atoi(s) - 1; | |
| while (isdigit(*s)) s++; | |
| while (wspace(*s)) s++; | |
| if (*s == '"') | |
| loc->pathname = s; | |
| } else { | |
| s = save; | |
| goto Ldone; | |
| } | |
| } | |
| while (*s && *s != '\n') s++; | |
| } | |
| Lmore: | |
| while (wspace(*s)) s++; | |
| if (*s == '\n') { | |
| loc->line++; | |
| scol = s + 1; | |
| s++; | |
| if (*s == '#') | |
| goto Ldirective; | |
| else | |
| goto Lmore; | |
| } | |
| if (s[0] == '/') { | |
| if (s[1] == '/') { | |
| while (*s && *s != '\n') { s++; } | |
| loc->line++; | |
| s++; | |
| goto Lmore; | |
| } | |
| if (s[1] == '*') { | |
| s += 2; | |
| LnestComment: | |
| rec++; | |
| LmoreComment: | |
| while (*s) { | |
| if (s[0] == '*' && s[1] == '/') { | |
| s += 2; | |
| rec--; | |
| if (!rec) | |
| goto Lmore; | |
| goto LmoreComment; | |
| } | |
| if (s[0] == '/' && s[1] == '*') { | |
| s += 2; | |
| goto LnestComment; | |
| } | |
| if (*s == '\n') { | |
| loc->line++; | |
| scol = s + 1; | |
| } | |
| s++; | |
| } | |
| } | |
| } | |
| Ldone: | |
| if (scol) | |
| loc->col = s - scol; | |
| else | |
| loc->col = -1; | |
| loc->s = s; | |
| return; | |
| } | |
| void null_white_space(D_Parser *p, d_loc_t *loc, void **p_globals) { } | |
| D_Parser * | |
| new_D_Parser(D_ParserTables *t, int sizeof_ParseNode_User) { | |
| Parser *p = MALLOC(sizeof(Parser)); | |
| memset(p, 0, sizeof(Parser)); | |
| p->t = t; | |
| p->user.loc.line = 1; | |
| p->user.sizeof_user_parse_node = sizeof_ParseNode_User; | |
| p->user.commit_actions_interval = DEFAULT_COMMIT_ACTIONS_INTERVAL; | |
| p->user.syntax_error_fn = syntax_error_report_fn; | |
| p->user.ambiguity_fn = ambiguity_abort_fn; | |
| p->user.error_recovery = 1; | |
| p->user.save_parse_tree = t->save_parse_tree; | |
| if (p->t->default_white_space) | |
| p->user.initial_white_space_fn = p->t->default_white_space; | |
| else if (p->t->whitespace_state) | |
| p->user.initial_white_space_fn = parse_whitespace; | |
| else | |
| p->user.initial_white_space_fn = white_space; | |
| return (D_Parser*)p; | |
| } | |
| void | |
| free_D_Parser(D_Parser *ap) { | |
| Parser *p = (Parser *)ap; | |
| if (p->top_scope && !p->user.initial_scope) | |
| free_D_Scope(p->top_scope, 0); | |
| if (p->whitespace_parser) | |
| free_D_Parser((D_Parser*)p->whitespace_parser); | |
| FREE(ap); | |
| } | |
| void | |
| free_D_ParseNode(D_Parser * p, D_ParseNode *dpn) { | |
| if (dpn != NO_DPN) { | |
| unref_pn((Parser*)p, DPN_TO_PN(dpn)); | |
| free_parser_working_data((Parser*)p); | |
| } | |
| #ifdef TRACK_PNODES | |
| if (((Parser*)p)->xall) | |
| printf("tracked pnodes\n"); | |
| #endif | |
| } | |
| Parser * | |
| new_subparser(Parser *p) { | |
| Parser * pp = (Parser *)new_D_Parser(p->t, p->user.sizeof_user_parse_node); | |
| pp->end = p->end; | |
| pp->pinterface1 = p->pinterface1; | |
| alloc_parser_working_data(pp); | |
| return pp; | |
| } | |
| static void | |
| initialize_whitespace_parser(Parser *p) { | |
| if (p->t->whitespace_state) { | |
| p->whitespace_parser = new_subparser(p); | |
| p->whitespace_parser->user.initial_white_space_fn = null_white_space; | |
| p->whitespace_parser->user.error_recovery = 0; | |
| p->whitespace_parser->user.partial_parses = 1; | |
| } | |
| } | |
| D_ParseNode * | |
| dparse(D_Parser *ap, char *buf, int buf_len) { | |
| int r; | |
| Parser *p = (Parser *)ap; | |
| SNode *ps; | |
| PNode *pn; | |
| D_ParseNode *res = NULL; | |
| p->states = p->scans = p->shifts = p->reductions = p->compares = 0; | |
| p->start = buf; | |
| p->end = buf + buf_len; | |
| initialize_whitespace_parser(p); | |
| alloc_parser_working_data(p); | |
| if (p->user.initial_scope) | |
| p->top_scope = p->user.initial_scope; | |
| else { | |
| if (p->top_scope) | |
| free_D_Scope(p->top_scope, 0); | |
| p->top_scope = new_D_Scope(NULL); | |
| p->top_scope->kind = SCOPE_SEQUENTIAL; | |
| } | |
| r = exhaustive_parse(p, p->user.start_state); | |
| if (!r) { | |
| ps = p->accept; | |
| if (ps->zns.n != 1 || ps->zns.v[0]->pn->children.n != 1) | |
| d_fail("internal error: bad final reduction"); | |
| pn = ps->zns.v[0]->pn->latest->children.v[0]; | |
| pn = commit_tree(p, pn); | |
| if (verbose_level) { | |
| printf( | |
| "%d states %d scans %d shifts %d reductions " | |
| "%d compares %d ambiguities\n", | |
| p->states, p->scans, p->shifts, p->reductions, | |
| p->compares, p->ambiguities); | |
| if (p->user.save_parse_tree) { | |
| if (verbose_level > 1) | |
| xprint_paren(p, pn); | |
| else | |
| print_paren(pn); | |
| printf("\n"); | |
| } | |
| } | |
| if (p->user.save_parse_tree) { | |
| ref_pn(pn); | |
| res = &pn->parse_node; | |
| } else | |
| res = NO_DPN; | |
| unref_sn(p, p->accept); | |
| p->accept = NULL; | |
| } else | |
| p->accept = NULL; | |
| free_parser_working_data(p); | |
| return res; | |
| } | |