QEEE Session on "Syntax Directed Translation - Compiler Design"
15th, 17th & 19th February, 2016
QEEE Session on "Syntax Directed Translation - Compiler Design" was conducted on February 15, 17 & 19, 2016 with an objective to clarify the principles and process of syntax directed translation in compilers.
Through Quality Enhancement In Engineering Education (QEEE), IITs provide quality technical education at par with the premier institutes. QEEE is conducted in real time through ICT and synchronous technology is used to allow for an integration of superior external scholastic inputs into current pedagogical practices. QEEE project is funded by MHRD, Government of India.
Prof. V. Krishna Nandivada, IIT Madras conducted the sessions. Ms. Gargi Amoli, Assistant Professor (CSE) coordinated the workshop at Dronacharya Group of Institutions, Greater Noida as the Local Coordinator. The students of Computer Science & Engineering and Information Technology of sixth semester attended the workshop.
February 15, 2016
Prof. V Krishna Nandivada initiated the first session with a brief introduction to compilers. He gave a brief description of the phases of compiler. He explained the process of Lexical Analysis in compilers. He then stated the relevance of Syntax Directed Translation which is the process of translating from a sequence of tokens to some other form, based on the underlying syntax. He explained the concept of Context Free Grammars. He took an example of a simple expression grammar that generates addition and subtraction expressions. He then gave an example of syntax directed definition which specifies the values of attributes by associating semantic rules with the productions. He further explained Syntax Directed Translation which embeds program fragments (also called semantic actions) within production bodies.
Prof Krishna continued his lecture by giving an overview of Syntax Directed Translation process which includes cconstruction of a parse tree and computation of the values of the attributes at the nodes of the tree by visiting the tree. He then showed how to perform infix to postfix translation. He then explained attribute which is any quantity associated with a programming construct. He categorized attributes as synthesized attributes and inherited attributes. He further explained the dependencies between attributes. He then explained attribute dependency graph and the evaluation strategies. He then stated the ways to avoid cycles in the attribute dependency graph. He concluded his lecture by solving the queries of the participants.
February 17, 2016
Dr V Krishna Nandivada initiated the second day session with a brief recapitulation of the first day session. He then discussed L - attributed grammar. He elaborated on dependency graph which show interdependencies between attributes. He further discussed the procedure to construct a dependency graph which starts with the construction of a node in the dependency graph for each attribute of the grammar symbol at the node and then constructing an edge for the nodes for each semantic rule associated with the productions at the nodes. He then discussed about syntax trees which are an intermediate representation of the compiler’s input. After that he demonstrated the construction of syntax tree. He further explained DAG (Directed Acyclic Graph) representation with the help of an example and then showed the implementation of DAG representation.
Dr Krishna continued his lecture with an explanation on bottom up evaluation of attributed definitions. He discussed top down LL and bottom - up (LR). He then showed how an LL parser handles actions. Then there was a discussion on action - controlled semantic stacks. He stated that a syntax - directed definition is S - Attributed if all attributes are synthesized, can be evaluated in bottom - up fashion and is consistent with (bottom - up) Shift / Reduce parsing. He further took example to show how stack can be used to compute the attributes which involves reducing by a production that has some semantic action. He discussed the various phases that a high level language code goes through before it gets converted into an equivalent machine code. Dr Krishna concluded his lecture by answering the queries of the participants.
February 19, 2016
Dr V Krishna Nandivada initiated the third day session with a brief recapitulation of the first and second day sessions. He then gave a brief description of all the phases of the compiler. He discussed the intermediate representation of the program code. He stated that the intermediate representation breaks the compiler into manageable pieces, simplifies retargeting to new host and simplifies handling of "poly - architecture" problem. He mentioned that the backend converts the intermediate representation into the native code for the target machine. He further stated that the high level language code gets converted into the higher intermediate representation which further gets into mid - level intermediate representation of the code. He then talked about the properties of the intermediate representation including ease of generation and manipulation, level of abstraction, freedom of expression and size of typical procedure. After that there was a discussion on the design issues of intermediate representation including the representation level and appropriateness of the intermediate representation for the passes under consideration.
Dr Krishna continued the lecture with a discussion on the categories of intermediate representation like structural, linear and hybrids. He discussed abstract syntax tree which is the procedure's parse tree with the nodes for most non - terminal symbols removed. He then discussed the different levels of optimization. He discussed the advantages of address codes He discussed different types of address codes like zero address codes, one address codes, two address codes and three address codes. He demonstrated the usage of addressing modes in the intermediate representation with the help of an example. Next, there was a discussion on the implementation of address code. He then talked about the gap between the high level languages and the intermediate representation. He mentioned that the deep nesting of constructs, recursive grammars are the challenges in translation. He then demonstrated generation of intermediate representation for flow-of-control statements and intermediate representation generation for Boolean expressions.
In the end he gave few closing remarks on the intermediate code generation and took the queries of the participants.
The sessions were very benefitting to the students of Computer Science & Engineering and Information Technology. Dr V Krishna Nandivada used the traditional chalk and green board presentation method which totally grasped the attention of all the participants. The study material and the practice question provided in the course packs were highly useful.