Brainfuck is one of my favourite languages. Not that I _write_ any code in it, mind you, but there's a bunch of code out there written for it (thank you, you crazy people), and it's so tiny and so simple that you can write an interpreter for it in an hour or two.
Because the syntax is so minimal, there's little point for a naive interpreter to include a parser and you can write it directly as a bytecode interpreter (and my experience has been that most beginners will do exactly that on their first attempt).
However, if you _do_ decide to write a (really basic) parser for it, you can easily end up with a tree walking interpreter instead, and, from there, it's only a tiny jump to start manipulating the AST. E.g. the simplest change you can make is to do away with the separate Increment and Decrement instructions, and replace them with a generic Add instruction, so + and - get parsed as Add 1 and Add -1 respectively. Then you can replace runs of mixed - and + characters as one single Add instruction (--+-+++ becomes Add 1, for example). If you add a Set instruction, the [-] sequence can be translated to Set 0. Likewise, [.>] can become printf(ptr) instead of a loop of putchar(*ptr).
Put all of this together, and it turns out that BF is perfect to introduce people to interpreters, and to demistify the whole "writing a language" thing.
It's quite fun to write a bf->c "compiler" and look at the assembly output that results from compiling that c. The result can be remarkably efficient; GCC will trivially reduce a double-loop of incrementation down to a single multiply instruction for example, it will optimize away pointer manipulation and just use registers, etc.
Because the syntax is so minimal, there's little point for a naive interpreter to include a parser and you can write it directly as a bytecode interpreter (and my experience has been that most beginners will do exactly that on their first attempt).
However, if you _do_ decide to write a (really basic) parser for it, you can easily end up with a tree walking interpreter instead, and, from there, it's only a tiny jump to start manipulating the AST. E.g. the simplest change you can make is to do away with the separate Increment and Decrement instructions, and replace them with a generic Add instruction, so + and - get parsed as Add 1 and Add -1 respectively. Then you can replace runs of mixed - and + characters as one single Add instruction (--+-+++ becomes Add 1, for example). If you add a Set instruction, the [-] sequence can be translated to Set 0. Likewise, [.>] can become printf(ptr) instead of a loop of putchar(*ptr).
Put all of this together, and it turns out that BF is perfect to introduce people to interpreters, and to demistify the whole "writing a language" thing.