in Compiler Design recategorized by
387 views
1 vote
1 vote

The left-factoring of the given CFG is

  • $S \rightarrow aBcD \mid aBD \mid daB \mid d$
  • $B \rightarrow b$
  • $D \rightarrow d$
  1. $S \rightarrow aBB' \mid d$
    $B' \rightarrow cD \mid D$
    $B \rightarrow b$
    $D \rightarrow d$
  2. $S \rightarrow B'cD \mid B'D \mid d$
    $B' \rightarrow aB$
    $B \rightarrow b$
    $D \rightarrow d$
  3. $S \rightarrow B'cD \mid B'D \mid dB' \mid d$
    $B' \rightarrow aB$
    $B \rightarrow b$
    $D \rightarrow d$
  4. None of them
in Compiler Design recategorized by
387 views

1 Answer

1 vote
1 vote
Left-Factoring : The process of conversion of the grammar with common prefixes into deterministic grammar is known as left factoring.
Syntax: if the CFG is of the form $A \rightarrow aA_1 \mid aA_2 \mid \dots aA_n$
Left factored grammar is
$A \rightarrow aA'$
$A' \rightarrow A_1 \mid A_2 \mid \dots A_n$
Left factored grammar for the given grammar is
$S \rightarrow aA' \mid dB'$
$A' \rightarrow BcD \mid BD$
$B' \rightarrow aB \mid \epsilon$
$B \rightarrow b$
$D \rightarrow d$

2 Comments

does left factored  only applied to starting symbol?
0
0
why not C
0
0