The grammatical approach outlined herein is in many ways complementary to such deep generative models. A simple generative grammar can be defined with very little reference data or derived from physical concepts (partial understanding) like charge neutrality. Furthermore, 'modecollapse' is not an issue, as the grammar can simply be sampled uniformly. On the flipside, deep generative models are currently a much more powerful and mature technology. In this context we can again take cues from the related field of molecular design, where it has been shown that the robust SELFIES grammar can be used both to enhance the quality of deep generative models and as a competitive generative model in its own right. Conclusions: In this perspective, we have discussed the potential benefits of using formal grammars to discover new heterogeneous catalysts. This approach is intellectually stimulating, though it may seem slightly frivolous at first glance. Considering the leading role that string representations and grammars play in molecular design, we firmly believe that this can lead to real advances in catalyst discovery, however. To achieve this goal, we have sketched several promising research directions. These include the development of powerful string representations for solids and surfaces, the use of graph-based grammars and the combination of grammars with deep generative models.