Formula Sheets: Lexical Analysis | Compiler Design - Computer Science Engineering (CSE) PDF Download

 Page 1


Lexical Analysis
Lexical Analysis Basics
T ok en Definition
• T ok en: ? tok en-name, attribute-v alue? , where tok en-name is an iden tifier, k eyw ord, op erator, etc., and
attribute-v alue is optional metadata (e.g., lexeme).
Lexeme and P attern
• Le xeme: Sequence of c haracters matc hing a pattern.
• P attern: Regular expression defining tok en structure.
Regular Expressions
Regular Expression Op erations
• Union: R |S ={w |w ?R or w ?S} .
• Conc atenation: R·S ={rs|r ?R,s ?S} .
• Kleene Star: R
*
=
?
8
i=0
R
i
, where R
0
={?} .
• Klee ne Plus: R
+
=
?
8
i=1
R
i
.
Iden tities of Regular Expressions
• ?R =R? =R .
• R |R =R .
• R |Ø =R , R·Ø =Ø .
• (R
*
)
*
=R
*
.
Finite A utomata
Deterministic Finite A utomata (DF A)
• Definition: M = (Q,S,d,q
0
,F) , whereQ is states, S is alphab et,d :Q×S?Q is transition function,
q
0
is start state, F ?Q is final state s.
• T ransition: d(q,a) =q
'
, where q
'
is next state on input a .
• Time Complexit y: O(|w|) , where |w| is input string length.
Nondeterministic Finite A utomata (NF A)
• Definition: M = (Q,S,d,q
0
,F) , where d :Q×(S?{?})? 2
Q
.
• ? -T ransition: Mo v e without consuming input.
• Tim e Complexit y: O(|w|·|Q|
2
) for sim ulation, O(2
|Q|
) for DF A con v ersion.
Con v ersions
Regular Expression to NF A
• Thomps on’s Construction: F or R , construct NF A with ? -transitions.
• Time Complexit y: O(|R|) , where |R| is expression length.
NF A to D F A
• Subset C onstruction: Eac h DF A state is a set of NF A states.
• ? -Closure: Set of states reac hable from state q via ? -transitions.
• T ransition: d
D
(S,a) =? -closure(
?
q?S
d
N
(q,a)) .
1
Page 2


Lexical Analysis
Lexical Analysis Basics
T ok en Definition
• T ok en: ? tok en-name, attribute-v alue? , where tok en-name is an iden tifier, k eyw ord, op erator, etc., and
attribute-v alue is optional metadata (e.g., lexeme).
Lexeme and P attern
• Le xeme: Sequence of c haracters matc hing a pattern.
• P attern: Regular expression defining tok en structure.
Regular Expressions
Regular Expression Op erations
• Union: R |S ={w |w ?R or w ?S} .
• Conc atenation: R·S ={rs|r ?R,s ?S} .
• Kleene Star: R
*
=
?
8
i=0
R
i
, where R
0
={?} .
• Klee ne Plus: R
+
=
?
8
i=1
R
i
.
Iden tities of Regular Expressions
• ?R =R? =R .
• R |R =R .
• R |Ø =R , R·Ø =Ø .
• (R
*
)
*
=R
*
.
Finite A utomata
Deterministic Finite A utomata (DF A)
• Definition: M = (Q,S,d,q
0
,F) , whereQ is states, S is alphab et,d :Q×S?Q is transition function,
q
0
is start state, F ?Q is final state s.
• T ransition: d(q,a) =q
'
, where q
'
is next state on input a .
• Time Complexit y: O(|w|) , where |w| is input string length.
Nondeterministic Finite A utomata (NF A)
• Definition: M = (Q,S,d,q
0
,F) , where d :Q×(S?{?})? 2
Q
.
• ? -T ransition: Mo v e without consuming input.
• Tim e Complexit y: O(|w|·|Q|
2
) for sim ulation, O(2
|Q|
) for DF A con v ersion.
Con v ersions
Regular Expression to NF A
• Thomps on’s Construction: F or R , construct NF A with ? -transitions.
• Time Complexit y: O(|R|) , where |R| is expression length.
NF A to D F A
• Subset C onstruction: Eac h DF A state is a set of NF A states.
• ? -Closure: Set of states reac hable from state q via ? -transitions.
• T ransition: d
D
(S,a) =? -closure(
?
q?S
d
N
(q,a)) .
1
• Time Complexit y: O(2
|Q|
) for state construction.
DF A to Regular Expression
• Arden’s Theorem: F or equation R =Q+R·P , solution is R =QP
*
.
• State Elimination: Remo v e states iterativ ely , com bine transitions as regular expressions.
• Time Complexit y: O(|Q|
3
) .
Input Buffering
T w o-Buffer Sc heme
• Buffers: T w o blo c ks of size b , read alternately .
• Lo o kahead: lexeme_b egin, forw ard p oin ters; forw ard adv ances un til tok en end.
• Time Complexit y: O(1) p er c haracter read.
Lexical Analyzer Generator
Lex T o ol
• I nput: Regular expressions and actions.
• Outp ut: DF A-based lexical analyzer.
• Pro c essing: Con v erts regular expressions to NF A, then DF A, generates transition table.
T ransition Diagram
• G raphical DF A: No des are states, edges are transitions lab eled with input sym b ols.
• A ccepting State: Double circle for tok ens, rollbac k to lexeme_b egin on failure.
2