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.
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.
Table of Contents
There are two types of 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.
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:
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-
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
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.
In Syntax analysis phase, the PARSE tree is being made. And in Semantic phase compiler checks the PARSE TREE for any kind of error.
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.
Lets take a example.
S -> cAd A -> bc|a
Practice as much example as you can. The more complicated grammar you will practice, you will get better idea.
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:
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.
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:
After finding the LEADER just make basic blocks by forming loops in the goto statements.
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?
What is Inherited attribute?
What is L-attributed SDT?
SDD refers to syntax directed definition which contains grammar+semantic rule.
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:
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!