How to Study Compiler Design for GATE | Important Questions

Hi, this blog is on how to prepare Compiler Design for GATE .

If you have a look upon the GATE syllabus, then every year GATE asks 4-5 marks of question on Compiler Design part.

So, considering this as an important subject below are few topics and tricks to solve these questions in minimum time and get a good rank.

First I will point out some important topics. Then, I will describe that in detail and tricks to solve the problem.

• Type of compiler and its phases
• Lexical analysis and tokens
• First and follow calculation
• Some shortcut trick for Parserand it’s table
• Dag and control flow graph
• Synthesized and inherited attribute
• Liveness analysis of variable (newly added)

Do not get confused by seeing this topics, they are quite short and easy. Just a little understanding is required.

Now, if you have not covered the theory of computation before, then just revise that regular grammar part, nothing much required.

Let’s start the topics from Compiler Design for GATE one-by-one.

Types of Compiler and Its Phase

There are two types of compiler-

1. Single pass compiler
2. Multi-pass compiler

In single pass total compilation should be done at once. And in multi-pass compiler, it should be done phase by phase.

GATE may ask a question on difference, advantage and disadvantage.

• For single-pass compiler- less time required and more RAM space required.
• For multi-pass compiler- more time required and less RAM space required.

Now, comes to its phase, have a look at the hand written notes image below.

Read detail guide about phases of compiler.

Few important points to remember in Phases:

• Code optimization phase is a optional phase in many compiler.
• Semantic analysis phase will do the checking.
• Each phase is capable of handling the error.

Lexical analysis and Tokens

The main work here is to convert the stream into tokens. GATE will ask a question on calculation of tokens in a code.

Few tips on calculation of tokens-

• Always take the longest matching sequence. For example, if + is a token and ++ is a token and they are present in the same line then first take ++.
• All the words present in an inverted comma are single token.
• If an inverted comma started but not ended, then ignore that, it will not count in tokens.

Practice many examples on taking sample of codes, you will get good grasp.

The main work of the lexical analyzer is to convert the code into tokens. For example, if a line is like x=a+b*c;  then it will be converted to id=id+id*id.

Error Types:

This is quite important. From last few years, GATE ask question on finding the type of error in a code.

There are basically three types of error.

• Lexical error- Variable declaration error, exceeding length of the code.
• Syntax error- Declaration on data types , missing semicolon, etc.
• Semantic error- Type conversion error, variable not declared error.

In Syntax analysis phase, the PARSE tree is being made. And in Semantic phase compiler checks the PARSE TREE for any kind of error.

First and Follow Calculation

This is probably the basic and most important part of Compiler Design for GATE. Without this, you cannot construct Parser Table.

Rules to find First and Follow:

Few rules are there. I will list it here. The more example you will practice, the better you will be in this.

• While calculating a First, always follow bottom-up approach. And in calculating a Follow, always follow the top-down approach.
• Terminals will always be the first of themselves. For Non-Terminals, you need to calculate first of that Non-Terminals separately. The first of epsilon is always epsilon.
• Make sure every time epsilon can only come in First, and not in Follow.
• For calculation of Follow, always search the variable on the right-hand side.
• Follow of start symbol will always be a dollar. Along with the dollar, it can contain any other thing also.

Lets take a example.

S -> cAd
A -> bc|a

• Here, First of S will be c and First of A will be [b, a]
• Follow of S will be [$] and follow of A will be [d]

Practice as much example as you can. The more complicated grammar you will practice, you will get better idea.

Some shortcut on Parser and its Table

This is quite important as every year GATE asks one mark question on checking grammar is LL(1) ACCEPTABLE or not. Sometimes they ask about LR(1) and Parsing table size.

How to check Grammar LL(1)?

Shortcut on checking a Grammar LL(1) or Not:

• If the production doesn’t have any null, then-
• Assume each production to be alpha, and calculate first of all of them. In case any common found in their intersection then its not LL(1) ACCEPTED, and if no common found then its accepted.
• If it have a null production then calculate FOLLOW (S), and take intersection, rest all same with above rule.
• If a grammar is LL(1) accepted then it must be a LR(1) grammar.

Always remember top-down parser follow the leftmost derivation. And bottom-up parser follows the reverse of the rightmost derivation. This is the favorite question of the examiner.

Important Notes:

• CLR parser is having the highest power among all of the parsers.
• Grammar will not be LL(1), if it has left recursion and the grammar is ambiguous.
• If a grammar has more than 1 parse tree possible for single production then it’s ambiguous.
• Formula to calculate LL(1) Parsing table size- (V*T+1) where ‘V’ is the variable and ‘T’ is the operator.

Dag and Control Flow Graph

This is not that much important, but sometimes GATE asks to count the number of edge and node. In that case, just solve the expression and form a DAG, and then calculate.

In control flow graph, they will ask to find out the Leader sometimes.

How to find the leader?

Some basic rule to find out LEADER:

• The first statement is always a LEADER
• Goto() marked statements are a leader.
• The next line of the goto statement is also a leader.

After finding the LEADER just make basic blocks by forming loops in  the goto statements.

Synthesized and Inherited Attribute

Even this is not that important, still, before 3-4 years they ask some questions on identifying the S, and L- attributed SDT. Else, they will give some statement, and ask which one is correct among them.

What is Synthesized attribute?

• The attribute of a non-terminal which is present in L.H.S.
• Here parent can take value from the child.
• It follows bottom-up parsing.

What is Inherited attribute?

• The attribute of Non- terminal that is present in R.H.S of production rule.
• It can take value from siblings and parent.

What is L-attributed SDT?

• Here, the variable only allowed to take value from the left side.
• No value taken from the right sibling.
• It follows top-down parsing.

SDD refers to syntax directed definition which contains grammar+semantic rule.

Liveness Analysis of Variable

The liveness analysis of variables is a newly added topic in GATE. We have only one question asked so far from this. But this year I expect a question from this. it’s not complicated. You have to practice some examples from it.

I will give the shortcut and algorithm rule to find out if a variable is live or not.

Few important point on Liveness:

• Liveness calculation helps us to allocate resisters because we have a limited number of resisters available.
• We generally call a variable Live if it present in R.H.S of that line and if not then a way should be there to reach that variable from the same line, and before that, it should not be used anywhere in L.H.S.
• If a variable is used before its defined then we call it Dead.
• Generally, if it’s present in L.H.S then it’s defined and in R.H.S it’s used.

Above is the shortcut to find it. And it is valid only for a single line statement block.

If they ask from a block where more than two statements are present, then you have to calculate with help of a table and it takes 4-5 minute.

Formula to calculate Liveness in an Block:

USE/GEN -= variable in R.H.S but, not present in L.H.S of previous statement.
DEF/KILL=variable in L.H.S statement,
IN(n)=USE(n) union (OUT-DEF)
OUT(n)=IN[s]  Here 's' represent successor statements.

Do not get confused by seeing the above formula and statement. Just practice some examples, you will get clear idea. I just mentioned formula here.

This all about how to study Compiler Design for GATE. Practice different examples from above topics. This much is enough for GATE. Any questions? Let me know in the comment.

All the Best!

Umakant Biswal

This is Umakant, a B.tech(CSE) student, quora writer, and a good problem solver. I like to write about technical topics and enjoy solving problems efficiently. I'm a Python lover and always curious to learn new facts.