Parsing English

In most cases, a parser for a programming language never has to back up: if it sees if, the input must be an if statement or an error.

Parsing English requires that the parser be able to fail, back up, and try something else: if it sees in, the input might be in Austin or in April, which may be handled by different kinds of grammar rules.

Backup means that parsing is a search process, i.e. likely to be NP-complete. However, since English sentences are usually short, this is not a problem in practice.

An Augmented Transition Network (ATN) framework facilitates parsing of English.