PadhaikoAll subjects

Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing

Theory of Computation (ENCT 203)

Open in the Padhaiko app

6.1–6.2 Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing

6.1 Basic Concepts & Structure of a Compiler

A compiler is a systems software program that translates source code written in a high-level programming language (such as C, C++, Rust, or Java) into an equivalent target program in low-level machine code or assembly language executable by a computer processor.

The compilation process is conceptually divided into two major operational halves:

  1. Analysis (Front End): Deconstructs the source program into its constituent grammatical pieces, creates intermediate representations, validates syntactic and semantic correctness, and builds the symbol table. It is largely machine-independent.
  2. Synthesis (Back End): Takes the intermediate representation produced by the analysis phase, applies machine-dependent and machine-independent optimizations, and generates target machine code.
Source Program
      |
      v
+--------------------------+
| 1. Lexical Analyzer      | <---> Symbol Table
+--------------------------+         & Error Handler
      | Tokens
      v
+--------------------------+
| 2. Syntax Analyzer       |
+--------------------------+
      | Parse Tree / AST
      v
+--------------------------+
| 3. Semantic Analyzer     |
+--------------------------+
      | Decorated AST
      v
+--------------------------+
| 4. Intermediate Code Gen |
+--------------------------+
      | Three-Address Code
      v
+--------------------------+
| 5. Code Optimizer        |
+--------------------------+
      | Optimized IR
      v
+--------------------------+
| 6. Code Generator        |
+--------------------------+
      |
      v
Target Machine Code

The Six Sequential Compiler Phases

Definition

The Six Compiler Phases

  1. Lexical Analysis (Scanner): Reads the continuous stream of raw source characters, strips out whitespace and comments, and groups characters into meaningful character sequences called lexemes, which are mapped to tokens .
  2. Syntax Analysis (Parser): Takes the stream of tokens from the scanner and verifies whether the token sequence conforms to the syntactic rules of the language defined by a Context-Free Grammar (CFG), constructing a parse tree or Abstract Syntax Tree (AST).
  3. Semantic Analysis: Checks the parse tree for semantic consistency with language definitions. Its primary tasks include type checking, type coercion, ensuring variables are declared before use, verifying array bounds, and checking function argument counts.
  4. Intermediate Code Generation (ICG): Translates the verified abstract syntax tree into an explicit, machine-independent, low-level intermediate representation (such as Three-Address Code (TAC), quadruples, or quadruples/triples) that is easy to generate and easy to translate to target architectures.
  5. Code Optimization: Analyzes the intermediate code to eliminate redundancies, reduce execution time, and minimize memory footprint without altering the observable semantics of the program. Common techniques include constant folding, common subexpression elimination, loop-invariant code motion, and dead-code elimination.
  6. Code Generation: Maps the optimized intermediate code into target machine instructions, managing physical CPU registers, memory addresses, instruction scheduling, and hardware calling conventions.

6.2 Role of the Lexical Analyzer

