$Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers$

Is there a BNF grammar of the TeX language?

submited by

Style Pass

2024-06-06 22:30:07

Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Ask questions, find answers and collaborate at work with Stack Overflow for Teams. Explore Teams

For those who don't know their Chomsky, a CFG is a context-free grammar, which means (very roughly) that substitutions can be made independently of their use context.

TeX can only be parsed by a complete Turing machine (modulo the finite space available), which precludes it from having a BNF. This comes from a combination of two features: first, TeX is Turing complete (if you need proof, this Turing machine simulator should suffice); and second, TeX can redefine macros (and their parsing rules) at runtime. Since TeX can require that macros be followed by specific characters, redefining a macro can mean redefining the syntax of TeX. Combining these facts means that we can write TeX code like the following, where \f is defined to be the algorithmic representation in TeX of some arbitrary (computable) function f : ℤ → ℤ:

Will this TeX parse? That depends on the value of f(0) / \f{0}! And since TeX is Turing-complete, computing this value may require a full Turing machine, and therefore so will determining whether or not \Required! is valid TeX syntax.