This was the first day we came face to face with Prof. N. Ganguly.
He immediately caught our attention when he took a special attention.... it consisted of asking people their halls as well as as their hailing cities. He also asked many students the meanings of their names. This day ended much as anticipated and with everyone quite happy at the end of it ........ NOTHING TAUGHT THAT DAY ...... YIPPEE!!!
This was the "INTRODUCTION TO COMPILERS" day. We learnt in a very highly INTERACTIVE session what a compiler was. After a lot of discussion we finally came to a general agreement ..... that, a compiler translates a high level language to a low level language, generally to a machine code. A compiler analyzes the source language based on its rules and synthesizes the target language on its rule set.The analysis part consists of lexical, syntax and semantic analysis.
We learnt that lexical analysis consists of breaking the sentences into a set of tokens. Then the parser creates the PARSE TREE. All tokens should be consumed by the tree and no non terminals are left to be expanded. Semantics checks for the meaning and validity of the sentences.
The synthesis consists of generating an intermediate code and iteratively optimising it and finally converting it to machine code.
On this day, we dealt with the major issues regarding compiler construction. It was then we came to appreciate the fact that compiler construction is indeed, a mammoth task. It has to deal with different set of processor architectures -- RISC and CISC, different sets of instruction sets, has to be Operating System compatible. Error Handling is the ART of intelligently replacing error conditions with feasible alternatives. WE WERE SURPRISED to know that "Aid in Debugging Optimisation" is STILL HEAVILY RESEARCHED!! Runtime Environment, Speed of Compilation are major Issues. Also the loader function is quite varied among different machines. We also came to know that stack segment management is also an important issue. Sir also discussed the types of tokens possible.
The class kicked off with a process map of the link between the lexical analyzer and the syntax analyzer ( parser ). How do we indentify tokens? ..... using a finite automata to identify the regular expressions. After this we had a sort of FLASHBACK ..... we sort of started re-learnig FLAT. The simplest regular expression was retaught, the rules of regular expression combination to form another regular expression was taught to us once more. Then we were given a few problems of identifying the set generated from a few reg. exp(s). We also dealt with reg. exp(s). from varied field like e-mail ids. Then Thompson's construction was taught. The construction of different NFAs from regular expression machines went by peacefully. Then came the time for all of us to be confused. Things which seemed UNNATURAL smiled proudly at us telling us they were true. This bit was unfortunately a bit difficult to digest. But finally all were happy with the conclusion ..... that -- given a r.e. of cardinality |r|, we can construct a NFA in O(|r|) states. Then came the algo pseudo code to end the class.
Well to be very honest, this class seemed tediuos. We were to convert a NFA to a DFA. One can imagine our plight of trying to convert an NFA with 10 states!! It started with copying the humongous state transition table. Then came a welcome respite ( being ironic ... [;)] ), drawing the graph. And what followed, was the most boring thing one can imagine ...... finding the epsilon closures of all states starting from the start state set and adding all alphabet symbol transition. Trying out all different combinations, and getting redundant states, our plight finally came to an end when all the states' sets had exhausted themselves. And finally we constructed the DFA ... this NEARLY concluded our session. We ended on a happy note ( don't you think the ending on happy notes every time we get bored/ unhappy has become a cyclic event?? .. makes me wonder as to how this Prof can manage to pull this feat every single time!! ), we wrote the pseudo code for the conversion. PHEW!! so many events in just a class!!
We had an extra class today.....that too in the afternoon!! We were feeling too sleepy...but we got awakened when sir came and started to elaborate some technique named Cache Technique.Sir reminded us of COAA classes(paging algorithm) and we attentively started to look at the "GREEN" board. We came to know about Lexical Analyzer.Then sir taught us how to write a lex file and get the output C file. Sir gave an example of a lex code which counts the number of characters and number of words and number of new lines . The class ended with totally confused minds (about lex syntax)!!!
Today we got a clear idea about the lex syntax.Sir gave another exaple code to detect the number of characters and words and lines in a file.Now sir started with the new topic - Parser which is also known as Syntax Analyzer . Sir talked about some techniques of error handling and we realized how difficult it is to parse a language.Panic mode worked as a tonic and we got some relief due to its simplicity.But there was some "panic" yet to come.The first panic was Phrase Level Recovery and we came to know that how missing a semicolon can make a big trouble.
"TI SI A OHT ADY".......what is this!!! may be German we thought !!! oh no no it is "IT IS A HOT DAY"....this is what is known as Global Recovery.Human brain is an expert to do this error handling.....but how difficult it is to make a computer do that!! Still lots of research going on............
So after 2 free classes we meet again. Today’s Class was based on ambiguity in Grammar. Sir explained nature of ambiguous grammar....
Sir explained the ambiguity with the rule of IF-THEN-ELSE statements.
The result was a chaotic class...each one trying to express one’s own views...
Ultimately sir concluded with an assumption that we will match the “else” with the nearest “if”. Class ended with a modified version of the rule.
Class started with previous day's discussion....."ambiguity in grammar".Today sir started with the idea of Parser... two types of parsers --- namely top-down and bottom-up.Today sir elaborated a method to get free of left recursion.This was a new and very interesting topic.So everyone was very attentive in the class.The class ended with a neat and clean idea about left recursion.
Today we have a double lecture!! Class is so early ,so could not get time to have breakfast :(( ......Today we came to know that Top Down Parser cannot parse every string that belongs to context free grammar.So we need to remove left recursion and left factoring. Sir explained the method to free the grammar from Left Recursion & Left Factoring.Now sir moved to Build Predictive Parser and transition diagrams for it. It was looking so simple in way sir explained. Then sir presented a Table Driven Approach to parse a grammer. Sir started the concept of FIRST and FOLLOW but we were not able to Follow it so quickly and class ended with the Following topics: 1) FIRST 2) FOLLOW............
The classes are now taking a more serious turn as students started attending the class more regularly because the midsem are not so far. Exams are approaching and nobody has any idea how far is the syllabus for the midsems. Sir started today's topic with a example of a Grammar & explained the How to get FIRST & FOLLOW of Non-Terminals. Sir built up a magic table for parsing and sir showed the simulation of predictive parser on an input string. At the end of class we got a goodnews that there would be no class next Monday & Tuesday.
Class started with a new parser called LL(1) parser. Sir elobrated the idea of parser with an example. We got the clear idea how to build a parser table & its simulation on a input "STRING". Idea was simple & we understood it clearly. At the end of class "Class Test" was anounced. Every student was shocked.
Finally we got rid of Top Down Parser ... and sir started with Bottom up parser. But we soon understood that Bottom up Parsing was even more dangerous.You can't intuitively visualize what is happening here... a confusing method.The communication pipe between sir's STDOUT and our STDIN was blocked for a while but after sometime it started working well.New problem creeped in...when to use SHIFT and when to use REDUCE.The grammar is ambiguous but we are parsing the input with some precedence among the operators. The conflicts led to conflicting minds about the implementation of the algorithm.We have to wait for the next class for the funda!!
So the class-test is tommorrow and we are yet to read a lot.Today we got a double lecture of "Operator Precedence" and "LR(0)".Now we are getting the clear idea of how parsers work.But they are all confusing with each other...each has it's own rules and that too thay are similar...but not the same.Now we have too much material to read for tommorrow's class test.As the class continued more and more algos creeped in and there is a lot to study.But at the start of the next half we had a surprise!! Sir found some guys missing...again attendance!! Sir asked us to threaten them.Now we started with LR parser table construction.Time was out and the board was full of tables and boxes.Sir had to finish the entire topic anyhow...otherwise he had to draw all those frightening structures once again.So the class ended with thirty five past nine with everyone screaming "Sir time up".Lot for today we have to study now!!
Today is the day before midsem and we are completely infected by exam phobia !! The syllabus is almost complete.Today sir has showed how reduce/reduce conflict can arise in case SLR parse table. The SLR grammar cannot handle all grammars. Finally the class ended with a happy news….the exam paper would be easy ! So enjoy !!
