Programming Languages: Concepts and Implementation

2.3 Regular Expressions and Regular Languages

2.3.1 Regular Expressions

Since languages can be infinite, we need a concise, yet formal method of describing languages. A regular expression is a pattern represented as a string that concisely and formally denotes the strings of a language. A regular expression is itself a string in a language, albeit a metalanguage—a language used to describe a language. Thus, regular expressions have their own alphabet and syntax, not to be confused with the alphabet and syntax of the language that a regular expression is used to define.

Table 2.3 presents the six primitive constructs from which any regular expression can be constructed. These constructs are factored into three primitive regular expressions (i.e., ...