Grammar looks easy until a paper asks for a parse-tree count or an LL(1) decision. Grammar and CFG join Compiler Design with Theory of Computation, so the same preparation pays twice. The whole subject fits on one expression grammar: ambiguity shows up first, precedence layering removes it, and FIRST with FOLLOW settles whether what is left is LL(1).
What a grammar is and where CFG sits
A grammar is G = (V, T, P, S): nonterminals, terminals, productions, and start symbol. Exams usually use capitals for nonterminals, lowercase for terminals, and epsilon for the empty string.
The Chomsky classes nest as Type 3 regular inside Type 2 context-free, inside Type 1 context-sensitive, inside Type 0 recursively enumerable. A CFG is Type 2: every production has one nonterminal on its left.
Regular expressions handle tokens, but nested parentheses, blocks, and if-else constructs need a stack; a DFA cannot count nesting depth. Compilers use regular languages for tokens and CFGs for syntax. Lexical Analysis in Compiler Design covers the token side.
Derivations, parse trees, and ambiguity
Use this running grammar, G1:
E -> E + E | E * E | ( E ) | id
For 2 + 3 * 4, treat each number as one id token. G1 permits two leftmost derivations.
Derivation 1, plus at the root:
E => E + E => id + E => id + E * E => id + id * E => id + id * id
With lexemes 2, 3, and 4, this is 2 + (3 * 4) = 2 + 12 = 14.
Derivation 2, multiplication at the root:
E => E * E => E + E * E => id + E * E => id + id * E => id + id * id
This is (2 + 3) * 4 = 5 * 4 = 20. One string has two parse trees and two answers, so G1 is ambiguous.
A derivation is a production sequence; each intermediate string is a sentential form. Leftmost and rightmost derivations expand the corresponding nonterminal. One parse tree determines exactly one leftmost and one rightmost derivation, though many other expansion orders describe that same tree.
The standard disambiguated grammar G2 is:
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
The layers place multiplication deeper than addition, so * has higher precedence; left recursion supplies left associativity. G2 gives 2 + 3 * 4 one tree, worth 14.
Left recursion and left factoring
A top-down parser loops on A -> A alpha because it expands without consuming input. Transform A -> A alpha | beta as follows:
A -> beta A'
A' -> alpha A' | epsilon
G2 then becomes G3:
E -> T E'E' -> + T E' | epsilonT -> F T'T' -> * F T' | epsilonF -> ( E ) | id
Left factoring solves a different problem. S -> i E t S | i E t S e S | a becomes S -> i E t S S' | a and S' -> e S | epsilon. Left recursion removal prevents looping; factoring postpones a choice past a shared prefix. Both preserve the language but change parse trees, and neither automatically removes every ambiguity.
FIRST and FOLLOW for G3
FIRST(X) holds possible opening terminals, plus epsilon if X can vanish. FOLLOW(X) holds terminals that may immediately follow X, plus end marker $.
Nonterminal | FIRST | FOLLOW |
|---|---|---|
E |
|
|
E' |
|
|
T |
|
|
T' |
|
|
F |
|
|
For FIRST(E), chase E -> T E' -> F T' E'. Since F -> ( E ) | id, FIRST(E) = { (, id }.
For FOLLOW(T), E -> T E' contributes FIRST(E') - { epsilon } = { + }. Because E' can vanish, T also inherits FOLLOW(E). As the start symbol, E gets $; F -> ( E ) adds ). Thus FOLLOW(T) = { +, ), $ }.
For E', the nonempty alternative has FIRST { + }; the epsilon alternative uses FOLLOW(E') = { ), $ }. The sets are disjoint, so no table cell gets both productions. Generally, alternatives need disjoint FIRST sets, and a nullable choice must be disjoint from that nonterminal's FOLLOW set. G3 is LL(1).
CFL facts from Theory of Computation
CFLs are closed under union, concatenation, and Kleene star, but not intersection or complement. The favourite MSQ exception is that a CFL intersected with a regular language is a CFL.
Every regular language is context-free; the converse fails for { a^n b^n | n >= 1 }. Finite automata match regular languages, while pushdown automata match CFLs. Deterministic CFLs are a strict subset of CFLs. Context-Free Grammars and Pushdown Automata develops the machine connection.
Ambiguity describes a grammar. An inherently ambiguous language has no unambiguous grammar, as with { a^i b^j c^k | i = j or j = k, i, j, k >= 1 }.
Grammar and CFG traps that cost marks
Trees versus derivations: G1 gives
id + id * idtwo trees but more unrestricted derivations. Count the named object.Language versus trees: left recursion removal preserves the language, not tree shape.
Epsilon in FOLLOW:
epsiloncan appear in FIRST, never FOLLOW. FOLLOW contains terminals and$.Grammar versus language: one ambiguous grammar does not prove inherent ambiguity.
Hierarchy direction: every regular language is context-free, not conversely.
LL input: left recursion makes a top-down parser loop. Check it before building the table.
How GATE and interviews test Grammar and CFG
Grammar and parsing appear under Compiler Design, while CFGs and PDAs return under Theory of Computation. Check the conducting institute's official GATE website for the applicable syllabus and pattern, not remembered marks distributions.
Recent GATE papers have favoured four moves: count parse trees, identify a generated language, compute FIRST or FOLLOW, and find an LL(1) conflict. All four fall out of the G1 to G3 chain, which is why transforming a grammar by hand beats memorising a finished table. Over a hundred solved grammar and CFG questions sit in the Compiler Design question bank, and Context-Free Grammar MCQs: 11 Solved GATE Questions is a good set to start on.
Compiler interviews often ask you to disambiguate a grammar or explain precedence by layering. Reproducing G1 to G2 on a whiteboard is the complete answer.
The short version and the next step
A CFG is a Type 2 grammar whose production left side is one nonterminal.
G1 is ambiguous because
2 + 3 * 4has trees worth 14 and 20.Left recursion removal prevents top-down looping; left factoring separates shared prefixes.
G3 has conflict-free FIRST and FOLLOW choices, so it is LL(1).
CFLs have specific closure limits, and a CFL intersected with a regular language remains context-free.
Learn in sequence with GATE Guidance by Sanchit Sir, then practise under time in GATE Test Series - Mocks & Topic-wise Tests. Use GATE CS Exam Preparation Courses & Test Series to place grammar inside the wider plan.
