How your code executes !

The evolution of how code executes truly began when John Backus, a Turing Award winning computer scientist, introduced FORTRAN, one of the first high-level programming languages. Before this breakthrough, programmers had to write everything in assembly language, a tedious and error-prone process tied closely to the hardware. Backus’s idea was revolutionary: instead of forcing humans to think like machines, he created a language that let machines translate human-readable instructions into machine code. This gave rise to two major approaches to translation compilers, which convert the entire program into machine code before running it, and interpreters, which execute code line by line as it is read. Together, these concepts laid the foundation for modern programming and shaped how software is developed today.

Below is a clear, high-level architectural flow overview of how a program moves from source code to machine-target execution

Big picture of compiler

This article serves as the foundation for a larger series in which we will explore compilers in great detail. In the upcoming parts, we’ll break down each stage of the compilation pipeline ,lexing, parsing, semantic analysis, intermediate representations, optimization strategies, machine-code generation, and linking.

A compiler

Before we break this familiar compiler architecture into a full multi-part series, this article will take a deep dive into the complete overview of how a source program is transformed into assembly language. We’ll examine each major stage of the translation process and introduce the core terminology and important buzzwords that frequently appear in compiler design. This overview will act as the foundation for the detailed articles that follow

This article is intended for readers who already have a reasonable understanding of compilers and basic programming language concepts. You don’t need to be an expert in compiler construction, but a general familiarity with terms like syntax, parsing, tokens, and assembly will help you follow the discussion more comfortably

Why are there so many different ways to implement a lexer, and which approach is actually the best?This exact rabbit hole is what led me down hours of reading, experimenting, and exploring discussions across the internet. Eventually, that curiosity and the surprising variety of answers became the motivation for writing this article :)

The basic buzz words related to compiler

Token

A token is the smallest meaningful unit in a program.

Examples:
ID (identifier)
NUM (number)
+
*
( )
A token is usually:(TOKEN_TYPE, LEXEME)
Example:
ID("count")
NUM("123")

Lexeme

The actual text in the source code that forms a token.

Example:
Input:   age = 24
Lexeme:  age
Token:   ID

Lexer / Scanner / Lexical Analyzer

A program that:
reads characters
groups them into tokens
removes whitespace and comments
Built using:
regex
Lex/Flex
manual code

Regular Expression (Regex)

A pattern used to describe valid strings.

Examples:
[0-9]+     → numbers
[a-zA-Z]+  → identifiers
Regex is used ONLY for lexing, not parsing.

NFA (Nondeterministic Finite Automaton)

A state machine where
multiple transitions possible
ε-transitions allowed
easy to build from regex
Lex first converts regex → NFA.

DFA (Deterministic Finite Automaton)

A state machine with: one transition per input symbol
faster than NFA
used by scanners to recognize tokens
Lex converts NFA → DFA → C code.

Context-Free Grammar (CFG)

A set of rules describing the syntax (structure) of a language.

Format:
A → α
(Left side always a single nonterminal)
Example:
Expr → Expr + Term | Term
Parsers use CFGs.

Production Rule

A grammar rule.

Example: Statement → if Expr then Statement

Parse Tree

A tree that shows how grammar rules generate the input.

Example for a + b * c:

      Expr
     /   \
   Expr   +
    |     Term
    a     Term * Factor
            b      c

Abstract Syntax Tree (AST)

A simplified parse tree containing only essential structure.

    (+)
   /   \
 a      (*)
       /   \
      b     c

Compilers use the AST to generate code.

Ambiguous Grammar

A grammar that can generate multiple parse trees for the same input.

Example:
Expr → Expr + Expr | number
Input 1 + 2 + 3 has two parse trees → ambiguous.

Left Recursion

A grammar where a nonterminal starts with itself.

Example:
E → E + T
LL parsers cannot handle it directly.

Parser

Component that checks syntax using CFG.

Types:
LL (top-down)
LR (bottom-up → used by Yacc/Bison)
Input to parser: tokens
Output: AST

LL Parser

“Left-to-right scanning, Leftmost derivation.”

