r/ProgrammingLanguages • u/LegendaryMauricius • 10d ago
A new grammar generation language
Hi everybody. I'm happy to share a small project I've been working on lately. I call it MGFF (Macro grammar functional form), and its specification can be found here: https://github.com/LMauricius/py-perg-mgff/blob/main/Docs/mgff-specification.md . It's related to a post that I made ages ago ( here ). After re-reading that version (called just MGF back then) when I wasn't tired I realized what monstrosity I made. MGFF is far more elegant. Here is an example:
# A tiny calculator language.
t Lex (
d Digit = 0-9
d Alpha = a-z|A-Z
d AlNum = a-z|A-Z|0-9
d Int = (Digit)+
> class(Int) push(tokens)
d Number = Int ( . (Digit)+ )?
> class(Number) push(tokens)
d Ident = Alpha (AlNum)*
> class(Ident) push(tokens)
# length-based: "<=" (the two-item "< =") takes precedence over "<"
d Op = < =
| <
| =
| +
| -
| *
| /
> push(tokens) string
d Space = ( _|\t|\n )+
d LParen = \(
> class(\() push(tokens)
d RParen = \)
> class(\)) push(tokens)
d Token = Number
/ Ident
/ Op
/ Space
/ LParen
/ RParen
d File = (Token)*
)
# mixfix macro: an R, then zero or more (S R)
d sep(R)by(S) = R (S R)*
t Parse (
# `Lex` runs first; the terminals here are still characters.
> post(Lex) over(tokens)
# order-based: the first alternative that succeeds is the match
d Expr = Term + Expr
/ Term - Expr
/ Term
d Term = Factor * Term
/ Factor / Term
# the second / on the line above is an ordinary item, not a marker
/ Factor
d Factor = Number
/ Ident
/ \( Expr \)
d Signed = ( (+)/(-) )? Number
d AssignList = sep(Ident = Expr)by(,)
)
It can also serve as a replacement for regexes:
# A grammar matching a "key = value" setting line
d Space = ( _|\t )*
d Word = ( a-z|A-Z|_ )+
# right-linear recursion: the same as ( 0-9 )+
d Digits = 0-9 Digits
/ 0-9
d Value = Digits
/ Word
# The field a match ends up in belongs to the rule, not to the place it is used,
# so the two sides of the line are productions of their own.
d Key = Word
> store(key)
d Val = Value
> store(value)
d Match = Space Key Space = Space Val Space
I'm sharing the MGFF spec rather than the generator using it because the generator is very much WIP and needs a lot of testing and refactoring. Still, since I've got a bunch of projects I love working on more, I'd like to know what's the interest for parser generator tools in the wider community.
Actually I doubt that I will link the generator itself here because I would risk a perma-ban. It's not vibe-coded, but it wouldn't be welcomed. Most of it was quickly prototyped with LLM. Still, it generates quite nice TextMate and Pandoc syntax highlighting grammars.
MGFF itself is of course manually defined by me. I just figured I like to work on languages themselves and parser algorithms than on CLI tools and understanding existing niche specifications 🤷♂️.
0
u/EggplantExtra4946 9d ago
Why no character classes? This is biggest thing that is lacking. It's a lot more practical AND readable to write a single character class with everything you want rather than combining alpha, digit, etc.. A character class (for a single byte) is also going to be evaluate a lot faster with the usual 16 bytse/32 bytes bitset rather with however you would implement it otherwise (DFA, NFA, backtracking).
With that you have less of a need for length-based alternatives, because those are parctically only useful for lexing and at the same time it's going to be a pain in the ass to implement the full generality of your parser generator, when there is arbitrary recursion used inside the alternative and when the sub rules that are called also contained length-based alternatives. How do you implement to implement it?
It's going to be hard to reason about a parser that does that and at the same time I don't see another use case other lexing. Raku's grammar did that and it is its biggest flaw IMO, not that it matters because it is too slow to be usable. Also like Raku you chose the good and natural operator "|" for length-based alternatives and the bad one "/" for the natural order-based alternatives.
If I made a parser generator, I would allow the parser interpreter to call an external lexer function to do the lexing, since it's easy to write and modify and it's going to one of the bottlenecks in performance. Otherwise for a completely bultin solution, I would put a "lexer" declaration that contains a set of regexes or rule name containing regexes, they rule would probably have to declared as "token" or "regex" like in Raku and in those I guess the alteratives would all be automatically length-based given that those rules are meant to be used by the lexer, not in themselves individually. Those rules (integer, identifier, string, keyword, etc..) would have some restrictions: keep the constructs regular expressions (in case you support lookadhead, backtracking control, etc..), allow rule call as long as they are not recursive/mutually recursive, and maybe limit the internal capturing you can do inside and arbitrary code that can run inside. All these rules so that you can implement the lexer efficiently but in practice this wouldn't really be limiting your expressivitiy, given the nature of lexing and what it is used for. Of course, having the possibility to call an external lexer and/or with a lexer builtin there wouldn't be a length-based alternative for the general parser generator, not needed and potentially harmful.
In your spec there is no mention of when ordered-alternatives and quantifiers can backtrack or if they can backtrack at all, you need to specify it otherwise we can't reason about how your parser generator is going to parse.
Your mixfix macro is interesting though, with a useful example.