Regular expression in compiler design

The finite set of valid string token lexeme which belongs to the language in hand are scarred and identified by the lexical analyzer. The pattern defined by the language rules is searched by the lexical analyzer.

It defines a search pattern for stings.Regular expressions have the capability to express finite language by defining a pattern for finite strings of symbol. The grammar defined by regular expression Is known as regular grammar . The language defined by regular grammar is known as regular language.

Why Regular expression is important?

>> Regular expression is an important notation for specifying patterns.Each patterns matches a set string , so regular expression server as names for a set of strings,programming language . Regular expression is an example of recursive definition . Regular languages are easy to understand and have efficient implementation.

Rules of regular expressions

Regular expressions are used to denote regular languages, AN expression is regular if

1) ø is regular expression for regular language ø.

2) ε is a regular expression for regular language { ε }.

3) If a ε Ʃ ( Ʃ represents the input alphabet ) a is regular expression with language { a }.

4) If a and b are regular expression, a+b is also regular expression with language {a,b}.

5) If a,b are regular expression , ab (concatenation of a and b ) is also regular .

6) If a is regular expression a^*(0 or more times a ) is also regular .

Closure properties of regular language

Union

If L1 and L2 are two regular languages,their union L1 U L2 will also be regular . for example ,

L1 = {aⁿ| ≥ 0} and L2 = {bⁿ| n ≥ 0}

L3 = L1 + L2 ;

= {aⁿU bⁿ| ≥ 0} is also regular expression .

Intersection

If L1 and L2 are two regular languages,their union L1 ⋂L2 will also be regular . for example ,

L1 = {aⁿ b^m| n≥ 0 and m ≥0}

L1 = {aⁿ b^mUb^maⁿ | n≥ 0 and m ≥0}

L3 = L1 intersection L2

= {aⁿ b^m| n≥ 0 and m ≥0}

Concatenation

If L1 and L2 are two regular languages,their union L1 ⋂L2 will also be regular . for example ,

L1 = {aⁿ| ≥ 0} and L2 = {b^m| n ≥ 0}

L3 = L1.L2 = {aⁿ b^m | n≥ 0 and m ≥0} is also regular

Complement

If L(G) is regular language ,its complement will also be regular expression.complement of a language can be found by substracting string which are in l(G) from all possible strings for example.

Note :

l 1) r1r2 = r1 followed by an r2

l R1 | r2 = r1 or r2 /either r1 or r2

l R? =means an R or nothing