Expression programming languages

According the Chomsky hierarchy, there are 4 categories. From most expressive to least:

• Type-0: Recursively Enumerable Grammar

• Type-1: Context Sensitive Grammar

• Type-3: Context Free Grammar

• Type-4: Regular Grammar

These grammars are used to express the syntax of the programming language. Semantics, on the other hand - which deals with how we evaluate the constructs - gives the programming language ability to do things. In practice, programming languages like C, JS, etc can be expressed with a Type-3 grammar (CFG) but are turning complete (i.e. most powerful machines we know).

Example of a Type-4 - Regular Grammar is during the lexical analysis stage of the compilation process of a language i.e. break the input into tokens. Also, pattern matching using simple regular expressions are an example. RegExps using lookahead and backtracking are a different story.

---

• Tags: cs programming