SRM University 2007 B.Tech Computer Science and Engineering BANK : COMPILER DESIGN - Question Paper

02. Show that the subsequent grammar is ambiguous
S --> aSbS/bSaS/
For a sentence belonging to the above grammar:
a) Draw the parse tree.
b) Construct the left-most and right-most derivations of "abab".
03. Construct a minimal DFA for (a/b)*(a/b) and write the algorithm for
minimizing a DFA.
04. discuss the process of constructing an NFA from the regular expression.
obtain the NFA for the expression (a/b)*abb.
05. Construct the DFA for (a/b)*abb and minimise the DFA.
06. How would you construct a DFA directly from a regular expression?
Write the improper rules and algorithm wherever necessary.
07. discuss the simulation of NFA with suitable example.
08. discuss the subset construction technique to convert NFA into DFA
with an example.
09. (a) discuss the algorithm for the simulation of DFA. (5)
(b) provide the rules for nullable, firstpos and lastpos in construction of DFA

10. discuss the Thomson's construction technique in detail. Construct the
NFA for the expression d(a/b)*a.









Unit - three

2 MARKS

1.What is a Lexical analyser?

2.Write the algorithm for moving forward pointer in "input buffering" scheme.

3. What is the use of sentinels?

4. Write the algorithm for moving forward pointer in "input buffering" scheme using sentinels.

5. Distinguish tokens, trends and lexemes.

6. elaborate the lexical-error recovery actions?

7. What is the need for input buffering?

8. discuss prefix and suffix of the string with example.

9. discuss proper prefix, proper suffix and proper substring with example.

10. What is subsequence of a sting?

11. Draw the transition diagram for identifiers.

12. What is the use of lexeme- beginning pointer and forward pointer?

13. What is a parser?

14. Write the role of parser.

15. Mention the fault recovery strategies of parser.

16. What is ambiguity? Write the ways to eliminate ambiguity.

17. Consider the Grammer

S??? (L) / a
L???L, S / S
Construct the left most derivation for the subsequent sentence

(a, a)

Earning:   Approval pending.