Register

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 1 (Page No. 206)

• retagged by
10,861 views
4 votes
4 votes

Consider the context-free grammar:$$S\rightarrow SS + \mid SS {\ast} \mid a$$and the string $aa + a{\ast}$.

  1. Give a leftmost derivation for the string.
  2. Give a rightmost derivation for the string.
  3. Give a parse tree for the string.
  4. Is the grammar ambiguous or unambiguous? Justify your answer.
  5. Describe the language generated by this grammar.
• retagged by
User Avatar

1 Answer

1 votes
1 votes
  1. S =lm=> SS* => SS+S* => aS+S* => aa+S* => aa+a*
  2. S =rm=> SS* => Sa* => SS+a* => Sa+a* => aa+a*
  4. Unambiguous
  5. The set of all postfix expressions consist of addition and multiplication
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
2
admin asked Aug 20, 2019
705 views
Ullman (Compiler Design) Edition 2 Exercise 4.8 Question 1 (Page No. 285 - 286)
The following is an ambiguous grammar for expressions with $n$ binary, infix operators, at $n$ ... ambiguous and unambiguous) grammars compare? What does that comparison tell you about the use of ambiguous expression grammars?
The following is an ambiguous grammar for expressions with $n$ binary, infix operators, at $n$ different levels of precedence: $E\rightarrow E\theta_{1}E\mid E\theta_{2}E...
User Avatar
1 votes
1 votes
2 answers
3
admin asked Jul 26, 2019
1,190 views
Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 3 (Page No. 51)
Which of the grammars are ambiguous? $S\rightarrow 0S1 \mid 01$ $S\rightarrow +SS \mid -SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow aSbS \mid bSaS \mid \epsilon$ $S\rightarrow a \mid S+S \mid SS \mid S^{\ast} \mid (S)$
Which of the grammars are ambiguous? $S\rightarrow 0S1 \mid 01$$S\rightarrow +SS \mid -SS \mid a$$S\rightarrow S(S)S \mid \epsilon$$S\rightarrow aSbS \mid bSaS \mid \epsi...
User Avatar
Link Copied!