The lexical analyzer serves as the initial gatekeeper of the compiler, transforming character-level source text into structured tokens:

  1. Tokenization: Groups characters into atomic grammatical units (keywords, identifiers, integer/float constants, string literals, operators, punctuation).
  2. Stripping Whitespace and Comments: Discards space characters, tab stops, newline characters, and source code comments, relieving subsequent phases from low-level text formatting.
  3. Lexical Error Handling: Identifies illegal characters (e.g. an isolated @ in C) and unclosed string or character literals, issuing precise line and column diagnostics.
  4. Symbol Table Interaction: Enters identified variable and function identifiers into the symbol table along with line numbers and scope attributes.
  5. Lookahead Management: Uses single- or two-character buffers to distinguish single-character operators from composite operators (e.g. distinguishing = from ==, < from <=, / from /*).

6.3 Lexical Analysis with Deterministic Finite Automata (DFA)

In modern compiler tools (such as Lex, Flex, and hand-written scanners), token patterns are specified using regular expressions and implemented as Deterministic Finite Automata (DFAs).

Because regular languages are recognized by finite automata, a DFA can scan input characters sequentially and determine token boundaries in strictly linear time with memory.

Pattern Matching via DFA

For example, in C-like languages:

DFA: Identifier Lexical TokenDFA
DFA: Identifier Lexical Token L, D, _ L, _ q0 q1
StateL_D
→q0q1q1—
*q1q1q1q1

In the state machine above:


6.4 Parsers & Context-Free Grammars

The syntax of programming languages is formally specified using Context-Free Grammars (CFGs). A parser accepts tokens from the scanner and verifies syntactic structure by constructing a derivation or parse tree.

       Context-Free Grammar (CFG)
                  |
         +--------+--------+
         |                 |
         v                 v
  Top-Down Parsers    Bottom-Up Parsers
  - Recursive Descent - Shift-Reduce
  - LL(1)             - LR(0), SLR(1)
  - Leftmost deriv.   - LALR(1), LR(1)
                      - Rightmost deriv. in reverse
Definition

Top-Down vs Bottom-Up Parsing

  1. Top-Down Parsing (LL Parsers):
    • Constructs the parse tree from the root (start symbol ) downward toward the leaves (input tokens).
    • Corresponds to tracing a leftmost derivation.
    • Examples: Recursive Descent Parsing, Predictive LL(1) Parsing.
    • Limitation: Cannot handle grammars with left recursion () without infinite looping; requires left-recursion elimination and left-factoring.
  2. Bottom-Up Parsing (LR Parsers):
    • Constructs the parse tree from the leaves (terminal tokens) upward toward the root start symbol .
    • Corresponds to tracing a rightmost derivation in reverse.
    • Operates via the shift-reduce mechanism using a state-and-symbol stack:
      • Shift: Push the current input token onto the stack.
      • Reduce: When a stack substring matches the right-hand side of a production (called a handle), replace with non-terminal .
      • Accept: When the stack contains only the start symbol and input is empty.
      • Error: When no shift or reduce move is valid.
    • Examples: LR(0), SLR(1), LALR(1), Canonical LR(1). Used by parser generators like Yacc and Bison due to superior language coverage.

Ambiguity and Operator Precedence

In programming languages, arithmetic expressions must adhere strictly to standard operator precedence and associativity:

To enforce precedence unambiguously in a CFG:

Lower tiers (closer to factors ) have higher operator precedence in the resulting parse tree.


Worked Out Examples

Example 1

1

Construct the syntax tree / parse tree for the arithmetic expression:

using standard operator precedence rules.

Operator Precedence and Sub-expression Grouping

Analyze operator binding strengths:

  1. Sub-expression is enclosed in parentheses, giving it the highest precedence.
  2. Multiplication and division by have equal precedence, evaluated left to right:
  1. Addition has the lowest precedence and forms the root operator of the entire expression:
Hierarchical Tree Structure

The tree is structured with operators as internal nodes and operands as leaves:

  • Root: +
    • Left subtree: operand a
    • Right subtree: operator /
      • Left child: operator *
        • Left leaf: b
        • Right leaf: c
      • Right child: operator *
        • Left leaf: d
        • Right leaf: e
Answer:

The hierarchical tree structure is:

       +
      / \
     a   /
        / \
       *   *
      / \ / \
      b c d e

Evaluation begins at the deepest leaves ( and ), divides their results, and finally adds .

Example 2

2

Draw the parse tree for the expression:

Precedence Partitioning

Evaluate binding strengths:

  • forms a multiplicative term.
  • forms a divisional term.
  • + joins the two terms at the root level: .
Parse Tree Generation

Using the standard expression grammar:

The derivation proceeds:

Parse tree for a * b + c / d E E T T F a * F b + T T F c / F d
Parse tree for a * b + c / d · E -> E + T | T; T -> T * F | T / F | F; F -> a | b | c | d
Answer:

The syntax tree joins the product and the quotient under the root addition operator:

       +
      / \
     *   /
    / \ / \
    a b c d
Example 3

3

Draw the parse tree for the assignment expression:

Syntax Tree Decomposition
  1. The assignment operator = forms the topmost root of the syntax tree:
    • Left child: target variable .
    • Right child: evaluated expression .
  2. Within the right-hand side expression:
    • Root is +.
    • Left operand: product .
    • Right operand: quotient where denominator is difference .
Hierarchical Tree Structure

The tree decomposes as:

       =
      / \
     r   +
        / \
       *   /
      / \ / \
      a b c  -
            / \
            d  e
Answer:

The assignment statement evaluates the right-hand expression tree and binds the computed value to variable .

Example 4

4

Draw the parse tree for the expression:

Associativity and Precedence Analysis

Multiplication and division share equal precedence and associate from left to right:

  1. is computed first.
  2. is computed second.
  3. is computed last.
Parse Tree Construction

Using the standard arithmetic expression grammar:

Parse tree for a + b * c / d E E T F a + T T T F b * F c / F d
Parse tree for a + b * c / d · E -> E + T | T; T -> T * F | T / F | F; F -> a | b | c | d
Answer:

The syntax tree represents :

       +
      / \
     a   /
        / \
       *   d
      / \
      b c
Example 5

5

Draw the parse tree / syntax tree for the compound arithmetic assignment:

Hierarchical Decomposition

Analyze grouping from sub-expressions:

  1. Root is assignment =:
    • Left side: identifier .
    • Right side: compound rational expression.
  2. In the right-hand expression, division / is the principal operator:
    • Numerator: product of two parenthesized terms: .
    • Denominator: parenthesized sum .
  3. Within numerator product *:
    • Left term: sum .
    • Right term: difference .
  4. Within denominator sum +:
    • Left term: .
    • Right term: product .
Syntax Tree Representation
         =
        / \
       r   /
          / \
         *   +
        / \ / \
       +  - e  *
      / \/ \  / \
      a bc d  f g
Answer:

The complete syntax tree reflects all parenthesized sub-expressions, performing , , and at the lowest level before multiplying and dividing.

Example 6

6

Explain how tokens are generated by the lexical analyzer for the following C function code segment:

#include<stdio.h>
int func(int a, int b)
{
    if(a>b)
        return a;
    else
        return b;
}
Lexeme Extraction and Classification

The lexical analyzer scans the source text from left to right, identifies character boundaries, ignores indentation whitespaces, and classifies each lexeme into a recognized token category:

LexemeToken CategorySemantic Description
#Preprocessor OperatorPreprocessor directive prefix
includePreprocessor DirectiveHeader inclusion directive
<DelimiterHeader path opening bracket
stdio.hHeader IdentifierStandard I/O library header file
>DelimiterHeader path closing bracket
intKeywordBuilt-in integer primitive type
funcIdentifierFunction name identifier
(SeparatorParameter list opening delimiter
intKeywordType specifier for first parameter
aIdentifierFirst parameter identifier
,SeparatorParameter list item separator
intKeywordType specifier for second parameter
bIdentifierSecond parameter identifier
)SeparatorParameter list closing delimiter
{SeparatorFunction body opening brace
ifKeywordConditional control-flow statement
(SeparatorCondition opening parenthesis
aIdentifierLeft operand variable
>Relational OperatorGreater-than comparison operator
bIdentifierRight operand variable
)SeparatorCondition closing parenthesis
returnKeywordFunction return statement
aIdentifierReturn value expression variable
;DelimiterStatement terminator
elseKeywordAlternative branch keyword
returnKeywordReturn statement
bIdentifierReturn value variable
;DelimiterStatement terminator
}SeparatorFunction body closing brace
Symbol Table Registration

During this scan, the identifiers func, a, and b are inserted into the compiler's symbol table along with their data types, scopes, and source locations.

Answer:

The lexical analyzer converts the 10-line source code segment into 29 discrete tokens while discarding all tabs, newlines, and spaces.


Exercises

Exercises

Question 1

List down the different phases of compiler design and state the primary function of each phase.

Analysis Phases (Compiler Front End): The front-end phases analyze the source program to verify correctness and build an intermediate representation:

  1. Lexical Analysis (Scanner): Reads the incoming stream of source characters, removes whitespace and comments, and groups characters into meaningful character sequences called lexemes. It maps each lexeme into a token of the form and enters identifiers into the symbol table.
  2. Syntax Analysis (Parser): Takes the sequence of tokens produced by the scanner and checks whether it conforms to the syntactic rules of the language defined by a Context-Free Grammar (CFG). It outputs a hierarchical parse tree or Abstract Syntax Tree (AST).
  3. Semantic Analysis: Checks the parse tree for semantic consistency with programming language definitions. Key functions include type checking, verifying that variables are declared before use, checking array dimensions, and ensuring function call arguments match declared parameter signatures.

Synthesis Phases (Compiler Back End): The back-end phases take the verified intermediate structure and synthesize target code:

  1. Intermediate Code Generation (ICG): Translates the decorated AST into an explicit, machine-independent low-level intermediate representation, typically Three-Address Code (TAC) or quadruples, facilitating portable optimization.
  2. Code Optimization: Inspects intermediate code to eliminate redundancies and improve execution efficiency without altering program semantics. Common techniques include constant folding, dead-code elimination, common subexpression elimination, and loop-invariant hoisting.
  3. Code Generation: Maps optimized intermediate instructions into executable target machine or assembly code, handling CPU register allocation, instruction scheduling, and memory addressing.

Cross-Cutting Supporting Modules: Two essential modules interact with all six compiler phases:

  • Symbol Table Manager: Maintains a centralized database storing identifier names, types, scopes, memory offsets, and function signatures.
  • Error Handler: Detects, reports, and recovers from errors encountered at each phase (lexical errors, syntax errors, and semantic errors) to allow compilation to continue discovering further diagnostic issues.
Answer:

The six sequential phases of a compiler are: (1) Lexical Analysis: converts characters into tokens and strips comments/whitespace; (2) Syntax Analysis: validates token sequences against a CFG and builds a parse tree; (3) Semantic Analysis: performs type checking and semantic validation; (4) Intermediate Code Generation: produces machine-independent Three-Address Code; (5) Code Optimization: improves execution speed and reduces memory footprint; and (6) Code Generation: generates target machine/assembly instructions while allocating physical CPU registers. These are supported throughout by the Symbol Table Manager and Error Handler.

Question 2

How are the syntax analyzer and Context-Free Grammar (CFG) related with each other? Explain with an appropriate example.

Formal Relationship: CFG as Specification, Parser as Implementation: A Context-Free Grammar (CFG) provides the formal mathematical specification defining the syntax of a programming language, whereas the syntax analyzer (parser) is the practical algorithmic software component that enforces that grammar:

  • The CFG, defined as a 4-tuple , specifies the set of all syntactically valid token sequences through production rules .
  • The parser accepts the stream of tokens produced by the lexical analyzer and attempts to construct a valid derivation or parse tree according to the productions of .
  • If a valid parse tree rooted at start symbol is found, the syntax is valid; otherwise, a syntax error is raised.

Enforcing Operator Precedence via Grammar Hierarchy: Consider an arithmetic expression involving addition and multiplication. An ambiguous grammar such as allows two different parse trees for , leading to conflicting semantic evaluations.

To eliminate ambiguity and enforce standard operator precedence ( binding tighter than ) and left-associativity, the grammar is stratified into distinct non-terminal tiers:

Lower-tier productions ( and ) bind tighter and appear deeper in the resulting parse tree.

Derivation and Parse Tree for : Given input tokens , the parser traces a leftmost derivation:

Parse tree for a + b * c E E T F a + T T F b * F c
Parse tree for a + b * c · E -> E + T | T; T -> T * F | F; F -> a | b | c

Because is derived under the right child of the root , the multiplication forms a subtree evaluated before the addition of , ensuring mathematical precedence is preserved.

Answer:

A Context-Free Grammar (CFG) serves as the formal mathematical specification of a language's syntax, while the syntax analyzer (parser) is the computational engine that validates incoming tokens by constructing a parse tree according to the CFG's productions. For example, the stratified grammar , , and ensures that in , the multiplication is grouped as a term before the addition, enforcing standard operator precedence in the generated parse tree.

Question 3

How are the lexical analyzer and Deterministic Finite Automata (DFA) related with each other? Explain with an appropriate example.

Theoretical Equivalence: Regular Expressions and DFAs: The primary duty of the lexical analyzer (scanner) is to identify tokens—such as identifiers, keywords, numeric constants, and operators—whose patterns are formally defined using regular expressions.

By Kleene's Theorem, every regular expression can be converted into an equivalent Deterministic Finite Automaton (DFA). Because a DFA processes input characters in strictly linear time where is the source character length and requires only auxiliary memory (storing only its current state), compilers (and scanner generators like Lex/Flex) translate token patterns into a composite DFA. The lexical analyzer is literally an implementation of this DFA.

DFA Construction for Identifier Token Recognition: Consider the standard lexical definition of an identifier in C-like languages:

where denotes a letter (), denotes a digit (), and is an underscore:

  • Start state reads a leading letter or underscore and transitions to accepting state .
  • In state , any subsequent letter, digit, or underscore loops back into .
  • If an input begins with a digit in state , the DFA has no valid move (or transitions to a dead/reject state), enforcing that identifiers cannot commence with digits.
DFA: Identifier Token RecognitionDFA
DFA: Identifier Token Recognition L, D, _ L, _ q0 q1
StateL_D
→q0q1q1—
*q1q1q1q1
  • Machine-checked
  • ✓ accepts L
  • ✓ accepts _L
  • ✓ accepts LLD
  • ✓ accepts L_D
  • ✓ accepts _D
  • ✓ rejects D
  • ✓ rejects DL
  • ✓ rejects D_L

Operational Mechanism: Longest Match and Token Output: The lexical analyzer executes the DFA on the source character stream using the longest match (maximal munch) rule:

  1. The scanner feeds characters into the DFA until no transition is possible or a delimiter (whitespace, operator) is encountered.
  2. If the DFA halts in accepting state , the scanned characters form a valid lexeme and are emitted as a token: .
  3. The scanner records new identifiers in the symbol table and resets the DFA to for the next token.
  4. If the DFA halts in a non-accepting state, a lexical error is reported.
Answer:

Token patterns are defined using regular expressions, and because every regular expression corresponds to an equivalent Deterministic Finite Automaton (DFA), the lexical analyzer utilizes DFAs as its underlying recognition engine. For instance, an identifier pattern is implemented as a 2-state DFA where state requires a leading letter or underscore to reach accept state , which then loops on letters, digits, and underscores. Operating in linear time and memory, the DFA provides the exact pattern-matching mechanism for the scanner.

Past exam questions for Theory of Computation

← Time/Space Complexity; P, NP & NP-Complete