pratt_mixfix_test.c (8967B)
1 #include "generated_pratt_mixfix.h" 2 3 #include <ctype.h> 4 #include <stdarg.h> 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <string.h> 8 9 /* Each semantic value is a heap string holding an s-expression of the parse so 10 * tests can assert precedence/associativity structurally rather than by value. */ 11 typedef struct { 12 char **mem; 13 size_t nmem, capmem; 14 int enters, exits, tokens; 15 } Emb; 16 17 static char *track(Emb *e, char *s) { 18 if (e->nmem == e->capmem) { 19 e->capmem = e->capmem ? e->capmem * 2 : 32; 20 e->mem = realloc(e->mem, e->capmem * sizeof *e->mem); 21 } 22 e->mem[e->nmem++] = s; 23 return s; 24 } 25 26 static void emb_free(Emb *e) { 27 for (size_t i = 0; i < e->nmem; i++) free(e->mem[i]); 28 free(e->mem); 29 } 30 31 static char *mk(Emb *e, const char *fmt, ...) { 32 va_list ap; 33 va_start(ap, fmt); 34 int n = vsnprintf(NULL, 0, fmt, ap); 35 va_end(ap); 36 char *s = malloc((size_t)n + 1); 37 va_start(ap, fmt); 38 vsnprintf(s, (size_t)n + 1, fmt, ap); 39 va_end(ap); 40 return track(e, s); 41 } 42 43 static const char *S(KitGramSem v) { return v ? (const char *)v : ""; } 44 45 static KitGramSem cb_lift(void *ud, KitGramToken t) { 46 Emb *e = ud; 47 return mk(e, "%.*s", (int)t.len, t.lexeme); 48 } 49 50 static KitGramSem cb_list_empty(void *ud) { return mk((Emb *)ud, "%s", ""); } 51 52 static KitGramSem cb_list_push(void *ud, KitGramSem list, KitGramSem item) { 53 Emb *e = ud; 54 const char *l = S(list); 55 return l[0] ? mk(e, "%s %s", l, S(item)) : mk(e, "%s", S(item)); 56 } 57 58 static KitGramSem cb_reduce(void *ud, KitGramRuleId r, int prod, KitGramSem *k, size_t n) { 59 Emb *e = ud; 60 (void)n; 61 switch (r) { 62 case PRATT_MIXFIX_R_primary: 63 return prod == 0 ? k[0] : prod == 1 ? k[0] : k[1]; 64 case PRATT_MIXFIX_R_arg_more: 65 return k[1]; /* drop the comma */ 66 case PRATT_MIXFIX_R_args: 67 if (prod == 0) return mk(e, "%s", ""); /* %empty */ 68 return S(k[1])[0] ? mk(e, "%s %s", S(k[0]), S(k[1])) : k[0]; 69 case PRATT_MIXFIX_R_expr: 70 switch (prod) { 71 case PRATT_MIXFIX_EXPR_PRIMARY: return k[0]; 72 case PRATT_MIXFIX_EXPR_TERNARY_QUESTION: return mk(e, "(?: %s %s %s)", S(k[0]), S(k[2]), S(k[4])); 73 case PRATT_MIXFIX_EXPR_INFIX_PLUS: return mk(e, "(+ %s %s)", S(k[0]), S(k[2])); 74 case PRATT_MIXFIX_EXPR_INFIX_MINUS: return mk(e, "(- %s %s)", S(k[0]), S(k[2])); 75 case PRATT_MIXFIX_EXPR_INFIX_STAR: return mk(e, "(* %s %s)", S(k[0]), S(k[2])); 76 case PRATT_MIXFIX_EXPR_INFIX_SLASH: return mk(e, "(/ %s %s)", S(k[0]), S(k[2])); 77 case PRATT_MIXFIX_EXPR_INFIX_DOT: return mk(e, "(. %s %s)", S(k[0]), S(k[2])); 78 case PRATT_MIXFIX_EXPR_CIRCUMFIX_LPAREN: 79 return S(k[2])[0] ? mk(e, "(call %s %s)", S(k[0]), S(k[2])) 80 : mk(e, "(call %s)", S(k[0])); 81 case PRATT_MIXFIX_EXPR_CIRCUMFIX_LBRACKET: return mk(e, "(index %s %s)", S(k[0]), S(k[2])); 82 } 83 break; 84 } 85 return NULL; 86 } 87 88 static void cb_enter(void *ud, KitGramRuleId r, int prod) { (void)r; (void)prod; ((Emb *)ud)->enters++; } 89 static void cb_exit(void *ud, KitGramRuleId r, int prod) { (void)r; (void)prod; ((Emb *)ud)->exits++; } 90 static void cb_token(void *ud, KitGramToken t) { (void)t; ((Emb *)ud)->tokens++; } 91 92 typedef struct { const char *s; size_t i; } Lexer; 93 94 static int lex_next(Lexer *lx, KitGramToken *out) { 95 while (lx->s[lx->i] && isspace((unsigned char)lx->s[lx->i])) lx->i++; 96 char c = lx->s[lx->i]; 97 if (!c) return 0; 98 99 out->lexeme = &lx->s[lx->i]; 100 out->len = 1; 101 out->line = 1; 102 out->col = (uint32_t)(lx->i + 1); 103 104 if (isdigit((unsigned char)c)) { 105 size_t j = lx->i; 106 while (isdigit((unsigned char)lx->s[j])) j++; 107 out->kind = PRATT_MIXFIX_TOK_NUMBER; 108 out->len = j - lx->i; 109 lx->i = j; 110 return 1; 111 } 112 if (isalpha((unsigned char)c) || c == '_') { 113 size_t j = lx->i; 114 while (isalnum((unsigned char)lx->s[j]) || lx->s[j] == '_') j++; 115 out->kind = PRATT_MIXFIX_TOK_NAME; 116 out->len = j - lx->i; 117 lx->i = j; 118 return 1; 119 } 120 121 lx->i++; 122 switch (c) { 123 case '+': out->kind = PRATT_MIXFIX_TOK_PLUS; break; 124 case '-': out->kind = PRATT_MIXFIX_TOK_MINUS; break; 125 case '*': out->kind = PRATT_MIXFIX_TOK_STAR; break; 126 case '/': out->kind = PRATT_MIXFIX_TOK_SLASH; break; 127 case '.': out->kind = PRATT_MIXFIX_TOK_DOT; break; 128 case '?': out->kind = PRATT_MIXFIX_TOK_QUESTION; break; 129 case ':': out->kind = PRATT_MIXFIX_TOK_COLON; break; 130 case ',': out->kind = PRATT_MIXFIX_TOK_COMMA; break; 131 case '(': out->kind = PRATT_MIXFIX_TOK_LPAREN; break; 132 case ')': out->kind = PRATT_MIXFIX_TOK_RPAREN; break; 133 case '[': out->kind = PRATT_MIXFIX_TOK_LBRACKET; break; 134 case ']': out->kind = PRATT_MIXFIX_TOK_RBRACKET; break; 135 default: out->kind = PRATT_MIXFIX_TOK__COUNT; break; 136 } 137 return 1; 138 } 139 140 static int parse(const char *src, char **result, int *enters, int *exits, int *tokens) { 141 Emb e; 142 memset(&e, 0, sizeof e); 143 KitGramActions acts = { 144 .reduce = cb_reduce, 145 .lift_token = cb_lift, 146 .list_empty = cb_list_empty, 147 .list_push = cb_list_push, 148 .enter = cb_enter, 149 .exit = cb_exit, 150 .on_token = cb_token, 151 }; 152 KitGramParser ps; 153 KitGramSlot ctl[512]; 154 KitGramSem vals[512]; 155 KitGramConfig cfg = { .actions = &acts, .ud = &e, .recover = false, 156 .ctl_stack = ctl, .ctl_cap = 512, 157 .val_stack = vals, .val_cap = 512 }; 158 pratt_mixfix_parser_init(&ps, &cfg); 159 160 Lexer lx = { src, 0 }; 161 KitGramToken t; 162 int ok = 1; 163 while (ok && lex_next(&lx, &t)) 164 if (kit_gram_parser_push(&ps, t) == KIT_GRAM_PARSE_ERROR) ok = 0; 165 if (ok && kit_gram_parser_finish(&ps) != KIT_GRAM_PARSE_ACCEPT) ok = 0; 166 if (ok && result) { 167 KitGramSem r = kit_gram_parser_result(&ps); 168 *result = strdup(r ? (const char *)r : ""); 169 } 170 if (enters) *enters = e.enters; 171 if (exits) *exits = e.exits; 172 if (tokens) *tokens = e.tokens; 173 emb_free(&e); 174 return ok; 175 } 176 177 static int failures = 0; 178 179 static void check_ast(const char *src, const char *want) { 180 char *got = NULL; 181 int en = 0, ex = 0, tk = 0; 182 if (!parse(src, &got, &en, &ex, &tk)) { 183 printf("FAIL %-24s parse error (wanted %s)\n", src, want); 184 failures++; 185 free(got); 186 return; 187 } 188 if (strcmp(got, want) != 0) { 189 printf("FAIL %-24s = %s (wanted %s)\n", src, got, want); 190 failures++; 191 free(got); 192 return; 193 } 194 if (en != ex || en == 0 || tk == 0) { 195 printf("FAIL %-24s listener mismatch enter=%d exit=%d tok=%d\n", src, en, ex, tk); 196 failures++; 197 free(got); 198 return; 199 } 200 printf("ok %-24s = %s\n", src, got); 201 free(got); 202 } 203 204 static void check_err(const char *src) { 205 char *got = NULL; 206 if (parse(src, &got, NULL, NULL, NULL)) { 207 printf("FAIL %-24s parsed = %s (wanted rejection)\n", src, got); 208 failures++; 209 free(got); 210 return; 211 } 212 printf("ok %-24s -> rejected\n", src); 213 free(got); 214 } 215 216 int main(void) { 217 printf("== generated mixfix Pratt parser ==\n"); 218 219 /* precedence + associativity of the unary/binary base */ 220 check_ast("1 + 2 * 3", "(+ 1 (* 2 3))"); 221 check_ast("(1 + 2) * 3", "(* (+ 1 2) 3)"); 222 check_ast("10 - 2 - 3", "(- (- 10 2) 3)"); 223 224 /* ternary: right-associative, loosest */ 225 check_ast("a ? b : c", "(?: a b c)"); 226 check_ast("a ? b : c ? d : e", "(?: a b (?: c d e))"); 227 check_ast("p ? q : r + s", "(?: p q (+ r s))"); 228 check_ast("a ? b ? c : d : e", "(?: a (?: b c d) e)"); 229 230 /* circumfix call: empty / single / list args */ 231 check_ast("f()", "(call f)"); 232 check_ast("f(x)", "(call f x)"); 233 check_ast("f(a, b, c)", "(call f a b c)"); 234 check_ast("f(g(x))", "(call f (call g x))"); 235 236 /* circumfix index, chaining at constant depth */ 237 check_ast("a[i]", "(index a i)"); 238 check_ast("a[i][j]", "(index (index a i) j)"); 239 check_ast("m[i + 1]", "(index m (+ i 1))"); 240 241 /* `.` member chains and mixtures with call/index */ 242 check_ast("a.b.c", "(. (. a b) c)"); 243 check_ast("f(x).y", "(. (call f x) y)"); 244 check_ast("a.b(c)", "(call (. a b) c)"); 245 check_ast("a[i].b", "(. (index a i) b)"); 246 check_ast("o.f(a)[k]", "(index (call (. o f) a) k)"); 247 248 /* mixfix nesting: ternary inside args, expressions inside brackets */ 249 check_ast("f(a ? b : c, d)", "(call f (?: a b c) d)"); 250 check_ast("cond ? x[0] : y.z", "(?: cond (index x 0) (. y z))"); 251 252 /* rejections: unbalanced / missing structural tokens */ 253 check_err("a ? b"); 254 check_err("a ? b c"); 255 check_err("f(a"); 256 check_err("a[i"); 257 check_err("f(a,)"); 258 check_err("1 +"); 259 check_err("(1"); 260 check_err("a[]"); 261 262 return failures ? 1 : 0; 263 }