Lexical Analysis
Tutorial 02
CSCI415 – Compiler Design
Announcement
Project Teams Registration STARTS!
• 3 – 4 Members
• Within the SAME Lecture Group
• Form and Deadline are on MOODLE
• Penalty will be applied on LATE registration
CSCI415 – Compiler Design
Language Processing System
Source Program Pre-processor
Pre-processed code
Compiler
Target assembly code
Assembler
Relocatable machine code
Library Files /
Relocatable Linker
modules Executable machine code
Loader Target Machine Code
CSCI415 – Compiler Design
Phases of a Compiler
Lexical Analyzer
Source Program Pre-processor
Syntax Analyzer
Pre-processed code
Compiler
Sematic Analyzer
Target assembly code
Assembler Intermediate Code Generator
Relocatable machine code
Library Files /
Relocatable Linker Machine Independent Code Optimizer
modules Executable machine code
Loader Code Generator
Target Machine Code Machine Dependent Code Optimizer
CSCI415 – Compiler Design
Lexical Analyzer
CSCI415 – Compiler Design
Lexical Analyzer
❑ First Phase of a compiler
❑ Takes ‘Source Code’ as a stream of characters
❑ Converts into a sequence of tokens
Source Stream of
Code Scanner Tokens
Lexical Analyzer
CSCI415 – Compiler Design
Basic Terminologies
❑ Lexeme is a sequence of characters that are included in the source
program according to the matching pattern of a token. It is nothing
but an instance of a token.
❑ Token is the sequence of characters which represents a unit of
information in the source program.
CSCI415 – Compiler Design
Lexical Analyzer Tasks
Tasks Preformed:
❑ Identify Lexemes and Tokens into the symbol table
❑ Removes whitespace characters and comments from the source
program
❑ Prepare the token stream to pass to the parser
CSCI415 – Compiler Design
What is a Scanner?
A scanner is a part of the lexical analyzer It
uses predefined patterns to identify
lexemes and match them with their
correct tokens.
CSCI415 – Compiler Design
Let’s Build a Scanner
START
Define Code Language using Hopcroft Algorithm /
Regex Equivalence Method
Regex Minimized DFA
Appropriate Definition Code
Thompson Construction
[ANTLR]
NFA
DFA
Subset Construction READY
SCANNER
CSCI415 – Compiler Design
Define Code Language using Regex
Here are some basic lexical regular expressions
An identifier should start with a letter followed by any combination of letters
and numbers
IDENTIFIER = [a-zA-Z]([a-zA-Z] | [0-9])* LETTER = [a-zA-Z]
Token Regex / Lexeme Pattern DIGIT = [0-9]
IDENTIFIER = LETTER(LETTER | DIGIT)*
Token
Both Solutions are correct BUT, the right side is the best
Define Code Language using Regex
Here are some basic lexical regular expressions
An unsigned integer is any combination of unsigned numbers
DIGIT = [0-9]
UNSIGNED = (DIGIT)+
A signed integer is an unsigned integer that can be preceded by a sign
(We will build on the previous answer)
SIGNED = (+ | -) UNSIGNED
Define Code Language using Regex
Here are some basic lexical regular expressions
A float number with exponent is a float number followed by optional e and a
signed number.
DIGIT = [0-9]
DOT = .
FLOAT = DIGIT+ DOT DIGIT+
SIGNED = (+ | -)? DIGIT+
FEXPONENT = FLOAT (e SIGNED )?
Define Code Language using Regex
Here are some basic lexical regular expressions
Accepts all numbers signed or unsigned as well as floats or integers
DIGIT = [0-9] DIGIT = [0-9]
NUMBER = (+ | -)? DIGIT+ (. DIGIT+)? UNSIGNED = DIGIT+
SIGNED = (+ | -)? UNSIGNED
FLOAT = SIGNED . UNSIGNED
NUMBER = UNSIGNED | SIGNED | FLOAT
Easy Solution Extra Solution
Define Code Language using Regex
Here are some basic lexical regular expressions
A Reserved word can be one of the following keywords (if, while, int,
for, float, char, else, endif,……)
The token for any reserved word is always itself to help with the parsing in phase
2 of the compiler.
IF = if FOR = for
WHILE = while FLOAT = float
INT = int CHAR = char
Define Code Language using Regex
Here are some basic lexical regular expressions
An Operator can be one of the following signs (+, -, *, /, %, <, >)
In this example we categorized all the operators into one token, however some
operators would need to have unique tokens to be able to differentiate between
them as shown in the following slides.
OPERATOR = + | - | * | / | % | < | >
Define Code Language using Regex
Here are some basic lexical regular expressions
An example of UNIQUE Categorization of operators.
MATHOP: + | - | * | / | % (Mathematical Operators)
LOGOP: < | > | ! | == | <= | >= | != (Logical Operators)
ASSIGN: = (Assignment Operator)
INCROP: ++ | -- (Increment/Decrement Operators)
Define Code Language using Regex
Here are some basic lexical regular expressions
We can also categorize different brackets to identify them for different usage.
LPAR: ( COMMA: ,
RPAR: ) SEMICOLON: ;
LCUR: { COLON: :
RCUR: }
LSQU: [
RSQU: ]
Now, Solve an Example
Given a C++ code snippet, define the lexemes and tokens
Lexeme Token
float FLOAT
match0 IDENTIFIER
( LPAR
char IDENTIFIER
* STAR We will use the earlier defined
tokens!
s IDENTIFIER
) RPAR
CSCI415 – Compiler Design
Given a C++ code snippet, define the lexemes and tokens
Lexeme Token
float FLOAT
match0 IDENTIFIER
( LPAR
char IDENTIFIER
* STAR
s IDENTIFIER
) RPAR
For demonstration purposes, we
{ RCUR
have avoided repeating the
if IF
lexeme-token pair however,
! NOT
you’re are supposed to tokenize
strncmp STRNCMP
in the order of the code passed.
“0.0” STRING
3 NUMBER
return RETURN
CSCI415 – Compiler Design
LAB TASK
Define the lexeme-token pairs for the following PYTHON codes:
Write the code first then the scanner output
1. Reads from a 20 items list and prints it to the user.
2. Returns the sum of 10 numbers taken from the user.
SOLVE ON PAPER WITH YOUR NAME AND ID
After you finish, don’t forget to give it to your TA
CSCI415 – Compiler Design
Reads from a 20 items list and prints it to the user.
Lexeme Token
l1 IDENTIFIER
[ LSQUARE
i IDENTIFIER
for FOR
in IN
Used Patterns
range IDENTIFIER
LETTER: [a-z]
( LPAREN
20 INTEGER DIGIT: [0-9] INTEGER: DIGIT+
) RPAREN IDENTIFIER: LETTER(LETTER | DIGIT)*
] RSQUARE LSQUARE: [ COLON: :
item IDENTIFIER RSQUARE: ] FOR: for
: COLON LPAREN: ( IN: in
print IDENTIFIER RPAREN: )
CSCI415 – Compiler Design
Returns the sum of 10 numbers taken from the user. Used Patterns
Lexeme Token Lexeme Token LETTER: [a-z] INT: int
def IDENTIFIER number IDENTIFIER DIGIT: [0-9] IN: in
sum_of_numbers IDENTIFIER int INT INTEGER: DIGIT+ FOR: for
IDENTIFIER: LETTER(LETTER | DIGIT)*
( LPAREN input IDENTIFIER
STRING: “(IDENTIFIER | COLON)*”
) RPAREN “Enter a number: “ STRING
INCRASSIGN: += COLON: :
: COLON += INCRASSIGN
LPAREN: ( RPAREN: )
total IDENTIFIER return RETURN RETURN: return COMMA:
= ASSIGNMENT print IDENTIFIER ,UNDERSCORE: _
0 DIGIT , COMMA ASSIGNMENT: =
for FOR
_ UNDERSCORE
in IN
range IDENTIFIER
10 INTEGER
CSCI415 – Compiler Design
Thank
You