Register

GO Classes DPP | TOC|CFG

501 views
2 2 votes

Consider the language $L$ of arithmetic expressions over the alphabet $\{i d,+, *,()$,$\} , where id$ represents any identifier or number. An example string in the language is id * (id + id) .

Which of the following Context-Free Grammars that generate $L$ is ambiguous?
 

  1. $\begin{aligned}
    & E \rightarrow E+T \mid T \\
    & T \rightarrow T * F \mid F \\
    & F \rightarrow(E) \mid i d
    \end{aligned}$

     
  2. $\begin{aligned}
    & E \rightarrow T E^{\prime} \\
    & E^{\prime} \rightarrow+T E^{\prime} \mid \epsilon \\
    & T \rightarrow F T^{\prime} \\
    & T^{\prime} \rightarrow * F T^{\prime} \mid \epsilon \\
    & F \rightarrow(E) \mid i d
    \end{aligned}$

     
  3. $E \rightarrow E+E|E * E|(E) \mid i d$

     
  4. $E \rightarrow E+i d|E * i d| i d$

3 Answers

2 2 votes

C is ambigious 
A is removing ambiguity by giving preference to * over + as per bodmas rule and made them left associativity
B.we removed left recursion  and made into right recursion whole grammar and priorities as per bodmas rule we do to parse for LL1
D.it is unambigious for given string but remember it doesnot generate all arithmetic expressions try arithmetic expression including bracket and it will fail

1 1 vote

 

 

1 flag:
✌ Low quality (Mihir27 “nonsense example”)
0 0 votes
c
example :- id*id+id derives two different parse trees so its ambiguous
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | TOC...Next → · Computer Networks - ...
← Previous in category · GO Classes DPP | TOC...Next in category → · Theory of compiler U...
Position:
Show:

Related questions

2 2 votes
1 1 answer
309
309 views
GO Classes asked Oct 13, 2025
309 views
GO Classes DPP | TOC|MIN DFA
Consider the language $L$ over the alphabet $\Sigma=\{a, b\}$ defined as follows:$L=\left\{w \in\{a, b\}^* \mid\left(2 \cdot n_a(w)+3 \cdot n_b(w)\right)\right.$ is a mul...
4 4 votes
1 1 answer
328
328 views
GO Classes asked Oct 13, 2025
328 views
GO Classes DPP | TOC|REGULAR LANGUAGE
Given a language $L$ over the alphabet $\{a, b, c\}$, let $L^R$ denote the language of the reversal of all strings in $L$ (e.g., if $w=w_1 w_2 \ldots w_k$, then its rever...
4 4 votes
1 1 answer
336
336 views
GO Classes asked Oct 13, 2025
336 views
GO Classes DPP | TOC|REGULAR LANGUAGE
If $s$ is a string over the alphabet $\{0,1\}^*$, let $n_x(s)$ denote the number of occurrences of a symbol $x \in\{0,1\}$ in $s$. Further, let $n_{x y}(s)$ denote the nu...
4 4 votes
2 2 answers
379
379 views
GO Classes asked Oct 13, 2025
379 views
GO Classes DPP | TOC|REGULAR LANGUAGE
Consider the following languages over their respective alphabets:$L_1=\left\{w \in\{0,1\}^* \mid w\right.$ does not contain the substring 101} $L_2=\left\{a^n b^m c^{n+m}...