BNF (short for Backus-Naur Form) is a notation for specifying syntaxes. It allows specifying syntax with sums (|) and products (). For example, foo ::= 1 | 2
specifies that foo
can be either 1 or 2, and baz = <foo>2
specifies that baz
can be either 12 or 22.
A BNF matcher is a program that takes as input a grammar and a string and tells us whether the string is captured by the grammar or not. A BNF parser works similarly, but instead, it generates a syntax tree out of it rather than telling if a particular string matches the structure.
BNF is important because it’s used as the syntax of languages in computing, mainly in programming languages. That is, any time you get a “Syntax error! Missing ;” or a similar error, you can freely blame BNF 🙂
We will start with a concrete example, then give a general algorithm and finally write a BNF matcher in PHP and Lisp.
Continue reading “An algorithm for a BNF matcher” →