Instructions:

Any Assignment submitted LATE, will be marked as ZERO.

Any assignment found copied, will be marked as ZERO.

No assignment will be accepted in hard form

Marks of Assignment are 6.

Solve the given problems carefully

Any Text Copied From Internet Will Be Marked As Zero

1. Consider the context-free grammar

S -> 55+ | 55* | a

a) Show how the string aa+a* can be generated by this grammar.

b) Construct a parse tree for this string.

c) What language does this grammar generate? Justify your answer.

2. Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct.

a) Arithmetic expressions in postfix notation.

b) Left-associative lists of identifiers separated by commas.

c) Right-associative lists of identifiers separated by commas.

d) Arithmetic expressions of integers and identifiers with the four binary operators +, -, *, /.

3. Construct a syntax-directed translation scheme that translates arithmetic expressions from infix notation into prefix notation in which an operator appears before its operands; e.g., xy is the prefix notation for x y. Give annotated parse trees for the inputs 9-5+2 and 9-5*2.

4. Construct a syntax-directed translation scheme that translates integers into roman numerals.

5. Construct a syntax-directed translation scheme that translates postfix arithmetic expressions into equivalent infix arithmetic expressions