CS337 - PRINCIPLES OF COMPLIER DESIGN

[aruljothi]

CS337 - PRINCIPLES OF COMPLIER DESIGN

Time:   Three Hours                   Maximum:   100 Marks

Answer All The Questions
PART – A (10 x 2 = 20 Marks)

1.    List any two complier construction tools, indicating their inputs and outputs.
2.    Briefly explain any two language conventions that impact the difficulty of lexical analysis.
3.     Write regular definition for the following language over {0,1} A string of 0's and 1's, which has 0 at the third position when counted from night.
4.     Formally define a nondeterministic finite automation (NFA)
5.     Prove that the following grammar is ambiguous: S→ aSbS │bSaS│ Є
6.    Write down the predictive parsing algorithm.
7.     Give the algorithm for generating the closure of a set of LR (0) items.
8.     Translate the expression : - (a+b) * (a+b+c) into quadruples and indirect triples.
9.     Give the grammar for generating binary numbers. Add semantic rules to the above grammar to compute the decimal equivalent of the binary number, generated.
10.    Write down the algorithm that partitions the given sequence of three-address statements into basic books.

Part – B (5 x 16 = 80 Marks)

11.     Draw the transition diagram for the lexical analyzer that recognize the following tokens.
                Identifiers, relational operators. Use the following rules to form the identifier

•   begins with an alphabet
•   consists of alphabets, digits and hyphen
•   should not end with an hyphen
•   not two hyphens appear together

12.a)   Draw the NFA for the following regular expression using Thompson's Construction and then convert it into an equivalent DFA.
   (a/b) * (a/c) * b

(OR)
12.b)i)   List the tasks performed by a lexical analyzer
ii)   Give the complete algorithm that takes a NFA and converts it into an equivalent DFA.

13.a)   Remove left recursion from the following grammar and build the predictive parsing table.
               S → (L) │a
               L → (L, S) │S
(OR)
13.b)   Build LR(1) parsing table for the grammar:
   S → Aa │bAc │Bc │bBa

                A → d
      B → d

14.a)   Write down the translation scheme for generating three address code for evaluating Boolean expressions using back patching. Explain the attributes used.  Use the above and generate three address code for:

   While ( (a<b) and (c>d) ) do
begin

                if(p=q) then p = 1
                else p = 2
While (p>q) do
                Begin
                P: = x+y
                q: = x-y
                end
end
(OR)
14.b)   Explain how declarations are processed by the computer. Take into consideration nested procedures also. Explain clearly the attributes used. Show with an example how the symbol tables are formed.

15.a)i)   Explain how 'next use' information about names in basic blocks can be collected.
ii)   Discuss about the actions performed by a simple code generator while generating code for a typical three-address statement of a form x: = y op z.
(OR)
15.b)i)   Write the syntax directed definition that computers and prints the post-fix equivalent of the given infix expression.

       ii)  Write down the unambiguous CFG for generating Boolean expressions.
-----