This made me think: Would it make sense to make a formal BNF grammar for the Wikipedia text format, so a LALR(1) parser could be made for it? Would that make any sense at all with PHP, or just be too hard to code and inflexible?
I'd love to have a formal grammar of some kind (I think regexps would be fine), and I agree with Jan that a totally wiki-specific syntax would be far better than out current mish-mash of HTML and wiki markup. But I'm not sure if it's not already too late to revisit those decisions.
But if it isn't, I'll be happy to discuss what a syntax might look like.