Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing
Open in the Padhaiko app6.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:
- 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.
- 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
The Six Compiler Phases
- 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 .
- 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).
- 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.
- 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.
- 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.
- 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:
- Tokenization: Groups characters into atomic grammatical units (keywords, identifiers, integer/float constants, string literals, operators, punctuation).
- Stripping Whitespace and Comments: Discards space characters, tab stops, newline characters, and source code comments, relieving subsequent phases from low-level text formatting.
- Lexical Error Handling: Identifies illegal characters (e.g. an isolated
@in C) and unclosed string or character literals, issuing precise line and column diagnostics. - Symbol Table Interaction: Enters identified variable and function identifiers into the symbol table along with line numbers and scope attributes.
- 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:
- Identifiers follow the regular expression:
- Integer Constants follow:
| State | L | _ | D |
|---|---|---|---|
| →q0 | q1 | q1 | — |
| *q1 | q1 | q1 | q1 |
- Machine-checked
- ✓ accepts L
- ✓ accepts _L
- ✓ accepts LLD
- ✓ accepts L_D
- ✓ rejects D
- ✓ rejects DL
In the state machine above:
- denotes any alphabetical letter ().
- denotes any numerical digit ().
- Reading a leading letter or underscore transitions from start state to accepting state .
- Any subsequent combination of letters, digits, or underscores loops in accept state .
- Any initial digit leaves the machine in a non-accepting reject configuration, signaling that an identifier cannot commence with a digit.
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
Top-Down vs Bottom-Up Parsing
- 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.
- 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:
- Multiplication and division () bind tighter than addition and subtraction ().
- Binary operators are left-associative ().
To enforce precedence unambiguously in a CFG:
- Introduce separate non-terminal tiers for expressions (), terms (), and factors ():
Lower tiers (closer to factors ) have higher operator precedence in the resulting parse tree.
Worked Out Examples
1
Construct the syntax tree / parse tree for the arithmetic expression:
using standard operator precedence rules.
Analyze operator binding strengths:
- Sub-expression is enclosed in parentheses, giving it the highest precedence.
- Multiplication and division by have equal precedence, evaluated left to right:
- Addition has the lowest precedence and forms the root operator of the entire expression:
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
- Left leaf:
- Right child: operator
*- Left leaf:
d - Right leaf:
e
- Left leaf:
- Left child: operator
- Left subtree: operand
The hierarchical tree structure is:
+
/ \
a /
/ \
* *
/ \ / \
b c d e
Evaluation begins at the deepest leaves ( and ), divides their results, and finally adds .
2
Draw the parse tree for the expression:
Evaluate binding strengths:
- forms a multiplicative term.
- forms a divisional term.
+joins the two terms at the root level: .
Using the standard expression grammar:
The derivation proceeds:
The syntax tree joins the product and the quotient under the root addition operator:
+
/ \
* /
/ \ / \
a b c d3
Draw the parse tree for the assignment expression:
- The assignment operator
=forms the topmost root of the syntax tree:- Left child: target variable .
- Right child: evaluated expression .
- Within the right-hand side expression:
- Root is
+. - Left operand: product .
- Right operand: quotient where denominator is difference .
- Root is
The tree decomposes as:
=
/ \
r +
/ \
* /
/ \ / \
a b c -
/ \
d eThe assignment statement evaluates the right-hand expression tree and binds the computed value to variable .
4
Draw the parse tree for the expression:
Multiplication and division share equal precedence and associate from left to right:
- is computed first.
- is computed second.
- is computed last.
Using the standard arithmetic expression grammar:
The syntax tree represents :
+
/ \
a /
/ \
* d
/ \
b c5
Draw the parse tree / syntax tree for the compound arithmetic assignment:
Analyze grouping from sub-expressions:
- Root is assignment
=:- Left side: identifier .
- Right side: compound rational expression.
- In the right-hand expression, division
/is the principal operator:- Numerator: product of two parenthesized terms: .
- Denominator: parenthesized sum .
- Within numerator product
*:- Left term: sum .
- Right term: difference .
- Within denominator sum
+:- Left term: .
- Right term: product .
=
/ \
r /
/ \
* +
/ \ / \
+ - e *
/ \/ \ / \
a bc d f gThe complete syntax tree reflects all parenthesized sub-expressions, performing , , and at the lowest level before multiplying and dividing.
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;
}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:
| Lexeme | Token Category | Semantic Description |
|---|---|---|
# | Preprocessor Operator | Preprocessor directive prefix |
include | Preprocessor Directive | Header inclusion directive |
< | Delimiter | Header path opening bracket |
stdio.h | Header Identifier | Standard I/O library header file |
> | Delimiter | Header path closing bracket |
int | Keyword | Built-in integer primitive type |
func | Identifier | Function name identifier |
( | Separator | Parameter list opening delimiter |
int | Keyword | Type specifier for first parameter |
a | Identifier | First parameter identifier |
, | Separator | Parameter list item separator |
int | Keyword | Type specifier for second parameter |
b | Identifier | Second parameter identifier |
) | Separator | Parameter list closing delimiter |
{ | Separator | Function body opening brace |
if | Keyword | Conditional control-flow statement |
( | Separator | Condition opening parenthesis |
a | Identifier | Left operand variable |
> | Relational Operator | Greater-than comparison operator |
b | Identifier | Right operand variable |
) | Separator | Condition closing parenthesis |
return | Keyword | Function return statement |
a | Identifier | Return value expression variable |
; | Delimiter | Statement terminator |
else | Keyword | Alternative branch keyword |
return | Keyword | Return statement |
b | Identifier | Return value variable |
; | Delimiter | Statement terminator |
} | Separator | Function body closing brace |
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.
The lexical analyzer converts the 10-line source code segment into 29 discrete tokens while discarding all tabs, newlines, and spaces.
Exercises
Exercises
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:
- 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.
- 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).
- 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:
- 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.
- 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.
- 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.
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.
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:
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.
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.
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.
| State | L | _ | D |
|---|---|---|---|
| →q0 | q1 | q1 | — |
| *q1 | q1 | q1 | q1 |
- 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:
- The scanner feeds characters into the DFA until no transition is possible or a delimiter (whitespace, operator) is encountered.
- If the DFA halts in accepting state , the scanned characters form a valid lexeme and are emitted as a token: .
- The scanner records new identifiers in the symbol table and resets the DFA to for the next token.
- If the DFA halts in a non-accepting state, a lexical error is reported.
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.