| /* |
| 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[0], 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; |
| } |
| |