test_clike.c (14368B)
1 /* Realistic C-like lexer+parser test driver. 2 * 3 * 1. token-level: hex/decimal ints, floats, char/string literals, comment 4 * skipping, keyword-vs-identifier, and longest-match operator splitting. 5 * 2. expression structure: the whole program is reduced through the value 6 * channel into an s-expression; for a `int main(){ EXPR; }` wrapper the 7 * program text contains EXPR's s-expr, which pins Pratt precedence and 8 * associativity exactly. 9 * 3. accept/reject: a corpus of realistic programs and malformed ones. 10 * 11 * Written to the natural expectation; left red where the implementation 12 * disagrees. 13 */ 14 #include "generated_clike.h" 15 16 #include <stdarg.h> 17 #include <stdio.h> 18 #include <stdlib.h> 19 #include <string.h> 20 21 static int failures = 0; 22 static void okfail(int ok, const char *fmt, ...) { 23 va_list ap; va_start(ap, fmt); 24 char buf[640]; vsnprintf(buf, sizeof buf, fmt, ap); va_end(ap); 25 printf("%s %s\n", ok ? "ok " : "FAIL", buf); 26 if (!ok) failures++; 27 } 28 29 /* ------------------------------------------------------------------ arena -- */ 30 typedef struct { char **mem; size_t n, cap; } Arena; 31 static char *areg(Arena *a, char *s) { 32 if (a->n == a->cap) { a->cap = a->cap ? a->cap * 2 : 64; a->mem = realloc(a->mem, a->cap * sizeof *a->mem); } 33 a->mem[a->n++] = s; return s; 34 } 35 static char *adup(Arena *a, const char *s, size_t len) { 36 char *p = malloc(len + 1); memcpy(p, s, len); p[len] = 0; return areg(a, p); 37 } 38 static char *afmt(Arena *a, const char *fmt, ...) { 39 va_list ap; va_start(ap, fmt); 40 char buf[1024]; vsnprintf(buf, sizeof buf, fmt, ap); va_end(ap); 41 return adup(a, buf, strlen(buf)); 42 } 43 static void afree(Arena *a) { for (size_t i = 0; i < a->n; i++) free(a->mem[i]); free(a->mem); a->mem = 0; a->n = a->cap = 0; } 44 #define S(x) ((char *)(x)) 45 46 /* ----------------------------------------------------------- value channel -- */ 47 /* Every rule returns a heap s-expression string. Expressions are precise; the 48 * surrounding statement/decl rules pass the interesting child through so the 49 * root program string contains the expression s-expr verbatim. */ 50 static KitGramSem cb_lift(void *ud, KitGramToken t) { return adup(ud, t.lexeme, t.len); } 51 static KitGramSem cb_list_empty(void *ud) { return adup(ud, "", 0); } 52 static KitGramSem cb_list_push(void *ud, KitGramSem l, KitGramSem i) { 53 const char *ls = l; return *ls ? afmt(ud, "%s %s", ls, S(i)) : S(i); 54 } 55 static KitGramSem cb_opt_none(void *ud) { return adup(ud, "", 0); } 56 static KitGramSem cb_opt_some(void *ud, KitGramSem i) { (void)ud; return i; } 57 58 static KitGramSem cb_reduce(void *ud, KitGramRuleId r, int prod, KitGramSem *k, size_t n) { 59 Arena *a = ud; (void)n; 60 switch (r) { 61 case CLIKE_R_program: return n ? k[0] : adup(a, "", 0); /* decl* */ 62 case CLIKE_R_decl: return k[2]; /* carry decl_tail */ 63 case CLIKE_R_decl_tail: 64 switch (prod) { 65 case 0: return k[3]; /* function body */ 66 case 1: return adup(a, "", 0); /* ";" */ 67 default: return k[1]; /* "=" expr ";" */ 68 } 69 case CLIKE_R_type: return k[0]; 70 case CLIKE_R_params: return afmt(a, "%s %s", S(k[0]), S(k[1])); 71 case CLIKE_R_param_tail:return k[1]; 72 case CLIKE_R_param: return afmt(a, "%s", S(k[1])); 73 case CLIKE_R_block: return k[1]; /* "{" stmt* "}" */ 74 case CLIKE_R_stmt: 75 switch (prod) { 76 case 0: return k[0]; /* block */ 77 case 1: return afmt(a, "if(%s){%s}else{%s}", S(k[2]), S(k[4]), S(k[5])); 78 case 2: return afmt(a, "while(%s){%s}", S(k[2]), S(k[4])); 79 case 3: return k[1]; /* return expr? ; */ 80 case 4: return k[2]; /* type IDENT init?;*/ 81 default: return k[0]; /* expr ";" */ 82 } 83 case CLIKE_R_else_part: return k[1]; 84 case CLIKE_R_var_init: return k[1]; /* "=" expr */ 85 case CLIKE_R_expr: 86 switch (prod) { 87 case CLIKE_EXPR_PRIMARY: return k[0]; 88 case CLIKE_EXPR_PREFIX_MINUS: 89 case CLIKE_EXPR_PREFIX_BANG: return afmt(a, "(%s %s)", S(k[0]), S(k[1])); /* {op, operand} */ 90 default: return afmt(a, "(%s %s %s)", S(k[1]), S(k[0]), S(k[2])); /* {lhs, op, rhs} */ 91 } 92 case CLIKE_R_primary: 93 switch (prod) { 94 case 4: return k[1]; /* "(" expr ")" */ 95 case 5: { /* IDENT call_tail */ 96 const char *ct = k[1]; 97 return *ct == '@' ? afmt(a, "(call %s%s)", S(k[0]), ct + 1) : S(k[0]); 98 } 99 default: return k[0]; /* INT/FLOAT/STR/CHAR */ 100 } 101 case CLIKE_R_call_tail: /* "@" marks a call; suffix is the (possibly empty) args */ 102 return prod == 0 ? (*S(k[1]) ? afmt(a, "@ %s", S(k[1])) : adup(a, "@", 1)) 103 : adup(a, "", 0); 104 case CLIKE_R_args: return *S(k[1]) ? afmt(a, "%s %s", S(k[0]), S(k[1])) : S(k[0]); 105 case CLIKE_R_arg_tail: return k[1]; 106 } 107 return adup(a, "?", 1); 108 } 109 110 /* The value-channel vtable that reduces a program to its s-expression. Shared 111 * verbatim by the table parser and the generated pull-RD parser, so both run the 112 * same real actions (including the Pratt expression reductions). */ 113 static KitGramActions clike_value_actions(void) { 114 return (KitGramActions){ 115 .reduce = cb_reduce, .lift_token = cb_lift, 116 .list_empty = cb_list_empty, .list_push = cb_list_push, 117 .opt_none = cb_opt_none, .opt_some = cb_opt_some, 118 }; 119 } 120 121 /* ----------------------------------------------------------------- driver --- */ 122 static int parse_prog(const char *src, Arena *a, const char **out) { 123 KitGramActions acts = clike_value_actions(); 124 unsigned char carry[128]; 125 KitGramLexInput in; kit_gram_lex_input_init(&in, &(KitGramLexInputConfig){ .carry = carry, .carry_cap = sizeof carry }); 126 KitGramLexer lx; clike_lexer_init(&lx, &in, &(KitGramLexConfig){0}); 127 KitGramParser ps; 128 KitGramSlot ctl[1024]; KitGramSem vals[1024]; 129 KitGramConfig cfg = { .actions = &acts, .ud = a, .ctl_stack = ctl, .ctl_cap = 1024, .val_stack = vals, .val_cap = 1024 }; 130 clike_parser_init(&ps, &cfg); 131 132 KitGramLexInputSpan span = { .bytes = (const unsigned char *)src, .len = strlen(src) }; 133 kit_gram_lex_input_push(&in, &span); kit_gram_lex_input_finish(&in); 134 for (;;) { 135 KitGramToken tok; 136 switch (kit_gram_lexer_next(&lx, &tok)) { 137 case KIT_GRAM_LEX_TOKEN: if (kit_gram_parser_push(&ps, tok) == KIT_GRAM_PARSE_ERROR) return 0; break; 138 case KIT_GRAM_LEX_NEED_MORE: 139 case KIT_GRAM_LEX_ERROR: return 0; 140 case KIT_GRAM_LEX_EOF: 141 if (kit_gram_parser_finish(&ps) != KIT_GRAM_PARSE_ACCEPT) return 0; 142 if (out) *out = kit_gram_parser_result(&ps); 143 return 1; 144 } 145 } 146 } 147 148 /* ---- the same real actions, driven through the generated parsers ---------- */ 149 /* parse_rd consumes a token array (lexed here with the table lexer). It reduces 150 * through the s-expression value channel and returns the program's KitGramSem 151 * string. */ 152 static const char *parse_prog_rd(const char *src, Arena *a, int *ok) { 153 KitGramLexInput in; kit_gram_lex_input_init(&in, &(KitGramLexInputConfig){0}); 154 KitGramLexer lx; clike_lexer_init(&lx, &in, &(KitGramLexConfig){0}); 155 KitGramLexInputSpan span = { .bytes = (const unsigned char *)src, .len = strlen(src) }; 156 kit_gram_lex_input_push(&in, &span); kit_gram_lex_input_finish(&in); 157 KitGramToken *toks = NULL; size_t n = 0, cap = 0; 158 for (;;) { 159 KitGramToken t; KitGramLexStatus st = kit_gram_lexer_next(&lx, &t); 160 if (st == KIT_GRAM_LEX_TOKEN) { 161 if (n == cap) { cap = cap ? cap * 2 : 64; toks = realloc(toks, cap * sizeof *toks); } 162 toks[n++] = t; continue; 163 } 164 if (st != KIT_GRAM_LEX_EOF) { free(toks); *ok = 0; return NULL; } /* lex error */ 165 break; 166 } 167 KitGramActions acts = clike_value_actions(); 168 KitGramError err = {0}; int okv = 0; 169 KitGramSem r = clike_parse_rd(toks, n, &acts, a, &err, &okv); 170 free(toks); 171 *ok = okv; 172 return okv ? (const char *)r : NULL; 173 } 174 /* Cross-check the generated pull-RD parser against the table parser: same 175 * accept/reject decision, and the same reconstructed program string on accept. 176 * `got` is the table parser's result (NULL when it rejected). Returns 1 on 177 * agreement; emits its own ok/FAIL line. */ 178 static int codegen_agrees(const char *src, int acc, const char *got) { 179 Arena a = {0}; 180 int rd_ok = 0; 181 const char *rd = parse_prog_rd(src, &a, &rd_ok); 182 int ok = rd_ok == acc; 183 if (ok && acc) 184 ok = got && rd && strcmp(rd, got) == 0; 185 okfail(ok, " codegen rd matches table (acc=%d) for %s", acc, src); 186 afree(&a); 187 return ok; 188 } 189 190 /* ----------------------------------------------------------- token checks --- */ 191 static int lex_one(const char *src, KitGramToken *out) { 192 KitGramLexInput in; kit_gram_lex_input_init(&in, &(KitGramLexInputConfig){0}); 193 KitGramLexer lx; clike_lexer_init(&lx, &in, &(KitGramLexConfig){0}); 194 KitGramLexInputSpan span = { .bytes = (const unsigned char *)src, .len = strlen(src) }; 195 kit_gram_lex_input_push(&in, &span); kit_gram_lex_input_finish(&in); 196 if (kit_gram_lexer_next(&lx, out) != KIT_GRAM_LEX_TOKEN) return 0; 197 KitGramToken next; 198 return kit_gram_lexer_next(&lx, &next) == KIT_GRAM_LEX_EOF; 199 } 200 static void check_tok(const char *src, KitGramTokenKind kind) { 201 KitGramToken t; 202 int ok = lex_one(src, &t) && t.kind == kind && t.len == strlen(src); 203 okfail(ok, "lex %-14s -> kind=%u len=%zu (want kind=%u, single token)", 204 src, ok ? (unsigned)t.kind : 0u, ok ? t.len : 0u, (unsigned)kind); 205 } 206 207 /* expr precedence/associativity: wrap EXPR in a minimal program, require the 208 * reduced program string to contain the expected s-expr. */ 209 static void check_expr(const char *expr, const char *want_sexpr) { 210 char prog[512]; 211 snprintf(prog, sizeof prog, "int main() { %s; }", expr); 212 Arena a = {0}; 213 const char *got = NULL; 214 int acc = parse_prog(prog, &a, &got); 215 int ok = acc && got && strstr(got, want_sexpr) != NULL; 216 okfail(ok, "expr %-20s -> %s (want substring \"%s\")", expr, got ? got : "(reject)", want_sexpr); 217 /* The Pratt expression reductions must come out identical on the codegen 218 * parsers (this is where operator precedence/associativity actions run). */ 219 codegen_agrees(prog, acc, got); 220 afree(&a); 221 } 222 223 static void check_prog(const char *src, int want_accept) { 224 Arena a = {0}; 225 const char *got = NULL; 226 int acc = parse_prog(src, &a, &got); 227 okfail(acc == want_accept, "%-46s -> %s (want %s)", src, 228 acc ? "accept" : "reject", want_accept ? "accept" : "reject"); 229 codegen_agrees(src, acc, got); 230 afree(&a); 231 } 232 233 int main(void) { 234 printf("== C-like lexer token edges ==\n"); 235 check_tok("0x1F", CLIKE_TOK_INT); 236 check_tok("255", CLIKE_TOK_INT); 237 check_tok("0", CLIKE_TOK_INT); 238 check_tok("3.14", CLIKE_TOK_FLOAT); 239 check_tok("1.5e9", CLIKE_TOK_FLOAT); 240 check_tok("'a'", CLIKE_TOK_CHAR); 241 check_tok("'\\n'", CLIKE_TOK_CHAR); 242 check_tok("\"hi\\n\"", CLIKE_TOK_STRING); 243 check_tok("if", CLIKE_TOK_IF); 244 check_tok("iffy", CLIKE_TOK_IDENT); 245 check_tok("int", CLIKE_TOK_INT_T); 246 check_tok("integer", CLIKE_TOK_IDENT); 247 check_tok("return", CLIKE_TOK_RETURN); 248 check_tok("<=", CLIKE_TOK_LE); 249 check_tok("==", CLIKE_TOK_EQEQ); 250 check_tok("!=", CLIKE_TOK_BANGEQ); 251 check_tok("&&", CLIKE_TOK_ANDAND); 252 check_tok("||", CLIKE_TOK_OROR); 253 254 printf("\n== C-like expression precedence / associativity ==\n"); 255 check_expr("a + b * c", "(+ a (* b c))"); 256 check_expr("a * b + c", "(+ (* a b) c)"); 257 check_expr("a - b - c", "(- (- a b) c)"); /* left assoc */ 258 check_expr("a + b + c", "(+ (+ a b) c)"); 259 check_expr("(a + b) * c", "(* (+ a b) c)"); 260 check_expr("a || b && c", "(|| a (&& b c))"); 261 check_expr("a == b < c", "(== a (< b c))"); 262 check_expr("a < b == c < d", "(== (< a b) (< c d))"); 263 check_expr("-a * b", "(* (- a) b)"); /* prefix tightest */ 264 check_expr("!a && b", "(&& (! a) b)"); 265 check_expr("a * -b", "(* a (- b))"); 266 check_expr("f(x, y + 1)", "(call f x (+ y 1))"); 267 check_expr("g()", "(call g)"); 268 check_expr("a + b < c && d", "(&& (< (+ a b) c) d)"); 269 check_expr("a = b = c", "(= a (= b c))"); /* right assoc */ 270 check_expr("a = b + c", "(= a (+ b c))"); /* = is loosest */ 271 272 printf("\n== C-like program accept/reject ==\n"); 273 check_prog("int x;", 1); 274 check_prog("int main() { return 0; }", 1); 275 check_prog("int f(int a, int b) { int c = a + b; return c; }", 1); 276 check_prog("void loop(int n) { while (n) { n = n - 1; } }", 1); 277 check_prog("int g() { if (a < b) { return a; } else { return b; } }", 1); 278 check_prog("int h() { /* block */ int x = 0x1F; // line\n return x * 2; }", 1); 279 check_prog("int a; int b; int main() { return f(a, b); }", 1); 280 check_prog("int main() { if (x) y; else z; }", 1); 281 282 /* rejects */ 283 check_prog("int x", 0); /* missing ; */ 284 check_prog("int main() { return 0 }", 0); /* missing ; */ 285 check_prog("int main() { if (x) y; }", 0); /* missing else (this grammar)*/ 286 check_prog("int f( { }", 0); /* malformed params */ 287 check_prog("return 0;", 0); /* stmt at top level */ 288 check_prog("int main() { 1 + ; }", 0); /* bad expression */ 289 check_prog("int main() { ) }", 0); /* stray paren */ 290 check_prog("3 + 4", 0); /* expr at top level */ 291 292 return failures ? 1 : 0; 293 }