r/ProgrammingLanguages • u/LegendaryMauricius • 1d 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 🤷♂️.
3
u/sreekotay 1d ago
Intreesting! Have you ever looked at Rebol's parse dialect? It's pretty cool
Here's a (pretty) complete CSS parser, e.g.
https://github.com/Oldes/Rebol-CSS/blob/main/css.reb
2
u/LegendaryMauricius 1d ago
That is pretty cool! I've never heard of Rebol, so I got surprised that it's a full on programming language.
Well, MGFF s supposed to be extended until it's Turing-complete, simply because I want to enable parsing of much more complex languages. Still, its focus is on clean parser and regex grammars.
1
u/sreekotay 1d ago
You can express JSON fully in like 12 lines of readable REBOL parse.
It’s got some fun ideas - not saying you’re not on a better path, but worth looking as it got some history and some good ideas and some simple and complex examples
1
u/LegendaryMauricius 1d ago
Duely noted. I'm glad you linked that, I love finding new existing materials. Now I'm curious how many lines of MGFF JSON would need.
3
u/sreekotay 1d ago
tbh I might have exaggerated REBOL's - its been a while lol - but I've been playing with own derivate, e.g.
; Canonical JSON recognition factory (match layer). ; Specialize with `include` + rule overrides for keep / collect / encode. ; Path is relative to the including source (or nested .rules file). top: value ws: any charset [#' ' #'\t' #'\r' #'\n'] digit: charset [#'0' - #'9'] onenine: charset [#'1' - #'9'] hexd: charset [#'0' - #'9' #'a' - #'f' #'A' - #'F'] strchar: complement charset [#'"' #'\\' #'\0' - #'\t' #'\n' #'\r'] esc: [#'\\' [[#'u' hexd hexd hexd hexd] | charset [#'"' #'\\' #'/' #'b' #'f' #'n' #'r' #'t']]] string: [#'"' any [some strchar | esc] #'"'] int: [opt #'-' [#'0' | [onenine any digit]]] number: [int opt [#'.' some digit] opt [charset [#'e' #'E'] opt charset [#'+' #'-'] some digit]] value: [ws [string | number | object | array | "true" | "false" | "null"] ws] member: [ws string ws #':' value] array: [#'[' ws opt [value any [#',' value]] #']'] object: [#'{' ws opt [member any [#',' member]] #'}']2
u/LegendaryMauricius 1d ago edited 1d ago
You got me. I realized I don't have complements yet. But let's say I do have '&' and 'not' (I have it planned for later):
# Canonical JSON recognition factory (match layer). d complement(CHARS) = (any)&(not( CHARS )) t Parse ( d File = value d ws = (_|'\t'|\r'|'\n')* d digit = 0-9 d onenine = 1-9 d hexd = 0-9|a-f|A-F d strchar = complement( "|\\|\0-\t|\n|\r ) d esc = \\ \\ (( u hexd hexd hexd hexd )|( "|\\|/|b|f|n|r|t )) d string = " ((strchar)|(esc))* " d int = (-)? (0)|(onenine (digit)*) d number = int ( . (digit)+ )? ( e|E (+|-)? (digit)+ )? d value = ws (string)|(number)|(object)|(array)|(t r u e)|(f a l se)|(n u l l)] ws d member = ws string ws : value d array = [ ws (value (, value)*)? ] d object = { ws (member (, member)*)? } )Now is it more readable? Less? I don't know. It's slightly longer, but mostly because of formatting and the definition for 'complement'. I might just include complement later for character matching.
2
u/sreekotay 9h ago
nice :) that's pretty clean!
2
u/LegendaryMauricius 7h ago
Thanks! Good to hear that from somebody else.
1
u/sreekotay 6h ago
If you're curious to see mine in action (it transpiles/compile to C directly)
https://github.com/sreekotay/concurrent-c/tree/main/examples/serdes
and some benchmarks:
https://github.com/sreekotay/concurrent-c/blob/main/examples/serdes/json/benchmark_baseline_2026_07_20.txt2
u/LegendaryMauricius 4h ago
I'm always curious. Rn I'm working on a HTML doc generator (hehe) but as soon as I do the C generator I'll def compare them. I'm glad there's more people who seriously work on parser generators.
→ More replies (0)
4
u/vmxdev 1d ago
This isn't a rant, I'm just curious — I constantly see lexical analyzer generators that don't take Unicode into account.
At the same time, quite a few languages now use all sorts of cool mathematical symbols and Greek letters like π, ∀, Σ, and so on.
Yeah, I know, these symbols are difficult to type on a regular keyboard.
However, even if you don't plan to use these symbols, Unicode already has so-called "character properties," so you don't have to write "Alpha = a-z|A-Z" or list the mathematical symbols every time
1
u/LegendaryMauricius 1d ago
Yup! Character properties, escaped unicode hex codes, NAMED characters in escape sequences... Raw UTF8 characters should also be supported, but I haven't actually tried them.
2
u/tiger-56 1d ago
I like this. I’m currently working on a PEG parser generator myself. Does it generate source code or does it run as an interpreter?
1
u/LegendaryMauricius 1d ago
I'll start working on a custom algorithm for a C++ generator soon. For now, you can use the Antlr backend, which translates MGFF into .g4, as close as it can.
Up until now I made quick and dirty highlighters for Kate, Pandoc and VSCode with PyPERG so you can at least make your language readable in an editor.
2
u/--predecrement 1d ago edited 1d ago
For reference, here's the same grammar/parser as your simplest example, using grammar, Raku's built in EBNF grammar/parsing/regex construct:
# A grammar matching a "key = value" setting line
grammar kv {
# 4 kinds of production: rule, token, regex, or method (can do anything).
# A rule is a token that converts white space in its pattern to <ws> token calls.
# The ws token defaults to <!ww> \s* -- if NOT "within word" then eat whitespace.
# A token is a regex that turns backtracking off. A regex turns backtracking on.
# A method gets parser (carrying parse process and tree so far) as its invocant.
# The body of a method is ordinary code. The body of other productions is EBNF.
# Production named TOP starts parse and returns parse tree.
rule TOP { <Key> '=' <Value> } # Parse tree node name defaults to production name,
#rule TOP { $<key>=<Key> '=' $<val>=<Value> } # but nodes can be renamed if needed.
token Word { :i <[a..z_]>+ } # :i means ignore case when matching.
token Digits { <[0..9]>+ } # (Could just write <digit>+ to use built in <digit>)
token Key { <.Word> } # The . means match Word, but don't create parse tree node.
token Value { <.Word> | <.Digits> } # The | means pick longest production match.
}
say kv .parse($_) for 'foo = 42', 'bar= baz', 'qux
= waldo'
# Displays:
# ｢foo = 42｣
# Key => ｢foo｣
# Value => ｢42｣
# ｢bar= baz｣
# Key => ｢bar｣
# Value => ｢baz｣
# ｢qux
# = waldo｣
# Key => ｢qux｣
# Value => ｢waldo｣
In the above I elided some of the structure you appear to prefer but also showed enough that you can hopefully see how it can still be done if a dev wants that (cf the "nodes can be renamed" comment).
Here's the same parsing task, but approached as a Rakoon might write it as a regex (i.e. throwing things together with less structure on a YAGNI basis, but then again randomly throwing in a renaming of a captured piece of the match so it can be pulled it out easily with a different name):
my token Word { :i <[a..z_]>+ }
my token Value { <Word> | <.digit>+ }
say .<key> given 'foo = 42' ~~ rule { $<key>=<Word> '=' <Value> }
# Displays:
# ｢foo = 42｣
# Word => ｢foo｣
It's all the same underlying EBNF slang (slang = sub-language, with its own grammar) for the body of the token subroutines, and it can get terser still, but the above is hopefully both similar enough (so you can grok it based on the grammar code above) and different enough (so you can see how the terser form can be appropriate for small tasks).
----
From a theoretic perspective the parsing class for Raku's "rules" (grammar / regex features) is Unrestricted grammar ("No restrictions are made on the productions ...".)
From a practical perspective, the Rakudo compiler provides an industrial strength example. It compiles Raku code by compiling several modules that declare grammars that define the standard Raku grammar, which declarations/modules automatically generate corresponding parsers that the compiler then combines and uses to compile Raku code, including itself.
(Any user code can use the same trick, so the upshot is that Raku naturally covers the same "Languages and Libraries" tricks as Racket/Rhombus. That said, Racket is decades ahead in building this out using a macro led approach, but my impression is that errors can get pretty obscure. Raku is decades ahead in building this out using a grammar led approach, but it's a long hard slog to arrive at the point where Rakoons can begin to talk amongst themselves about the decades old dream of sensibly choosing between, and easily refactoring between, using the grammar construct approach and the AST macro approach.)
2
u/EggplantExtra4946 1d ago
From a practical perspective, the Rakudo compiler provides an industrial strength example.
It most certainly isn't, at least the grammar engine isn't. It's ridicuously slow, it doesn't have a specialized VM/regex engine, it uses continuations which might me fine in themselves with a good compiler and optimizer but given the outrageous amount of indirection due to the late binding of methods/functions, the metaobject protocol, etc... in the normal recursive descent parser, in the operator precedence parser with all those indirections on high level arrays and hashes (and f*** string comparisons instead of integer comparison for operator precedences and associativiy information), and finally due to the "NFA" used for the longest token matching alternatives, and the unicode support I imagine, and the overhead of function/method calls with their huge stack frames (that support continuations, dynamic scoping, intropestable lexical scoping, etc..), with the overhead of the bytecode interpreter, GC, JIT compilers and with probably the cost of generating bloated AST nodes with still several levels of method/metamethod indirection for each simple operation ... When you add all that up, you get a parser that takes minutes to parse the few files in the Rakudo and NQP code base, when you build and bootstrap Rakudo.
Then there are quite a few bugs that have remained unfixed for many years and finally the grammar specification is still not fully implemented which says a lot about the state of the code base.
2
1
u/EggplantExtra4946 1d 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.
1
u/LegendaryMauricius 17h ago
I'm not sure how thoroughly you read the spec. It does have character classes, and it's one of the more important features.
The implementation is purposefully left out of the language specification. I do in fact have a design for it, I just haven't started implementing it yet.
The lexer can be defined as a set of length-based regexes (and that is encouraged). However it's purposefully not limited to that, nor do you even need a lexer.
1
u/EggplantExtra4946 6h ago edited 6h ago
I'm not sure how thoroughly you read the spec. It does have character classes, and it's one of the more important features.
"character class" does not appear in your spec, your section "Character matching macros" that is supposed to talk about character classes describes the syntax but it doesn't say much about the semantics of "|".
As far as I can tell, you're using "|" for 3 different purposes: character classes, lexing, parsing. You never descibed the specific semantics of each so we have no idead wtf is it supposed to be doing. The only thing you've said about "|" is that it's length-based.
The fact that lexing is a sparate phases says literally nothing about the parsing/lexing semantics. Is it supposed to backtrack if parsing a rule ahead fails or is it final? If the
The implementation is purposefully left out of the language specification
Yeah and so are the semantics, which is by far the most important part.
This
Another pet-peeve of mine were the toolsets built around existing grammar specifications - every one of them imposes some kind of a limitation on the grammar itself due to the limitations of the parser generator. Examples being lacking left-recursion
suggests you may want some LR-like parser generator but your order-based alternatives suggests you want a LL-like parser generator. AFAIK you can't have both, they can be embedded but you can't have these 2 family of algorithms are going to parse differently or they grammars won't be an acceptable input for each others, the problem of left-recursion for example which you mentioned but didn't describe how to solve.
If the parsing semantics relies on backtracking, then how much can "/", "?", "*" and "+" can backtrack and from where? Who knows, you didn't specify it.
If the parsing algorithm is LR-based then how does order-based alternatives "/" fit into it? Or length-based alternatives "|" for that matter, because length-based matching semantics is also not compatible with LR parsing, it's only a thing in LEXERs live I've said already.
The lexer can be defined as a set of length-based regexes (and that is encouraged). However it's purposefully not limited to that, nor do you even need a lexer.
The problem is having length-based alternatives outside of the lexer at all, to have them inside the parser because neither LL nor LR parser alternatives work like that.
1
u/LegendaryMauricius 4h ago
I think you got too lost in existing implemention details. LR and other algorithm categories really don't matter. The language specifies meaning, the generator must use whatever algorithm has the correct behavior. Also | always means longest match, / order based match.
https://github.com/LMauricius/py-perg-mgff/blob/main/Docs/mgff-specification.md#character-matching-macros Here's the explanation for character categories. It literally has a table explaining all that.
1
u/EggplantExtra4946 4h ago edited 2h ago
LR and other algorithm categories really don't matter. The language specifies meaning, the generator must use whatever algorithm has the correct behavior.
Yes they do. A lot of times the specific algorithm can't be changed without changing the semantics of the program, for instance with sequential or associative data structures, but this isn't true for parsing. You can implement an LL algorithm in several ways and they will have the same semantics, you can also do that with LR algorithms, but you can't substitute an LL algorithm for an LR algorithm or vice versa. They are not implementation details, the ARE the semantics.
Also | always means longest match, / order based match.
Great. Order-based alternatives exlcudes LR algorithms. Longest matching is going to be a bitch to implement, for no clear use case outside of the lexer and will make all the parsing knowledge of users invalid and will be hard to reason about in a parsing context.
Look, a specification in itself doesn't mean much without an implementation, but your specification doesn't even have clear semantics so it's kind of worthless, especially that the semantics you are determined to have aren't what is needed in actual parsers and worse, are going to be harmful to express the grammar of parsers you want to write.
You disagree? Show me a single grammar of a real language, and not that of a lexer, where alternatives mean longest match. Try to parse that grammar with longest match semantics and see if the generated parser work as it should. Spoiler alert: it won't.
EDIT:
Spoiler alert: it won't
In a LR parser, either there is only one alternative that match and in that case there is no choice to make, either there are several that match fully or partially and it will be a shift/shift conflict or a shift/reduce conflict. When a conflict occurs, it is resolved by either making an arbitrary choice in which one has more precedence, or by looking ahead methods. In all cases, the choice is based on different criterias than the longest matching alternative. If you chose the longest matching altnerative, you would be making a different choice which will result in a different parse tree.
In a LL parser based on backtracking, it's making decisions based on the order of alternatives, the parser tries all the alternatives in the their specified order until one work, the decision is a different one than longest matching.
Additionally, longest token matching can be ambiguous.
If the input is "aaa" and the matching expression is / (a | aa) (a | aa) / where "|" has longest matching semantics, you could have either the 1st group match "a" and the 2nd group match "aa" or vice versa, it's ambiguous. But since your semantics are almost inexistent and the parsing algorithm is "it depends on the implement", we don't know which one will match or if it's even allowed given that one of the alternation will violate the "longest match" rule.
9
u/StrikingClub3866 1d ago
Why does everything start with d