Back to the 2023 paper

Module 2: Syntax Analysis (Parser)

20232m

Left factoring guarantees
(i) Not occurring of backtracking
(ii) Cycle free parse tree
(iii) Error free target code
(iv) Correct LL(1) parsing table

Worked SolutionAI Assisted

Answer: (i) Not occurring of backtracking

Explanation

  • Left factoring is a grammar transformation that factors out the common prefix of two or more production alternatives.
  • It is used to remove uncertainty about which alternative to choose when a common prefix could lead to two different nonterminal, which otherwise forces the parser to backtrack while building a predictive (LL) parser.

How it works:
A→αβ1∣αβ2  ⇒  A→αA′,A′→β1∣β2A \to \alpha\beta_1 \mid \alpha\beta_2 \;\Rightarrow\; A \to \alpha A', \quad A' \to \beta_1 \mid \beta_2

In an LL(1) (predictive top-down) parser the decision is made by looking at the first token; factoring out a common prefix ensures the choice is deterministic, so backtracking never occurs.

Hence left factoring guarantees:
(i) Not occurring of backtracking\boxed{\text{(i) Not occurring of backtracking}}

Similar questions

Free AppAndroid App

Coursify Android App

Generate AI courses, take quick quizzes between classes, and master complex engineering concepts on the go.