Regular, Recursive, Restricted: Floyd!

(I sent this as an email at first, but I'm not sure if it landed in your Spam folder; figured I'd try here) So, there's a very tractable subset of the context-free grammars that's an exact match to your desires: Floyd grammars, AKA operator-precedence grammars. They're parsed by either the Shunting-Yard algorithm (Donald Knuth, bottom-up) or Pratt parsing (Vaughan Pratt, top-down), and are closed under all the usual operations (more than CFG is!). They are also a deterministic class. They have an operator precedence _matrix_, allowing them to represent a partial order of operator precedence, including operators that are incomparable and must be parenthesized; this is strictly more expressive than numeric precedence. They do _not_ have the nasty "undecidable emptiness" problems of CFG. A good thesis that goes into depth about them, by Federica Panella: [PDF](https://www.politesi.polimi.it/retrieve/a81cb05b-abbf-616b-e053-1605fe0a889a/2016_01_PhD_Panella.pdf) There are also generalizations of them to the world of infinite streams, where ω-grammars live.