parse_runtime.c (60585B)
1 /* gramparse.c — the shared push driver for gramgen-generated parsers. 2 * 3 * Allocation-free: the caller supplies the parser instance (an `KitGramParser` 4 * blob) and both parse stacks (via KitGramConfig). This file reinterprets that 5 * storage as the real layout below; _Static_assert guards the size/alignment. 6 * 7 * An explicit-stack LL(1) automaton. Two stacks: 8 * control stack (ctl): pending work — symbols to process, builders to run, 9 * reductions to fire. This *is* the suspended state. 10 * value stack (val): semantic values, yacc-style, threaded to reduce(). 11 * 12 * Only matching a terminal consumes the lookahead; at that point the driver 13 * returns and waits for the next push. Everything else (predicting, expanding, 14 * folding lists, reducing) runs on the current lookahead without consuming it. 15 */ 16 #include <kit/support/gram_parse_tables.h> 17 18 #define KIT_GRAM_MAX_STEPS 4000000u /* defensive bound against malformed tables */ 19 20 /* ---- control-stack items ---- */ 21 typedef enum { 22 C_SYM, 23 C_REP, 24 C_LISTPUSH, 25 C_OPTSOME, 26 C_REDUCE, 27 C_PRATT_EXPR, 28 C_PRATT_LOOP, 29 C_PRATT_AFTER_PRIMARY, 30 C_PRATT_AFTER_PREFIX, 31 C_PRATT_AFTER_INFIX, 32 C_PRATT_END, 33 /* mixfix continuations (ternary `c ? a : b`, circumfix `lhs ( inner )`): 34 * AFTER_TERNARY_MID expects op2 then parses the else-branch at rbp; 35 * AFTER_TERNARY_ELSE folds the 5-kid node; AFTER_CIRCUMFIX expects the 36 * close token then folds the 4-kid node. */ 37 C_PRATT_AFTER_TERNARY_MID, 38 C_PRATT_AFTER_TERNARY_ELSE, 39 C_PRATT_AFTER_CIRCUMFIX 40 } ctl_kind; 41 typedef struct { 42 ctl_kind kind; 43 const KitGramSym* sym; /* C_SYM, C_REP */ 44 KitGramRuleId rule; /* C_REDUCE */ 45 uint16_t prod, nkids; /* C_REDUCE */ 46 uint16_t min_bp; /* Pratt parse_expr/loop frames */ 47 uint32_t vbase; /* C_REDUCE: value-stack base for this rule */ 48 KitGramToken start; /* C_REDUCE: lookahead when the rule was entered */ 49 } kit_gram_ctl; 50 51 /* The real parser. The public KitGramParser is opaque storage we reinterpret; the 52 * stacks live in the caller's buffers (cfg.ctl_stack / cfg.val_stack), so this 53 * holds only depths and scalar state. */ 54 typedef struct kit_gram_parser_impl { 55 const KitGramGrammar* g; 56 KitGramConfig cfg; /* carries the caller's stack buffers */ 57 size_t nctl, nval; /* current stack depths */ 58 size_t ctl_hwm, val_hwm; /* peak depths reached (high-water) */ 59 /* Token-generation incremental state. gen_min_rule is non-NULL only while a 60 * generation is in progress; when set, ctl_push/ctl_pop keep gen_min_sum 61 * (sum of per-entry minimum token counts) and gen_rdepth (count of reduce 62 * frames) current so the generator never rescans the whole control stack. 63 * gen_min_rule sits next to nctl/ctl_hwm so the per-push/pop null check 64 * shares a cache line already touched on the hot recognition path. */ 65 const size_t* gen_min_rule; 66 size_t gen_min_sum; 67 size_t gen_rdepth; 68 KitGramToken look; 69 bool have_look, done, failed, overflow; 70 KitGramSem result; 71 size_t nerrors; 72 KitGramSym start_sym; 73 KitGramTokenKind scratch; /* backing store for singleton "expected" */ 74 bool pred_cache_valid, set_cache_valid, set_cache_result; 75 KitGramRuleId pred_cache_rule; 76 KitGramTokenKind pred_cache_tok, set_cache_tok; 77 int pred_cache_prod; 78 uint16_t set_cache_idx; 79 } kit_gram_parser_impl; 80 81 /* The opaque public types must be able to hold the real ones. */ 82 _Static_assert( 83 sizeof(kit_gram_parser_impl) <= sizeof(KitGramParser), 84 "KitGramParser storage too small — raise KIT_GRAM_PARSER_SIZE in gramparse.h"); 85 _Static_assert(_Alignof(kit_gram_parser_impl) <= _Alignof(KitGramParser), 86 "KitGramParser storage under-aligned"); 87 _Static_assert(sizeof(kit_gram_ctl) <= sizeof(KitGramSlot), 88 "KitGramSlot too small — raise KIT_GRAM_SLOT_SIZE in gramparse.h"); 89 _Static_assert(_Alignof(kit_gram_ctl) <= _Alignof(KitGramSlot), 90 "KitGramSlot under-aligned"); 91 92 static kit_gram_parser_impl* impl(KitGramParser* p) { return (kit_gram_parser_impl*)p; } 93 static const kit_gram_parser_impl* cimpl(const KitGramParser* p) { 94 return (const kit_gram_parser_impl*)p; 95 } 96 97 /* The control buffer is an array of KitGramSlot, each >= sizeof(kit_gram_ctl) and at 98 * least as aligned, so a `cap`-slot buffer holds `cap` packed kit_gram_ctl. */ 99 static kit_gram_ctl* ctl_buf(kit_gram_parser_impl* p) { 100 return (kit_gram_ctl*)p->cfg.ctl_stack; 101 } 102 static const kit_gram_ctl* cctl_buf(const kit_gram_parser_impl* p) { 103 return (const kit_gram_ctl*)p->cfg.ctl_stack; 104 } 105 106 /* Per-entry minimum token count, used by the generator's incremental upkeep. 107 * Defined below; only ever called when p->gen_min_rule is non-NULL. */ 108 static size_t gen_entry_min(const kit_gram_parser_impl* p, const kit_gram_ctl* c); 109 110 /* The incremental upkeep below runs only during token generation. It is kept 111 * out of line and behind an unlikely branch so the recognition hot path 112 * (ctl_push/ctl_pop with gen_min_rule == NULL) pays only one predicted branch 113 * and stays small enough to inline into expand(). */ 114 static __attribute__((noinline)) void gen_account_push(kit_gram_parser_impl* p, 115 kit_gram_ctl c) { 116 p->gen_min_sum += gen_entry_min(p, &c); 117 if (c.kind == C_REDUCE || c.kind == C_PRATT_END) p->gen_rdepth++; 118 } 119 static __attribute__((noinline)) void gen_account_pop(kit_gram_parser_impl* p, 120 kit_gram_ctl c) { 121 p->gen_min_sum -= gen_entry_min(p, &c); 122 if (c.kind == C_REDUCE || c.kind == C_PRATT_END) p->gen_rdepth--; 123 } 124 125 /* ---- caller-provided stacks (bounds-checked; no allocation) ---- */ 126 static void ctl_push(kit_gram_parser_impl* p, kit_gram_ctl c) { 127 if (p->nctl >= p->cfg.ctl_cap) { 128 p->failed = p->overflow = true; 129 return; 130 } 131 ctl_buf(p)[p->nctl++] = c; 132 if (p->nctl > p->ctl_hwm) p->ctl_hwm = p->nctl; 133 if (__builtin_expect(p->gen_min_rule != NULL, 0)) gen_account_push(p, c); 134 } 135 /* Pop the top control entry, reversing the incremental upkeep done by ctl_push. 136 * Callers must ensure p->nctl > 0. */ 137 static kit_gram_ctl ctl_pop(kit_gram_parser_impl* p) { 138 kit_gram_ctl c = ctl_buf(p)[--p->nctl]; 139 if (__builtin_expect(p->gen_min_rule != NULL, 0)) gen_account_pop(p, c); 140 return c; 141 } 142 /* C_SYM is the hottest control entry and reads only .kind/.sym in run(); write 143 * just those two fields rather than zero-filling the whole 64-byte slot (the 144 * unused tail includes the 32-byte `start` token, which only 145 * C_REDUCE/C_PRATT_END frames populate for introspection). */ 146 static void ctl_push_sym(kit_gram_parser_impl* p, const KitGramSym* s) { 147 if (p->nctl >= p->cfg.ctl_cap) { 148 p->failed = p->overflow = true; 149 return; 150 } 151 kit_gram_ctl* e = &ctl_buf(p)[p->nctl++]; 152 e->kind = C_SYM; 153 e->sym = s; 154 if (p->nctl > p->ctl_hwm) p->ctl_hwm = p->nctl; 155 if (__builtin_expect(p->gen_min_rule != NULL, 0)) gen_account_push(p, *e); 156 } 157 static void ctl_push_syms_reversed(kit_gram_parser_impl* p, const KitGramSym* syms, 158 uint16_t nsyms) { 159 if (!nsyms) return; 160 if (p->cfg.ctl_cap - p->nctl < nsyms) { 161 p->failed = p->overflow = true; 162 return; 163 } 164 kit_gram_ctl* cb = ctl_buf(p); 165 size_t base = p->nctl; 166 for (uint16_t i = 0; i < nsyms; i++) { 167 cb[base + i].kind = C_SYM; 168 cb[base + i].sym = &syms[nsyms - 1u - i]; 169 } 170 p->nctl += nsyms; 171 if (p->nctl > p->ctl_hwm) p->ctl_hwm = p->nctl; 172 if (__builtin_expect(p->gen_min_rule != NULL, 0)) { 173 for (uint16_t i = 0; i < nsyms; i++) gen_account_push(p, cb[base + i]); 174 } 175 } 176 static void val_push(kit_gram_parser_impl* p, KitGramSem v) { 177 if (p->nval >= p->cfg.val_cap) { 178 p->failed = p->overflow = true; 179 return; 180 } 181 p->cfg.val_stack[p->nval] = v; 182 p->nval++; 183 if (p->nval > p->val_hwm) p->val_hwm = p->nval; 184 } 185 static KitGramSem val_pop(kit_gram_parser_impl* p) { 186 if (!p->nval) return NULL; 187 p->nval--; 188 return p->cfg.val_stack[p->nval]; 189 } 190 191 /* ---- guarded vtable calls (any field may be NULL) ---- */ 192 static KitGramSem do_lift(kit_gram_parser_impl* p, KitGramToken t) { 193 const KitGramActions* a = p->cfg.actions; 194 return (a && a->lift_token) ? a->lift_token(p->cfg.ud, t) : NULL; 195 } 196 static KitGramSem do_reduce(kit_gram_parser_impl* p, KitGramRuleId r, int prod, 197 KitGramSem* k, size_t n) { 198 const KitGramActions* a = p->cfg.actions; 199 return (a && a->reduce) ? a->reduce(p->cfg.ud, r, prod, k, n) : NULL; 200 } 201 static KitGramSem do_list_empty(kit_gram_parser_impl* p) { 202 const KitGramActions* a = p->cfg.actions; 203 return (a && a->list_empty) ? a->list_empty(p->cfg.ud) : NULL; 204 } 205 static KitGramSem do_list_push(kit_gram_parser_impl* p, KitGramSem l, KitGramSem it) { 206 const KitGramActions* a = p->cfg.actions; 207 return (a && a->list_push) ? a->list_push(p->cfg.ud, l, it) : NULL; 208 } 209 static KitGramSem do_opt_none(kit_gram_parser_impl* p) { 210 const KitGramActions* a = p->cfg.actions; 211 return (a && a->opt_none) ? a->opt_none(p->cfg.ud) : NULL; 212 } 213 static KitGramSem do_opt_some(kit_gram_parser_impl* p, KitGramSem it) { 214 const KitGramActions* a = p->cfg.actions; 215 return (a && a->opt_some) ? a->opt_some(p->cfg.ud, it) : NULL; 216 } 217 218 static bool shift_token(kit_gram_parser_impl* p) { 219 val_push(p, do_lift(p, p->look)); 220 if (p->failed) return false; 221 if (p->cfg.actions && p->cfg.actions->on_token) 222 p->cfg.actions->on_token(p->cfg.ud, p->look); 223 p->have_look = false; 224 return true; 225 } 226 227 /* ---- set membership & prediction ---- */ 228 static int find_tok_sorted(const KitGramTokenKind* s, uint16_t n, 229 KitGramTokenKind k) { 230 if (n) { 231 KitGramTokenKind first = s[0]; 232 uint16_t idx = (uint16_t)(k - first); 233 if (k >= first && idx < n && s[idx] == k) return (int)idx; 234 } 235 if (n <= 16) { 236 for (uint16_t i = 0; i < n; i++) 237 if (s[i] == k) return (int)i; 238 return -1; 239 } 240 uint16_t lo = 0, hi = n; 241 while (lo < hi) { 242 uint16_t mid = (uint16_t)(lo + (uint16_t)((hi - lo) / 2u)); 243 KitGramTokenKind got = s[mid]; 244 if (got < k) 245 lo = (uint16_t)(mid + 1u); 246 else 247 hi = mid; 248 } 249 return lo < n && s[lo] == k ? (int)lo : -1; 250 } 251 252 static bool contains(const KitGramTokenKind* s, uint16_t n, KitGramTokenKind k) { 253 return find_tok_sorted(s, n, k) >= 0; 254 } 255 static bool set_in(const KitGramGrammar* g, uint16_t idx, KitGramTokenKind k) { 256 uint16_t a = g->set_off[idx], b = g->set_off[idx + 1]; 257 return contains(&g->sets[a], (uint16_t)(b - a), k); 258 } 259 static int predict(const KitGramRule* r, KitGramTokenKind k) { 260 int i = find_tok_sorted(r->predict_tok, r->npredict, k); 261 return i >= 0 ? r->predict_prod[i] : (r->nullable ? r->empty_prod : -1); 262 } 263 264 static int predict_cached(kit_gram_parser_impl* p, KitGramRuleId rid, 265 const KitGramRule* r, KitGramTokenKind k) { 266 if (p->pred_cache_valid && p->pred_cache_rule == rid && 267 p->pred_cache_tok == k) 268 return p->pred_cache_prod; 269 int prod = predict(r, k); 270 p->pred_cache_valid = true; 271 p->pred_cache_rule = rid; 272 p->pred_cache_tok = k; 273 p->pred_cache_prod = prod; 274 return prod; 275 } 276 277 static bool set_in_cached(kit_gram_parser_impl* p, uint16_t idx, KitGramTokenKind k) { 278 if (p->set_cache_valid && p->set_cache_idx == idx && p->set_cache_tok == k) 279 return p->set_cache_result; 280 bool result = set_in(p->g, idx, k); 281 p->set_cache_valid = true; 282 p->set_cache_idx = idx; 283 p->set_cache_tok = k; 284 p->set_cache_result = result; 285 return result; 286 } 287 static const KitGramPrattOp* pratt_prefix(const KitGramPratt* pt, 288 KitGramTokenKind k) { 289 for (uint16_t i = 0; i < pt->nops; i++) 290 if (pt->ops[i].role == KIT_GRAM_PO_PREFIX && pt->ops[i].tok == k) 291 return &pt->ops[i]; 292 return NULL; 293 } 294 static const KitGramPrattOp* pratt_cont(const KitGramPratt* pt, KitGramTokenKind k, 295 uint16_t min_bp) { 296 for (uint16_t i = 0; i < pt->nops; i++) 297 if (pt->ops[i].role != KIT_GRAM_PO_PREFIX && pt->ops[i].tok == k && 298 pt->ops[i].lbp > min_bp) 299 return &pt->ops[i]; 300 return NULL; 301 } 302 /* The mixfix AFTER-frames carry only the operator's `prod`; recover the full op 303 * record (for tok2 / rbp) by that key. Linear over the small per-rule op list. 304 */ 305 static const KitGramPrattOp* pratt_op_by_prod(const KitGramPratt* pt, 306 uint16_t prod) { 307 for (uint16_t i = 0; i < pt->nops; i++) 308 if (pt->ops[i].prod == prod) return &pt->ops[i]; 309 return NULL; 310 } 311 static KitGramRuleId cur_rule(const kit_gram_parser_impl* p) { 312 const kit_gram_ctl* cb = cctl_buf(p); 313 for (size_t i = p->nctl; i > 0; i--) 314 if ((cb[i - 1].kind == C_REDUCE || cb[i - 1].kind == C_PRATT_END) && 315 !p->g->rules[cb[i - 1].rule].hidden) 316 return cb[i - 1].rule; 317 return p->g->start; 318 } 319 320 /* Reduce a named rule: gather the kids in [vbase, nval), run the reduce action 321 * (or pass kid 0 through for a hidden wrapper), reset the value stack to vbase, 322 * push the result, and fire the exit listener. Shared by the C_REDUCE step and 323 * the single-terminal expansion fast path. */ 324 static void reduce_named(kit_gram_parser_impl* p, KitGramRuleId rule, uint16_t prod, 325 uint32_t vbase) { 326 size_t n = p->nval - vbase; 327 const KitGramRule* r = &p->g->rules[rule]; 328 KitGramSem* kids = &p->cfg.val_stack[vbase]; 329 KitGramSem res = 330 r->hidden ? (n ? kids[0] : NULL) : do_reduce(p, rule, prod, kids, n); 331 p->nval = vbase; 332 val_push(p, res); 333 if (!r->hidden && p->cfg.actions && p->cfg.actions->exit) 334 p->cfg.actions->exit(p->cfg.ud, rule, prod); 335 } 336 337 /* expand named rule `rid` via production `prod`: enter, schedule reduce, then 338 * push the production's symbols so they are processed left to right. 339 * 340 * Leading-terminal fusion: in LL(1), if the chosen production's first symbol is 341 * a terminal, that terminal necessarily equals the current lookahead (it is why 342 * predict picked this production). When `may_shift` is set (the recognition 343 * path, not token generation) we shift it here rather than pushing a C_SYM only 344 * to pop and match it on the very next step. The common special case of a 345 * *single* terminal production (`value = STRING`, `type = "int"`, a Pratt INT 346 * primary) is fused further: shift then reduce in place, with no reduce frame 347 * round trip at all — the rule is entered and exited within this one step. 348 * Returns true when it shifted (and thus consumed the lookahead): the caller 349 * must then suspend. */ 350 static bool expand(kit_gram_parser_impl* p, KitGramRuleId rid, int prod, 351 bool may_shift) { 352 const KitGramRule* r = &p->g->rules[rid]; 353 const KitGramProd* pr = &r->prods[prod]; 354 const KitGramActions* a = p->cfg.actions; 355 uint16_t nsyms = pr->nsyms; 356 bool fuse = may_shift && nsyms && p->have_look && 357 pr->syms[0].kind == KIT_GRAM_S_TERM && 358 pr->syms[0].tok == p->look.kind; 359 if (!r->hidden && a && a->enter) a->enter(p->cfg.ud, rid, prod); 360 if (fuse && nsyms == 1) { 361 uint32_t vbase = (uint32_t)p->nval; 362 if (!shift_token(p)) return false; 363 reduce_named(p, rid, (uint16_t)prod, vbase); 364 return !p->failed; 365 } 366 if (p->nctl >= p->cfg.ctl_cap) { 367 p->failed = p->overflow = true; 368 return false; 369 } 370 kit_gram_ctl* rc = &ctl_buf(p)[p->nctl++]; /* build the reduce frame in place */ 371 rc->kind = C_REDUCE; 372 rc->rule = rid; 373 rc->prod = (uint16_t)prod; 374 rc->nkids = nsyms; 375 rc->vbase = (uint32_t)p->nval; 376 rc->start = p->look; 377 if (p->nctl > p->ctl_hwm) p->ctl_hwm = p->nctl; 378 if (__builtin_expect(p->gen_min_rule != NULL, 0)) gen_account_push(p, *rc); 379 if (fuse) { 380 ctl_push_syms_reversed(p, pr->syms + 1, (uint16_t)(nsyms - 1)); 381 if (p->failed) return false; 382 return shift_token(p); 383 } 384 ctl_push_syms_reversed(p, pr->syms, nsyms); 385 return false; 386 } 387 388 static void expand_pratt(kit_gram_parser_impl* p, KitGramRuleId rid) { 389 const KitGramRule* r = &p->g->rules[rid]; 390 const KitGramPratt* pt = r->pratt; 391 const KitGramActions* a = p->cfg.actions; 392 if (!r->hidden && a && a->enter) a->enter(p->cfg.ud, rid, pt->primary_prod); 393 kit_gram_ctl end = {.kind = C_PRATT_END, 394 .rule = rid, 395 .prod = pt->primary_prod, 396 .vbase = (uint32_t)p->nval, 397 .start = p->look}; 398 kit_gram_ctl expr = {.kind = C_PRATT_EXPR, 399 .rule = rid, 400 .min_bp = 0, 401 .vbase = (uint32_t)p->nval}; 402 ctl_push(p, end); 403 ctl_push(p, expr); 404 } 405 406 static void pratt_reduce_at(kit_gram_parser_impl* p, KitGramRuleId rule, 407 uint16_t prod, uint32_t vbase, size_t n) { 408 KitGramSem* kids = &p->cfg.val_stack[vbase]; 409 KitGramSem res = do_reduce(p, rule, prod, kids, n); 410 p->nval = vbase; 411 val_push(p, res); 412 } 413 414 /* ---- error handling / recovery ---- */ 415 /* `failed` points at the just-popped control slot (still live: pop only lowers 416 * the depth). Taking it by pointer rather than by value keeps `c.start` — the 417 * 32-byte introspection token that error handling never reads — out of the hot 418 * pop in run(), so the compiler elides copying it on every step. */ 419 typedef enum { ER_CONTINUE, ER_SUSPEND, ER_ABORT } er_res; 420 static er_res handle_error(kit_gram_parser_impl* p, const kit_gram_ctl* failed, 421 const KitGramTokenKind* expected, size_t nexp, 422 KitGramRuleId in_rule) { 423 p->nerrors++; 424 const KitGramActions* a = p->cfg.actions; 425 KitGramError e = {.found = p->look, 426 .expected = expected, 427 .nexpected = nexp, 428 .in_rule = in_rule}; 429 KitGramErrorAction act = (a && a->on_error) 430 ? a->on_error(p->cfg.ud, &e) 431 : (p->cfg.recover ? KIT_GRAM_RESYNC : KIT_GRAM_ABORT); 432 switch (act) { 433 case KIT_GRAM_ABORT: 434 p->failed = true; 435 return ER_ABORT; 436 case KIT_GRAM_SKIP: 437 ctl_push(p, *failed); /* retry the same expectation with the next token */ 438 p->have_look = false; 439 return ER_SUSPEND; 440 case KIT_GRAM_RESYNC: 441 /* abandon enclosing rules until one is dropped; substitute NULL value 442 * so the parent's kid accounting stays balanced. Bounded by stack depth. 443 */ 444 while (p->nctl > 0) { 445 kit_gram_ctl x = ctl_pop(p); 446 if (x.kind == C_REDUCE || x.kind == C_PRATT_END) { 447 p->nval = x.vbase; 448 val_push(p, NULL); 449 return ER_CONTINUE; 450 } 451 } 452 p->failed = true; 453 return ER_ABORT; 454 } 455 p->failed = true; 456 return ER_ABORT; 457 } 458 459 /* Pratt continuation: given a just-completed left operand at `vbase`, look for 460 * a continuation operator binding tighter than `min_bp` and set up its parse, 461 * or report that the operator loop is done. Returns PL_SUSPEND when it consumed 462 * the operator token (caller must suspend), PL_BREAK when no operator continues 463 * the loop (caller falls through to the enclosing frame), or PL_ERROR. 464 * 465 * This is the body of the operator loop. The AFTER_* handlers that still hold 466 * the lookahead (PRIMARY/PREFIX/INFIX/TERNARY_ELSE) call it directly instead of 467 * pushing a C_PRATT_LOOP frame to be popped next step — eliminating one 468 * control-stack round trip per operator. POSTFIX and CIRCUMFIX consume a token 469 * before the loop can resume, so they still go through a pushed C_PRATT_LOOP. 470 */ 471 typedef enum { PL_BREAK, PL_SUSPEND, PL_ERROR } pl_res; 472 static pl_res pratt_continue(kit_gram_parser_impl* p, KitGramRuleId rule, 473 uint16_t min_bp, uint32_t vbase) { 474 const KitGramRule* r = &p->g->rules[rule]; 475 const KitGramPrattOp* op = pratt_cont(r->pratt, p->look.kind, min_bp); 476 if (!op) return PL_BREAK; 477 if (op->role == KIT_GRAM_PO_POSTFIX) { 478 if (!shift_token(p)) return PL_ERROR; 479 pratt_reduce_at(p, rule, op->prod, vbase, 2); 480 if (p->failed) return PL_ERROR; 481 kit_gram_ctl loop = { 482 .kind = C_PRATT_LOOP, .rule = rule, .min_bp = min_bp, .vbase = vbase}; 483 ctl_push(p, loop); 484 return p->failed ? PL_ERROR : PL_SUSPEND; 485 } 486 if (op->role == KIT_GRAM_PO_TERNARY) { 487 kit_gram_ctl mid = {.kind = C_PRATT_AFTER_TERNARY_MID, 488 .rule = rule, 489 .prod = op->prod, 490 .min_bp = min_bp, 491 .vbase = vbase}; 492 kit_gram_ctl child = { 493 .kind = C_PRATT_EXPR, .rule = rule, .min_bp = 0, .vbase = vbase + 2}; 494 ctl_push(p, mid); 495 ctl_push(p, child); 496 if (p->failed) return PL_ERROR; 497 if (!shift_token(p)) return PL_ERROR; 498 return PL_SUSPEND; 499 } 500 if (op->role == KIT_GRAM_PO_CIRCUMFIX) { 501 kit_gram_ctl after = {.kind = C_PRATT_AFTER_CIRCUMFIX, 502 .rule = rule, 503 .prod = op->prod, 504 .min_bp = min_bp, 505 .vbase = vbase}; 506 ctl_push(p, after); 507 ctl_push_sym(p, &op->inner); 508 if (p->failed) return PL_ERROR; 509 if (!shift_token(p)) return PL_ERROR; 510 return PL_SUSPEND; 511 } 512 kit_gram_ctl after = {.kind = C_PRATT_AFTER_INFIX, 513 .rule = rule, 514 .prod = op->prod, 515 .min_bp = min_bp, 516 .vbase = vbase}; 517 kit_gram_ctl child = {.kind = C_PRATT_EXPR, 518 .rule = rule, 519 .min_bp = op->rbp, 520 .vbase = vbase + 2}; 521 ctl_push(p, after); 522 ctl_push(p, child); 523 if (p->failed) return PL_ERROR; 524 if (!shift_token(p)) return PL_ERROR; 525 return PL_SUSPEND; 526 } 527 528 typedef enum { RUN_SUSPEND, RUN_DONE, RUN_ERROR } run_res; 529 530 static run_res run(kit_gram_parser_impl* p) { 531 unsigned steps = 0; 532 while (p->nctl > 0) { 533 if (++steps > KIT_GRAM_MAX_STEPS) { 534 p->failed = true; 535 return RUN_ERROR; 536 } 537 kit_gram_ctl c = ctl_pop(p); 538 switch (c.kind) { 539 case C_SYM: { 540 const KitGramSym* s = c.sym; 541 switch (s->kind) { 542 case KIT_GRAM_S_TERM: 543 if (p->look.kind == s->tok) { 544 if (!shift_token(p)) return RUN_ERROR; /* value-stack overflow */ 545 return RUN_SUSPEND; /* consumed the lookahead */ 546 } else { 547 p->scratch = s->tok; 548 er_res er = handle_error(p, &ctl_buf(p)[p->nctl], &p->scratch, 1, 549 cur_rule(p)); 550 if (er == ER_ABORT) return RUN_ERROR; 551 if (er == ER_SUSPEND) return RUN_SUSPEND; 552 } 553 break; 554 case KIT_GRAM_S_RULE: { 555 const KitGramRule* r = &p->g->rules[s->rule]; 556 if (r->is_pratt) { 557 if (!contains(r->first, r->nfirst, p->look.kind)) { 558 er_res er = handle_error(p, &ctl_buf(p)[p->nctl], r->first, 559 r->nfirst, s->rule); 560 if (er == ER_ABORT) return RUN_ERROR; 561 if (er == ER_SUSPEND) return RUN_SUSPEND; 562 } else { 563 expand_pratt(p, s->rule); 564 } 565 } else { 566 int prod = predict_cached(p, s->rule, r, p->look.kind); 567 if (prod < 0) { 568 er_res er = handle_error(p, &ctl_buf(p)[p->nctl], r->first, 569 r->nfirst, s->rule); 570 if (er == ER_ABORT) return RUN_ERROR; 571 if (er == ER_SUSPEND) return RUN_SUSPEND; 572 } else { 573 bool shifted = expand(p, s->rule, prod, true); 574 if (p->failed) return RUN_ERROR; 575 if (shifted) return RUN_SUSPEND; 576 } 577 } 578 break; 579 } 580 case KIT_GRAM_S_REP: { 581 val_push(p, do_list_empty(p)); /* the REP's single kid slot */ 582 kit_gram_ctl rep = {.kind = C_REP, .sym = s}; 583 ctl_push(p, rep); 584 break; 585 } 586 case KIT_GRAM_S_OPT: 587 if (set_in_cached(p, s->first, p->look.kind)) { 588 kit_gram_ctl os = {.kind = C_OPTSOME}; 589 ctl_push(p, os); 590 ctl_push_sym(p, &s->sub[0]); 591 } else { 592 val_push(p, do_opt_none(p)); 593 } 594 break; 595 } 596 break; 597 } 598 case C_REP: 599 if (set_in_cached(p, c.sym->first, p->look.kind)) { 600 kit_gram_ctl rep = {.kind = C_REP, .sym = c.sym}; 601 kit_gram_ctl lp = {.kind = C_LISTPUSH}; 602 ctl_push(p, rep); /* loop after this iteration */ 603 ctl_push(p, lp); 604 ctl_push_sym(p, &c.sym->sub[0]); /* parse one item */ 605 } 606 break; 607 case C_LISTPUSH: { 608 KitGramSem item = val_pop(p); 609 KitGramSem list = val_pop(p); 610 val_push(p, do_list_push(p, list, item)); 611 break; 612 } 613 case C_OPTSOME: { 614 KitGramSem item = val_pop(p); 615 val_push(p, do_opt_some(p, item)); 616 break; 617 } 618 case C_REDUCE: 619 reduce_named(p, c.rule, c.prod, c.vbase); 620 break; 621 case C_PRATT_EXPR: { 622 const KitGramRule* r = &p->g->rules[c.rule]; 623 const KitGramPratt* pt = r->pratt; 624 const KitGramPrattOp* op = pratt_prefix(pt, p->look.kind); 625 if (op) { 626 kit_gram_ctl after = {.kind = C_PRATT_AFTER_PREFIX, 627 .rule = c.rule, 628 .prod = op->prod, 629 .min_bp = c.min_bp, 630 .vbase = c.vbase}; 631 kit_gram_ctl child = {.kind = C_PRATT_EXPR, 632 .rule = c.rule, 633 .min_bp = op->rbp, 634 .vbase = c.vbase + 1}; 635 ctl_push(p, after); 636 ctl_push(p, child); 637 if (p->failed) return RUN_ERROR; 638 if (!shift_token(p)) return RUN_ERROR; 639 return RUN_SUSPEND; 640 } 641 642 const KitGramRule* primary = &p->g->rules[pt->primary]; 643 int prod = predict_cached(p, pt->primary, primary, p->look.kind); 644 if (prod < 0) { 645 er_res er = handle_error(p, &ctl_buf(p)[p->nctl], r->first, r->nfirst, 646 c.rule); 647 if (er == ER_ABORT) return RUN_ERROR; 648 if (er == ER_SUSPEND) return RUN_SUSPEND; 649 } else { 650 kit_gram_ctl after = {.kind = C_PRATT_AFTER_PRIMARY, 651 .rule = c.rule, 652 .prod = pt->primary_prod, 653 .min_bp = c.min_bp, 654 .vbase = c.vbase}; 655 ctl_push(p, after); 656 bool shifted = expand(p, pt->primary, prod, true); 657 if (p->failed) return RUN_ERROR; 658 if (shifted) return RUN_SUSPEND; 659 } 660 break; 661 } 662 case C_PRATT_LOOP: { 663 /* Reached only via a token-consuming continuation (postfix/circumfix 664 * push this frame to resume the loop after the next token). */ 665 pl_res pl = pratt_continue(p, c.rule, c.min_bp, c.vbase); 666 if (pl == PL_ERROR) return RUN_ERROR; 667 if (pl == PL_SUSPEND) return RUN_SUSPEND; 668 break; 669 } 670 case C_PRATT_AFTER_PRIMARY: { 671 size_t n = p->nval - c.vbase; 672 pratt_reduce_at(p, c.rule, c.prod, c.vbase, n); 673 if (p->failed) return RUN_ERROR; 674 pl_res pl = pratt_continue(p, c.rule, c.min_bp, c.vbase); 675 if (pl == PL_ERROR) return RUN_ERROR; 676 if (pl == PL_SUSPEND) return RUN_SUSPEND; 677 break; 678 } 679 case C_PRATT_AFTER_PREFIX: { 680 pratt_reduce_at(p, c.rule, c.prod, c.vbase, 2); 681 if (p->failed) return RUN_ERROR; 682 pl_res pl = pratt_continue(p, c.rule, c.min_bp, c.vbase); 683 if (pl == PL_ERROR) return RUN_ERROR; 684 if (pl == PL_SUSPEND) return RUN_SUSPEND; 685 break; 686 } 687 case C_PRATT_AFTER_INFIX: { 688 pratt_reduce_at(p, c.rule, c.prod, c.vbase, 3); 689 if (p->failed) return RUN_ERROR; 690 pl_res pl = pratt_continue(p, c.rule, c.min_bp, c.vbase); 691 if (pl == PL_ERROR) return RUN_ERROR; 692 if (pl == PL_SUSPEND) return RUN_SUSPEND; 693 break; 694 } 695 case C_PRATT_AFTER_TERNARY_MID: { 696 const KitGramRule* r = &p->g->rules[c.rule]; 697 const KitGramPrattOp* op = pratt_op_by_prod(r->pratt, c.prod); 698 if (p->look.kind != op->tok2) { 699 p->scratch = op->tok2; 700 er_res er = 701 handle_error(p, &ctl_buf(p)[p->nctl], &p->scratch, 1, c.rule); 702 if (er == ER_ABORT) return RUN_ERROR; 703 if (er == ER_SUSPEND) return RUN_SUSPEND; 704 break; /* ER_CONTINUE: resynced */ 705 } 706 kit_gram_ctl els = {.kind = C_PRATT_AFTER_TERNARY_ELSE, 707 .rule = c.rule, 708 .prod = c.prod, 709 .min_bp = c.min_bp, 710 .vbase = c.vbase}; 711 kit_gram_ctl child = {.kind = C_PRATT_EXPR, 712 .rule = c.rule, 713 .min_bp = op->rbp, 714 .vbase = c.vbase + 4}; 715 ctl_push(p, els); 716 ctl_push(p, child); 717 if (p->failed) return RUN_ERROR; 718 if (!shift_token(p)) return RUN_ERROR; /* op2 -> vbase+3 */ 719 return RUN_SUSPEND; 720 } 721 case C_PRATT_AFTER_TERNARY_ELSE: { 722 pratt_reduce_at(p, c.rule, c.prod, c.vbase, 5); 723 if (p->failed) return RUN_ERROR; 724 pl_res pl = pratt_continue(p, c.rule, c.min_bp, c.vbase); 725 if (pl == PL_ERROR) return RUN_ERROR; 726 if (pl == PL_SUSPEND) return RUN_SUSPEND; 727 break; 728 } 729 case C_PRATT_AFTER_CIRCUMFIX: { 730 const KitGramRule* r = &p->g->rules[c.rule]; 731 const KitGramPrattOp* op = pratt_op_by_prod(r->pratt, c.prod); 732 if (p->look.kind != op->tok2) { 733 p->scratch = op->tok2; 734 er_res er = 735 handle_error(p, &ctl_buf(p)[p->nctl], &p->scratch, 1, c.rule); 736 if (er == ER_ABORT) return RUN_ERROR; 737 if (er == ER_SUSPEND) return RUN_SUSPEND; 738 break; /* ER_CONTINUE: resynced */ 739 } 740 if (!shift_token(p)) return RUN_ERROR; /* close -> vbase+3 */ 741 pratt_reduce_at(p, c.rule, c.prod, c.vbase, 4); 742 if (p->failed) return RUN_ERROR; 743 kit_gram_ctl loop = {.kind = C_PRATT_LOOP, 744 .rule = c.rule, 745 .min_bp = c.min_bp, 746 .vbase = c.vbase}; 747 ctl_push(p, loop); 748 return RUN_SUSPEND; 749 } 750 case C_PRATT_END: 751 if (!p->g->rules[c.rule].hidden && p->cfg.actions && 752 p->cfg.actions->exit) 753 p->cfg.actions->exit(p->cfg.ud, c.rule, c.prod); 754 break; 755 } 756 if (p->failed) return RUN_ERROR; 757 } 758 p->done = true; 759 p->result = p->nval ? p->cfg.val_stack[p->nval - 1] : NULL; 760 return RUN_DONE; 761 } 762 763 /* ---- token generation ---- */ 764 #define KIT_GRAM_GEN_INF (SIZE_MAX / 4) 765 #define KIT_GRAM_GEN_CACHE_WORDS 4u 766 #define KIT_GRAM_GEN_CACHE_MAGIC ((size_t)0x6c6c67656e6d696eULL) 767 768 typedef struct { 769 kit_gram_parser_impl* p; 770 KitGramGenConfig* cfg; 771 size_t* min_rule; 772 size_t max_depth; 773 size_t max_repeat; 774 size_t max_tokens; 775 } gen_ctx; 776 777 static size_t gen_add(size_t a, size_t b) { 778 if (a >= KIT_GRAM_GEN_INF || b >= KIT_GRAM_GEN_INF || a > KIT_GRAM_GEN_INF - b) 779 return KIT_GRAM_GEN_INF; 780 return a + b; 781 } 782 783 static size_t gen_sym_min(const gen_ctx* gc, const KitGramSym* sym); 784 785 static size_t gen_prod_min(const gen_ctx* gc, const KitGramProd* prod) { 786 size_t out = 0; 787 for (uint16_t i = 0; i < prod->nsyms; i++) 788 out = gen_add(out, gen_sym_min(gc, &prod->syms[i])); 789 return out; 790 } 791 792 static size_t gen_sym_min(const gen_ctx* gc, const KitGramSym* sym) { 793 switch (sym->kind) { 794 case KIT_GRAM_S_TERM: 795 return 1; 796 case KIT_GRAM_S_RULE: 797 return gc->min_rule[sym->rule]; 798 case KIT_GRAM_S_REP: 799 case KIT_GRAM_S_OPT: 800 return 0; 801 } 802 return KIT_GRAM_GEN_INF; 803 } 804 805 static bool gen_compute_min_rules(gen_ctx* gc) { 806 const KitGramGrammar* g = gc->p->g; 807 for (uint16_t i = 0; i < g->nrules; i++) gc->min_rule[i] = KIT_GRAM_GEN_INF; 808 809 bool changed = true; 810 while (changed) { 811 changed = false; 812 for (uint16_t ri = 0; ri < g->nrules; ri++) { 813 const KitGramRule* rule = &g->rules[ri]; 814 size_t best = KIT_GRAM_GEN_INF; 815 if (rule->is_pratt) { 816 best = gc->min_rule[rule->pratt->primary]; 817 } else { 818 for (uint16_t pi = 0; pi < rule->nprods; pi++) { 819 size_t n = gen_prod_min(gc, &rule->prods[pi]); 820 if (n < best) best = n; 821 } 822 } 823 if (best < gc->min_rule[ri]) { 824 gc->min_rule[ri] = best; 825 changed = true; 826 } 827 } 828 } 829 return gc->min_rule[g->start] < KIT_GRAM_GEN_INF; 830 } 831 832 static size_t gen_scratch_need(const KitGramGrammar* g) { 833 return g ? (size_t)g->nrules + KIT_GRAM_GEN_CACHE_WORDS : 0; 834 } 835 836 static size_t gen_cache_shape(const KitGramGrammar* g) { 837 return (size_t)g->nrules ^ ((size_t)g->ntoks << 16); 838 } 839 840 static bool gen_cache_valid(const KitGramGrammar* g, const size_t* scratch) { 841 return scratch[0] == KIT_GRAM_GEN_CACHE_MAGIC && 842 scratch[1] == (size_t)(uintptr_t)g && 843 scratch[2] == (size_t)(uintptr_t)g->rules && 844 scratch[3] == gen_cache_shape(g); 845 } 846 847 static void gen_cache_mark(const KitGramGrammar* g, size_t* scratch) { 848 scratch[0] = KIT_GRAM_GEN_CACHE_MAGIC; 849 scratch[1] = (size_t)(uintptr_t)g; 850 scratch[2] = (size_t)(uintptr_t)g->rules; 851 scratch[3] = gen_cache_shape(g); 852 } 853 854 static uint64_t gen_rand(KitGramGenConfig* cfg) { 855 uint64_t z = (cfg->seed += UINT64_C(0x9E3779B97F4A7C15)); 856 z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9); 857 z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB); 858 return z ^ (z >> 31); 859 } 860 861 static size_t gen_pick(KitGramGenConfig* cfg, size_t n) { 862 return n ? (size_t)(gen_rand(cfg) % n) : 0; 863 } 864 865 static size_t gen_remaining(const gen_ctx* gc) { 866 return gc->cfg->emitted < gc->max_tokens ? gc->max_tokens - gc->cfg->emitted 867 : 0; 868 } 869 870 /* Minimum tokens a single control entry can still emit. Mirrors gen_sym_min for 871 * symbols; every builder/reduce frame contributes nothing. Reads gen_min_rule 872 * (set for the duration of a generation) so ctl_push/ctl_pop can call it. */ 873 static size_t gen_entry_min(const kit_gram_parser_impl* p, const kit_gram_ctl* c) { 874 const size_t* mr = p->gen_min_rule; 875 switch (c->kind) { 876 case C_SYM: 877 switch (c->sym->kind) { 878 case KIT_GRAM_S_TERM: 879 return 1; 880 case KIT_GRAM_S_RULE: 881 return mr[c->sym->rule]; 882 case KIT_GRAM_S_REP: 883 case KIT_GRAM_S_OPT: 884 return 0; 885 } 886 return KIT_GRAM_GEN_INF; 887 case C_PRATT_EXPR: 888 return mr[p->g->rules[c->rule].pratt->primary]; 889 case C_PRATT_AFTER_CIRCUMFIX: 890 return 1; /* still owes the close token */ 891 case C_PRATT_AFTER_TERNARY_MID: 892 /* still owes op2 plus the else-operand (at least one primary) */ 893 return 1 + mr[p->g->rules[c->rule].pratt->primary]; 894 default: 895 return 0; 896 } 897 } 898 899 /* O(1): ctl_push/ctl_pop keep gen_min_sum and gen_rdepth current, so the 900 * generator no longer rescans the whole control stack on every step. */ 901 static size_t gen_stack_min(const gen_ctx* gc) { return gc->p->gen_min_sum; } 902 903 static bool gen_deep(const gen_ctx* gc) { 904 return gc->p->gen_rdepth >= gc->max_depth; 905 } 906 907 static int gen_choose_prod(gen_ctx* gc, KitGramRuleId rid) { 908 const KitGramRule* rule = &gc->p->g->rules[rid]; 909 size_t rest = gen_stack_min(gc); 910 size_t rem = gen_remaining(gc); 911 bool deep = gen_deep(gc); 912 size_t rule_min = gc->min_rule[rid]; 913 914 /* gen_prod_min is pure, so a single pass records the eligible production 915 * indices and the chosen one is indexed directly — no second pass that 916 * recomputes every production's minimum. Selection is identical to the 917 * two-pass form: one gen_pick over the eligible count, picking the pick-th 918 * eligible production in ascending order. The elig buffer is bounded by the 919 * 255-alternative compile cap (gen/kit_gram_ll1.c); a malformed table with 920 * more productions falls back to the allocation-free two-pass form below. */ 921 if (rule->nprods <= 256) { 922 uint16_t elig[256]; 923 size_t count = 0; 924 for (uint16_t pi = 0; pi < rule->nprods; pi++) { 925 size_t n = gen_prod_min(gc, &rule->prods[pi]); 926 if (gen_add(n, rest) <= rem && (!deep || n == rule_min)) 927 elig[count++] = pi; 928 } 929 if (!count) return -1; 930 return (int)elig[deep ? 0 : gen_pick(gc->cfg, count)]; 931 } 932 933 size_t count = 0; 934 for (uint16_t pi = 0; pi < rule->nprods; pi++) { 935 size_t n = gen_prod_min(gc, &rule->prods[pi]); 936 if (gen_add(n, rest) <= rem && (!deep || n == rule_min)) count++; 937 } 938 if (!count) return -1; 939 940 size_t pick = deep ? 0 : gen_pick(gc->cfg, count); 941 for (uint16_t pi = 0; pi < rule->nprods; pi++) { 942 size_t n = gen_prod_min(gc, &rule->prods[pi]); 943 if (gen_add(n, rest) <= rem && (!deep || n == rule_min)) { 944 if (pick-- == 0) return (int)pi; 945 } 946 } 947 return -1; 948 } 949 950 static KitGramGenStatus gen_shift(kit_gram_parser_impl* p, KitGramGenConfig* cfg, 951 KitGramTokenKind kind, KitGramToken* out) { 952 uint32_t col = 953 cfg->emitted < UINT32_MAX ? (uint32_t)cfg->emitted + 1 : UINT32_MAX; 954 KitGramToken t = {.kind = kind, .line = 1, .col = col}; 955 p->look = t; 956 p->have_look = true; 957 if (!shift_token(p)) return KIT_GRAM_GEN_ERROR; 958 cfg->emitted++; 959 if (out) *out = t; 960 return KIT_GRAM_GEN_TOKEN; 961 } 962 963 static KitGramGenStatus gen_expand_rule(gen_ctx* gc, KitGramRuleId rid) { 964 const KitGramRule* rule = &gc->p->g->rules[rid]; 965 if (rule->is_pratt) { 966 expand_pratt(gc->p, rid); 967 return gc->p->failed ? KIT_GRAM_GEN_ERROR : KIT_GRAM_GEN_DONE; 968 } 969 int prod = gen_choose_prod(gc, rid); 970 if (prod < 0) return KIT_GRAM_GEN_LIMIT; 971 expand(gc->p, rid, prod, false); /* generation drives shifts via gen_shift */ 972 return gc->p->failed ? KIT_GRAM_GEN_ERROR : KIT_GRAM_GEN_DONE; 973 } 974 975 static bool gen_prefix_op(const KitGramPrattOp* op) { 976 return op->role == KIT_GRAM_PO_PREFIX; 977 } 978 979 static bool gen_postfix_op(const KitGramPrattOp* op) { 980 return op->role == KIT_GRAM_PO_POSTFIX; 981 } 982 983 /* Minimum tokens a continuation op needs to fully apply, gating the generator's 984 * budget. Mirrors the frame sequence each role pushes on the parse path. */ 985 static size_t gen_op_cost(const gen_ctx* gc, const KitGramPrattOp* op, 986 size_t primary_min) { 987 switch (op->role) { 988 case KIT_GRAM_PO_POSTFIX: 989 return 1; /* op */ 990 case KIT_GRAM_PO_TERNARY: 991 return gen_add(2, gen_add(primary_min, primary_min)); /* op1 a op2 b */ 992 case KIT_GRAM_PO_CIRCUMFIX: 993 return gen_add(2, gc->min_rule[op->inner.rule]); /* open inner cl */ 994 default: 995 return gen_add(1, primary_min); /* infix: op rhs */ 996 } 997 } 998 999 size_t kit_gram_parser_generate_scratch_count(const KitGramGrammar* g) { 1000 return gen_scratch_need(g); 1001 } 1002 1003 KitGramGenStatus kit_gram_parser_generate_next(KitGramParser* pp, KitGramGenConfig* cfg, 1004 KitGramToken* out) { 1005 kit_gram_parser_impl* p = impl(pp); 1006 if (out) *out = (KitGramToken){0}; 1007 size_t scratch_need = p && p->g ? gen_scratch_need(p->g) : 0; 1008 if (!p || !p->g || !cfg || !cfg->scratch || cfg->scratch_cap < scratch_need) 1009 return KIT_GRAM_GEN_ERROR; 1010 if (p->failed) return KIT_GRAM_GEN_ERROR; 1011 if (p->done) return KIT_GRAM_GEN_DONE; 1012 if (p->have_look) return KIT_GRAM_GEN_ERROR; 1013 1014 gen_ctx gc = { 1015 .p = p, 1016 .cfg = cfg, 1017 .min_rule = cfg->scratch + KIT_GRAM_GEN_CACHE_WORDS, 1018 .max_depth = cfg->max_depth ? cfg->max_depth : 8, 1019 .max_repeat = cfg->max_repeat ? cfg->max_repeat : 2, 1020 .max_tokens = cfg->max_tokens ? cfg->max_tokens : 128, 1021 }; 1022 if (!gen_cache_valid(p->g, cfg->scratch)) { 1023 if (!gen_compute_min_rules(&gc)) return KIT_GRAM_GEN_ERROR; 1024 gen_cache_mark(p->g, cfg->scratch); 1025 } 1026 1027 /* On the first generation step for this parser, seed the incremental stack 1028 * totals from whatever is already on the control stack (the start symbol). 1029 * Setting gen_min_rule arms the upkeep in ctl_push/ctl_pop. min_rule lives 1030 * in the caller's scratch and has identical contents across calls (it is a 1031 * function of the grammar), so refreshing the pointer each call is safe. */ 1032 bool gen_first = (p->gen_min_rule == NULL); 1033 p->gen_min_rule = gc.min_rule; 1034 if (gen_first) { 1035 p->gen_min_sum = 0; 1036 p->gen_rdepth = 0; 1037 const kit_gram_ctl* cb = cctl_buf(p); 1038 for (size_t i = 0; i < p->nctl; i++) { 1039 p->gen_min_sum += gen_entry_min(p, &cb[i]); 1040 if (cb[i].kind == C_REDUCE || cb[i].kind == C_PRATT_END) p->gen_rdepth++; 1041 } 1042 } 1043 1044 p->look = (KitGramToken){.kind = p->g->eof}; 1045 1046 unsigned steps = 0; 1047 while (p->nctl > 0) { 1048 if (++steps > KIT_GRAM_MAX_STEPS) { 1049 p->failed = true; 1050 return KIT_GRAM_GEN_ERROR; 1051 } 1052 if (gen_stack_min(&gc) > gen_remaining(&gc)) return KIT_GRAM_GEN_LIMIT; 1053 1054 kit_gram_ctl c = ctl_pop(p); 1055 switch (c.kind) { 1056 case C_SYM: { 1057 const KitGramSym* s = c.sym; 1058 switch (s->kind) { 1059 case KIT_GRAM_S_TERM: 1060 return gen_shift(p, cfg, s->tok, out); 1061 case KIT_GRAM_S_RULE: { 1062 KitGramGenStatus st = gen_expand_rule(&gc, s->rule); 1063 if (st == KIT_GRAM_GEN_ERROR || st == KIT_GRAM_GEN_LIMIT) { 1064 ctl_push(p, c); 1065 return st; 1066 } 1067 break; 1068 } 1069 case KIT_GRAM_S_REP: { 1070 val_push(p, do_list_empty(p)); 1071 kit_gram_ctl rep = {.kind = C_REP, .sym = s}; 1072 ctl_push(p, rep); 1073 break; 1074 } 1075 case KIT_GRAM_S_OPT: { 1076 size_t rest = gen_stack_min(&gc); 1077 size_t sub_min = gen_sym_min(&gc, &s->sub[0]); 1078 bool take = !gen_deep(&gc) && 1079 gen_add(sub_min, rest) <= gen_remaining(&gc) && 1080 gen_pick(cfg, 2) != 0; 1081 if (take) { 1082 kit_gram_ctl os = {.kind = C_OPTSOME}; 1083 ctl_push(p, os); 1084 ctl_push_sym(p, &s->sub[0]); 1085 } else { 1086 val_push(p, do_opt_none(p)); 1087 } 1088 break; 1089 } 1090 } 1091 break; 1092 } 1093 case C_REP: { 1094 size_t rest = gen_stack_min(&gc); 1095 size_t sub_min = gen_sym_min(&gc, &c.sym->sub[0]); 1096 bool take = !gen_deep(&gc) && c.prod < gc.max_repeat && sub_min > 0 && 1097 gen_add(sub_min, rest) <= gen_remaining(&gc) && 1098 gen_pick(cfg, 2) != 0; 1099 if (take) { 1100 kit_gram_ctl rep = { 1101 .kind = C_REP, .sym = c.sym, .prod = (uint16_t)(c.prod + 1)}; 1102 kit_gram_ctl lp = {.kind = C_LISTPUSH}; 1103 ctl_push(p, rep); 1104 ctl_push(p, lp); 1105 ctl_push_sym(p, &c.sym->sub[0]); 1106 } 1107 break; 1108 } 1109 case C_LISTPUSH: { 1110 KitGramSem item = val_pop(p); 1111 KitGramSem list = val_pop(p); 1112 val_push(p, do_list_push(p, list, item)); 1113 break; 1114 } 1115 case C_OPTSOME: { 1116 KitGramSem item = val_pop(p); 1117 val_push(p, do_opt_some(p, item)); 1118 break; 1119 } 1120 case C_REDUCE: 1121 reduce_named(p, c.rule, c.prod, c.vbase); 1122 break; 1123 case C_PRATT_EXPR: { 1124 const KitGramRule* r = &p->g->rules[c.rule]; 1125 const KitGramPratt* pt = r->pratt; 1126 size_t rest = gen_stack_min(&gc); 1127 size_t primary_min = gc.min_rule[pt->primary]; 1128 size_t count = 0; 1129 if (!gen_deep(&gc)) { 1130 for (uint16_t oi = 0; oi < pt->nops; oi++) { 1131 const KitGramPrattOp* op = &pt->ops[oi]; 1132 if (gen_prefix_op(op) && 1133 gen_add(gen_add(1, primary_min), rest) <= gen_remaining(&gc)) 1134 count++; 1135 } 1136 } 1137 size_t pick = count ? gen_pick(cfg, count + 1) : 0; 1138 if (pick == 0) { 1139 kit_gram_ctl after = {.kind = C_PRATT_AFTER_PRIMARY, 1140 .rule = c.rule, 1141 .prod = pt->primary_prod, 1142 .min_bp = c.min_bp, 1143 .vbase = c.vbase, 1144 .nkids = c.nkids}; 1145 ctl_push(p, after); 1146 int prod = gen_choose_prod(&gc, pt->primary); 1147 if (prod < 0) { 1148 if (p->nctl > 0) (void)ctl_pop(p); 1149 ctl_push(p, c); 1150 return KIT_GRAM_GEN_LIMIT; 1151 } 1152 expand(p, pt->primary, prod, false); 1153 } else { 1154 pick--; 1155 for (uint16_t oi = 0; oi < pt->nops; oi++) { 1156 const KitGramPrattOp* op = &pt->ops[oi]; 1157 if (gen_prefix_op(op) && 1158 gen_add(gen_add(1, primary_min), rest) <= gen_remaining(&gc)) { 1159 if (pick-- == 0) { 1160 kit_gram_ctl after = {.kind = C_PRATT_AFTER_PREFIX, 1161 .rule = c.rule, 1162 .prod = op->prod, 1163 .min_bp = c.min_bp, 1164 .vbase = c.vbase, 1165 .nkids = c.nkids}; 1166 kit_gram_ctl child = {.kind = C_PRATT_EXPR, 1167 .rule = c.rule, 1168 .min_bp = op->rbp, 1169 .vbase = c.vbase + 1, 1170 .nkids = c.nkids}; 1171 ctl_push(p, after); 1172 ctl_push(p, child); 1173 if (p->failed) return KIT_GRAM_GEN_ERROR; 1174 return gen_shift(p, cfg, op->tok, out); 1175 } 1176 } 1177 } 1178 } 1179 break; 1180 } 1181 case C_PRATT_LOOP: { 1182 const KitGramRule* r = &p->g->rules[c.rule]; 1183 const KitGramPratt* pt = r->pratt; 1184 size_t rest = gen_stack_min(&gc); 1185 size_t primary_min = gc.min_rule[pt->primary]; 1186 size_t count = 0; 1187 if (!gen_deep(&gc) && c.prod < gc.max_repeat) { 1188 for (uint16_t oi = 0; oi < pt->nops; oi++) { 1189 const KitGramPrattOp* op = &pt->ops[oi]; 1190 if (gen_prefix_op(op) || op->lbp <= c.min_bp) continue; 1191 if (gen_add(gen_op_cost(&gc, op, primary_min), rest) <= 1192 gen_remaining(&gc)) 1193 count++; 1194 } 1195 } 1196 size_t pick = count ? gen_pick(cfg, count + 1) : 0; 1197 if (pick == 0) break; 1198 pick--; 1199 uint16_t reps = (uint16_t)(c.prod + 1); 1200 for (uint16_t oi = 0; oi < pt->nops; oi++) { 1201 const KitGramPrattOp* op = &pt->ops[oi]; 1202 if (gen_prefix_op(op) || op->lbp <= c.min_bp) continue; 1203 if (gen_add(gen_op_cost(&gc, op, primary_min), rest) <= 1204 gen_remaining(&gc)) { 1205 if (pick-- == 0) { 1206 if (gen_postfix_op(op)) { 1207 KitGramGenStatus st = gen_shift(p, cfg, op->tok, out); 1208 if (st != KIT_GRAM_GEN_TOKEN) return st; 1209 pratt_reduce_at(p, c.rule, op->prod, c.vbase, 2); 1210 if (p->failed) return KIT_GRAM_GEN_ERROR; 1211 kit_gram_ctl loop = {.kind = C_PRATT_LOOP, 1212 .rule = c.rule, 1213 .min_bp = c.min_bp, 1214 .vbase = c.vbase, 1215 .prod = reps}; 1216 ctl_push(p, loop); 1217 return p->failed ? KIT_GRAM_GEN_ERROR : KIT_GRAM_GEN_TOKEN; 1218 } 1219 if (op->role == KIT_GRAM_PO_TERNARY) { 1220 kit_gram_ctl mid = {.kind = C_PRATT_AFTER_TERNARY_MID, 1221 .rule = c.rule, 1222 .prod = op->prod, 1223 .min_bp = c.min_bp, 1224 .vbase = c.vbase, 1225 .nkids = reps}; 1226 kit_gram_ctl child = {.kind = C_PRATT_EXPR, 1227 .rule = c.rule, 1228 .min_bp = 0, 1229 .vbase = c.vbase + 2, 1230 .nkids = reps}; 1231 ctl_push(p, mid); 1232 ctl_push(p, child); 1233 if (p->failed) return KIT_GRAM_GEN_ERROR; 1234 return gen_shift(p, cfg, op->tok, out); 1235 } 1236 if (op->role == KIT_GRAM_PO_CIRCUMFIX) { 1237 kit_gram_ctl after = {.kind = C_PRATT_AFTER_CIRCUMFIX, 1238 .rule = c.rule, 1239 .prod = op->prod, 1240 .min_bp = c.min_bp, 1241 .vbase = c.vbase, 1242 .nkids = reps}; 1243 ctl_push(p, after); 1244 ctl_push_sym(p, &op->inner); 1245 if (p->failed) return KIT_GRAM_GEN_ERROR; 1246 return gen_shift(p, cfg, op->tok, out); 1247 } 1248 kit_gram_ctl after = {.kind = C_PRATT_AFTER_INFIX, 1249 .rule = c.rule, 1250 .prod = op->prod, 1251 .min_bp = c.min_bp, 1252 .vbase = c.vbase, 1253 .nkids = reps}; 1254 kit_gram_ctl child = {.kind = C_PRATT_EXPR, 1255 .rule = c.rule, 1256 .min_bp = op->rbp, 1257 .vbase = c.vbase + 2, 1258 .nkids = reps}; 1259 ctl_push(p, after); 1260 ctl_push(p, child); 1261 if (p->failed) return KIT_GRAM_GEN_ERROR; 1262 return gen_shift(p, cfg, op->tok, out); 1263 } 1264 } 1265 } 1266 break; 1267 } 1268 case C_PRATT_AFTER_PRIMARY: { 1269 size_t n = p->nval - c.vbase; 1270 pratt_reduce_at(p, c.rule, c.prod, c.vbase, n); 1271 if (p->failed) return KIT_GRAM_GEN_ERROR; 1272 kit_gram_ctl loop = {.kind = C_PRATT_LOOP, 1273 .rule = c.rule, 1274 .min_bp = c.min_bp, 1275 .vbase = c.vbase, 1276 .prod = c.nkids}; 1277 ctl_push(p, loop); 1278 break; 1279 } 1280 case C_PRATT_AFTER_PREFIX: { 1281 pratt_reduce_at(p, c.rule, c.prod, c.vbase, 2); 1282 if (p->failed) return KIT_GRAM_GEN_ERROR; 1283 kit_gram_ctl loop = {.kind = C_PRATT_LOOP, 1284 .rule = c.rule, 1285 .min_bp = c.min_bp, 1286 .vbase = c.vbase, 1287 .prod = c.nkids}; 1288 ctl_push(p, loop); 1289 break; 1290 } 1291 case C_PRATT_AFTER_INFIX: { 1292 pratt_reduce_at(p, c.rule, c.prod, c.vbase, 3); 1293 if (p->failed) return KIT_GRAM_GEN_ERROR; 1294 kit_gram_ctl loop = {.kind = C_PRATT_LOOP, 1295 .rule = c.rule, 1296 .min_bp = c.min_bp, 1297 .vbase = c.vbase, 1298 .prod = c.nkids}; 1299 ctl_push(p, loop); 1300 break; 1301 } 1302 case C_PRATT_AFTER_TERNARY_MID: { 1303 const KitGramPratt* pt = p->g->rules[c.rule].pratt; 1304 const KitGramPrattOp* op = pratt_op_by_prod(pt, c.prod); 1305 kit_gram_ctl els = {.kind = C_PRATT_AFTER_TERNARY_ELSE, 1306 .rule = c.rule, 1307 .prod = c.prod, 1308 .min_bp = c.min_bp, 1309 .vbase = c.vbase, 1310 .nkids = c.nkids}; 1311 kit_gram_ctl child = {.kind = C_PRATT_EXPR, 1312 .rule = c.rule, 1313 .min_bp = op->rbp, 1314 .vbase = c.vbase + 4, 1315 .nkids = c.nkids}; 1316 ctl_push(p, els); 1317 ctl_push(p, child); 1318 if (p->failed) return KIT_GRAM_GEN_ERROR; 1319 return gen_shift(p, cfg, op->tok2, out); 1320 } 1321 case C_PRATT_AFTER_TERNARY_ELSE: { 1322 pratt_reduce_at(p, c.rule, c.prod, c.vbase, 5); 1323 if (p->failed) return KIT_GRAM_GEN_ERROR; 1324 kit_gram_ctl loop = {.kind = C_PRATT_LOOP, 1325 .rule = c.rule, 1326 .min_bp = c.min_bp, 1327 .vbase = c.vbase, 1328 .prod = c.nkids}; 1329 ctl_push(p, loop); 1330 break; 1331 } 1332 case C_PRATT_AFTER_CIRCUMFIX: { 1333 const KitGramPratt* pt = p->g->rules[c.rule].pratt; 1334 const KitGramPrattOp* op = pratt_op_by_prod(pt, c.prod); 1335 KitGramGenStatus st = gen_shift(p, cfg, op->tok2, out); 1336 if (st != KIT_GRAM_GEN_TOKEN) return st; 1337 pratt_reduce_at(p, c.rule, c.prod, c.vbase, 4); 1338 if (p->failed) return KIT_GRAM_GEN_ERROR; 1339 kit_gram_ctl loop = {.kind = C_PRATT_LOOP, 1340 .rule = c.rule, 1341 .min_bp = c.min_bp, 1342 .vbase = c.vbase, 1343 .prod = c.nkids}; 1344 ctl_push(p, loop); 1345 return p->failed ? KIT_GRAM_GEN_ERROR : KIT_GRAM_GEN_TOKEN; 1346 } 1347 case C_PRATT_END: 1348 if (!p->g->rules[c.rule].hidden && p->cfg.actions && 1349 p->cfg.actions->exit) 1350 p->cfg.actions->exit(p->cfg.ud, c.rule, c.prod); 1351 break; 1352 } 1353 if (p->failed) return KIT_GRAM_GEN_ERROR; 1354 } 1355 1356 p->done = true; 1357 p->result = p->nval ? p->cfg.val_stack[p->nval - 1] : NULL; 1358 return KIT_GRAM_GEN_DONE; 1359 } 1360 1361 /* ---- public API ---- */ 1362 void kit_gram_parser_init(KitGramParser* mem, const KitGramGrammar* g, 1363 const KitGramConfig* cfg) { 1364 kit_gram_parser_impl* p = impl(mem); 1365 *p = (kit_gram_parser_impl){.g = g, .cfg = *cfg}; /* zeroes depths/marks/flags */ 1366 p->start_sym = (KitGramSym){.kind = KIT_GRAM_S_RULE, .rule = g->start}; 1367 if (!cfg->ctl_stack || !cfg->val_stack || cfg->ctl_cap == 0 || 1368 cfg->val_cap == 0) { 1369 p->failed = true; /* unusable config: every push/finish reports error */ 1370 return; 1371 } 1372 ctl_push_sym(p, &p->start_sym); 1373 } 1374 1375 static KitGramStatus report_simple(kit_gram_parser_impl* p, KitGramTokenKind expected) { 1376 p->nerrors++; 1377 if (p->cfg.actions && p->cfg.actions->on_error) { 1378 p->scratch = expected; 1379 KitGramError e = {.found = p->look, 1380 .expected = &p->scratch, 1381 .nexpected = 1, 1382 .in_rule = cur_rule(p)}; 1383 p->cfg.actions->on_error(p->cfg.ud, &e); 1384 } 1385 p->failed = true; 1386 return KIT_GRAM_PARSE_ERROR; 1387 } 1388 1389 KitGramStatus kit_gram_parser_push(KitGramParser* pp, KitGramToken t) { 1390 kit_gram_parser_impl* p = impl(pp); 1391 if (p->failed) return KIT_GRAM_PARSE_ERROR; 1392 if (p->done) { 1393 p->look = t; 1394 return report_simple(p, p->g->eof); 1395 } /* trailing input */ 1396 p->look = t; 1397 p->have_look = true; 1398 switch (run(p)) { 1399 case RUN_SUSPEND: 1400 return KIT_GRAM_NEED_MORE; 1401 case RUN_ERROR: 1402 return KIT_GRAM_PARSE_ERROR; 1403 case RUN_DONE: /* derived the start symbol but a real token remains */ 1404 return (t.kind == p->g->eof) ? KIT_GRAM_PARSE_ACCEPT 1405 : report_simple(p, p->g->eof); 1406 } 1407 return KIT_GRAM_PARSE_ERROR; 1408 } 1409 1410 /* Feed a run of tokens in one call, amortizing the per-token entry boundary 1411 * over the batch. Identical in effect to calling kit_gram_parser_push for each 1412 * token: stops early on accept/error, otherwise returns KIT_GRAM_NEED_MORE after 1413 * consuming all n. */ 1414 KitGramStatus kit_gram_parser_push_n(KitGramParser* pp, const KitGramToken* toks, 1415 size_t n) { 1416 kit_gram_parser_impl* p = impl(pp); 1417 for (size_t i = 0; i < n; i++) { 1418 if (p->failed) return KIT_GRAM_PARSE_ERROR; 1419 if (p->done) { 1420 p->look = toks[i]; 1421 return report_simple(p, p->g->eof); 1422 } 1423 p->look = toks[i]; 1424 p->have_look = true; 1425 switch (run(p)) { 1426 case RUN_SUSPEND: 1427 continue; 1428 case RUN_ERROR: 1429 return KIT_GRAM_PARSE_ERROR; 1430 case RUN_DONE: 1431 return (toks[i].kind == p->g->eof) ? KIT_GRAM_PARSE_ACCEPT 1432 : report_simple(p, p->g->eof); 1433 } 1434 return KIT_GRAM_PARSE_ERROR; 1435 } 1436 return KIT_GRAM_NEED_MORE; 1437 } 1438 1439 KitGramStatus kit_gram_parser_finish(KitGramParser* pp) { 1440 kit_gram_parser_impl* p = impl(pp); 1441 if (p->failed) return KIT_GRAM_PARSE_ERROR; 1442 if (p->done) return KIT_GRAM_PARSE_ACCEPT; 1443 p->look = (KitGramToken){.kind = p->g->eof}; 1444 p->have_look = true; 1445 switch (run(p)) { 1446 case RUN_DONE: 1447 return KIT_GRAM_PARSE_ACCEPT; 1448 case RUN_ERROR: 1449 return KIT_GRAM_PARSE_ERROR; 1450 case RUN_SUSPEND: 1451 return report_simple(p, p->g->eof); /* unexpected end of input */ 1452 } 1453 return KIT_GRAM_PARSE_ERROR; 1454 } 1455 1456 KitGramSem kit_gram_parser_result(const KitGramParser* p) { return cimpl(p)->result; } 1457 size_t kit_gram_parser_errors(const KitGramParser* p) { return cimpl(p)->nerrors; } 1458 bool kit_gram_parser_overflowed(const KitGramParser* p) { return cimpl(p)->overflow; } 1459 size_t kit_gram_parser_ctl_hwm(const KitGramParser* p) { return cimpl(p)->ctl_hwm; } 1460 size_t kit_gram_parser_val_hwm(const KitGramParser* p) { return cimpl(p)->val_hwm; } 1461 1462 /* Stack sizing is per nesting level: a frame holds at most max_nsyms symbols 1463 * plus its reduce marker, plus a couple of transient builder entries for an 1464 * in-flight postfix wrapper. max_nsyms (the longest production) comes straight 1465 * from the tables, so no generated constants are needed. */ 1466 void kit_gram_stack_bounds(const KitGramGrammar* g, size_t max_depth, size_t* ctl_cap, 1467 size_t* val_cap) { 1468 size_t max_nsyms = 1; 1469 bool has_pratt = false; 1470 for (uint16_t r = 0; r < g->nrules; r++) { 1471 if (g->rules[r].is_pratt) has_pratt = true; 1472 for (uint16_t pr = 0; pr < g->rules[r].nprods; pr++) { 1473 size_t L = g->rules[r].prods[pr].nsyms; 1474 if (L > max_nsyms) max_nsyms = L; 1475 } 1476 } 1477 if (has_pratt) 1478 max_nsyms += 4; /* episode, loop, and pending mixfix operator frames */ 1479 if (ctl_cap) 1480 *ctl_cap = max_depth * (max_nsyms + 3) + 2; /* +start symbol + margin */ 1481 if (val_cap) *val_cap = max_depth * (max_nsyms + 1) + 2; 1482 } 1483 KitGramRuleId kit_gram_parser_context(const KitGramParser* p) { 1484 return cur_rule(cimpl(p)); 1485 } 1486 size_t kit_gram_parser_depth(const KitGramParser* pp) { 1487 const kit_gram_parser_impl* p = cimpl(pp); 1488 const kit_gram_ctl* cb = cctl_buf(p); 1489 size_t d = 0; 1490 for (size_t i = 0; i < p->nctl; i++) 1491 if ((cb[i].kind == C_REDUCE || cb[i].kind == C_PRATT_END) && 1492 !p->g->rules[cb[i].rule].hidden) 1493 d++; 1494 return d; 1495 } 1496 1497 static KitGramFrame frame_of(const kit_gram_ctl* c) { 1498 return (KitGramFrame){.rule = c->rule, .prod = (int)c->prod, .start = c->start}; 1499 } 1500 size_t kit_gram_parser_frames(const KitGramParser* pp, KitGramFrame* out, size_t cap) { 1501 const kit_gram_parser_impl* p = cimpl(pp); 1502 const kit_gram_ctl* cb = cctl_buf(p); 1503 size_t n = 0; /* scan top -> bottom = innermost first */ 1504 for (size_t i = p->nctl; i > 0; i--) 1505 if ((cb[i - 1].kind == C_REDUCE || cb[i - 1].kind == C_PRATT_END) && 1506 !p->g->rules[cb[i - 1].rule].hidden) { 1507 if (n < cap) out[n] = frame_of(&cb[i - 1]); 1508 n++; 1509 } 1510 return n; 1511 } 1512 bool kit_gram_parser_frame(const KitGramParser* pp, size_t idx, KitGramFrame* out) { 1513 const kit_gram_parser_impl* p = cimpl(pp); 1514 const kit_gram_ctl* cb = cctl_buf(p); 1515 size_t n = 0; 1516 for (size_t i = p->nctl; i > 0; i--) 1517 if ((cb[i - 1].kind == C_REDUCE || cb[i - 1].kind == C_PRATT_END) && 1518 !p->g->rules[cb[i - 1].rule].hidden && n++ == idx) { 1519 *out = frame_of(&cb[i - 1]); 1520 return true; 1521 } 1522 return false; 1523 } 1524 const char* kit_gram_parser_rule_name(const KitGramParser* pp, KitGramRuleId r) { 1525 const kit_gram_parser_impl* p = cimpl(pp); 1526 return (r < p->g->nrules && p->g->rules[r].name) ? p->g->rules[r].name : "?"; 1527 } 1528 const char* kit_gram_parser_tok_name(const KitGramParser* pp, KitGramTokenKind k) { 1529 const kit_gram_parser_impl* p = cimpl(pp); 1530 return (p->g->tok_names && k < p->g->ntoks) ? p->g->tok_names[k] : "?"; 1531 } 1532 1533 bool kit_gram_parser_expects(const KitGramParser* pp, KitGramTokenKind k) { 1534 const kit_gram_parser_impl* p = cimpl(pp); 1535 const kit_gram_ctl* cb = cctl_buf(p); 1536 for (size_t i = p->nctl; i > 0; i--) { 1537 kit_gram_ctl c = cb[i - 1]; 1538 if (c.kind == C_PRATT_EXPR) { 1539 const KitGramRule* r = &p->g->rules[c.rule]; 1540 return contains(r->first, r->nfirst, k); 1541 } 1542 if (c.kind == C_PRATT_LOOP) { 1543 const KitGramRule* r = &p->g->rules[c.rule]; 1544 if (pratt_cont(r->pratt, k, c.min_bp)) return true; 1545 continue; 1546 } 1547 if (c.kind == C_PRATT_AFTER_TERNARY_MID || 1548 c.kind == C_PRATT_AFTER_CIRCUMFIX) { 1549 const KitGramRule* r = &p->g->rules[c.rule]; 1550 const KitGramPrattOp* op = pratt_op_by_prod(r->pratt, c.prod); 1551 return op && k == op->tok2; 1552 } 1553 if (c.kind != C_SYM) continue; 1554 if (c.sym->kind == KIT_GRAM_S_TERM) return c.sym->tok == k; 1555 if (c.sym->kind == KIT_GRAM_S_RULE) { 1556 const KitGramRule* r = &p->g->rules[c.sym->rule]; 1557 return contains(r->first, r->nfirst, k); 1558 } 1559 if (c.sym->kind == KIT_GRAM_S_REP || c.sym->kind == KIT_GRAM_S_OPT) 1560 return set_in(p->g, c.sym->first, k); 1561 } 1562 return false; 1563 }