char-fork/llama.cpp

git clone https://git.t4t.associates/char-fork/llama.cpp

Aldehir Rojasgrammar : degrade max repetition >= 2000 to unbounded (#26613)cd0fa6051

char/aliceai-t5-moe
brancheschar/aliceai-t5-moeall refs →
18.0 KiB584 linesraw
1#ifdef NDEBUG
2#undef NDEBUG
3#endif
4
5#include "llama.h"
6
7// TODO: shold not include libllama sources
8#include "../src/llama-grammar.h"
9
10#include <cassert>
11
12static const char * type_str(llama_gretype type) {
13    switch (type) {
14        case LLAMA_GRETYPE_CHAR: return "LLAMA_GRETYPE_CHAR";
15        case LLAMA_GRETYPE_CHAR_NOT: return "LLAMA_GRETYPE_CHAR_NOT";
16        case LLAMA_GRETYPE_CHAR_ALT: return "LLAMA_GRETYPE_CHAR_ALT";
17        case LLAMA_GRETYPE_CHAR_RNG_UPPER: return "LLAMA_GRETYPE_CHAR_RNG_UPPER";
18        case LLAMA_GRETYPE_RULE_REF: return "LLAMA_GRETYPE_RULE_REF";
19        case LLAMA_GRETYPE_ALT: return "LLAMA_GRETYPE_ALT";
20        case LLAMA_GRETYPE_END: return "LLAMA_GRETYPE_END";
21        default: return "?";
22    }
23}
24
25static void verify_parsing(const char *grammar_bytes, const std::vector<std::pair<std::string, uint32_t>> expected, const std::vector<llama_grammar_element> &expected_rules) {
26    uint32_t index = 0;
27    llama_grammar_parser parsed_grammar;
28    parsed_grammar.parse(grammar_bytes);
29
30    std::map<uint32_t, std::string> symbol_names;
31    for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it) {
32        symbol_names[it->second] = it->first;
33    }
34
35    auto print_all = [&]() {
36        fprintf(stderr, "    verify_parsing(R\"\"\"(%s)\"\"\", {\n", grammar_bytes);
37        for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it) {
38            fprintf(stderr, "        {\"%s\", %u},\n", it->first.c_str(), it->second);
39        }
40        fprintf(stderr, "    }, {\n");
41        for (size_t i_rule = 0; i_rule < parsed_grammar.rules.size(); i_rule++) {
42            fprintf(stderr, "        // %s (index %zu)\n", symbol_names[i_rule].c_str(), i_rule);
43            auto & rule = parsed_grammar.rules[i_rule];
44            for (uint32_t i = 0; i < rule.size(); i++) {
45                std::string rule_str;
46                fprintf(stderr, "        {%s, ", type_str(rule[i].type));
47                if (rule[i].type == LLAMA_GRETYPE_CHAR || rule[i].type == LLAMA_GRETYPE_CHAR_ALT ||
48                    rule[i].type == LLAMA_GRETYPE_CHAR_NOT || rule[i].type == LLAMA_GRETYPE_CHAR_RNG_UPPER) {
49                    char c = rule[i].value;
50                    if (c == '\n') {
51                        fprintf(stderr, "'\\n'");
52                    } else if (c == '\t') {
53                        fprintf(stderr, "'\\t'");
54                    } else if (c == '\r') {
55                        fprintf(stderr, "'\\r'");
56                    } else if (c == '\0') {
57                        fprintf(stderr, "'\\0'");
58                    } else {
59                        fprintf(stderr, "'%c'", c);
60                    }
61                } else if (rule[i].type == LLAMA_GRETYPE_RULE_REF) {
62                    fprintf(stderr, "/* %s */ %u", symbol_names[rule[i].value].c_str(), rule[i].value);
63                } else {
64                    fprintf(stderr, "%u", rule[i].value);
65                }
66                fprintf(stderr, "},\n");
67            }
68        }
69        fprintf(stderr, "    });\n");
70    };
71
72    if (getenv("TEST_GRAMMAR_PARSER_PRINT_ALL")) {
73        print_all();
74        fprintf(stderr, "\n");
75        return;
76    }
77
78    fprintf(stderr, "Testing grammar:%s\n", grammar_bytes);
79
80    if (parsed_grammar.symbol_ids.size() != expected.size()) {
81        fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");
82        print_all();
83        assert(parsed_grammar.symbol_ids.size() == expected.size());
84    }
85
86    for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it)
87    {
88        std::string key = it->first;
89        uint32_t value = it->second;
90        std::pair<std::string, uint32_t> expected_pair = expected[index];
91
92        // pretty print error message before asserting
93        if (expected_pair.first != key || expected_pair.second != value)
94        {
95            fprintf(stderr, "index: %u\n", index);
96            fprintf(stderr, "expected_pair: %s, %u\n", expected_pair.first.c_str(), expected_pair.second);
97            fprintf(stderr, "actual_pair: %s, %u\n", key.c_str(), value);
98            fprintf(stderr, "expected_pair != actual_pair\n");
99            fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");
100            print_all();
101        }
102
103        assert(expected_pair.first == key && expected_pair.second == value);
104
105        index++;
106    }
107
108    index = 0;
109    for (auto rule : parsed_grammar.rules)
110    {
111        // compare rule to expected rule
112        for (uint32_t i = 0; i < rule.size(); i++)
113        {
114            llama_grammar_element element = rule[i];
115            llama_grammar_element expected_element = expected_rules[index];
116
117            // pretty print error message before asserting
118            if (expected_element.type != element.type || expected_element.value != element.value)
119            {
120                fprintf(stderr, "index: %u\n", index);
121                fprintf(stderr, "expected_element: %s, %u\n", type_str(expected_element.type), expected_element.value);
122                fprintf(stderr, "actual_element: %s, %u\n", type_str(element.type), element.value);
123                fprintf(stderr, "expected_element != actual_element\n");
124                fprintf(stderr, "all elements:\n");
125                fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");
126                print_all();
127            }
128
129            assert(expected_element.type == element.type && expected_element.value == element.value);
130            index++;
131        }
132    }
133}
134
135static void verify_failure(const char * grammar_bytes) {
136    fprintf(stderr, "Testing expected failure:%s\n", grammar_bytes);
137    llama_grammar_parser result;
138    result.parse(grammar_bytes);
139    assert(result.rules.empty() && "should have failed");
140}
141
142int main()
143{
144    verify_failure(R"""(
145        root ::= "a"{,}"
146    )""");
147
148    verify_failure(R"""(
149        root ::= (((((([^x]*){0,99}){0,99}){0,99}){0,99}){0,99}){0,99}
150    )""");
151
152    verify_failure(R"""(
153        root ::= "a"{,10}"
154    )""");
155
156    verify_failure(R"""(
157        root ::= "a"{5000}
158    )""");
159
160    verify_failure(R"""(
161        root ::= "a"{5000,}
162    )""");
163
164    verify_failure(R"""(
165        root ::= "a"{5000,6000}
166    )""");
167
168    verify_parsing(R"""(
169        root ::= "a"{0,5000}
170    )""", {
171        {"root", 0},
172        {"root_1", 1},
173    }, {
174        // root (index 0)
175        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
176        {LLAMA_GRETYPE_END, 0},
177        // root_1 (index 1)
178        {LLAMA_GRETYPE_CHAR, 'a'},
179        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
180        {LLAMA_GRETYPE_ALT, 0},
181        {LLAMA_GRETYPE_END, 0},
182    });
183
184    verify_parsing(R"""(
185        root ::= "a"{3,5000}
186    )""", {
187        {"root", 0},
188        {"root_1", 1},
189    }, {
190        // root (index 0)
191        {LLAMA_GRETYPE_CHAR, 'a'},
192        {LLAMA_GRETYPE_CHAR, 'a'},
193        {LLAMA_GRETYPE_CHAR, 'a'},
194        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
195        {LLAMA_GRETYPE_END, 0},
196        // root_1 (index 1)
197        {LLAMA_GRETYPE_CHAR, 'a'},
198        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
199        {LLAMA_GRETYPE_ALT, 0},
200        {LLAMA_GRETYPE_END, 0},
201    });
202
203    verify_parsing(R"""(
204        root  ::= "a"
205    )""", {
206        {"root", 0},
207    }, {
208        // root (index 0)
209        {LLAMA_GRETYPE_CHAR, 'a'},
210        {LLAMA_GRETYPE_END, 0},
211    });
212
213    verify_parsing(R"""(
214        root  ::= "a" | [bdx-z] | [^1-3]
215    )""", {
216        {"root", 0},
217    }, {
218        // root (index 0)
219        {LLAMA_GRETYPE_CHAR, 'a'},
220        {LLAMA_GRETYPE_ALT, 0},
221        {LLAMA_GRETYPE_CHAR, 'b'},
222        {LLAMA_GRETYPE_CHAR_ALT, 'd'},
223        {LLAMA_GRETYPE_CHAR_ALT, 'x'},
224        {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},
225        {LLAMA_GRETYPE_ALT, 0},
226        {LLAMA_GRETYPE_CHAR_NOT, '1'},
227        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '3'},
228        {LLAMA_GRETYPE_END, 0},
229    });
230
231    verify_parsing(R"""(
232        root  ::= a+
233        a     ::= "a"
234    )""", {
235        {"a", 1},
236        {"root", 0},
237        {"root_2", 2},
238    }, {
239        // root (index 0)
240        {LLAMA_GRETYPE_RULE_REF, /* a */ 1},
241        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},
242        {LLAMA_GRETYPE_END, 0},
243        // a (index 1)
244        {LLAMA_GRETYPE_CHAR, 'a'},
245        {LLAMA_GRETYPE_END, 0},
246        // root_2 (index 2)
247        {LLAMA_GRETYPE_RULE_REF, /* a */ 1},
248        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},
249        {LLAMA_GRETYPE_ALT, 0},
250        {LLAMA_GRETYPE_END, 0},
251    });
252
253    verify_parsing(R"""(
254        root  ::= "a"+
255    )""", {
256        {"root", 0},
257        {"root_1", 1},
258    }, {
259        // root (index 0)
260        {LLAMA_GRETYPE_CHAR, 'a'},
261        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
262        {LLAMA_GRETYPE_END, 0},
263        // root_1 (index 1)
264        {LLAMA_GRETYPE_CHAR, 'a'},
265        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
266        {LLAMA_GRETYPE_ALT, 0},
267        {LLAMA_GRETYPE_END, 0},
268    });
269
270    verify_parsing(R"""(
271        root  ::= a?
272        a     ::= "a"
273    )""", {
274        {"a", 1},
275        {"root", 0},
276        {"root_2", 2},
277    }, {
278        // root (index 0)
279        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},
280        {LLAMA_GRETYPE_END, 0},
281        // a (index 1)
282        {LLAMA_GRETYPE_CHAR, 'a'},
283        {LLAMA_GRETYPE_END, 0},
284        // root_2 (index 2)
285        {LLAMA_GRETYPE_RULE_REF, /* a */ 1},
286        {LLAMA_GRETYPE_ALT, 0},
287        {LLAMA_GRETYPE_END, 0},
288    });
289
290    verify_parsing(R"""(
291        root  ::= "a"?
292    )""", {
293        {"root", 0},
294        {"root_1", 1},
295    }, {
296        // root (index 0)
297        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
298        {LLAMA_GRETYPE_END, 0},
299        // root_1 (index 1)
300        {LLAMA_GRETYPE_CHAR, 'a'},
301        {LLAMA_GRETYPE_ALT, 0},
302        {LLAMA_GRETYPE_END, 0},
303    });
304
305    verify_parsing(R"""(
306        root  ::= a*
307        a     ::= "a"
308    )""", {
309        {"a", 1},
310        {"root", 0},
311        {"root_2", 2},
312    }, {
313        // root (index 0)
314        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},
315        {LLAMA_GRETYPE_END, 0},
316        // a (index 1)
317        {LLAMA_GRETYPE_CHAR, 'a'},
318        {LLAMA_GRETYPE_END, 0},
319        // root_2 (index 2)
320        {LLAMA_GRETYPE_RULE_REF, /* a */ 1},
321        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},
322        {LLAMA_GRETYPE_ALT, 0},
323        {LLAMA_GRETYPE_END, 0},
324    });
325
326    verify_parsing(R"""(
327        root  ::= "a"*
328    )""", {
329        {"root", 0},
330        {"root_1", 1},
331    }, {
332        // root (index 0)
333        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
334        {LLAMA_GRETYPE_END, 0},
335        // root_1 (index 1)
336        {LLAMA_GRETYPE_CHAR, 'a'},
337        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
338        {LLAMA_GRETYPE_ALT, 0},
339        {LLAMA_GRETYPE_END, 0},
340    });
341
342    verify_parsing(R"""(
343        root  ::= "a"{2}
344    )""", {
345        {"root", 0},
346    }, {
347        // root (index 0)
348        {LLAMA_GRETYPE_CHAR, 'a'},
349        {LLAMA_GRETYPE_CHAR, 'a'},
350        {LLAMA_GRETYPE_END, 0},
351    });
352
353    verify_parsing(R"""(
354        root  ::= "a"{2,}
355    )""", {
356        {"root", 0},
357        {"root_1", 1},
358    }, {
359        // root (index 0)
360        {LLAMA_GRETYPE_CHAR, 'a'},
361        {LLAMA_GRETYPE_CHAR, 'a'},
362        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
363        {LLAMA_GRETYPE_END, 0},
364        // root_1 (index 1)
365        {LLAMA_GRETYPE_CHAR, 'a'},
366        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
367        {LLAMA_GRETYPE_ALT, 0},
368        {LLAMA_GRETYPE_END, 0},
369    });
370
371    verify_parsing(R"""(
372        root  ::= "a"{ 4}
373    )""", {
374        {"root", 0},
375    }, {
376        // root (index 0)
377        {LLAMA_GRETYPE_CHAR, 'a'},
378        {LLAMA_GRETYPE_CHAR, 'a'},
379        {LLAMA_GRETYPE_CHAR, 'a'},
380        {LLAMA_GRETYPE_CHAR, 'a'},
381        {LLAMA_GRETYPE_END, 0},
382    });
383
384    verify_parsing(R"""(
385        root  ::= "a"{2,4}
386    )""", {
387        {"root", 0},
388        {"root_1", 1},
389        {"root_2", 2},
390    }, {
391        // root (index 0)
392        {LLAMA_GRETYPE_CHAR, 'a'},
393        {LLAMA_GRETYPE_CHAR, 'a'},
394        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},
395        {LLAMA_GRETYPE_END, 0},
396        // root_1 (index 1)
397        {LLAMA_GRETYPE_CHAR, 'a'},
398        {LLAMA_GRETYPE_ALT, 0},
399        {LLAMA_GRETYPE_END, 0},
400        // root_2 (index 2)
401        {LLAMA_GRETYPE_CHAR, 'a'},
402        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
403        {LLAMA_GRETYPE_ALT, 0},
404        {LLAMA_GRETYPE_END, 0},
405    });
406
407    verify_parsing(R"""(
408        root  ::= (expr "=" term "\n")+
409        expr  ::= term ([-+*/] term)*
410        term  ::= [0-9]+
411    )""", {
412        {"expr", 2},
413        {"expr_5", 5},
414        {"expr_6", 6},
415        {"root", 0},
416        {"root_1", 1},
417        {"root_4", 4},
418        {"term", 3},
419        {"term_7", 7},
420    }, {
421        // root (index 0)
422        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
423        {LLAMA_GRETYPE_RULE_REF, /* root_4 */ 4},
424        {LLAMA_GRETYPE_END, 0},
425        // root_1 (index 1)
426        {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},
427        {LLAMA_GRETYPE_CHAR, '='},
428        {LLAMA_GRETYPE_RULE_REF, /* term */ 3},
429        {LLAMA_GRETYPE_CHAR, '\n'},
430        {LLAMA_GRETYPE_END, 0},
431        // expr (index 2)
432        {LLAMA_GRETYPE_RULE_REF, /* term */ 3},
433        {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},
434        {LLAMA_GRETYPE_END, 0},
435        // term (index 3)
436        {LLAMA_GRETYPE_CHAR, '0'},
437        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},
438        {LLAMA_GRETYPE_RULE_REF, /* term_7 */ 7},
439        {LLAMA_GRETYPE_END, 0},
440        // root_4 (index 4)
441        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
442        {LLAMA_GRETYPE_RULE_REF, /* root_4 */ 4},
443        {LLAMA_GRETYPE_ALT, 0},
444        {LLAMA_GRETYPE_END, 0},
445        // expr_5 (index 5)
446        {LLAMA_GRETYPE_CHAR, '-'},
447        {LLAMA_GRETYPE_CHAR_ALT, '+'},
448        {LLAMA_GRETYPE_CHAR_ALT, '*'},
449        {LLAMA_GRETYPE_CHAR_ALT, '/'},
450        {LLAMA_GRETYPE_RULE_REF, /* term */ 3},
451        {LLAMA_GRETYPE_END, 0},
452        // expr_6 (index 6)
453        {LLAMA_GRETYPE_RULE_REF, /* expr_5 */ 5},
454        {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},
455        {LLAMA_GRETYPE_ALT, 0},
456        {LLAMA_GRETYPE_END, 0},
457        // term_7 (index 7)
458        {LLAMA_GRETYPE_CHAR, '0'},
459        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},
460        {LLAMA_GRETYPE_RULE_REF, /* term_7 */ 7},
461        {LLAMA_GRETYPE_ALT, 0},
462        {LLAMA_GRETYPE_END, 0},
463    });
464
465    verify_parsing(R"""(
466        root  ::= (expr "=" ws term "\n")+
467        expr  ::= term ([-+*/] term)*
468        term  ::= ident | num | "(" ws expr ")" ws
469        ident ::= [a-z] [a-z0-9_]* ws
470        num   ::= [0-9]+ ws
471        ws    ::= [ \t\n]*
472    )""", {
473        {"expr", 2},
474        {"expr_6", 6},
475        {"expr_7", 7},
476        {"ident", 8},
477        {"ident_10", 10},
478        {"num", 9},
479        {"num_11", 11},
480        {"root", 0},
481        {"root_1", 1},
482        {"root_5", 5},
483        {"term", 4},
484        {"ws", 3},
485        {"ws_12", 12},
486    }, {
487        // root (index 0)
488        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
489        {LLAMA_GRETYPE_RULE_REF, /* root_5 */ 5},
490        {LLAMA_GRETYPE_END, 0},
491        // root_1 (index 1)
492        {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},
493        {LLAMA_GRETYPE_CHAR, '='},
494        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},
495        {LLAMA_GRETYPE_RULE_REF, /* term */ 4},
496        {LLAMA_GRETYPE_CHAR, '\n'},
497        {LLAMA_GRETYPE_END, 0},
498        // expr (index 2)
499        {LLAMA_GRETYPE_RULE_REF, /* term */ 4},
500        {LLAMA_GRETYPE_RULE_REF, /* expr_7 */ 7},
501        {LLAMA_GRETYPE_END, 0},
502        // ws (index 3)
503        {LLAMA_GRETYPE_RULE_REF, /* ws_12 */ 12},
504        {LLAMA_GRETYPE_END, 0},
505        // term (index 4)
506        {LLAMA_GRETYPE_RULE_REF, /* ident */ 8},
507        {LLAMA_GRETYPE_ALT, 0},
508        {LLAMA_GRETYPE_RULE_REF, /* num */ 9},
509        {LLAMA_GRETYPE_ALT, 0},
510        {LLAMA_GRETYPE_CHAR, '('},
511        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},
512        {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},
513        {LLAMA_GRETYPE_CHAR, ')'},
514        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},
515        {LLAMA_GRETYPE_END, 0},
516        // root_5 (index 5)
517        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},
518        {LLAMA_GRETYPE_RULE_REF, /* root_5 */ 5},
519        {LLAMA_GRETYPE_ALT, 0},
520        {LLAMA_GRETYPE_END, 0},
521        // expr_6 (index 6)
522        {LLAMA_GRETYPE_CHAR, '-'},
523        {LLAMA_GRETYPE_CHAR_ALT, '+'},
524        {LLAMA_GRETYPE_CHAR_ALT, '*'},
525        {LLAMA_GRETYPE_CHAR_ALT, '/'},
526        {LLAMA_GRETYPE_RULE_REF, /* term */ 4},
527        {LLAMA_GRETYPE_END, 0},
528        // expr_7 (index 7)
529        {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},
530        {LLAMA_GRETYPE_RULE_REF, /* expr_7 */ 7},
531        {LLAMA_GRETYPE_ALT, 0},
532        {LLAMA_GRETYPE_END, 0},
533        // ident (index 8)
534        {LLAMA_GRETYPE_CHAR, 'a'},
535        {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},
536        {LLAMA_GRETYPE_RULE_REF, /* ident_10 */ 10},
537        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},
538        {LLAMA_GRETYPE_END, 0},
539        // num (index 9)
540        {LLAMA_GRETYPE_CHAR, '0'},
541        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},
542        {LLAMA_GRETYPE_RULE_REF, /* num_11 */ 11},
543        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},
544        {LLAMA_GRETYPE_END, 0},
545        // ident_10 (index 10)
546        {LLAMA_GRETYPE_CHAR, 'a'},
547        {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},
548        {LLAMA_GRETYPE_CHAR_ALT, '0'},
549        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},
550        {LLAMA_GRETYPE_CHAR_ALT, '_'},
551        {LLAMA_GRETYPE_RULE_REF, /* ident_10 */ 10},
552        {LLAMA_GRETYPE_ALT, 0},
553        {LLAMA_GRETYPE_END, 0},
554        // num_11 (index 11)
555        {LLAMA_GRETYPE_CHAR, '0'},
556        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},
557        {LLAMA_GRETYPE_RULE_REF, /* num_11 */ 11},
558        {LLAMA_GRETYPE_ALT, 0},
559        {LLAMA_GRETYPE_END, 0},
560        // ws_12 (index 12)
561        {LLAMA_GRETYPE_CHAR, ' '},
562        {LLAMA_GRETYPE_CHAR_ALT, '\t'},
563        {LLAMA_GRETYPE_CHAR_ALT, '\n'},
564        {LLAMA_GRETYPE_RULE_REF, /* ws_12 */ 12},
565        {LLAMA_GRETYPE_ALT, 0},
566        {LLAMA_GRETYPE_END, 0},
567    });
568
569    // <[1000]> = "<think>"
570    // <[1001]> = "</think>"
571    verify_parsing(R"""(
572        root  ::= <[1000]> !<[1001]> <[1001]>
573    )""", {
574        {"root", 0}
575    }, {
576        // root (index 0)
577        {LLAMA_GRETYPE_TOKEN, 1000},
578        {LLAMA_GRETYPE_TOKEN_NOT, 1001},
579        {LLAMA_GRETYPE_TOKEN, 1001},
580        {LLAMA_GRETYPE_END, 0},
581    });
582
583    return 0;
584}