* 10 Most Frequently Asked Questions in GATE on Compiler Design*

Here are 10 most frequently asked asked questions on Compiler Design. 

1. Questions on Lexical Analyser

They can ask this kind of questions in three ways:

I. They can directly ask you the functionality of a lexical analyser.

Que: In a complier, the module which checks every character of the source text is called:

(a) The code generator

(b) The code optimizer

(c) The lexical analyzer

(d) The syntax analyzer

II. They can give the functionality and ask whose responsibility is this?

Que: Grouping of characters into tokens is done by:

(a) Scanner

(b) Parser

(c) Code generator

(d) Code optimizer

III. They can form two groups, one with the phases of compiler and other with the functionalities; you have to match the given phases with their associated functionalities.

Que: Match the following:

Group 1	Group 2
a. Lexical analysis	p. DAG's
b. Code optimization	q. Syntax trees
c. Code generation	r. Push down automata
d. Abelian group	s. Finite automata

To answer these questions, you don’t have to go through a long theory. Here is what you need to know:

• Lexical Analysis is the first phase of compiler also known as scanner. It converts the input program into a sequence of Tokens.
• Lexical Analysis can be implemented with the Deterministic finite Automata.
• Syntax analysis phase takes the token produced by lexical analysis as input and generates a parse tree (or syntax tree).
• Semantic analysis checks whether the parse tree constructed follows the rules of language.
• After semantic analysis the compiler generates an intermediate code of the source code for the target machine. It represents a program for some abstract machine.
• Optimization can be assumed as something that removes unnecessary code lines, and arranges the sequence of statements in order to speed up the program execution without wasting resources (CPU, memory).
• Code generator takes the optimized representation of the intermediate code and maps it to the target machine language.

2. Questions on the number of Tokens

In this type of questions, they give you a piece of code, and ask you to tell the number of tokens.

Que: The number of tokens in the following C statement is 

printf("i = %d, &i = %x", i, &i);

(a) 3                       (b) 26

(c) 10                     (d) 21

To solve these questions, you have to keep the following points in mind:

• Tokens are specified using Regular Expressions.
• Example of tokens:

1. Type token (id, number, real, . . . )
2. Punctuation tokens (IF, void, return, . . . )
3. Alphabetic tokens (keywords)

• Example of Non-Tokens: Comments, pre-processor directive, macros, blanks, tabs, and newline etc.

3. Questions on Top Down/ Bottom Up approach

Que: Recursive descent parsing is an example of

(a) Top-down parsers

(b) Bottom-up parsers

(c) Predictive parsers

(d) None of the above

Examples of Bottom-Up Parsers:

• Precedence parser
• Operator-precedence parser
• Simple precedence parser
• LR parser (Left-to-right, Rightmost derivation)
• Simple LR (SLR) parser
• LALR parser
• Canonical LR (LR(1)) parser
• Shift-Reduce Parser

Examples of Top Down Parsers

• Recursive descent parser
• Predictive parser

4. Questions on Associativity and Precedence

In this type of questions, they give you a grammar and ask you about the associativity and precedence of different operators. An example is:

Que: Given the following expression grammar:

E -> E * F | F+E | F

F -> F-F | id

Which of the following is true?

(a) * has higher precedence than +

(b) – has higher precedence than *

(c) + and — have same precedence

(d) + has higher precedence than *

All you need to remember about the associativity and precedence is:

• Productions that are left-recursive force evaluation in left-to-right order (left associativity). Productions that are right-recursive force evaluation in right-to-left order (right associativity).
• Precedence in a grammar is enforced by making sure that a production rule with higher precedence operator will never produce an expression with operator with lower precedence.
• So the operator in the lowest level will have highest precedence.

5. Question on Minimum Number of Registers

In this they give you a piece of code and ask what will be the minimum number or registers required to hold all the variables.

Que: The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have at most two source operands and one destination operand. Assume that all variables are dead after this code segment.

   c = a + b;

   d = c * a;

   e = c + a;

   x = c * c;

   if (x > a) {

      y = a * a;

   }

   else {

     d = d * d;

     e = e * e;

  }

Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?

(a) 0                       (b) 1

(c) 2                       (d) 3

6. Questions on Handles in Reduction

In this type of questions, they give you a grammar and a string. You are asked the handles in the given reduction following right sentential or left sentential form.

Que: Consider the grammar:

E→E+n∣E×n∣n

For a sentence n+n×n, the handles in the right-sentential form of the reduction are:

(a) n, E+n and E+n×n

(b) n,E+n and E+E×n

(c) n,n+n and n+n×n

(d) n,E+n and E×n

Know more about the handles in right sentential form!

7. Questions on Evaluating an Expression

In this type of questions, they give you a set of translation rules and you have to evaluate an expression according to the given translation rules.

Que: Consider the grammar with the following translation rules and E as the start symbol.

E → E1 # T { E.value = E1.value * T.value }

         | T{ E.value = T.value }

T → T1 & F { T.value = T1.value + F.value }

          | F{ T.value = F.value }

F → num { F.value = num.value }

Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

(a) 200                   (b) 180

(c) 160                   (d) 40

One way of solving this problem is to construct a parse tree for the given expression.

Alternatively, we can calculate by considering following precedence and associativity rules.

So expression 2 # 3 & 5 # 6 &4 will become ((2 # (3 & 5)) # (6 & 4))

Let us apply translation rules, we get ((2 * (3 + 5)) * (6 + 4)) = 160.

8. Questions on Inherited and Synthesized Attributes

Que: In a bottom-up evaluation of a syntax directed definition, inherited attributes can

(A) always be evaluated

(B) be evaluated only if the definition is L-­attributed

(C) be evaluated only if the definition has synthesized attributes

(D) never be evaluated

More on Synthesized and Inherited Attributes!

9. Questions on First & Follow and LL(1) Parsing

Usually if they ask separate questions on first & follow and LL(1) parsing, they will carry 1 mark each, but they can also ask a combined question of 4 marks.

For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3.   is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.

Que: The first and follow sets of terminals A and B are:

First(X) - It is the set of terminals that begin the 

            strings derivable from X.

Follow(X) - It is the set of terminals that can appear

            immediately to the right of X in some sentential

            form.

Now in the above question,

FIRST(S) = { a, b, epsilon}

FIRST(A) = FIRST(S) = { a, b, epsilon}

FIRST(B) = FIRST(S) = { a, b, epsilon}

FOLLOW (A) = { b , a }

FOLLOW (S) = { $ } U FOLLOW (A) = { b , a , $ }

FOLLOW (B) = FOLLOW (S) = { b ,a , $ }

10. Questions on Powers of Different Parsers

There are some direct questions related to powers of different parsers.

Que: Which of the following statements is true?

(a) SLR paper is more powerful than LALR

(b)LALR parser is more powerful than Canonical LR parser

(c) Canonical LR parser is more powerful than LALR parser

(d) The parsers SLR, Canonical CR, and LALR have the same power

You can learn more about the powers of the parsers here!