Lexical Analysis:
Input: Source Code
Output: Lexical Units <lexeme, type>
Regular Exp. (RE) Output C Program
LEX
RE NFA DFA
(Lexical Analyzer)
Lexical Specification: Natural language description of lexical units in a programming language.
Examples:
Identifier (C-like Description): An identifier starts with a letter (or an underscore “_” char) and
it may continue with a letter (or an underscore char) or a digit (0-9). We need at least one
letter in an identifier.
1. Let’s simplify the identifier definition: A identifier starts with a letter (lowercase or uppercase)
and it may continue with unlimited number of letters and digits.
Examples: myvariable, i, I, j, myfunct, streetno12a5b, aptno77, …
2. Integer number(simplified): An integer starts with an optional + or – symbol. It continues
with one or many digits (0-9).
Examples: +5, -22, 67, 23232224234343434, …
3. Comments (old-style): A comment starts with a “/” symbol immediately followed by a “*”.
It may have any symbols followed in any order and in any number. But, it should end with a
“*” immediately followed by a “/” symbol.
Examples: /**/, /* a sample comment line */, /*******/
4. Reserved Words: These are the words used by the programming language. So that they
Are reserved and programmers are not allowed to use them as identifiers. But, actually,
these are also identifiers.
Examples: if, while, for, repeat, do, done, end, begin, int, real, float, …
RE
LEX
int main ()
<”int”, reservedWord>
{ Lexical <’\t’, whitespace>
int i, j=0; Analyzer <”main”, identifier>
i = 1;
<” “, whitespace>
j = i*2;
<”(“, openparen>
return (j); update
<”)”, closeparen>
}
<’\n\l’, whitespace>
i <”{“, opencurly>
j …
Symbol table
REGULAR EXPRESSION (RE):
It is a special representation (formal way) to express a lexical specification.
Three most common operators: 1) Concatenation (.) operator, 2) Branching (|) operator,
3) Repetitions (*) operator (Kleene Closure)
1. Concatenation symbol: We can combine simple regular expressions into more complex
Regular expressions using the concatenation (.) symbol. Usually, the dot operator is omitted.
Example: w.h.i.l.e = while
2. Branching (or ORING) REs (|): We can combine simple regular expressions into more
Complex regular expressions using the branch symbol.
Example: while | for | do | repeat | begin | switch | if |else | …
3. Repetitions (*) operator: The star operator indicates that the prior regular expression
(or symbol) can be repeated zero, one, or many times.
Example:
2. Integer number(simplified): An integer starts with an optional + or – symbol. It continues
with one or many digits (0-9).
d=[0-9] = (0|1|2|3|4|5|6|7|8|9)
d* = {,0,1,2,3,4,5,6,7,8,9,00,01,02,..,11,12,13,..,99,000,001,002,…, 999, …}
d.d* = dd*= d+
(+|-|)dd* = [+-]?d+
Example:
3. Comments (old-style): A comment starts with a “/” symbol immediately followed by a “*”.
It may have any symbols followed in any order and in any number. But, it should end with a
“*” immediately followed by a “/” symbol.
Examples: /**/, /* a sample comment line */, /*******/
/*(.*)*/ = \/\*.*\*\/
Finite State Machines (Finite State Automata):
FSA is another formal representation for lexical specifications. We can convert a regular expression
into a FSA or vice versa.
In FSA, we have two elements:
1) Node (State)
2) Arc (Transition)
Let’s try to write a finite state automaton for recognizing the reserved word, if.
RE: i.f = if
Starting state Final state
Start i B f C
A
(no input is (i is (word is if)
consumed yet) encountered,
waiting for f)
if | int = i(f|nt)
Starting state Final state
Start i f C
A B
(no input is (i is (word is if
consumed yet) encountered, or int )
waiting for either
f or n)
n t
D
(waiting for t)
2. Integer number(simplified): d=[0-9] = (0|1|2|..|9)
(+|-|)dd*
+
Starting state Final state d
Start - d C
A
B
(no input is (integer)
consumed yet) (sign char is
consumed)
-CLOSURE = ECLOSE(A) = it is the set of reachable states from a given input state, A in this example.
ECLOSE(A)= {A, B}
3. Comments (old-style): A comment starts with a “/” symbol immediately followed by a “*”.
It may have any symbols followed in any order and in any number. But, it should end with a
“*” immediately followed by a “/” symbol.
Examples: /**/, /* a sample comment line */, /*******/
/*(.*)*/
CORRESPONDING NFA
Starting state all symbols
but nl
Start / * C
A
B (inside the
(no input is
consumed yet) (/ is comment)
encountered)
D
/
E (a * is encountered.
comment possible exit case)
/***/ (ACCEPTED)
/+**/ (REJECT)
/*(.*)*/
CORRESPONDING DFA
Starting state all symbols except *
Except
Start / * C nl and *
A
B
(no input is (inside the
consumed yet) (/ is comment)
encountered)
not / not *
not / and * *
any symbol
D
/
E (a * is encountered.
comment possible exit case)
*
NFA to DFA Conversion
NFA and DFA are equivalent. They have the same power.
One of the major advantages of NFA is its easy-to-write property. Because,
usually, we have less number of states and less number of transitions in an NFA.
Example: Convert the following NFA to its equivalent DFA form.
State a b
A B, D
B B, C
C C C, D
*D D
a a, b a
a a b
A B C D
D
a
State a b
A BD
* BD BC D =BCD =
* BCD BC C D = BCD CD
*CD C D = CD CD = CD
a a, b
a a b
A BD
BD C
BCD D
CDD
b b
Example: Convert the following NFA to an equivalent DFA
Starting state Final state d
Start - d C
A
B
(no input is (integer)
consumed yet) (sign char is
consumed)
We apply the same algorithm. But, before and after each step of the algorithm,
we take the ECLOSE set of all combined states.
State + - d
ECLOSE(A) = {A, B} = AB B = B, B = B, C = C,
ECLOSE(B)=B ECLOSE(B)=B ECLOSE(C)=C
B C, ECLOSE(C)=C
*C C, ECLOSE(C)=C
Example: Convert the following NFA to its corresponding DFA
1,
bA B C
0 0 0
C
1
E D
1
State 0 1
ECLOSE(A) = ABC E D = DE, AC,
ECLOSE(D) = DE ECLOSE(E)= E ECLOSE(A) = ABC ECLOSE(C)= C
= DE = ABC
*DE A = A, D D =D,
ECLOSE(A)=ABC, ECLOSE(D)=DE
=ABC
1
ABC
0 1
C
DE
0
This DFA accepts all binary strings with odd number of 0s.
Example: Assume {0,1, 2} alphabet for the following question. Draw an NFA that
accepts all strings that end with a repeated symbol.
010202010122, 11, 012111111111, …
Unacceptable strings:
0, 01, 012, 212, 1111111110
Regular expression:
(0|1|2)*(00|11|22)
0, 1, 2
0 B
0
A C
E
1 1
C
2 2
D