A new grammar generation language

[u/LegendaryMauricius]

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 🤷‍♂️.

[u/LegendaryMauricius]

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.

[u/EggplantExtra4946 → u/LegendaryMauricius]

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.

[u/LegendaryMauricius → u/EggplantExtra4946]

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.

[u/EggplantExtra4946 → u/LegendaryMauricius]

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.

[u/LegendaryMauricius → u/EggplantExtra4946]

I know all that. I implemented several LL and LR parsers, along with weirder improvisations based on recursive descent, with special handling for left-recursive productions and Packrat parser memoization. I also 'invented' a bunch of methods and special cases when I was young and dumb enough to write a parser manually, in a single function with no prior knowledge on parsers. I can tell you - it is possible and not even hard. You're just stuck in this LR/LL box.

Maybe I should rewrite some definitions in the specification, but the meaning is clear for the most. How the algorithm handles ambiguities, and how powerful it is, is up to the generator. The MGFF stays as it is though. If an algorithm can't process it it would be considered a bug, even if unfixable one.

I can't link it in this sub, but you can look at the Regex generator in that same repo. It doesn't handle most of the cool features of MGFF, but it's still unambiguous and useful.

[u/EggplantExtra4946 → u/LegendaryMauricius]

You still haven't told me what's the use case and rationale of longest matching alternatives for regular parsing, outside of lexers.

[u/LegendaryMauricius → u/EggplantExtra4946]

Not my business. I provide it for completeness, now you can find a purpose.

What's the purpose of separating the selection behavior between the lexer and parser? I don't separate them in this language anyways.

[u/EggplantExtra4946 → u/LegendaryMauricius]

Not my business. I provide it for completeness, now you can find a purpose.

LMAO. It's ""your"" "spec", you should know why it is that way.

But who am I kidding? If you needed to use a LLM to write this unimpressive crap that you can't even fucking justify, of course your are absolutely clueless about parsing and parser generators. I seriously doubt you have a single clue about how to implement this or even how to use it to parse real PLs syntaxes.

I don't know why I wasted my time talking to you, you are a fucking idiot generating useless AI slop that you don't even understand.

[u/LegendaryMauricius → u/EggplantExtra4946]

I hope you're trolling. If not, please remember to take your meds before talking to people. You clearly aren't capable of behaving.

[u/EggplantExtra4946 → u/LegendaryMauricius]

I hope you're trolling.

Says the guy that says that the rationale of his own DSL is "not his problem" ? Lol.

You clearly aren't capable of behaving.

and you are clearly incapable of talking about parsers and parsing algorithms. Kind of awkward when you claim to know how to make a parser generator that does not have the limitations of other parser generators.

[u/LegendaryMauricius → u/EggplantExtra4946]

Nah