02 Lexical Analysis

Also called as scanning

We specify tokens using Regular Expressions - sequence of characters specifying search pattern in input

We use NFA/DFA

Parts¶

Example¶

e = m * c ** 2

<id, pointer_to_symbol_table_entry_for_e>
<assign_op>
<id, pointer_to_symbol_table_entry_for_m>
<mult_op>
<id, pointer_to_symbol_table_entry_for_c>
<exp_op>
<number, 2>

Input Buffering¶

In Fortran, spaces are ignored. So, he l lo is the hello. This is because, there may exist blank instances in the magnetic tape.

We can’t tell if the statement do 5 i = 1.25 is to be treated as

do {i=1}
// or  
do51 = 1.52

until we reach the .

Fortran Loops¶

do index_variable = start, end, step
    statements
end do

// or

do n index_variable = start, end, step
    statements
n continue

Lookahead¶

Lookahead of atleast one/more characters beyond the next lexeme before we can be sure that we have the right lexeme.

Helps speed up reading source program

We usually use 2 buffer scheme lookahead, which are alternatively-reloaded; each buffer is of the same size \(n\), where \(n\) is size of a disk block

Advantages¶

• Using one system read command we can read \(n\) characters into a buffer, rather than using one system call per character
• A special character, represented by eof (character different from any possible character of source code), marks the end of the source file

2 Buffer Scheme¶

When the next lexeme is determined, the following steps are taken:

• forward is set to the character at its right end
• Record the lexeme as the attribute of the token
• lexemeBegin is set to the character immediately after the lexeme just found

Advancing forward requires checking if end of a buffer is reached.

Recovery Strategies¶

Recovery strategies are used when no pattern for tokens matches any prefix of remaining input, preventing lexical analyzer from proceeding

Goal: Transform prefix of remaining input into valid lexeme

Possible error-recovery actions are:

• Panic Mode Recovery: Delete successive characters from the remaining input, until the lexical analyzer can find a well-formed token at the beginning of what input is left
• Insert a missing character into the remaining input
• Replace a character by another character
• Transpose two adjacent characters

Parts of String¶

Operations¶

In order of precedence

Regular Definitions¶

Helps to give names to regular expressions and use those names in subsequent expressions

d1 -> r1
d2 -> r2
...
dn -> rn

where

• \(d_i\) is a new symbol, such that
• \(d_i \not \in \epsilon\)
• \(d_i \ne d_j\)
• \(r_i\) is a RE over alphabet \(\epsilon \cup \{d_1, \dots, d_{i-1} \}\)

Lex¶

Language that allows us to create our own lexical analyzer, without having handcode

It represents everything in terms of a Finite State Machine, and then generates the code

Lex Symbols¶

Transition/State Diagrams¶

Reg Exprs are translated into transition diagrams (representing Finite State Machines), which are then translated into program code for lexical analyzer

Relational Operators¶

Reserved Words/Identifiers¶

Unsigned Numbers¶

Whitespace¶

Conflict Resolution¶

• Longer prefix preferred
• If there are multiple matches for longest prefix, first pattern in lex program is preffered

a       {printf (“1A”);}
aa  {printf (“2A”);}

Input : aaa
Output: 2A1A

%%
letter(letter|digit)*   { printf (“ID”); }
if                                      { printf (“IF”); }

Input : if
Output: ID

Comments