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)/ ε
0 comments:
Post a Comment