Embedded Systems (IT-603 (C)) - Unit 2 Short Notes

II. Lexical Analysis

Need for Separating Lexical Analysis from Syntax Analysis

Separating lexical analysis (scanner) from syntax analysis (parser) enhances compiler design through:

• Simplicity: Scanner handles low-level token recognition (e.g., identifiers, operators), simplifying parser logic which focuses on grammatical structure.

• Efficiency: Scanner can be optimized independently (e.g., using buffered input, DFA-based recognition), and parser tables are smaller.

• Portability: Device-dependent I/O and character set handling are confined to scanner, making the parser portable across systems.

[!TIP] Common Pitfall: Avoid conflating lexical and syntax analysis. Lexical analysis deals with what tokens exist (e.g., id, +), while syntax analysis deals with how tokens combine (e.g., expressions, statements).

Finite Automata for Token Recognition

Token patterns are defined by regular expressions, converted to finite automata for recognition:

1. NFA Construction (Thompson’s Construction):

   Each regex operator (concatenation, union, closure) builds an NFA with ε-transitions.

   • Example: Regex a(b|c)* → NFA with states for a, then loop on b or c.

2. DFA Construction (Subset Construction):

   NFA states are grouped into DFA states; each DFA state is a set of NFA states. Eliminates nondeterminism.

3. DFA Minimization:

   Merge equivalent DFA states to reduce size.

Example: Identifier regex [a-zA-Z][a-zA-Z0-9]*

• NFA: Start → letter → (letter/digit)* loop.

• DFA: Unique transition per character class (letter/digit/other).

[!TIP] Exam Focus: Be able to convert a simple regex (e.g., (a|b)*abb) to NFA, then to DFA. Know that DFA is used in actual scanners for linear-time token recognition.

Lex Tool and Lex Program Structure

Lex is a lexical analyzer generator that transforms a specification into a C/C++ scanner.

Structure of a Lex Program:

%{

  /* C declarations: headers, global variables */

%}

%%

  /* Rules: regex   { C action } */

%%

  /* User subroutines: additional C functions (e.g., main) */

• Definitions Section (%{ ... %}): C code (includes, declarations).

• Rules Section (%% ... %%): Pattern-Action pairs. Pattern is a regex; action is C code executed on match.

• User Subroutines: Optional C code (e.g., main() calls yylex()).

Lex Program Example for Identifiers and Arithmetic Operators

%{

  #include <stdio.h>

%}

%%

[a-zA-Z][a-zA-Z0-9]*   { printf("Identifier: %s\n", yytext); }

"+"|"-"|"*"|"/"        { printf("Operator: %s\n", yytext); }

[ \t\n]+               ; /* Skip whitespace */

.                      { printf("Invalid: %s\n", yytext); }

%%

int main() {

  yylex();

  return 0;

}

Explanation:

• yytext: Global variable holding matched token string.

• Patterns:

  • [a-zA-Z][a-zA-Z0-9]* matches identifiers.

  • "+"|"-"|"*"|"/" matches arithmetic operators (quotes for literal characters).

  • [ \t\n]+ matches whitespace (ignored via empty action ;).

  • . matches any single character (catch-all for errors).

• main() invokes the scanner (yylex()).

[!TIP] Common Pitfall: Order of rules matters. Place longer patterns before shorter ones (e.g., == before =) to avoid premature matching. Always include a rule for whitespace and errors.