Post #2029199

2026-05-04 13:54 UTC

@bal4e I'm not an expert on the nuances of Rust macros, but after reading your blog post, it sounds to me like the matching part describes only regular languages. (I think the token-tree rules are what really make this possible, perhaps?) If that's true then, in principle, matching can always be done in time linear in the length of the input. Although the connection with Earley parsing makes sense, the algorithm you describe sounds a little like a Pike-style VM for regular expression matching, and a lot like the implementation from "A Play on Regular Expressions". Do you think regular expression matching algorithms apply here? If that's too restrictive, I'd want to go re-read the "Parsing with Derivatives" papers (by Matt Might, IIRC).

Replies (1)

@bal4e@tech.lgbt 2026-05-04 14:47

@jamey I think you're right, a macro match arm is pretty much limited to regular languages. I had considered mentioning regexes near the end, but omitted them because they can be ambiguous about ambiguity :p. But regular languages do explicitly allow for ambiguity, so that would work. I think the literature on regular languages could inform this design space further -- thanks for bringing that up! However, meta-variables like $:expr do not fit within regular languages. It seems there is another case of ambiguity there -- a match arm like $(0 +)* $e:expr, given 0 + 0 + 0 + 0 + 0 + 0 + 0, could still result in asymptotic (this time, at worst quadratic) blowup. You could guard for this by supporting packrat parsing for meta-variables too (perhaps only enabling it after certain iterations of the match arm, so that you don't waste time caching stuff in easy cases). I'll add a note to the blog post :)

Open ##2029200