I'm looking for a BNF grammar of the TeX language, does it exist?
Parsing TeX is Turing complete
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
Will this TeX parse? That depends on the value of f(0) /
It gets worse: category codes
Perhaps, though, you think that you can still perform a rough check for code that looks like a backslash, followed by letters, followed by braced stuff. This will already get inadequate quickly, but that's not all. If delimited macros weren't bad enough, things get even worse when you realize that the reason that the characters
means that all subsequent (La)TeX code must be written like so:
to get output like so:
Constructive Proof that TeX is (at least) Context-Sensitive
Additionally, inspired by TH.'s answer, here's a specific constructive proof that TeX is not context-free. And note that it doesn't have to rely on catcode trickery—just TeX's ability to define arbitrarily-delimited macros. (Yes, this is implied by the first section, but it's still nice to see a specific case in action.)
This code is set up to recognize what Wikipedia calls "the canonical non-context free language" of n copies of
Phew! If you didn't follow all that, here's what a trace looks like, if we only look at the important macros:
Thus, the following TeX
Yields the following output:
But TeX such as
Edit 1: In addition to minor bugfixes/cleanup and breaking the answer into sections with headings, I expanded the rationale for TeX being unparsable by anything short of a Turing machine to hopefully make it slightly more clear. This involved removing the previous
|show 6 more comments|
I can't prove that there is a BNF grammar for Tex but I would like to argue against couple of points made in Antal's answer:
Sorry that I have posted this as a separate answer but the site won't let me make this long comment.
Just to add another angle to the excellent posts by TH. and Antal, is that besides TeX being a Turing complete machine, it can also be coerced to do lambda calculus, the basis of all functional languages. On CTAN there is a package called lambda developed by Alan Jeffrey that implements, among other lambda concepts, unbounded lists. Not only does TeX do all these, but impressively, the routines were implemented in TeX's mouth, proving that TeX's mouth is as powerful as any computer anywhere.
To understand the relationship between the lambda calculus and Turing machines one needs to refer to the Entscheidungsproblem which is one of the famous 23 problems proposed by David Hilbert.
In 1936 and 1937 Alonzo Church and Alan Turing respectively, published independent papers showing that it is impossible to decide algorithmically whether statements in arithmetic are true or false, and thus a general solution to the Entscheidungsproblem is impossible.
This was done by Alonzo Church in 1936 with the concept of "effective calculability" based on his λ calculus and by Alan Turing in the same year with his concept of Turing machines. It was later recognized that these are equivalent models of computation. The work of both authors was heavily influenced by Kurt Gödel's earlier work on his incompleteness theorem - Wikipedia
So the lambda calculus, Turing machines and TeX are not just closely related but they are equivalent models of computation and this is one of many aspects that makes TeX and friends interesting!
It's extremely unlikely. TeX can change how it parses input while it's in the middle of reading the input. I'd have to think a bit longer, but I think that precludes TeX from having a context-free grammar and thus it could have no BNF.