A grammar example

bc is an arbitrary precision calculator. It’s part of the POSIX specification for Unix operating systems. That specification not only requires a bc program to be present but also gives a minimal grammar which it must recognise, which makes it useful as an example. Even this grammar is a bit too complex as an initial example though so I’ll only use pieces of it.

Grammars are usually specified in some variant of Backus-Naur form. The specification uses the variant used by yacc, a parser generator. Internet RFC’s, the documents which govern the internet, use a different variant, or really several different variants. I’m going to use yet a different variant, derived from one of the parser generators used by the Racket programming language, which is more concise than the others mentioned above. All of these are similar enough that if you have experience with one you can usually figure out any of the others without even needing to consult the documentation, unless the grammar writer has used some really obscure features of a particular one.