# Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 1 (Page No. 51)

16 views

Consider the context-free grammar

$S\rightarrow SS+\mid SS^{\ast}\mid a$

1. Show how the string $aa+a^{\ast}$ can be generated by this grammar.
2. Construct a parse tree for this string.

edited

## Related questions

1
69 views
Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct. Arithmetic expressions in postfix notation. Left-associative lists of identifiers separated by commas. Right-associative lists of identifiers separated by commas. Arithmetic ... binary operators $+, -, *, /$. Add unary plus and minus to the arithmetic operators of $(d)$.
1 vote
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)$
What language is generated by the following grammars? In each case justify your answer. $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)$
Consider the context-free grammar:$S\rightarrow SS + \mid SS {\ast} \mid a$and the string $aa + a{\ast}$. Give a leftmost derivation for the string. Give a rightmost derivation for the string. Give a parse tree for the string. Is the grammar ambiguous or unambiguous? Justify your answer. Describe the language generated by this grammar.