Regular Expression
Ø An expression
that represents a regular language is known as regular expression
Ø Regular expression
is a formula that describes a possible set of string
Ø Regular
expression are short hand notations to represent regular languages
Ø Regular
expression can be defined by following rules
§ Any terminal
symbol is a regular expression
Example: a, b,?,....
Empty
string is also a regular expression
o
Let R1, R2 be two regular expressions, the union of R1
and R2 can be written as R1 + R2 is also a regular expression
Example:
R1 = a, R2 = b
R1 + R2 = a + b
o
Let R1, R2 be two regular expressions, then concatenation
of R1 and R2 can be written as R1.R2 is also a regular expression
Example:
R1 = a, R2 = b
R1.R2 = ab
o
Let R1 be a regular expression, then iteration of R1 can
be written as (R1)* is also a regular expression
Example:
R1=a
(R1)* = a*
o
Let R1 be a regular expression, then (R1) is also a
regular expression. Here parenthesis indicates priority of an expression
Ø Regular
expression uses three operators. They are
§ Iteration (*)
§ Concatenation
(.)
§ Union (+)
Ø Precedence's
rules can be defined as
§ Iteration takes
higher precendence than concatenation
§ Concatenation
takes high precedence than union.
i.e.
iteration > concatenation > union
Ø Let L be a
language and R be regular expression then L(R) denotes the regular language
that represents regular expression
Example
o
The regular expression R=a+b denotes the language L(R)
={a,b}
R=(a)*
denote L(R) = {ε,a,aa,aaa,aaaa,...........}
R=(a)+
denote L(R) = {a,aa,aaa,aaaa,...........}
o
The regular expression for identifier is letter
(letter/digit)*
§ Regular
expression for letter is A/B/...../Z/a/b/b...../z
§ Regular
expression for digit is 0/1/2/..../9
o
Regular expression for number is digits fractional_part
exponential_part
o
Regular expression for digits is digit digit*
o
Regular expression for fractional_part is .digits/e
o
Regular expression for exponential_part is (E(+/-/ε ) digits)/ ε
Home
|
