MotivationAlias AnalysisGetting StartedThe AssignmentSyntax and Semantics for InputExtraHints for doing the assignmentYour ReportWhat to turn inDue dateCS 553 Compiler Construction — Fall 2005 Programming Assignment #1Scanners and Parsers for OpenAnalysis Test Input Due September 9, 2005In this assignment you will review or learn how to build scanners and parsers using the toolsflex and bison by building scanners and parsers for OpenAnalysis test input. You should work ingroups of size two.1 MotivationOpenAnalysis is a program analysis toolkit that is part of an ongoing research project to determinehow to separate program analysis from the specifics of the intermediate representations used bydifferent compiler infrastructures. The main idea is that abstract analysis-specific IR interfacesare designed so that many different analysis algorithms can use the interface. To use the analysisalgorithms within a specific compiler infrastructure the IR interfaces must be implemented forthat infrastructure. Currently we can only test an analysis implemented within OpenAnalysisby using an IR Interface that has been implemented for a specific compiler infrastructure. Thisis cumbersome because often compiler infrastructures are significant pieces of software that havelimited portability and whose IR Interface implementation might itself be buggy.The goal of this assignment will be to build scanners and parsers for test input to the aliasIR interface. Alias analysis is arguably the most important analysis because many other analysesdepend on it. The test input only has information required by alias analysis and does not dependon any existing compiler infrastructure.2 Alias AnalysisAlias and pointer analysis determines what program state each memory reference might access. Inthe C code shown below, the memory reference *p could access the location for variable x or thelocation for variable y. To perform conservatively correct pointer analysis, the alias analysis mustindicate that *p could reference either (unless gFlag happens to be a constant at compile time).int gFlag;int main(){int x, y, *p;if (gFlag) {p = &x;} else {p = &y;}*p = 4;}1Alias analysis is very difficult to solve. There are a number of heuristics that have been developedthat provide a broad spectrum of the tradeoff between accuracy and efficiency. In OpenAnalysiswe believe we have developed an IR interface for alias analysis that can support all of the heuristicsthat do not use type information. The alias IR interface requires only a subset of the informationthat might be available within any IR. It needs to know what memory references are within eachstatement, a lo c ation description for each variable, and also if there are any pointer assignmentswithin a statement (eg. p= &x).For this assignment you will be implementing scanners and parsers that translate test data forthe alias analysis in OpenAnalysis into the data structures required by the alias IR interface. Hereis an example input file:// int main() {PROCEDURE = { < ProcHandle("main"), SymHandle("main") > }// int x;LOCATION = { < SymHandle("x"), local > }// int *p;LOCATION = { < SymHandle("p"), local > }// all other symbols visible to this procedureLOCATION = { < SymHandle("g"), not local > }// x = g;MEMREFEXPRS = { StmtHandle("x = g;") =>[MemRefHandle("x_1") => NamedRef ( DEF, SymHandle("x") )MemRefHandle("g_1") => NamedRef ( USE, SymHandle("g") )] }// p = &x;MEMREFEXPRS = { StmtHandle("p = &x;") =>[MemRefHandle("p_1") => NamedRef( DEF, SymHandle("p") )MemRefHandle("&x_1") =>NamedRef( USE, SymHandle("x"), addressOf = T, accuracy = full )] }PTRASSIGNPAIRS = { StmtHandle("p = &x;") =>[< MemRefHandle("p_1"), MemRefHandle("&x_1") >] }The com mented out statements are the C program statements that the input describes. Eachtype of information will have its own scanner and parser, because each analysis IR interface will use2some set of the available information types and the goal is to keep things as modular as possible.In other words, there will be a scanner and parser to parse the PROCEDURE information, LOCATIONinformation MEMREFEXPRS information and PTRASSIGNPAIRS information. The strings that you willbe parsing lie within the curly braces. This is my second (and not last) round of designing these testinput files. I would be happy to hear any ideas you might have for improving the overall softwaredesign and input syntax for the testing framework.We will be covering alias analysis in more detail later in the course. For now the description Ihave provided here is should provide you sufficient background to do the assignment.A more detailed description of OpenAnalysis is the paper ”Re presentation-Independent Pro-gram Analysis” which can be found at http://www.mcs.anl.gov/∼mstrout/papers.html.3 Getting Started1. Install a copy of OpenAnalysis, which is available via a CVS repository at Rice.(a) Follow the directions at http://www.hipersoft.rice.edu/cvs/index.html#anonymousto get anonymous access to the CVS repository at Rice.(b) Checkout the FIAlias branch of OpenAnalysis// from your class account (or normal CS account)% cvs co -r FIAlias OpenAnalysis(c) Build OpenAnalysis% cd OpenAnalysis% setenv CXXFLAGS ’-g -O0’% make -f Makefile.quick configure% make -f Makefile.quick install2. Get a copy of the initial project1 files% cp ~cs553/project1/Project1.tar .% tar xf Project1.tar3. Build project1(a) Edit the Makefile to indicate the location of the OpenAnalysis directory. The platformis probably i686-Linux. Do an ls in the OpenAnalysis directory after building OA tocheck.(b) Build it, you have to do make twice because of some bug in the make file. If you knowthe fix, please share it with me.% make% makeBuilding the project will result in two executables. The testSubIR executable tes ts the cre-ation of the subsidiary IR that is then used by TestAliasIRInterface to implement the alias IRinterface. The driver executable takes an input file on the command line. The input file needs to3be parsed to generate the same kinds of datastructures that are being created in testSubIR. Theinput file Input/testSubIR.oa corresponds to calls made in testSubIR. The driver executablecalls the top parser function which in turn should call the appropriate sub parser for each stringwithin a curly brace. The sub parser for PROCEDURE = {...} has already been implemented as anexample. Your goal is to make calls to the SubsidiaryIR interface based on parsing input files.4 The AssignmentYou