ll1.c (43879B)
1 #include "internal.h" 2 3 static void prod_append(Builder* b, Prod* prod, Sym sym) { 4 if (prod->nsyms == prod->cap) { 5 prod->cap = prod->cap ? prod->cap * 2 : 4; 6 prod->syms = xrealloc(b->ctx, prod->syms, prod->cap * sizeof *prod->syms); 7 } 8 prod->syms[prod->nsyms++] = sym; 9 } 10 11 static void rule_append_prod(Builder* b, Rule* rule, Prod prod) { 12 if (rule->nprods == rule->cap_prods) { 13 rule->cap_prods = rule->cap_prods ? rule->cap_prods * 2 : 4; 14 rule->prods = 15 xrealloc(b->ctx, rule->prods, rule->cap_prods * sizeof *rule->prods); 16 } 17 rule->prods[rule->nprods++] = prod; 18 } 19 20 static void pratt_append_op(Builder* b, PrattInfo* info, PrattOp op) { 21 if (info->nops == info->cap) { 22 info->cap = info->cap ? info->cap * 2 : 4; 23 info->ops = xrealloc(b->ctx, info->ops, info->cap * sizeof *info->ops); 24 } 25 info->ops[info->nops++] = op; 26 } 27 28 static void builder_append_rule(Builder* b, Rule rule) { 29 if (b->nrules == b->cap_rules) { 30 b->cap_rules = b->cap_rules ? b->cap_rules * 2 : 16; 31 b->rules = xrealloc(b->ctx, b->rules, b->cap_rules * sizeof *b->rules); 32 } 33 name_index_put(b->ctx, &b->rule_index, rule.name, (int)b->nrules); 34 b->rules[b->nrules++] = rule; 35 } 36 37 static void builder_append_token(Builder* b, TokenDef tok) { 38 if (b->ntokens == b->cap_tokens) { 39 b->cap_tokens = b->cap_tokens ? b->cap_tokens * 2 : 16; 40 b->tokens = xrealloc(b->ctx, b->tokens, b->cap_tokens * sizeof *b->tokens); 41 } 42 name_index_put(b->ctx, &b->token_index, tok.name, (int)b->ntokens); 43 b->tokens[b->ntokens++] = tok; 44 } 45 46 static void builder_append_literal_rec(Builder* b, LexRecognizer rec) { 47 if (b->nliteral_recs == b->cap_literal_recs) { 48 b->cap_literal_recs = b->cap_literal_recs ? b->cap_literal_recs * 2 : 8; 49 b->literal_recs = xrealloc(b->ctx, b->literal_recs, 50 b->cap_literal_recs * sizeof *b->literal_recs); 51 } 52 b->literal_recs[b->nliteral_recs++] = rec; 53 } 54 55 static void builder_append_kw_binding(Builder* b, KeywordBinding kb) { 56 if (b->nkw_bindings == b->cap_kw_bindings) { 57 b->cap_kw_bindings = b->cap_kw_bindings ? b->cap_kw_bindings * 2 : 8; 58 b->kw_bindings = xrealloc(b->ctx, b->kw_bindings, 59 b->cap_kw_bindings * sizeof *b->kw_bindings); 60 } 61 b->kw_bindings[b->nkw_bindings++] = kb; 62 } 63 64 /* All lookup keys below are interned literal bytes (lit.s is the canonical 65 * per-(bytes,len) pointer), so the index maps compare by pointer identity. */ 66 static KeywordBinding* find_keyword_binding(Builder* b, Str lit) { 67 int idx; 68 return name_index_find(&b->kw_literal_index, lit.s, &idx) 69 ? &b->kw_bindings[idx] 70 : NULL; 71 } 72 73 typedef struct { 74 const char *lit, *name; 75 } PunctName; 76 static const PunctName punct_names[] = { 77 {"+", "PLUS"}, {"-", "MINUS"}, {"*", "STAR"}, {"/", "SLASH"}, 78 {"%", "PERCENT"}, {"(", "LPAREN"}, {")", "RPAREN"}, {"[", "LBRACKET"}, 79 {"]", "RBRACKET"}, {"{", "LBRACE"}, {"}", "RBRACE"}, {",", "COMMA"}, 80 {".", "DOT"}, {":", "COLON"}, {";", "SEMI"}, {"?", "QUESTION"}, 81 {"!", "BANG"}, {"=", "EQ"}, {"==", "EQEQ"}, {"!=", "BANGEQ"}, 82 {"<", "LT"}, {">", "GT"}, {"<=", "LE"}, {">=", "GE"}, 83 {"&&", "ANDAND"}, {"||", "OROR"}, {"&", "AMP"}, {"|", "PIPE"}, 84 {"^", "CARET"}, {"~", "TILDE"}, {"->", "ARROW"}, {"=>", "FATARROW"}, 85 {"::", "COLONCOLON"}, 86 }; 87 88 static char* literal_token_name(GramgenContext* ctx, Str lit) { 89 for (size_t i = 0; i < sizeof punct_names / sizeof punct_names[0]; i++) { 90 if (str_eq_c(lit, punct_names[i].lit)) 91 return xstrdup(ctx, punct_names[i].name); 92 } 93 if (!is_c_ident_str(lit)) return NULL; 94 char* name = xmalloc(ctx, lit.len + 1); 95 for (size_t i = 0; i < lit.len; i++) 96 name[i] = (char)toupper((unsigned char)lit.s[i]); 97 name[lit.len] = '\0'; 98 if (!is_token_name(name)) { 99 xfree(ctx, name); 100 return NULL; 101 } 102 return name; 103 } 104 105 static AstRule* find_ast_rule(Builder* b, const char* name) { 106 for (size_t i = 0; i < b->pg->nrules; i++) 107 if (b->pg->rules[i]->name == name) return b->pg->rules[i]; 108 return NULL; 109 } 110 111 static int find_rule_index(Builder* b, const char* name) { 112 int out = -1; 113 return name_index_find(&b->rule_index, name, &out) ? out : -1; 114 } 115 116 static int find_token_index(Builder* b, const char* name) { 117 int out = -1; 118 return name_index_find(&b->token_index, name, &out) ? out : -1; 119 } 120 121 static TokenDecl* find_literal_decl(Builder* b, Str lit) { 122 int idx; 123 return name_index_find(&b->literal_decl_index, lit.s, &idx) 124 ? b->pg->token_decls[idx] 125 : NULL; 126 } 127 128 static int display_is_name(TokenDef* tok) { 129 return str_eq_c(tok->display, tok->name); 130 } 131 132 static int register_token(Builder* b, const char* name, Str display, Loc loc) { 133 GramgenContext* ctx = b->ctx; 134 name = intern_c(ctx, name); 135 if (!is_token_name(name)) 136 kit_gram_error(ctx, loc, 137 "invalid token name %s; token names must be all uppercase", 138 name); 139 if (strcmp(name, "EOF") == 0 || strcmp(name, "__COUNT") == 0) 140 kit_gram_error(ctx, loc, "reserved token name %s", name); 141 int old_idx = find_token_index(b, name); 142 if (old_idx >= 0) { 143 TokenDef* old = &b->tokens[old_idx]; 144 if (display_is_name(old) && !str_eq_c(display, name)) { 145 old->display = str_dup_len(ctx, display.s, display.len); 146 } else if (!str_eq_c(display, name) && !str_eq(old->display, display)) { 147 char* q = c_string_str(ctx, old->display); 148 kit_gram_error(ctx, loc, "token %s is already bound to %s", name, q); 149 } 150 return old_idx; 151 } 152 Str stored_display = str_eq_c(display, name) 153 ? str_from_owned((char*)name, strlen(name)) 154 : str_dup_len(ctx, display.s, display.len); 155 TokenDef tok = {.name = (char*)name, .display = stored_display, .loc = loc}; 156 builder_append_token(b, tok); 157 return (int)b->ntokens - 1; 158 } 159 160 int kit_gram_token_for_ident(Builder* b, const char* name, Loc loc) { 161 name = intern_c(b->ctx, name); 162 return register_token(b, name, str_from_owned((char*)name, strlen(name)), 163 loc); 164 } 165 166 int kit_gram_next_rec_seq(Builder* b) { return b->rec_seq++; } 167 168 static AstLexAlt* single_literal_lex_alt(GramgenContext* ctx, Str lit, 169 Loc loc) { 170 AstLexNode* node = ast_lex_node_new(ctx, LEX_LITERAL, loc); 171 node->value = str_dup_len(ctx, lit.s, lit.len); 172 node->scalar_value = str_dup_len(ctx, lit.s, lit.len); 173 AstLexSeq* seq = ast_lex_seq_new(ctx, loc); 174 ast_lex_seq_append(seq, node); 175 AstLexAlt* alt = ast_lex_alt_new(ctx, loc); 176 ast_lex_alt_append(alt, seq); 177 return alt; 178 } 179 180 static void note_literal_recognizer(Builder* b, Str lit, int tok, Loc loc) { 181 int idx; 182 if (name_index_find(&b->literal_rec_index, lit.s, &idx)) { 183 LexRecognizer* old = &b->literal_recs[idx]; 184 if (loc.line < old->loc.line || 185 (loc.line == old->loc.line && loc.col < old->loc.col)) { 186 old->loc = loc; 187 old->seq = kit_gram_next_rec_seq(b); 188 } 189 return; 190 } 191 LexRecognizer rec = { 192 .name = b->tokens[tok].name, 193 .loc = loc, 194 .alts = single_literal_lex_alt(b->ctx, lit, loc), 195 .tok = tok, 196 .skip = 0, 197 .seq = kit_gram_next_rec_seq(b), 198 .has_literal_key = 1, 199 .literal_key = str_dup_len(b->ctx, lit.s, lit.len), 200 }; 201 builder_append_literal_rec(b, rec); 202 name_index_put(b->ctx, &b->literal_rec_index, lit.s, 203 (int)b->nliteral_recs - 1); 204 } 205 206 static int token_for_literal(Builder* b, Str lit, Loc loc) { 207 /* A literal declared as a %keywords entry resolves to that token and is not 208 * given a DFA recognizer (it lives in the host's keyword table instead). */ 209 KeywordBinding* kb = find_keyword_binding(b, lit); 210 if (kb) return kb->tok; 211 TokenDecl* decl = find_literal_decl(b, lit); 212 if (decl) { 213 decl->used = 1; 214 int tok = register_token(b, decl->name, lit, loc); 215 note_literal_recognizer(b, lit, tok, decl->loc); 216 return tok; 217 } 218 char* name = literal_token_name(b->ctx, lit); 219 if (name) { 220 int tok = register_token(b, name, lit, loc); 221 note_literal_recognizer(b, lit, tok, loc); 222 xfree(b->ctx, name); 223 return tok; 224 } 225 char* q = c_string_str(b->ctx, lit); 226 kit_gram_error( 227 b->ctx, loc, 228 "literal %s needs a token declaration; add %%token TOKEN_NAME = %s", q, 229 q); 230 return -1; 231 } 232 233 /* Find the literal a %token declaration bound to `name`, for a bare-name 234 * %keywords entry (`WHILE;` needs `%token WHILE = "while";`). */ 235 static int find_decl_literal(Builder* b, const char* name, Str* out) { 236 int idx; 237 if (!name_index_find(&b->decl_name_index, name, &idx)) return 0; 238 TokenDecl* d = b->pg->token_decls[idx]; 239 d->used = 1; 240 *out = d->literal; 241 return 1; 242 } 243 244 /* Collect %keywords declarations before parser rules: register each entry's 245 * token and record its (lexeme -> token, host, lexer) binding. Done early so a 246 * parser literal matching a keyword resolves to the keyword token (and gets no 247 * DFA recognizer). The host kind and DFA validation happen later, in 248 * prepare_lexer, once the lexer is built. */ 249 static void collect_keywords(Builder* b) { 250 GramgenContext* ctx = b->ctx; 251 for (size_t bi = 0; bi < b->pg->nlex_blocks; bi++) { 252 AstLexBlock* block = b->pg->lex_blocks[bi]; 253 for (size_t li = 0; li < block->nlines; li++) { 254 AstLexLine* line = block->lines[li]; 255 if (line->kind != LEX_LINE_KEYWORDS) continue; 256 for (size_t ei = 0; ei < line->nkw_entries; ei++) { 257 AstKwEntry* e = &line->kw_entries[ei]; 258 Str lit; 259 int tok; 260 if (e->name && e->has_literal) { /* NAME = "lit" */ 261 lit = e->literal; 262 tok = register_token( 263 b, e->name, str_from_owned(e->name, strlen(e->name)), e->loc); 264 } else if (e->name) { /* NAME (bare) */ 265 if (!find_decl_literal(b, e->name, &lit)) 266 kit_gram_error( 267 ctx, e->loc, 268 "keyword %s needs a literal; write %s = \"...\" or add " 269 "%%token %s = \"...\"", 270 e->name, e->name, e->name); 271 tok = register_token( 272 b, e->name, str_from_owned(e->name, strlen(e->name)), e->loc); 273 } else { /* "lit" (bare) */ 274 lit = e->literal; 275 TokenDecl* decl = find_literal_decl(b, lit); 276 if (decl) { 277 decl->used = 1; 278 tok = register_token(b, decl->name, lit, e->loc); 279 } else { 280 char* name = literal_token_name(ctx, lit); 281 if (!name) { 282 char* q = c_string_str(ctx, lit); 283 kit_gram_error(ctx, e->loc, 284 "keyword %s needs a token name; write NAME = %s", q, 285 q); 286 } 287 tok = register_token(b, name, lit, e->loc); 288 xfree(ctx, name); 289 } 290 } 291 if (lit.len == 0) 292 kit_gram_error(ctx, e->loc, "keyword literal must be non-empty"); 293 if (find_keyword_binding(b, lit)) { 294 char* q = c_string_str(ctx, lit); 295 kit_gram_error(ctx, e->loc, "duplicate keyword %s", q); 296 } 297 KeywordBinding kb = {.literal = str_dup_len(ctx, lit.s, lit.len), 298 .tok = tok, 299 .host = line->name, 300 .group = block->name, 301 .loc = e->loc}; 302 builder_append_kw_binding(b, kb); 303 name_index_put(ctx, &b->kw_literal_index, lit.s, 304 (int)b->nkw_bindings - 1); 305 } 306 } 307 } 308 } 309 310 static Sym transform_factor(Builder* b, AstNode* node); 311 static Prod transform_seq(Builder* b, AstSeq* seq, Loc fallback); 312 313 static int new_hidden_rule(Builder* b, Loc loc) { 314 int idx = (int)b->nrules; 315 int hid = idx - (int)b->public_count; 316 Rule r; 317 memset(&r, 0, sizeof r); 318 char* name = xasprintf(b->ctx, "$group%d", hid); 319 r.name = intern_c(b->ctx, name); 320 xfree(b->ctx, name); 321 r.loc = loc; 322 r.public_rule = 0; 323 r.index = idx; 324 builder_append_rule(b, r); 325 return idx; 326 } 327 328 static int hidden_from_alts(Builder* b, AstAlt* alts, Loc loc, const char* what, 329 int allow_empty) { 330 int ridx = new_hidden_rule(b, loc); 331 for (size_t i = 0; i < alts->nseqs; i++) { 332 Prod prod = transform_seq(b, alts->seqs[i], loc); 333 if (prod.nsyms > 1 || (!allow_empty && prod.nsyms == 0)) 334 kit_gram_error(b->ctx, loc, 335 "%s body must be a single symbol; name it as a rule", what); 336 rule_append_prod(b, &b->rules[ridx], prod); 337 } 338 return ridx; 339 } 340 341 static Sym single_symbol_from_alts(Builder* b, AstAlt* alts, Loc loc, 342 const char* what) { 343 if (alts->nseqs == 1 && alts->seqs[0]->nitems == 1) { 344 Sym sub = transform_factor(b, alts->seqs[0]->items[0]); 345 if (sub.kind != SYM_TERM && sub.kind != SYM_RULE) 346 kit_gram_error(b->ctx, loc, 347 "%s body must be a terminal or rule; name it as a rule", 348 what); 349 return sub; 350 } 351 int ridx = hidden_from_alts(b, alts, loc, what, 0); 352 Sym out = {.kind = SYM_RULE, 353 .loc = loc, 354 .value = ridx, 355 .set_index = -1, 356 .sub_array_id = -1}; 357 return out; 358 } 359 360 static Sym transform_factor(Builder* b, AstNode* node) { 361 Sym out; 362 memset(&out, 0, sizeof out); 363 out.loc = node->loc; 364 out.set_index = -1; 365 out.sub_array_id = -1; 366 switch (node->kind) { 367 case AST_NAME: { 368 char* name = node->value.s; 369 int ridx = find_rule_index(b, name); 370 if (ridx >= 0) { 371 out.kind = SYM_RULE; 372 out.value = ridx; 373 return out; 374 } 375 if (is_token_name(name)) { 376 out.kind = SYM_TERM; 377 out.value = kit_gram_token_for_ident(b, name, node->loc); 378 return out; 379 } 380 kit_gram_error(b->ctx, node->loc, "undefined nonterminal %s", name); 381 } 382 case AST_LITERAL: 383 out.kind = SYM_TERM; 384 out.value = token_for_literal(b, node->value, node->loc); 385 return out; 386 case AST_GROUP: 387 out.kind = SYM_RULE; 388 out.value = 389 hidden_from_alts(b, node->alts, node->loc, "parenthesized group", 1); 390 return out; 391 case AST_OPT: 392 case AST_REP: { 393 const char* what = node->kind == AST_OPT ? "optional" : "repetition"; 394 Sym sub = single_symbol_from_alts(b, node->alts, node->loc, what); 395 out.kind = node->kind == AST_OPT ? SYM_OPT : SYM_REP; 396 out.sub = xmalloc(b->ctx, sizeof *out.sub); 397 *out.sub = sub; 398 return out; 399 } 400 } 401 return out; 402 } 403 404 static Prod transform_seq(Builder* b, AstSeq* seq, Loc fallback) { 405 Prod prod; 406 memset(&prod, 0, sizeof prod); 407 prod.loc = seq->nitems ? seq->items[0]->loc : fallback; 408 for (size_t i = 0; i < seq->nitems; i++) 409 prod_append(b, &prod, transform_factor(b, seq->items[i])); 410 return prod; 411 } 412 413 char* kit_gram_pratt_prod_enum_name(GramgenContext* ctx, Builder* b, 414 const char* rule_name, const char* role, 415 int tok) { 416 Buf buf; 417 buf_init(ctx, &buf); 418 for (size_t i = 0; rule_name[i]; i++) { 419 char c = (char)toupper((unsigned char)rule_name[i]); 420 buf_appendn(&buf, &c, 1); 421 } 422 if (role == b->role.primary) { 423 buf_append(&buf, "_PRIMARY"); 424 } else { 425 buf_append(&buf, "_"); 426 for (size_t i = 0; role[i]; i++) { 427 char c = (char)toupper((unsigned char)role[i]); 428 buf_appendn(&buf, &c, 1); 429 } 430 buf_append(&buf, "_"); 431 buf_append(&buf, b->tokens[tok].name); 432 } 433 return buf_take(&buf); 434 } 435 436 static int token_for_pratt_atom(Builder* b, AstPrattAtom* atom) { 437 if (atom->kind == PRATT_LITERAL) 438 return token_for_literal(b, atom->value, atom->loc); 439 char* name = atom->value.s; 440 if (is_token_name(name)) { 441 int tok = kit_gram_token_for_ident(b, name, atom->loc); 442 return tok; 443 } 444 kit_gram_error(b->ctx, atom->loc, 445 "Pratt operator %s must be a token name or literal", name); 446 return -1; 447 } 448 449 static PrattInfo* transform_pratt(Builder* b, AstRule* rule, 450 AstPrattSpec* spec) { 451 AstPrattLine* primary_line = NULL; 452 for (size_t i = 0; i < spec->nlines; i++) { 453 AstPrattLine* line = spec->lines[i]; 454 if (line->kind == b->role.primary) { 455 if (primary_line) 456 kit_gram_error(b->ctx, line->loc, 457 "Pratt rule %s has multiple primary declarations", 458 rule->name); 459 primary_line = line; 460 } else if (line->kind != b->role.prefix && line->kind != b->role.postfix && 461 line->kind != b->role.infixl && line->kind != b->role.infixr && 462 line->kind != b->role.ternary && 463 line->kind != b->role.circumfix) { 464 kit_gram_error(b->ctx, line->loc, "unknown Pratt declaration '%s'", 465 line->kind); 466 } 467 } 468 if (!primary_line) 469 kit_gram_error(b->ctx, rule->loc, 470 "Pratt rule %s needs exactly one primary declaration", 471 rule->name); 472 if (primary_line->natoms != 1 || primary_line->atoms[0]->kind != PRATT_NAME) 473 kit_gram_error(b->ctx, primary_line->loc, 474 "primary declaration needs one rule name"); 475 char* primary_name = primary_line->atoms[0]->value.s; 476 int primary_rule = find_rule_index(b, primary_name); 477 if (primary_rule < 0) 478 kit_gram_error(b->ctx, primary_line->atoms[0]->loc, 479 "undefined Pratt primary rule %s", primary_name); 480 AstRule* primary_ast = find_ast_rule(b, primary_name); 481 if (primary_ast && primary_ast->pratt) 482 kit_gram_error(b->ctx, primary_line->atoms[0]->loc, 483 "Pratt primary must be an ordinary LL(1) rule"); 484 485 PrattInfo* info = xcalloc(b->ctx, 1, sizeof *info); 486 if (!info) die_oom(b->ctx); 487 info->primary_rule = primary_rule; 488 info->primary_prod = 0; 489 int prod = 1; 490 int level = 0; 491 for (size_t i = 0; i < spec->nlines; i++) { 492 AstPrattLine* line = spec->lines[i]; 493 if (line->kind == b->role.primary) continue; 494 level++; 495 int lbp = level * 2; 496 if (line->kind == b->role.ternary) { 497 /* `ternary OP1 OP2`: one right-associative conditional operator. */ 498 if (line->natoms != 2) 499 kit_gram_error(b->ctx, line->loc, 500 "ternary declaration needs exactly two operator tokens"); 501 int op1 = token_for_pratt_atom(b, line->atoms[0]); 502 int op2 = token_for_pratt_atom(b, line->atoms[1]); 503 PrattOp op = { 504 .role = b->role.ternary, 505 .tok = op1, 506 .tok2 = op2, 507 .inner_rule = -1, 508 .prod = prod++, 509 .lbp = lbp, 510 .rbp = lbp - 1, 511 .loc = line->atoms[0]->loc, 512 .enum_name = kit_gram_pratt_prod_enum_name(b->ctx, b, rule->name, 513 b->role.ternary, op1), 514 }; 515 pratt_append_op(b, info, op); 516 continue; 517 } 518 if (line->kind == b->role.circumfix) { 519 /* `circumfix OPEN inner CLOSE`: bracketed postfix (call/index). */ 520 if (line->natoms != 3) 521 kit_gram_error( 522 b->ctx, line->loc, 523 "circumfix declaration needs OPEN, an inner rule, and CLOSE"); 524 int open = token_for_pratt_atom(b, line->atoms[0]); 525 AstPrattAtom* mid = line->atoms[1]; 526 if (mid->kind != PRATT_NAME || is_token_name(mid->value.s)) 527 kit_gram_error(b->ctx, mid->loc, "circumfix inner must be a rule name"); 528 int inner = find_rule_index(b, mid->value.s); 529 if (inner < 0) 530 kit_gram_error(b->ctx, mid->loc, "undefined circumfix inner rule %s", 531 mid->value.s); 532 int close = token_for_pratt_atom(b, line->atoms[2]); 533 PrattOp op = { 534 .role = b->role.circumfix, 535 .tok = open, 536 .tok2 = close, 537 .inner_rule = inner, 538 .prod = prod++, 539 .lbp = lbp, 540 .rbp = 0, 541 .loc = line->atoms[0]->loc, 542 .enum_name = kit_gram_pratt_prod_enum_name(b->ctx, b, rule->name, 543 b->role.circumfix, open), 544 }; 545 pratt_append_op(b, info, op); 546 continue; 547 } 548 if (line->natoms == 0) 549 kit_gram_error(b->ctx, line->loc, 550 "%s declaration needs at least one operator", line->kind); 551 for (size_t j = 0; j < line->natoms; j++) { 552 int tok = token_for_pratt_atom(b, line->atoms[j]); 553 char* role = 554 (line->kind == b->role.infixl || line->kind == b->role.infixr) 555 ? b->role.infix 556 : line->kind; 557 int rbp = lbp; 558 if (line->kind == b->role.infixl) 559 rbp = lbp + 1; 560 else if (line->kind == b->role.infixr) 561 rbp = lbp - 1; 562 PrattOp op = { 563 .role = role, 564 .tok = tok, 565 .tok2 = 0, 566 .inner_rule = -1, 567 .prod = prod++, 568 .lbp = lbp, 569 .rbp = rbp, 570 .loc = line->atoms[j]->loc, 571 .enum_name = 572 kit_gram_pratt_prod_enum_name(b->ctx, b, rule->name, role, tok), 573 }; 574 pratt_append_op(b, info, op); 575 } 576 } 577 return info; 578 } 579 580 static IntSet first_sym(Builder* b, Sym* sym); 581 static int nullable_sym(Builder* b, Sym* sym); 582 583 static IntSet first_sym(Builder* b, Sym* sym) { 584 IntSet out = {0}; 585 if (sym->kind == SYM_TERM) 586 intset_add(b->ctx, &out, sym->value); 587 else if (sym->kind == SYM_RULE) 588 intset_union(b->ctx, &out, &b->rules[sym->value].first); 589 else if (sym->kind == SYM_REP || sym->kind == SYM_OPT) { 590 IntSet sub = first_sym(b, sym->sub); 591 intset_union(b->ctx, &out, &sub); 592 } 593 return out; 594 } 595 596 static int nullable_sym(Builder* b, Sym* sym) { 597 if (sym->kind == SYM_TERM) return 0; 598 if (sym->kind == SYM_RULE) return b->rules[sym->value].nullable; 599 if (sym->kind == SYM_REP || sym->kind == SYM_OPT) return 1; 600 return 0; 601 } 602 603 static IntSet pratt_prefix_tokens(Builder* b, Rule* rule) { 604 IntSet out = {0}; 605 if (!rule->pratt) return out; 606 for (size_t i = 0; i < rule->pratt->nops; i++) 607 if (rule->pratt->ops[i].role == b->role.prefix) 608 intset_add(b->ctx, &out, rule->pratt->ops[i].tok); 609 return out; 610 } 611 612 static IntSet pratt_cont_tokens(Builder* b, Rule* rule) { 613 IntSet out = {0}; 614 if (!rule->pratt) return out; 615 for (size_t i = 0; i < rule->pratt->nops; i++) 616 if (rule->pratt->ops[i].role != b->role.prefix) 617 intset_add(b->ctx, &out, rule->pratt->ops[i].tok); 618 return out; 619 } 620 621 static IntSet pratt_operator_tokens(GramgenContext* ctx, Rule* rule) { 622 IntSet out = {0}; 623 if (!rule->pratt) return out; 624 for (size_t i = 0; i < rule->pratt->nops; i++) 625 intset_add(ctx, &out, rule->pratt->ops[i].tok); 626 return out; 627 } 628 629 /* Continuation tokens that must not also start the primary. Circumfix opens are 630 * excluded: position disambiguates a leading `(` as grouping (nud) from a 631 * trailing `(` as a call (led), so the overlap is unambiguous and allowed. */ 632 static IntSet pratt_cont_tokens_nud(Builder* b, Rule* rule) { 633 IntSet out = {0}; 634 if (!rule->pratt) return out; 635 for (size_t i = 0; i < rule->pratt->nops; i++) { 636 PrattOp* op = &rule->pratt->ops[i]; 637 if (op->role == b->role.prefix || op->role == b->role.circumfix) continue; 638 intset_add(b->ctx, &out, op->tok); 639 } 640 return out; 641 } 642 643 static void first_seq(Builder* b, Sym* syms, size_t nsyms, IntSet* first, 644 int* nullable) { 645 *nullable = 1; 646 for (size_t i = 0; i < nsyms; i++) { 647 IntSet sf = first_sym(b, &syms[i]); 648 intset_union(b->ctx, first, &sf); 649 if (!nullable_sym(b, &syms[i])) { 650 *nullable = 0; 651 break; 652 } 653 } 654 } 655 656 static void compute_first_nullable(Builder* b) { 657 int changed = 1; 658 while (changed) { 659 changed = 0; 660 for (size_t ri = 0; ri < b->nrules; ri++) { 661 Rule* rule = &b->rules[ri]; 662 if (rule->pratt) { 663 IntSet first = 664 intset_copy(b->ctx, &b->rules[rule->pratt->primary_rule].first); 665 IntSet pref = pratt_prefix_tokens(b, rule); 666 intset_union(b->ctx, &first, &pref); 667 changed |= intset_union(b->ctx, &rule->first, &first); 668 if (b->rules[rule->pratt->primary_rule].nullable && !rule->nullable) { 669 rule->nullable = 1; 670 changed = 1; 671 } 672 } else { 673 for (size_t pi = 0; pi < rule->nprods; pi++) { 674 IntSet first = {0}; 675 int nullable = 0; 676 first_seq(b, rule->prods[pi].syms, rule->prods[pi].nsyms, &first, 677 &nullable); 678 changed |= intset_union(b->ctx, &rule->first, &first); 679 if (nullable && !rule->nullable) { 680 rule->nullable = 1; 681 changed = 1; 682 } 683 } 684 } 685 } 686 } 687 for (size_t ri = 0; ri < b->nrules; ri++) { 688 Rule* rule = &b->rules[ri]; 689 if (rule->pratt) continue; 690 int found_empty = 0; 691 for (size_t pi = 0; pi < rule->nprods; pi++) { 692 first_seq(b, rule->prods[pi].syms, rule->prods[pi].nsyms, 693 &rule->prods[pi].first, &rule->prods[pi].nullable); 694 if (rule->prods[pi].nullable && !found_empty) { 695 rule->empty_prod = (int)pi; 696 found_empty = 1; 697 } 698 } 699 } 700 } 701 702 static int add_follow_to_sym(Builder* b, Sym* sym, const IntSet* follow) { 703 if (sym->kind == SYM_RULE) 704 return intset_union(b->ctx, &b->rules[sym->value].follow, follow); 705 if (sym->kind == SYM_REP) { 706 IntSet item_follow = intset_copy(b->ctx, follow); 707 IntSet sf = first_sym(b, sym->sub); 708 intset_union(b->ctx, &item_follow, &sf); 709 return add_follow_to_sym(b, sym->sub, &item_follow); 710 } 711 if (sym->kind == SYM_OPT) return add_follow_to_sym(b, sym->sub, follow); 712 return 0; 713 } 714 715 static void compute_follow(Builder* b) { 716 intset_add(b->ctx, &b->rules[0].follow, 0); 717 int changed = 1; 718 while (changed) { 719 changed = 0; 720 for (size_t ri = 0; ri < b->nrules; ri++) { 721 Rule* rule = &b->rules[ri]; 722 if (rule->pratt) { 723 Rule* target = &b->rules[rule->pratt->primary_rule]; 724 changed |= intset_union(b->ctx, &target->follow, &rule->follow); 725 IntSet cont = pratt_cont_tokens(b, rule); 726 changed |= intset_union(b->ctx, &target->follow, &cont); 727 /* A circumfix inner rule is always followed by the close token. */ 728 for (size_t oi = 0; oi < rule->pratt->nops; oi++) { 729 PrattOp* op = &rule->pratt->ops[oi]; 730 if (op->role != b->role.circumfix) continue; 731 Rule* inner = &b->rules[op->inner_rule]; 732 if (!intset_contains(&inner->follow, op->tok2)) { 733 intset_add(b->ctx, &inner->follow, op->tok2); 734 changed = 1; 735 } 736 } 737 continue; 738 } 739 for (size_t pi = 0; pi < rule->nprods; pi++) { 740 Prod* prod = &rule->prods[pi]; 741 IntSet trailer = intset_copy(b->ctx, &rule->follow); 742 for (size_t si = prod->nsyms; si > 0; si--) { 743 Sym* sym = &prod->syms[si - 1]; 744 changed |= add_follow_to_sym(b, sym, &trailer); 745 IntSet sf = first_sym(b, sym); 746 if (nullable_sym(b, sym)) 747 intset_union(b->ctx, &trailer, &sf); 748 else 749 trailer = sf; 750 } 751 } 752 } 753 } 754 } 755 756 static const char* token_display(Builder* b, int tok) { 757 return b->tokens[tok].display.s; 758 } 759 760 static const char* rule_display(Builder* b, int idx) { 761 return b->rules[idx].name; 762 } 763 764 static void validate_wrapper_sym(Builder* b, Sym* sym) { 765 if (sym->kind == SYM_REP) { 766 if (nullable_sym(b, sym->sub)) 767 kit_gram_error(b->ctx, sym->loc, "repetition body is nullable"); 768 validate_wrapper_sym(b, sym->sub); 769 } else if (sym->kind == SYM_OPT) { 770 if (nullable_sym(b, sym->sub)) 771 kit_gram_error(b->ctx, sym->loc, "optional body is nullable"); 772 validate_wrapper_sym(b, sym->sub); 773 } 774 } 775 776 static void validate_ebnf_wrappers(Builder* b) { 777 for (size_t ri = 0; ri < b->nrules; ri++) { 778 Rule* rule = &b->rules[ri]; 779 for (size_t pi = 0; pi < rule->nprods; pi++) 780 for (size_t si = 0; si < rule->prods[pi].nsyms; si++) 781 validate_wrapper_sym(b, &rule->prods[pi].syms[si]); 782 } 783 } 784 785 static void check_ebnf_wrapper_ll1(Builder* b) { 786 for (size_t ri = 0; ri < b->nrules; ri++) { 787 Rule* rule = &b->rules[ri]; 788 for (size_t pi = 0; pi < rule->nprods; pi++) { 789 Prod* prod = &rule->prods[pi]; 790 IntSet trailer = intset_copy(b->ctx, &rule->follow); 791 for (size_t si = prod->nsyms; si > 0; si--) { 792 Sym* sym = &prod->syms[si - 1]; 793 if (sym->kind == SYM_REP || sym->kind == SYM_OPT) { 794 IntSet sf = first_sym(b, sym->sub); 795 int tok = intset_intersection_min(&sf, &trailer); 796 if (tok >= 0) { 797 const char* what = sym->kind == SYM_REP ? "repetition" : "optional"; 798 kit_gram_error( 799 b->ctx, sym->loc, 800 "LL(1) conflict in %s in rule %s: token '%s' can start " 801 "the body or follow the %s", 802 what, rule->name, token_display(b, tok), what); 803 } 804 } 805 IntSet sf = first_sym(b, sym); 806 if (nullable_sym(b, sym)) 807 intset_union(b->ctx, &trailer, &sf); 808 else 809 trailer = sf; 810 } 811 } 812 } 813 } 814 815 static void leading_rules(Builder* b, Sym* sym, IntSet* out) { 816 if (sym->kind == SYM_RULE) 817 intset_add(b->ctx, out, sym->value); 818 else if (sym->kind == SYM_REP || sym->kind == SYM_OPT) 819 leading_rules(b, sym->sub, out); 820 } 821 822 static int find_cycle(Builder* b, IntSet* edges, int start, int cur, int* path, 823 size_t npath, IntSet* seen, int* out, size_t* nout) { 824 (void)b; 825 for (size_t i = 0; i < edges[cur].n; i++) { 826 int nxt = edges[cur].v[i]; 827 if (nxt == start) { 828 memcpy(out, path, npath * sizeof *out); 829 out[npath] = nxt; 830 *nout = npath + 1; 831 return 1; 832 } 833 if (intset_contains(seen, nxt)) continue; 834 intset_add(b->ctx, seen, nxt); 835 path[npath] = nxt; 836 if (find_cycle(b, edges, start, nxt, path, npath + 1, seen, out, nout)) 837 return 1; 838 } 839 return 0; 840 } 841 842 static void check_left_recursion(Builder* b) { 843 IntSet* edges = xcalloc(b->ctx, b->nrules, sizeof *edges); 844 int* path = xmalloc(b->ctx, (b->nrules + 1) * sizeof *path); 845 int* cycle = xmalloc(b->ctx, (b->nrules + 1) * sizeof *cycle); 846 if (!edges) die_oom(b->ctx); 847 for (size_t ri = 0; ri < b->nrules; ri++) { 848 Rule* rule = &b->rules[ri]; 849 if (rule->pratt) intset_add(b->ctx, &edges[ri], rule->pratt->primary_rule); 850 for (size_t pi = 0; pi < rule->nprods; pi++) { 851 Prod* prod = &rule->prods[pi]; 852 for (size_t si = 0; si < prod->nsyms; si++) { 853 leading_rules(b, &prod->syms[si], &edges[ri]); 854 if (!nullable_sym(b, &prod->syms[si])) break; 855 } 856 } 857 } 858 for (size_t i = 0; i < b->nrules; i++) { 859 IntSet seen = {0}; 860 intset_add(b->ctx, &seen, (int)i); 861 path[0] = (int)i; 862 size_t ncycle = 0; 863 if (find_cycle(b, edges, (int)i, (int)i, path, 1, &seen, cycle, &ncycle)) { 864 Buf msg; 865 buf_init(b->ctx, &msg); 866 buf_append(&msg, "left recursion is not LL(1): "); 867 for (size_t j = 0; j < ncycle; j++) { 868 if (j) buf_append(&msg, " -> "); 869 buf_append(&msg, rule_display(b, cycle[j])); 870 } 871 kit_gram_error(b->ctx, b->rules[i].loc, "%s", msg.s); 872 } 873 } 874 } 875 876 static void visit_reachable_sym(Builder* b, Sym* sym, IntSet* seen); 877 878 static void visit_reachable_rule(Builder* b, int idx, IntSet* seen) { 879 if (intset_contains(seen, idx)) return; 880 intset_add(b->ctx, seen, idx); 881 Rule* rule = &b->rules[idx]; 882 if (rule->pratt) { 883 visit_reachable_rule(b, rule->pratt->primary_rule, seen); 884 for (size_t oi = 0; oi < rule->pratt->nops; oi++) 885 if (rule->pratt->ops[oi].role == b->role.circumfix) 886 visit_reachable_rule(b, rule->pratt->ops[oi].inner_rule, seen); 887 } 888 for (size_t pi = 0; pi < rule->nprods; pi++) 889 for (size_t si = 0; si < rule->prods[pi].nsyms; si++) 890 visit_reachable_sym(b, &rule->prods[pi].syms[si], seen); 891 } 892 893 static void visit_reachable_sym(Builder* b, Sym* sym, IntSet* seen) { 894 if (sym->kind == SYM_RULE) 895 visit_reachable_rule(b, sym->value, seen); 896 else if (sym->kind == SYM_REP || sym->kind == SYM_OPT) 897 visit_reachable_sym(b, sym->sub, seen); 898 } 899 900 static void check_reachable(Builder* b) { 901 IntSet seen = {0}; 902 visit_reachable_rule(b, 0, &seen); 903 for (size_t i = 0; i < b->public_count; i++) 904 if (!intset_contains(&seen, (int)i)) 905 kit_gram_error(b->ctx, b->rules[i].loc, "unreachable rule %s", 906 b->rules[i].name); 907 } 908 909 static void check_ll1(Builder* b) { 910 for (size_t ri = 0; ri < b->nrules; ri++) { 911 Rule* rule = &b->rules[ri]; 912 if (rule->pratt) continue; 913 int* seen_prod = xmalloc(b->ctx, b->ntokens * sizeof *seen_prod); 914 for (size_t i = 0; i < b->ntokens; i++) seen_prod[i] = -1; 915 IntSet all_first = {0}; 916 int nullable_alts[256]; 917 size_t nnullable = 0; 918 for (size_t pi = 0; pi < rule->nprods; pi++) { 919 Prod* prod = &rule->prods[pi]; 920 intset_union(b->ctx, &all_first, &prod->first); 921 for (size_t ti = 0; ti < prod->first.n; ti++) { 922 int tok = prod->first.v[ti]; 923 if (seen_prod[tok] >= 0) { 924 kit_gram_error( 925 b->ctx, prod->loc, 926 "LL(1) conflict in %s: token '%s' selects alternative %d " 927 "and alternative %zu", 928 rule->name, token_display(b, tok), seen_prod[tok], pi); 929 } 930 seen_prod[tok] = (int)pi; 931 } 932 if (prod->nullable && 933 nnullable < sizeof nullable_alts / sizeof nullable_alts[0]) 934 nullable_alts[nnullable++] = (int)pi; 935 } 936 if (nnullable > 1) { 937 int first = nullable_alts[0], second = nullable_alts[1]; 938 kit_gram_error( 939 b->ctx, rule->prods[second].loc, 940 "LL(1) conflict in %s: alternatives %d and %d are both nullable", 941 rule->name, first, second); 942 } 943 for (size_t i = 0; i < nnullable; i++) { 944 int tok = intset_intersection_min(&all_first, &rule->follow); 945 if (tok >= 0) { 946 int alt = nullable_alts[i]; 947 kit_gram_error(b->ctx, rule->prods[alt].loc, 948 "LL(1) conflict in %s: nullable alternative %d conflicts " 949 "with following token '%s'", 950 rule->name, alt, token_display(b, tok)); 951 } 952 } 953 xfree(b->ctx, seen_prod); 954 } 955 } 956 957 static void check_pratt(Builder* b) { 958 for (size_t ri = 0; ri < b->nrules; ri++) { 959 Rule* rule = &b->rules[ri]; 960 if (!rule->pratt) continue; 961 Rule* primary = &b->rules[rule->pratt->primary_rule]; 962 if (primary->nullable) 963 kit_gram_error(b->ctx, primary->loc, 964 "Pratt primary %s must not be nullable", primary->name); 965 if (!rule->first.n) 966 kit_gram_error(b->ctx, rule->loc, "Pratt rule %s cannot match any token", 967 rule->name); 968 IntSet prefix_seen = {0}; 969 IntSet cont_seen = {0}; 970 for (size_t i = 0; i < rule->pratt->nops; i++) { 971 PrattOp* op = &rule->pratt->ops[i]; 972 if (op->role == b->role.prefix) { 973 if (intset_contains(&prefix_seen, op->tok)) 974 kit_gram_error(b->ctx, op->loc, "duplicate Pratt prefix operator '%s'", 975 token_display(b, op->tok)); 976 intset_add(b->ctx, &prefix_seen, op->tok); 977 } else { 978 if (intset_contains(&cont_seen, op->tok)) 979 kit_gram_error(b->ctx, op->loc, 980 "Pratt operator '%s' has multiple continuation roles", 981 token_display(b, op->tok)); 982 intset_add(b->ctx, &cont_seen, op->tok); 983 } 984 } 985 IntSet cont_all = pratt_cont_tokens(b, rule); 986 for (size_t i = 0; i < rule->pratt->nops; i++) { 987 PrattOp* op = &rule->pratt->ops[i]; 988 if (op->role != b->role.ternary && op->role != b->role.circumfix) 989 continue; 990 if (op->tok2 == op->tok) 991 kit_gram_error( 992 b->ctx, op->loc, 993 "Pratt operator '%s' opening and closing tokens must differ", 994 token_display(b, op->tok)); 995 if (intset_contains(&cont_all, op->tok2)) 996 kit_gram_error( 997 b->ctx, op->loc, 998 "Pratt structural token '%s' cannot also continue an expression", 999 token_display(b, op->tok2)); 1000 } 1001 IntSet cont = pratt_cont_tokens_nud(b, rule); 1002 int tok = intset_intersection_min(&primary->first, &cont); 1003 if (tok >= 0) 1004 kit_gram_error( 1005 b->ctx, rule->loc, 1006 "Pratt rule %s: token '%s' can start the primary or continue " 1007 "the expression", 1008 rule->name, token_display(b, tok)); 1009 IntSet ops = pratt_operator_tokens(b->ctx, rule); 1010 tok = intset_intersection_min(&rule->follow, &ops); 1011 if (tok >= 0) 1012 kit_gram_error(b->ctx, rule->loc, 1013 "Pratt rule %s: operator token '%s' also appears in FOLLOW", 1014 rule->name, token_display(b, tok)); 1015 } 1016 } 1017 1018 static int intern_set(Builder* b, IntSet* set) { 1019 for (size_t i = 0; i < b->nsets; i++) 1020 if (intset_equal(&b->sets[i], set)) return (int)i; 1021 if (b->nsets == b->cap_sets) { 1022 b->cap_sets = b->cap_sets ? b->cap_sets * 2 : 8; 1023 b->sets = xrealloc(b->ctx, b->sets, b->cap_sets * sizeof *b->sets); 1024 } 1025 b->sets[b->nsets] = intset_copy(b->ctx, set); 1026 return (int)b->nsets++; 1027 } 1028 1029 static void collect_guard_sets_sym(Builder* b, Sym* sym) { 1030 if (sym->kind == SYM_REP || sym->kind == SYM_OPT) { 1031 IntSet fs = first_sym(b, sym->sub); 1032 sym->set_index = intern_set(b, &fs); 1033 collect_guard_sets_sym(b, sym->sub); 1034 } 1035 } 1036 1037 static void collect_guard_sets(Builder* b) { 1038 for (size_t ri = 0; ri < b->nrules; ri++) 1039 for (size_t pi = 0; pi < b->rules[ri].nprods; pi++) 1040 for (size_t si = 0; si < b->rules[ri].prods[pi].nsyms; si++) 1041 collect_guard_sets_sym(b, &b->rules[ri].prods[pi].syms[si]); 1042 } 1043 1044 static void append_wrapper_sym(Builder* b, Sym* sym) { 1045 if (b->nwrapper_syms == b->cap_wrapper_syms) { 1046 b->cap_wrapper_syms = b->cap_wrapper_syms ? b->cap_wrapper_syms * 2 : 8; 1047 b->wrapper_syms = xrealloc(b->ctx, b->wrapper_syms, 1048 b->cap_wrapper_syms * sizeof *b->wrapper_syms); 1049 } 1050 b->wrapper_syms[b->nwrapper_syms++] = sym; 1051 } 1052 1053 static void collect_wrapper_syms_sym(Builder* b, Sym* sym) { 1054 if (sym->kind == SYM_REP || sym->kind == SYM_OPT) { 1055 sym->sub_array_id = (int)b->nwrapper_syms; 1056 append_wrapper_sym(b, sym); 1057 collect_wrapper_syms_sym(b, sym->sub); 1058 } 1059 } 1060 1061 static void collect_wrapper_syms(Builder* b) { 1062 for (size_t ri = 0; ri < b->nrules; ri++) 1063 for (size_t pi = 0; pi < b->rules[ri].nprods; pi++) 1064 for (size_t si = 0; si < b->rules[ri].prods[pi].nsyms; si++) 1065 collect_wrapper_syms_sym(b, &b->rules[ri].prods[pi].syms[si]); 1066 } 1067 1068 static void prepare_rule_names(Builder* b) { 1069 NameIndexMap seen = {0}; 1070 for (size_t i = 0; i < b->pg->nrules; i++) { 1071 AstRule* r = b->pg->rules[i]; 1072 if (!is_rule_name(r->name)) 1073 kit_gram_error(b->ctx, r->loc, 1074 "invalid rule name '%s'; rule names must start with a " 1075 "lowercase letter", 1076 r->name); 1077 if (name_index_find(&seen, r->name, NULL)) 1078 kit_gram_error(b->ctx, r->loc, "duplicate rule %s", r->name); 1079 name_index_put(b->ctx, &seen, r->name, (int)i); 1080 } 1081 } 1082 1083 /* Validate token declarations and, in the same O(n) pass, build the 1084 * literal->decl and name->decl indexes used by literal/keyword resolution. */ 1085 static void prepare_decls(Builder* b) { 1086 GramgenContext* ctx = b->ctx; 1087 for (size_t i = 0; i < b->pg->ntoken_decls; i++) { 1088 TokenDecl* d = b->pg->token_decls[i]; 1089 if (!is_token_name(d->name)) 1090 kit_gram_error( 1091 ctx, d->loc, 1092 "invalid token name '%s'; token names must be all uppercase", 1093 d->name); 1094 if (strcmp(d->name, "EOF") == 0 || strcmp(d->name, "__COUNT") == 0) 1095 kit_gram_error(ctx, d->loc, "reserved token name %s", d->name); 1096 if (name_index_find(&b->literal_decl_index, d->literal.s, NULL)) { 1097 char* q = c_string_str(ctx, d->literal); 1098 kit_gram_error(ctx, d->loc, "duplicate %%token declaration for %s", q); 1099 } 1100 int prev; 1101 if (name_index_find(&b->decl_name_index, d->name, &prev) && 1102 !str_eq(b->pg->token_decls[prev]->literal, d->literal)) 1103 kit_gram_error(ctx, d->loc, 1104 "token name %s is already bound to another literal", 1105 d->name); 1106 name_index_put(ctx, &b->literal_decl_index, d->literal.s, (int)i); 1107 name_index_put(ctx, &b->decl_name_index, d->name, (int)i); 1108 } 1109 } 1110 1111 static void prepare_rules(Builder* b) { 1112 for (size_t i = 0; i < b->pg->nrules; i++) { 1113 Rule r; 1114 memset(&r, 0, sizeof r); 1115 r.name = b->pg->rules[i]->name; 1116 r.loc = b->pg->rules[i]->loc; 1117 r.public_rule = 1; 1118 r.index = (int)i; 1119 builder_append_rule(b, r); 1120 } 1121 b->public_count = b->nrules; 1122 for (size_t i = 0; i < b->public_count; i++) { 1123 AstRule* ast = b->pg->rules[i]; 1124 if (ast->pratt) { 1125 b->rules[i].pratt = transform_pratt(b, ast, ast->pratt); 1126 } else { 1127 for (size_t pi = 0; pi < ast->alts->nseqs; pi++) { 1128 Prod prod = transform_seq(b, ast->alts->seqs[pi], ast->loc); 1129 rule_append_prod(b, &b->rules[i], prod); 1130 } 1131 } 1132 } 1133 } 1134 1135 /* A file that declares only %machine blocks (and no parser rules) is a valid 1136 * standalone state-machine spec: it emits the codegen-only verifier + sampler 1137 * and no parser grammar. */ 1138 static int pg_has_machine(const ParsedGrammar* pg) { 1139 for (size_t i = 0; i < pg->nlex_blocks; i++) 1140 if (pg->lex_blocks[i]->mode == KIT_GRAM_LEX_INPUT_TOKENS) return 1; 1141 return 0; 1142 } 1143 1144 Builder* kit_gram_builder_new(GramgenContext* ctx, ParsedGrammar* pg) { 1145 if (!pg->nrules && !pg_has_machine(pg)) { 1146 Loc loc = {0}; 1147 kit_gram_error(ctx, loc, "grammar has no rules"); 1148 } 1149 Builder* b = xcalloc(ctx, 1, sizeof *b); 1150 if (!b) die_oom(ctx); 1151 b->ctx = ctx; 1152 b->role.primary = intern_c(ctx, "primary"); 1153 b->role.prefix = intern_c(ctx, "prefix"); 1154 b->role.postfix = intern_c(ctx, "postfix"); 1155 b->role.infixl = intern_c(ctx, "infixl"); 1156 b->role.infixr = intern_c(ctx, "infixr"); 1157 b->role.infix = intern_c(ctx, "infix"); 1158 b->role.ternary = intern_c(ctx, "ternary"); 1159 b->role.circumfix = intern_c(ctx, "circumfix"); 1160 b->pg = pg; 1161 Loc origin = pg->nrules 1162 ? pg->rules[0]->loc 1163 : (pg->nlex_blocks ? pg->lex_blocks[0]->loc : (Loc){0}); 1164 char* eof_name = intern_c(ctx, "EOF"); 1165 TokenDef eof = {.name = eof_name, 1166 .display = str_from_owned(eof_name, strlen(eof_name)), 1167 .loc = origin}; 1168 builder_append_token(b, eof); 1169 prepare_rule_names(b); 1170 prepare_decls(b); 1171 /* Register %keywords tokens and bindings before parser rules so a parser 1172 * literal that names a keyword resolves to it and gets no DFA recognizer. */ 1173 collect_keywords(b); 1174 prepare_rules(b); 1175 /* The lexer is prepared at the start of kit_gram_builder_build, after the 1176 * caller has set build-time options (b->multiline). */ 1177 return b; 1178 } 1179 1180 static void check_unused_token_decls(Builder* b) { 1181 for (size_t i = 0; i < b->pg->ntoken_decls; i++) { 1182 TokenDecl* d = b->pg->token_decls[i]; 1183 if (!d->used) { 1184 char* q = c_string_str(b->ctx, d->literal); 1185 kit_gram_error(b->ctx, d->loc, "%%token declaration for %s is unused", q); 1186 } 1187 } 1188 } 1189 1190 Builder* kit_gram_builder_build(Builder* b) { 1191 kit_gram_prepare_lexer(b); 1192 check_unused_token_decls(b); 1193 /* Parser validation is skipped for a machine-only file (no parser rules); the 1194 * %machine pipeline runs entirely inside kit_gram_prepare_lexer above. */ 1195 if (b->nrules) { 1196 compute_first_nullable(b); 1197 validate_ebnf_wrappers(b); 1198 check_left_recursion(b); 1199 compute_follow(b); 1200 check_reachable(b); 1201 check_ebnf_wrapper_ll1(b); 1202 check_ll1(b); 1203 check_pratt(b); 1204 collect_guard_sets(b); 1205 collect_wrapper_syms(b); 1206 } 1207 if (b->ntokens > 65535) { 1208 Loc loc = {0}; 1209 kit_gram_error(b->ctx, loc, "too many tokens"); 1210 } 1211 if (b->nrules > 65535) { 1212 Loc loc = {0}; 1213 kit_gram_error(b->ctx, loc, "too many rules"); 1214 } 1215 for (size_t i = 0; i < b->nrules; i++) 1216 if (b->rules[i].nprods > 255) 1217 kit_gram_error(b->ctx, b->rules[i].loc, 1218 "rule %s has too many alternatives", b->rules[i].name); 1219 return b; 1220 }