Support for Grammar Flow Graphs.

mdaines / grammophone

A tool for analyzing and transforming context-free grammars.

https://mdaines.github.io/grammophone

MIT License

200 stars 23 forks source link

Support for Grammar Flow Graphs. #27

Closed modulovalue closed 1 year ago

modulovalue commented 1 year ago

Hello @mdaines,

I've recently come across A Graphical Model for Context-Free Grammar Parsing. It establishes a connection between control flow graphs and context free grammars. It calls them Grammar Flow Graphs (GFGs):

I'm going to try to see how well graphviz can handle displaying them for my own tools. I think it would be really cool if grammophone supported them. If you'd consider doing that, I can share some of my experiments here.

mdaines commented 1 year ago

It seems interesting, although I'd need to give the paper a closer look to really say. The current feature set is based on Louden's Compiler Construction: Principles and Practice which was the textbook in the course Grammophone was developed to supplement. If this type of diagram is used in other textbooks or courses, maybe it's a good candidate for a feature to add. Otherwise, I'm not sure I want to support it.

If you'd like to generate this type of diagram in your own tools, it could be helpful if the Grammar class was available in a separate package, which is something I've been thinking about doing.

modulovalue commented 1 year ago

[...] I'm not sure I want to support it.

No problem, thank you for the response!

I have implemented a CFG to GFG to graphviz converter and here's how graphviz handles GFGs:

not well, I think. Increasing the rank separation doesn't help much.

Given the goals of grammophone that you've mentioned, and the fact that graphviz doesn't seem to be well suited for visualizing such flow graphs, I am going to close this issue.