Chomsky hierarchy

A classification of formal grammars by expressiveness - from simplest to most powerful: regular, Context-free (parsers), Context-sensitive (type systems), recursively enumerable; explains why parsing

A classification of formal grammars by expressiveness - from simplest to most powerful: regular, context-free (parsers), context-sensitive (type systems), recursively enumerable; explains why parsing and type checking are separate phases with different complexity.