Address parsing is actually very easy. Knowing when you got it right (or wrong), that's the hard part, and that's where address validation come in handy.

If you can start with a list of all the following, you've got a great start:

prefix abbreviations street names street types suffixes city names state names

Add to that all the possible misspellings and then factor in levenshtein and soundex to account for misspellings you didn't know about and you've got a pretty dang good address parser. Figure out how to do that lickety-split fast, and you've got gold.