Predicts which rule to use.
Cannot handle:
left recursion
some ambiguous grammars
Used in: ANTLR

LR Parser

“Left-to-right scanning, Rightmost derivation in reverse.”

Stronger than LL.
Used in:Yacc ,Bison
Works for most programming languages.

Derivation

How grammar rules produce the string.

Get ved prakash singh’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Example:

Expr → Expr + Term → Term + Term → id + id

First and Follow Sets

Used to construct LL or LR parsers.

FIRST(A) = possible starting terminals of A

FOLLOW(A) = terminals that can appear after A

Semantic Analysis

Checks meaning:
type checking
variable declarations
type conversion
scope rules

Symbol Table

Data structure storing:
variable names
types
scope information
memory locations

Intermediate Code (IR)

A machine-independent form of code.

Examples: 3-address code,Quadruples,Syntax trees

Example 3-address code:

t1 = b * c
t2 = a + t1

Code Generation

Converts IR → machine code.

MOV R1, a
ADD R1, b
STORE R1, x

The correct knowledge of these basic buzz words are actually very essential in order to proceed ,Comming to original question disscussion.

Lexing (tokenizing) is the first stage of a compiler or interpreter. It transforms raw characters into a stream of meaningful tokens like identifiers, numbers, and operators.

we’ll walk through implementing the exact same lexer in three different ways:

1. A fully hand-written lexer
2. Lex (the classic tool)
3. Flex (the modern, faster Lex replacement)

We’ll then compare all three and look at which approach is best for different scenarios.

For all three implementations, we want to tokenize:
NUMBER → sequences of digits
IDENT → alphabetic words
PLUS → the + symbol
WHITESPACE → ignored
UNKNOWN → any unexpected character

All three lexers must produce the same output for the same input.

1. Hand-Written Lexer

A manual lexer is written fully by hand using conditionals (isdigit, isalpha, etc.). This offers maximum control and often the highest performance. It is ideal for complex languages or performance-critical tools, but requires more effort and discipline to maintain

#include <stdio.h>
#include <ctype.h>

int main() {
    int c;

    // Read input character-by-character until EOF
    while ((c = getchar()) != EOF) {

        // Skip all whitespace characters (space, tab, newline, etc.)
        if (isspace(c))
            continue;

        // ---------- NUMBER TOKEN ----------
        // If the current character starts a number
        if (isdigit(c)) {
            char buf[256];
            int i = 0;

            // Store the first digit
            buf[i++] = c;

            // Read subsequent digits and accumulate them
            while ((c = getchar()) != EOF && isdigit(c))
                buf[i++] = c;

            // Null-terminate the string
            buf[i] = '\0';

            // Output the recognized token
            printf("NUMBER(%s)\n", buf);

            // Push back the non-digit character for next iteration
            if (c != EOF)
                ungetc(c, stdin);
            continue;
        }

        // ---------- IDENTIFIER TOKEN ----------
        // If the current character starts an identifier (alphabetic)
        if (isalpha(c)) {
            char buf[256];
            int i = 0;

            // Store the first letter
            buf[i++] = c;

            // Read subsequent alphabetic characters
            while ((c = getchar()) != EOF && isalpha(c))
                buf[i++] = c;

            // Null-terminate
            buf[i] = '\0';

            // Output the identifier
            printf("IDENT(%s)\n", buf);

            // Push back the non-identifier character
            if (c != EOF)
                ungetc(c, stdin);
            continue;
        }

        // ---------- PLUS TOKEN ----------
        if (c == '+') {
            printf("PLUS\n");
            continue;
        }

        // ---------- UNKNOWN CHARACTER ----------
        // Any other single character is reported as UNKNOWN
        printf("UNKNOWN(%c)\n", c);
    }

    return 0;
}
//build and run
//cc lexer.c -o lexer
//./lexer

2.Lex (Classic Lexical Analyzer Generator)

Lex uses simple regular expression rules to generate a lexer in C. It’s easy to learn and great for educational or legacy environments, but it lacks modern features and performance. Good for understanding the basics of lexical analysis.

