Alternative parsing methods

Question

I know something about regular expressions, parse trees and abstract syntax trees. But once I read there is still another parsing technique that, as far as I remember, people from SO used to re-implement its markdown parser.

What I don't recall is the name of this method, or how it did work. Do you? If not, what it could be?

Answer 1

Here's a blog about SO's markdown parser: http://blog.stackoverflow.com/2009/12/introducing-markdownsharp/

Here's the source: http://code.google.com/p/markdownsharp/

It does use advanced regular expressions. I'm not aware of any "other" technique of parsing. The most common solutions for parsing used by virtually all programmers are:

• Regular expressions (or finite state machines) for regular grammars.
• Non-deterministic pushdown automata for context-free grammars. This is where you get parser generators like yacc, bison, ANTLR, etc.

See also the Chomsky hierarchy of formal grammars.

Answer 2

Maybe you're thinking of Parsing Expression Grammars?

(If I'm remembering the same thing you're remembering, it's cletus writing about this here.)