Comparison of parser generators

Regular languages are a category of languages (sometimes termed Chomsky Type 3) which can be matched by a state machine (more specifically, by a deterministic finite automaton or a nondeterministic finite automaton) constructed from a regular expression.

A classic example of a problem which a regular grammar cannot handle is the question of whether a given string contains correctly nested parentheses.

The rules of Context-free grammars are purely local, however, and therefore cannot handle questions that require non-local analysis such as "Does a declaration exist for every variable that is used in a function?".

However, parser generators for context-free grammars often support the ability for user-written code to introduce limited amounts of context-sensitivity.

This table compares parser generators with context-sensitive grammars.