10000 grammars: x{min,max} repetition operator by ochafik · Pull Request #6640 · ggml-org/llama.cpp · GitHub
[go: up one dir, main page]
Skip to content

grammars: x{min,max} repetition operator #6640

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 36 commits into from
Jun 6, 2024
Merged

grammars: x{min,max} repetition operator #6640

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
36 commits
Select commit Hold shift + click to select a range
0160469
grammars: x{min,max} repetition operator + tweak +/*/? to avoid dupli…
Apr 12, 2024
f2030e3
grammars: handle `x{n}` and fix `x{n,n}`
Apr 12, 2024
de0fd3f
grammars: document new repetition operators
Apr 12, 2024
9d9b5a3
grammars: nit
Apr 12, 2024
6b5518c
grammars: uniform use of int for min & max
Apr 12, 2024
0ceb69a
grammars: refactor parser test
Apr 12, 2024
8938a05
grammar: parsing tests w/ natural pretty print of updated expectations
Apr 12, 2024
0d7347f
grammars: much prettier print of expectations (+ TEST_GRAMMAR_PARSER_…
Apr 12, 2024
2e2df72
grammars: improve test pretty print again
Apr 12, 2024
ffe321d
grammars: pretty print rules and chars
Apr 12, 2024
a9351b8
grammars: fix copy rule skipping
Apr 12, 2024
9d8efa5
grammars: disallow `a{,}` (not allowed in regexps)
Apr 12, 2024
2d98ebf
Update common/grammar-parser.cpp
ochafik Apr 12, 2024
ec91342
grammars: fix copy rule skipping (again) & display of expectations
Apr 12, 2024
22faba6
grammars: more test cases
Apr 12, 2024
1fb7787
Merge remote-tracking branch 'origin/master' into grammar-reps
Apr 15, 2024
15585e0
grammars: update reps parsing to bring ? / * / + closer to before
Apr 19, 2024
93b754e
json: use new GBNF repetitions{m,n} syntax
Apr 19, 2024
2ecc2ae
grammars: update performance gotchas w/ repetition advice
Apr 20, 2024
a9a2983
Merge remote-tracking branch 'origin/master' into grammar-reps
Apr 21, 2024
d47f537
Update examples/json_schema_to_grammar.py
ochafik Apr 24, 2024
724f879
Update examples/server/public/json-schema-to-grammar.mjs
ochafik Apr 24, 2024
a61281f
grammars: comment on rule repetitions
Apr 24, 2024
d03c98e
grammars: ensure unambiguous number alternatives
Apr 24, 2024
21bac1e
grammar: nit typo switched error msgs
Apr 24, 2024
0c74ad3
grammar: nit numbering in comment
Apr 24, 2024
218f41f
json: update numeric rule to be unambiguous
Apr 24, 2024
2813835
Apply suggestions from code review
ochafik Apr 24, 2024
46fe648
Update examples/server/public/json-schema-to-grammar.mjs
ochafik Apr 24, 2024
eb7ccd8
json: fix integral-part
Apr 24, 2024
3c02508
Merge branch 'grammar-reps' of https://github.com/ochafik/llama.cpp i…
Apr 24, 2024
476c97d
Merge remote-tracking branch 'origin/master' into grammar-reps
Apr 30, 2024
990bf57
grammar: add repetition tests
Apr 30, 2024
d070aee
Merge remote-tracking branch 'origin/master' into grammar-reps
May 18, 2024
8266b7c
Merge remote-tracking branch 'origin/master' into grammar-reps
May 21, 2024
2b79d47
Merge remote-tracking branch 'origin/master' into grammar-reps
Jun 4, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
grammars: fix copy rule skipping (again) & display of expectations
  • Loading branch i 8000 nformation
Olivier Chafik committed Apr 12, 2024
commit ec913426be308f6daef9cb3274c74585027c1b7a
4 changes: 2 additions & 2 deletions common/grammar-parser.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -174,11 +174,11 @@ namespace grammar_parser {
// Sstar ::= Scopy Sstar |

uint32_t content_rule_id = 0;
if (last_sym_start == out_elements.size() - 1) {
if (last_sym_start >= 0 && last_sym_start == out_elements.size() - 1 && out_elements[last_sym_start].type == LLAMA_GRETYPE_RULE_REF) {
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm trying to wrap my head around this change, and its potential impact -- best I can tell, this is the change that you refer to in the PR description re:

Except if S was trivial at the first place (e.g. single ref), then S is not 'copied' to a distinct rule, e.g.:

S+ --> S'     ::= S Sstar
       Sstar  ::= S Sstar |

(this 'copy' mechanism is to avoid repeating long S sequences - think large groups, or complex char ranges)

One thing I haven't fully wrapped my head around is if the new rewrite rules are more efficient than they were before, less efficient, or about the same. I might need to expand the gbnf-validator and compare the parsed grammars between old-and-new before I really wrap my mind around what's going on here.

Copy link
Collaborator Author
@ochafik ochafik Apr 13, 2024 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

if the new rewrite rules are more efficient than they were before, less efficient, or about the same

Yeah only some benchmarking will tell (and we’d need more real-world grammars for that). My hunch is it’s probably the same, the extra indirection might be negligible, and the saving of avoiding duplication too.

// The repeated content is already a rule ref, no need to copy it
content_rule_id = out_elements[last_sym_start].value;
} else {
content_rule_id = generate_symbol_id(state, rule_name);
content_rule_id = generate_symbol_id(state, rule_name + "_copy");
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

+1 -- One nice thing about using "_copy" for the name here is that underscores are not valid for rule names, so you're guaranteed that you won't get collisions with this. I like it!

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Note that the generate symbol id helper takes care of avoiding collisions anyway

// add preceding symbol to generated copy rule
std::vector<llama_grammar_element> copy_rule(out_elements.begin() + last_sym_start, out_elements.end());
copy_rule.push_back({LLAMA_GRETYPE_END, 0});
Expand Down
Loading
0