Compiler- Lab 10: Intermediate representation(s) Solved

generating Intermediate representation(s)

Q1 [AST]. There are various intermediate representations such as Abstract-Syntax-Tree (AST), Directed-acyclic-graph (DAG), and 3-address code. Consider your expression grammar from assignment 9 with operations such as addition, subtraction, multiplication and division.

Using semantic actions, design S-attributed/L-attributed translation grammar to generate AST. Explain all the semantic actions that you considered. Submit a document with brief explanations.
Implement your solution (NOTE: We had discussed about combining evaluation of semantic actions with top-down/bottom-up parsing). Your program should take an expression as input and generate its corresponding AST as output (you may decide about how you present/ store the output).
Q2 [3-address code]. There are various intermediate representations such as Abstract-Syntax-Tree (AST), Directed-acyclic-graph (DAG), and 3-address code. Consider your expression grammar from assignment 9 with operations such as addition, subtraction, multiplication and division.

Using semantic actions, design S-attributed/L-attributed translation grammar to generate -3-address code. Explain all the semantic actions that you considered. Submit a document with brief explanations.
Implement your solution (NOTE: We had discussed about combining evaluation of semantic actions with top-down/bottom-up parsing). Your program should take an expression as input and generate its corresponding 3-address code as output.
Q3 [DAG- OPTIONAL]. Semantic actions for generating DAG for the above problem. The output should be DAG of the input expression in a readable form.  

Q4 [OPTIONAL]. GCC intermediate codes:

You may explore the internals, and understand the intermediate representations used by gcc. 

Produce internal representations for some simple programs (program with few simple basic statements, program with 1 for loop etc), observe some of the intermediate representations generated by gcc for the considered programs.  

The GCC compiler uses three intermediate representations:

GENERIC: language independent tree representation of the entire function
GIMPLE: three-address representation generated from GENERIC
RTL: low-level representation known as register transfer language
gcc produces the textual forms of the following intermediate representations of a program being compiled:

Abstract Syntax Tree (AST). The -fdump-tree-original-raw switch dumps the textual representation of the AST for given input source.
Gnu SIMPLE representation (GIMPLE). The -fdump-tree-gimple-raw switch dumps the GIMPLE representation of the input source (more readable form without -raw).
Control Flow Graph (CFG). The -fdump-tree-cfg-raw switch dumps the CFG form of the GIMPLE code.
Register Transfer Language (RTL IR). The -da switch dumps the RTL IR of the input source program with the pass number as a part of the dump file name.