BUET M.Sc Admission — Exam: 2018 (CSE)প্রশ্ন ও সমাধান

Left recursion: a grammar rule where a non-terminal derives a string beginning with itself, e.g. A → Aα | β.

Why it must be eliminated: a top-down (recursive-descent / LL) parser expands the leftmost non-terminal by trying its alternatives in order; if the first alternative for A begins with A itself (A→Aα), the parser's function for A calls itself again before consuming any input token — this recursion never terminates (it will overflow the call stack instead of ever making progress through the input). Bottom-up (LR) parsers, in contrast, handle left recursion natively and don't need this transformation.

Standard elimination technique: rewrite
A → Aα | β (β does not itself start with A)
as the equivalent right-recursive grammar:

A  → β A'
A' → α A' | ε

No immediate left recursion remains — each call to A' either consumes input (via α) or terminates (via ε), so a recursive-descent parser is guaranteed to make progress.

Worked example: the expression grammar E → E + T | T (left recursive — natural for left-to-right addition) becomes:

E  → T E'
E' → + T E' | ε

Parsing "T + T + T": parse T, see "+", loop consuming "+T" repeatedly via E' until no more "+" remains, then apply the ε production to stop — no infinite recursion occurs.

(Indirect left recursion, e.g. A→Bα, B→Aβ, is removed by first substituting B's productions into A's productions, then applying the same immediate-left-recursion transformation.)

Exam takeaway: Left recursion (A→Aα) makes recursive-descent parsing loop forever since no input is consumed before the recursive call; transform A→Aα|β into A→βA', A'→αA'|ε to make the grammar LL-parseable.

A branch/control hazard occurs because a pipelined processor fetches later instructions before a branch's outcome (taken/not-taken) and target address are known — by the time the branch is actually resolved (typically in the EX or MEM stage), one or more wrong-path instructions may already be sitting in earlier pipeline stages.

graph LR
 IF["IF: Fetch"] --> ID["ID: Decode"] --> EX["EX: Execute / branch resolved here"] --> MEM["MEM"] --> WB["WB"]

Pipeline timeline illustrating the hazard (5-stage pipeline, branch resolved in EX):

Instruction	C1	C2	C3	C4	C5
I1 (branch)	IF	ID	EX (outcome known)	MEM	WB
I2 (wrong-path guess)		IF	ID — flushed ✗
I3 (wrong-path guess)			IF — flushed ✗
Correct-target instruction				IF	ID

• If the branch is resolved as taken but the pipeline had already fetched fall-through instructions (I2, I3), those instructions are flushed/squashed — the cycles already spent on them are wasted (a "bubble").
• The deeper the pipeline, the more instructions are speculatively fetched before resolution, so the branch penalty (wasted cycles) grows with pipeline depth.

Mitigation techniques:

• Stall/freeze — simplest: stop fetching new instructions until the branch resolves. Correct, but incurs the full penalty on every branch.
• Branch prediction (static or dynamic) — guess taken/not-taken (e.g. a static "backward branches taken, forward not taken" heuristic, or a dynamic 2-bit saturating counter in a Branch History Table) and speculatively fetch along the predicted path; flush and restart only on a misprediction.
• Branch Target Buffer (BTB) — caches previously-computed branch target addresses so the target is known at fetch time instead of waiting for EX.
• Delayed branch — the compiler fills the slot(s) immediately after a branch with useful, branch-independent instructions that execute regardless of the branch's outcome, so that delay slot is never wasted.
• Speculative execution with rollback — execute past the branch along the predicted path but hold results until confirmed; discard (flush) them only on misprediction, as used by modern superscalar/out-of-order CPUs.

Exam takeaway: A branch hazard is the uncertainty about which instruction to fetch next until the branch resolves; it is handled via stalling, (dynamic) branch prediction + BTB, delayed branch, or speculative execution with a pipeline flush on misprediction.