recategorized by
611 views
1 votes
1 votes

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
recategorized by

1 Answer

1 votes
1 votes
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$
Answer:

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
1 answer
2
Applied Course asked Jan 16, 2019
481 views
Which phase of the compiler generates parse tree?Lexical analyzerSemantic analyzerSyntax analyzerNone of them.
0 votes
0 votes
1 answer
4
admin asked Jan 5, 2019
353 views
The following grammar $\text{G}$ is left recursive.$\text{E} \rightarrow \text{E + T}\; \mid \; \text{T} $$\text{T} \rightarrow \text{T * F} \; \mid \; \text{F} $$\text{F...