%{
/*
 * Classic Lex Lexer
 * -----------------
 * Tokenizes:
 *   - NUMBER : sequences of digits
 *   - IDENT  : alphabetic identifiers
 *   - PLUS   : '+'
 *   - WHITESPACE : ignored
 *   - UNKNOWN : any other character
 */

#include <stdio.h>
%}

%%

/* ----- NUMBER TOKEN ----- */
/* Regex for one or more digits */
[0-9]+        {
                  /* yytext is the matched text */
                  printf("NUMBER(%s)\n", yytext);
              }

/* ----- IDENTIFIER TOKEN ----- */
/* Regex for alphabetic characters */
[A-Za-z]+     {
                  printf("IDENT(%s)\n", yytext);
              }

/* ----- PLUS TOKEN ----- */
"+"           {
                  printf("PLUS\n");
              }

/* ----- WHITESPACE ----- */
/* Ignore spaces, tabs, newlines */
[ \t\n]+      {
                  /* Do nothing (whitespace skipped) */
              }

/* ----- UNKNOWN CHARACTER ----- */
.             {
                  printf("UNKNOWN(%s)\n", yytext);
              }

%%

int main() {
    /* Start lexical analysis */
    yylex();
    return 0;
}
//build and run
//lex lexer.l
//cc lex.yy.c -o lexer
//./lexer

3. Flex (Fast Lex)

Flex is the modern, faster, more portable replacement for Lex. It accepts the same rule syntax but adds reentrancy, better debugging, and much higher performance. It is the practical choice for modern C/C++ compilers, interpreters, and language tools.

%option noyywrap        /* Do not use yywrap() */
%option reentrant       /* Create a reentrant scanner */
%option yylineno        /* Track line numbers */

%{
/*
 * Modern Flex Lexer
 * -----------------
 * This version behaves the same as the Lex version
 * but is faster, reentrant, and more flexible.
 */

#include <stdio.h>
%}

%%

/* ----- NUMBER TOKEN ----- */
/* Match one or more digits */
[0-9]+        {
                  printf("NUMBER(%s)\n", yytext);
              }

/* ----- IDENTIFIER TOKEN ----- */
/* Match alphabetic identifiers */
[A-Za-z]+     {
                  printf("IDENT(%s)\n", yytext);
              }

/* ----- PLUS TOKEN ----- */
/* Match the '+' character */
"+"           {
                  printf("PLUS\n");
              }

/* ----- WHITESPACE ----- */
/* Skip whitespace characters */
[ \t\n]+      {
                  /* Skip */
              }

/* ----- UNKNOWN CHARACTER ----- */
/* Match any single unexpected character */
.             {
                  printf("UNKNOWN(%s)\n", yytext);
              }

%%

int main() {
    yyscan_t scanner;

    /* Initialize reentrant scanner instance */
    yylex_init(&scanner);

    /* Begin tokenization */
    yylex(scanner);

    /* Clean up scanner */
    yylex_destroy(scanner);

    return 0;
}
//build and run
//flex lexer.l
//cc lex.yy.c -o lexer
//./lexer

Sample Input

abc + 123 + x9

Output (All Three Implementations Produce the Same)

IDENT(abc)
PLUS
NUMBER(123)
PLUS
IDENT(x9)

Comparison Table

| Method        | Strengths                         | Weaknesses                   | Best Use Case                 |
|---------------|-----------------------------------|-------------------------------|-------------------------------|
| Lex           | Simple, classic, easy to learn    | Old, slower, legacy quirks    | Teaching, legacy maintenance  |
| Flex          | Fast, modern, reentrant, robust   | Still generates dense C code  | Real-world compilers/tools    |
| Hand-written  | Fastest, total control, flexible  | More code, harder to maintain | High-performance custom tools |

In the end, Lex, Flex, and hand written lexers all walk into the same bar they just order different drinks.
Lex brings a classic vintage, Flex goes for an energy drink because it’s faster, and the hand-written lexer?
It brews its own.

Use Lex when you want simplicity, Flex when you want speed and modern comfort, and hand-written code when you want total control (and don’t mind a little extra elbow grease).

Whatever you choose, your tokens will thank you for keeping things clean and consistent :)