Revamp AST and code generation?

[hildjj]

I'm not sure there is enough value in generating bytecode before we generate code to make up for the complexity and difficulty in tracking sourcemap information accurately. That pass does provide the following in an output-independent way:

• Coalescing repeated copies of string constants (e.g. "foo")
• Coalescing repeated copies of character classes (e.g. [bar])
• Ensuring that rule ordering does not matter
• Coalescing repeated copies of action, predicate, and repeat function bodies
• Probably several other things

The goals of any new approach would be:

• Could be phased in. generate-bytecode could still be used by plugins for a while, until the new system is well-tested.
• Can generate the exact same code as current output, including indentation (at the start, to prove correctness)
• Track as many bits as possible from the source grammar into the generated code so that the source maps are accurate and complete
• Easy to add new output formats, both in Peggy and in plugins
• Easy to add new grammar features, such that older output formats don't break unless you use the new feature. Then a good error message is generated if the new feature is used
• Grammar generation performance matters a little, but not that much
• Size of the resulting bundled-up web version matters
• Easier to understand by JS programmers than the stack-based bytecode approach
• Can stream final output to generate larger outputs than are currently possible
• No runtime cost

What I was thinking about building was a template system that:

• Allows composition of templates
• Takes inputs to the template in the form of location-annotated AST nodes
• No radical change to the existing Peggy AST. Some change is ok, or we might write an adapter pass in the transition period.
• Source-map symbol name tracking for rule names, at least
• Doesn't have a lot of template features like loops, since that can be done by the visitor

Although we could probably whip something up without that much difficulty, I'd like to try to reuse something that already exists. @babel/template and @babel/generator might have most of what we need out of the box. I'm worried about runtime size and performance, but those are things we can measure.

My proposed course of action would be to play with the code in @peggyjs/eslint-plugin that generates simplified JS from a grammar file. We could see how that feels before deciding if we wanted to do anything similar to Peggy itself.

[reverofevil]

While I can't agree more on all of the said above, there is still a catch:

Easier to understand by JS programmers than the stack-based bytecode approach

Codegen without intermediate bytecode would likely have to employ something like ANF as its intermediate language, and even though it's easier to understand by a compiler engineer, I don't think it would as well be to an average JS programmer.

[reverofevil]

Also PEG.js employs a system very similar to a state-of-the-art bytecode-based LPEG. I never asked David, but this doesn't seem to be a pure coincidence, and both tools might be based on same papers. The difference is, bytecode and set of optimizations in LPEG are much more advanced. A good overview is given in chapter 3 of this thesis about another bytecode-based PEG generator.