Scribd Logo
Upload

Welcome to Scribd!

  • 47 views

    2 3 Marks

    Uploaded by

    ambatipudi praisy prasanna

    Copyright:

    © All Rights Reserved
    Download as PDF or read online from Scribd

    2 3 Marks

    Uploaded by

    ambatipudi praisy prasanna
    47 views24 pages

    Original Title

    2 3 marks

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF or read online from Scribd
    Download as pdf
    47 views24 pages

    2 3 Marks

    Uploaded by

    ambatipudi praisy prasanna

    Copyright:

    © All Rights Reserved
    Download as PDF or read online from Scribd
    Download as pdf
    You are on page 1of 24
    Language Processor Language processor is.a hardware device that translation all FORTRAN and COBOL into machine understandable form. Language Processing System. + re cy ie jo ast Sat ORO, eid pide esses al elu cots Tange MPS RENEE rs This translation can be done by dividing the source file into miodules. These modules are as ra 1. Preprocessor : 2. Compiler pore 3. Assembler 4. _Linker/loader. : Q2. Define compiler and interpreter. Answer: UBnOA T Compiler os : ‘A compiler is a program that converts a source program into a target PrOBTaM, .)} 8 4. : ‘ : Figue sas > Interpreter : ae : ‘An interpreter is also a program that reads the source prograth and executes the program line by line. Source prow ar Data input “| Tnespreter } MP Figure ¥ Q3. Define linker and loader and explain briefly... Answer = Linkers dotiegewhia| sof! Itis a program that links the two object files containing the compiled or assembled code to form a single file which be directly éXeciitable. It is also responsible for performing the following functions, a Linking the objeot program with that ofthe code for standard library functions and 1 2, Resources provided by the'operating system like memory allocators and input and output devices; Loaders : oa Pg It is a program which loads or resolves all the code (Celocatable code) whose principal memory references have unde mined initial locations present anywhere in the memory. It resolves with respect tothe given base or initial address, PF WARNING: xerxsPiopyia of is Beek WCRIINTALSAURH Be dd Wye UABLE Wide LEGAL py ws Seis a eT NIT-1_ Introduction to conan ign ' eae a Qh. Define bootstrapping, answer 1° , f © march-t6(Rt3), 210) Ifa language provides c les certain facilities toGomp (Bootstrapping helps in creation of. wine i a compilers ji) It also helps in making compiters ilers portable. ‘The structure of a compil pier is very com : Ty complicated, A Gompiler is not a hardware piece, rather itis also a program. ‘And to ynte a program we need & languay es guages. For exam it Be, @ pro Toole we popswned nc pepe ES oa otapattles ules in simple languages. For example, @5._ List the phases of compiler. answer # The six phases of compiler are, ; “1. Lexical analyzer 2, . Syntax analyzer , ar : 4. Intermediate code generator : 5, Code optimizer 6, _ Code generator. G6. Differentiate between pass one and pass two of 2 compiler. on ‘Dec 19418), 210) Answer “Multipass Compiler “scans the source code several times. translator is |" ‘Single Pass Compiler Thaingle pass compiler scans the entire source ime of the code for a single pass translator tum a od code is difficult. re to design a single pass,| 4 “Kmaltipass compile Execution ti Execution time of the code for a multipass is less. ° Debugging of the translate Memory requirement is mo! compiler., | -The generated code is less efficient. Going back to the previously.read Soure not allowed 4 it isalso-called'a narrow compiles Pascal and C uses a single pass compiler. ‘ow is input buffering im more. Debugging ofthe translated code is 25¥: Memory requirement is relatively less ‘The generates! code is more efficients 3 Backtracking to previously scanned, source code is ‘allowed... Tris also called a wide compiler: ™ Java requires a multipass compiler. : program is plemented?» 07," What is input buffering? H March-¢7(R43},Q4(0) Answer : ‘ the scanner orMexical'analyzer. The scanning is | wurce program is making the lexical analyzer to cope up with the Input Buffering ‘or scans the 80% The only phase of a compiler that reads oF $¢ 8 i Caried out on charaeter-by-BA’ AS ode which does hot change the set of strings that can be Define top-down parsing and predictive parsing. “Answer, + fica Top-down parsing may be considered.as a method to | build parse tee for an input string in preorder that is starting from the root and then creating the nodeSof a parse tree. It is a method that constructs a leftmost deriyation for an input string. Predictive Parsing resin Predictive parser is a special case of recursive descent \parsing which does not need backtracking. These parsers can function as predictive parser onl; y if the input grammar is free {from left recursion and left factoring SPECTRUM ALL-IN-ONE JOURNAL FOR ENGINEERING STUDENTS i///))) )NHAl Scanned with CamScanner 2.4 7, Test whether the following grammar is LL(1) or | not. S$ AaAb| BbBa “Ate Boe. Answer: E The given grammar is, S— AaAb | BbBa Ade Bpe The above grammar contains two productions S— Aadb | BoBa : Forthis grimimar to bé LL(1), it must satisfy the condition FIRST (4246) 0 FIRST (B6Ba) = (1) ~ “FIRST (Aa46) = FIRST (4) — {e}, U FIRST (248), - 79,00 = {e}-{€} U (a) = {a} rf ‘FIRST (BOBO) = FIRT (6) ~ {€} U FIRST(6Ba) SiGe eben! =Ye}- UB -B) FIRST (4adb) 7 FIRST (BbBa) = {a} {b} = Hence, itis shown that grammar is L(t), Q8. ‘Construct the predicti following grammar, SSIEtSS'|a s' > eSle Eo bears we Answer: The given grammars afer elminaton of lef ecoring (G: S-riEISSi a, Sa eSle ip ag pug a hixcogckanted a The set of terminals is (1, a, 1, B) and set of ‘non, terminals is {5, 5', E} First (terminal) = (terminal) ” “FIRST {) FIRST ()= (4) __ FIRST (a) = {a} a + FIRST (@) = {@ho so FIRST (€) = {©}, fe: WARNING: Xerox/Photocopying of this book's a CRIMINAL act “Anyone found guily js LIABLE to face LEGAL pi i FOLLOW (S) = ]'1. Lexical errors like misspelling of keywords, FIRST (@)= (6) i _ FIRST(S) = (1, f FIRST (S') = {e, €) FIRST (F) = 4b} FOLLOW (8) = (S,¢} (S,e} FOLLOW (E)= (5, €} By using the rules for constricting the predictive |table, we get the following predictive parser table Non, ‘Terminal, terminal [~a_ [be] Q9. Write a short note on error handling. Answer : & ‘The purpose of a compiler is to detect the errors at phases of compilation. Since most programming not specify how a compiler should respond ta errors. Hence! task of errorhandling is left to the compiler. The various that occur at various complication phase are as follows, +o operators in lexical analysis phase. 2.» Syntactic errors like extra or missing braces orn semicolons etc in syntax analysis phase. 3... Semanticrrors like type mismatches between! and operators during semantic analysis phase and 4. Logical errors Sach er a the part of the programmer. The parsing (syntax afalysis) methods oe _alickly because they have the vi Answer: ‘Rates for FIRST Function “The mules for computing FIRST (0, forall symbols X are, 1. 164%s terminal symbol then FIRST (X)= UX) 5 2. * IfXis a nonterminal having.a production rule Xe then FIRST (1) = {e}. Scanned with CamScanner UNIT-2_ Syntax Analysis °F IfX'isanon-terminal having a production leas, X> 4/4,» there is, (@) ain FIRST (A) and ©) € in FIRST ofall 4 A) IEFIRST (4) for all j= 1, 2, toF RST C0. ules for FOLLOW Function The rules for computing FOLLOW (A)’for al teminals A of the grammar are, se 1, For the start symbol’, FOLLOW (5) ={S) where $118 Seat mete me ~~» A, then add a FIRST (19 if for some / FIRST (4)))....., FIRST his then € is added 2,). «1A has a production as A —> aBB, Where FIRST (8) does not contain © then FOLLOW (B) = FIRST (B)~ {¢}. 3, _ If A has a production as A —» GBB, Where FIRST (B) “contain € then FOLLOW (B) ='FIRST (B) = (€) U FOLLOW (A). 4, _ If has a production as A —> oB then FOLLOW (B) = FOLLOW (4). we fed 5," IfAisthe rightmost symbol in some sentential form thea Sis added to FOLLOW (4). G11, Why to use LR parser? Answer Model Paper, a1(d) The following reasons illustrates the importance of LR, pase, 1. ” ER parsers can be constructed for those Ianguages.from. which CFGS can be derived. 2. LR parsing is the general shift-reduce parsing non- backtracking techhique. ia 3. LRparsers are subset of the those grammars which can be parsed by predictive parsers. 4. Error detection in LR parsing is very quick. Q12, What is the use of LR(0) automation? Answer : i The principle use of LR(0) automation is the construction OfSLR passing, The LR(0) automation consists of states and tnasition states represents the set of items from the canonice LR(0) collection where as transition represents the GoTo jon. This helps SLR parsing during shift-educe desisont Consider that an LR(0) automation reaches from jit A tate j due to the string y of the grammar symbols the. shift operation is {) if state j contains a transition on & carried out on next input symbol jon is carried out depending on ‘Otherwise, reduce ope the items of state. _ ibis AL sida 13. ‘List the properties of LR parser. : Answer © tay 48(R19), 2116) “The following are the various properties of LR parsers, =~ () The programming’ languages for which CFG can be ‘written are determined by constructing LR parsers. ‘LR parsers generally operates via non backtracking shift reduce approach. Hence, itis considered to be efficient. gb ‘The class of grammars parsed by the LR parser serves a5 a superset of class of grammars parsed by the predictive parsers, eit astpanserys ia) et Q14. Describe in brief about types of LR parsers. c 2 7 parenet6(R13), 0168) Gi) ‘Answer? ‘The different types of LR parsers are as follows, (Simple LR (SLR) ‘The SLR parser makes use of stack (Initially filled th $and the first state), inputbuffer (Inputstring and string end marker $), parsing table to check the acceptance of a ring! . Gi) Canonical LR(CLR) ‘A Canonical LR parser or CLR parser is an LR parser: | thatuies a look ahead symbol during parsing. The items in CLR parsing are of the form, | * . AS.a a wD Asafa AvoBan 4) Where, Aa is a production, ‘ct! and *B are strings of terminals and.non-terminals, and °c” is a lookahead symbol. CLR items are also, known as LR(1) items. ” “Where ‘1” indicates the number of lookahead symbols. (ti) Look Ahead LR (LALR) ~ ALALR parser table is constructed for a grammar G, ‘by first constructing a CLR parser and then computing the CLR parser table, This means a LALR parse table the compacted form of CLR paise table. Q15. What Is significance of lookahead operator in LR parsing? i Answer + March-17(R13), Qi(d) Lookahead operator is ‘an additional o that i perator that is being read by lex for differentiating extra pattern for token. It is used while deciding the grammar rule for string derivation, This operator improves the parsing efficiency and. backtracking issue, » ad SPECTRUM ALLAI-ONE JOURNAL FOR ENGINEERING STUDENTS a Scanned with CamScanner ‘CLR Parser. SLR parser is easier to implement and | CLR parser is expensive in terms | LALR parser Samay is less expensive than other parsers. | of time and space. time and space. The table obtained by itis smaller, | Ithas the largest size tables. __ | Ithas the same size as that stn parser. ; It uses FOLLOW information for | If ss the lookahead symbols. _ | It uss the lookahead symbols. reductions. vival HOLLOW grammars than SLR grammar, Itlies between SLR and LR} Q17.. What is operator precedence grammar? Give an example. cu. Answer ft © acta. a4 ; 3 en Operator Precedence Grammar Operator presedcnee parsing as jnpeentin ti form of sbi reduce parsing. The grammar f Parsing has the following properties, 1e None ofthe right-hand side of production rules c, tata 2. : png & aot NIE Noné of the righthand side of & production rule have two adjacent nonterminals, i) WOLDS: A grammar satisfying these conditions is called Operator grammar. >on.» 3 Nal Example: Consider the following grammar, EA FAE\(F)|-E\ id" A+ |=[8| Afi) 28 ¥ In the above grammar the production E — EAE have two (sctially) adjacent nonierminals E and 4. Thete grammar is not.an operator grammar, ‘An operator grammar can be obtained by substituting cach alternative for A: EE+ElE-E|E*E|E|E|ETE|(E)|-E| id To identify a handle, the operator precedence parsing defines three disjoint precedence relations. pair of terminals. These felations have the following meanings,| ee rneaine oeie 28) 11> Nestle at r pene 2. The relation a = 6 means a has same precedence as b. | i ae 3. The relation a > b means a has higher precedence than , = pee ca The precedence lation Hep in idtyng the handle ight sete‘ form by delimiting it where, 1.) The relation <:marks the left end of the handle. ee i f 2. The relation = marks the inferior ofthe handle. tsint10 sen ish 5: ris relation > marks the right end of the handle, mine? orl m0 ‘Due to the fact that inthe operator grammar no two nonterminals appear adjacent to each other in wenn Shand si ‘production, the right sentential form will also have no adjacent nonterminals and expressed as, 4 44 2, Ot, Where ¢, isa single nonterminal (or) € and 4, is a single terminal, ‘Suppose theré éxists exactly one relation >, = (or) < between two terminals a, and'a, .Delimit the string define the operator precedence tlatons Tor all terminals as $<: and f > S. Then all the nontcrminats are fe string. Next we'place’between each pair of terminals and between the end most terminals the right relation >, = or Y5, Yyr-na),, depends on, (“The inherited attributes of B. ii)’ The attributes of X,,X, «.» X,., tothe left of X, in the production. 7. How to find evaluation order for SDD's? Answer : May-19(R10),2100 The evaluation order for. attribute instance in a given Ise tree can be determined with the help of a special type of taph called dependency graph. Dependency graph for each node of parse tree can March-47(R13), 46) be created only if one attribute say ‘x’ dependents on one or : More attributes say y, Vrs), then the semantic rule for x" is faluated after the semantic rules for y,,J,y~s), af€ evaluated, To construct a dependency graph a prerequisite is to fonvert each semantic rule into the form, i £0 p Yd) " ‘ Where, /f”is a procedure for the semantie rule, € @9. Translate the executable ‘Answer ¢ 0. 1 location is assigned eee are cor abe, ne quadrplerscore, We | It is difficult to use a triple structure in an compiler. Since, changing a Value requires to change Indirect triples structure is similar to quadruple which requires changes in the ordering of the statement list. _ Quadruples and indirect triples requires the same amount ‘of space. , See Intriples, the temporaries that nted storage “until the code generation phase. ®: ‘The space required by indirect triples canbe reduced by dng the same temporary value more than once, ~ tater nts of the following ‘C’ program into a three-address code by assuming each element of an array ‘a’ takes Abytes. : e void main() hse ie Int} = 1, a[10}; \ £ 3 ‘while(i + +<= 10) aff] = 0; na } : are defered od basin 5 A EY ‘The sizeof an clement in array “ais 4 bytes, afi] = addr (a) + 44 5 a {10] isi if <= 10 Goto(S) Goto(8) temp, :=25 + 491, ql 4 [temp,) = 0 i Goto (2). Be re Stop. Scanned with CamScanner threo address statements. atti i jokeign sito i M0. Convert the expression a=b*—c+b*~c into Answer t c spore t-9 7-4 Given expression, a=b* The the adres stemens fo te above esoression bc ea | Brg 12) eatin oh ope i adicce bt Labty sats ote Perea neve eps wares Basen ttt Poae guy ’ | Gif. Discuss briefly on static-single assignment form. Answer : : i L ta , a Stati-single abvigamnent fort's abbreviaied as SSA Torm or simply SSA. It refers to an intermediate representa that allots to apply cad Optimization techniques wi8d only. | |< (1,705. ret HOM tee address code in two distinct ways which are as follows, td ‘ In SSA, every assignment is made to different variable name (i.c., Unique variable), Thus, the name given as static sin assignment. The following figure,llustates differentiation of SSA and thres-address code with intermediate,program. nudiiieed hint samheltyttog el ter. tf) cpt 7 Static single-assignment form is different ‘ sake . ts Ha | : ‘ha naif te rer a8 (1) Throe address code ingle-assignment form cobudati! Figure: Three Address Code and SSA with Inter Code Ifthe control flow passes through ‘if statement, then 6(,. i) returns the Valle‘, n the other hand, ifcontrol-flow, through ‘else’ statement then 6(j,i,) returns Value “i,” ie; the function returns the argument value corresponding to the path of casey the control flow. lL Q12. What are the various types of intermediate Code representation? | se 5 a pk i area Answet + May-18(R18), a) “The intermediate cole generator performs a conversion of syntax tre intd a code that i notin target code form. This GO is called is into an intermediate code. The intermediate code should be easily transferable to target code within a less time! intermediate code generator. " é t The intermediate code can be of three forms, f le ‘ene 1 Postfix . | “ Yolise deed 2. Triples Si i siyroqoh f to Sao 3. Quadruples, © * ‘ie | * di The intermediate code should have the folloying basic properties. Each instruction can have only one operator in addition to the assignment operator, ‘Compiler should generate temporary locations to store the value evaluated in each instruction io The code (3 address code) may have less than 3 operands in an instruction: WARNING: Xerox/PRtocopying of tle bok Is a CRIMINAL dc. Anyone found guilty is LIABLE to face LEGAL proveeding B Scanned with CamScanner ‘Scanned with CamScanner Fora:=b (iis, Q16. Define type equivalence. Answer t wc cea nee ae 1, Name equivalence 2.__ Structural equivalence. Q17. What is type Expression? Answer: : & oe ae ites Abele) Apes ae ‘A basic type lke int, char, float, double, boolean, void et, applied to programming language. ‘Atype name like “typedef int tp” assigned toa language. in the above statement (“typedef int *p), pis type expression. _-An array (of type all, T]) type constructor (of type a ETD ale integer datatype] anditstype(T] ‘ Q18. What is coercion? . Answer: : z Fe es oe cats a tack daciane Te cepienie ore ate type.or reject certain mixed type operations. An automatic type conversion is called coercion. “Conse an arithnetc expression FF + F that involves two rypes-eal and integers. The compiler converts into real whenever needed. ‘ G19. Write short note on semiantic analysis phase and static checking. Answer : ey ‘Semantic Analysis Phase : : ; Semi alas pus apa fer ebocking wir the paved tule es a me parser checks for syntactic errors, semantic analyzer checks for semantic erors, It does type checking for expresso statements. Static Checking The following-are some important points about static checking, A programming langnn ss sta cheting when wants pe checking 1 done compe tine Siatie checking is also called as “Early Binding” ' During static checking programmatic errors are caught eatly. This eauses program execution to be efficient Usage of at checking makes programs orale for xeon, This saementnens, at exec tint is hardly left with th basi ers, s the executor can fely exes the program, oh Oa WARNING: Xerox/Photocopying of this book is a CRIMINAL ct, Anyone fon uy 's LIABLE to face LEGAL pro i ratogy are 0s fol nowih at compile tn yf recursive prt calls because logal variables are bop ame atora of data structure dynamically af there'Is'no storage allocation at run location of storage to the program ol n an the Iangunye implementing state allocation, Singe the numb tion record or frame is conti 2 of orag that contains ale information i tivation record consists of seven fled as shown in the flgu [E-Retumed van i L [ seal dat | inporary vaes | | igure: An Activation Rocor tack allcention strat ‘Scanned with CamScanner UNIT-4 Run-Time Environments and Code Generation Q5. What are the advant allocation? ‘ages of heap storage ‘Answer ? = Dec.7(R15), (6) advantages of ‘allocation tages of heap storage allocation are as follows, 1.” Heap strategy can allocate and deallocate storage for data based on the requirement of the activation records. PE. Allocation and deallocation is, eis is fast for small amounis of « The time taken for large amounts of Storage is negligible ‘when compared with the time hen compare wih heim akento perform computations Je ean retain the values of al names when an activation Q6. _ Whatare the sub problems in register allocation, strategies? Answer Dee-19(R18), 10) “The main subproblems in register allocation strategy are, 1, Aliasing ‘The process of assigning a value of one register which affects the value of other register is called aliasing. For example, iffan architecture consists of 32 bit general purpose registers, then they can also be used as & bit and 16 bit registers. Thus, assigning 32 bit value to eax register will effect the al register value. 2. Pre-coloring ‘This subproblem makes few variables to be assigned for particular registers. 3. NP-Problem ris subproblem reduce the graph coloring problem 10 register allocation problem by an arbitrary graph. A program ean be developed in such a way that register allocation for program would color the original graph. Since, register allocation is in NPand graph coloring isa NP hard problem tis proves the NP completeness. 7, Write a short note'on Code Generation and fist the generic Issues in the design of code generator. Answer = Model Paper, Q1(9) Code Generation olde Generation phase is the lagt phase of compiler. 1 is an important phase of the compilation pecause, in this phase the compiler convert the intermediate ‘co(le into machine or the allocation of memory to variable assembly code, Moreover, Fa source probrar is also dong bY fuga Ibe code BAT assigns register to variable in the program ‘Design Issues of Code Generator . © Input Sears ‘ Gi) — Output “= Sreeoliemcate Lema Gi) Memory management (iv) _ Selection of machine instruction (9) Allocating resister (vi) Evaluation order } G Code generatic (vit) _Code generation, QB, Generate a machine code for the following statement a=b+¢7 15. ‘Answer : Given statement is anbeeris ‘The machine code for following statement i, MOVF id, Reg, < MULE #15.0 Reg, MULF | id,, © Reg, m Add Reg, Reg, MOVF Reg, id QS. Mention the properties that,a code generator should possess. i Answer # May.18(R19), 10 “The various properties of code generation phase are as follows, é 1. Correctness: The output of code must ensure correctness 2, Quality: The code generation phase must produce an high quality code. 3, __ Efficient Use of Resources: The code generator phase ‘make use of target machine resources efficiently. Immediate code Generation: The code generation ‘phase must produce a object code quick! Q10. Show various steps in the code generation algorithm of the expression (a + b)i(c + d), Assuming two machine registers to be available. ‘Answer : Leta variable ¢ hold the value of expression (a + b)/ (# dic, e=(at bea) 4 “The three-address code forabove expression is given as, ‘The variable ‘eis live till the end, SPECTRUM ALLIN-ONE JOURNAL FOR ENGINEERING STUDENTS ||) Scanned with CamScanner 7 : COMPILER DESIGN [JNTU-HYD! 44. Let the two available registers are R, and ,, then the code generation algorithm produces the following code au Three-address_| Generated Code | Content of Register Descriptor | Content of a oe | Area segs -_ iter MOV a, , R holds f | ADD}, R, MOV c, R, 4 R, holds 1, ie ADD 4, , DIVR:R, - R, holds e| ais ine ‘| 2 Mov Re “eisinR,and memory | It isassumed that inialy the registers and ade empty and the temporary Variables ¢ and , ae not in memory they are explicitly stored with a MOV instruction, a re clo GETREG function seus the available ester to store the valu of The istuction MOV a, loadsa ito R, since initially a isnot in R, the statement ADD b, R adds Band content of R A(t this the contents deseriptor are updated to indicate that R, contsns fy, The next call 6 GETREG function stata the oni R,, Sine te va isnot in register itis loaded by gencrating the instruction MOV eR. ‘ Code generation process precede till the last statement e= ft, Afler this Statement, the instruction MOY Ree is generat to store the live variable ‘e” in the memory location because itis lve till the end of the block * Qi. Define basic block. Answer + + cL basic block is bufich of three-address statements, suct thatthe flow of control if once enters a block of stat flow continuously without stopping or pausing and ends at the end of the block. coy al Every statement in a basic block is a three-address statement. : In an assignment statement, _ a:=b%e : ais defined by using’} and c. r x % Thus, we can say that the above statement defines ‘a’ and uses ‘b' and ‘c’, 4 » Q12. List the terminologies used in basic blocks. ' \ Answer : 215), a1 The terminologies used in basic blocks are as follows, 1. "Define and Use . Every statement n'a basic block isa three-addvess statement, oo Consider the following assignment statement, : > ¥ aroha az=b*e x Here, ‘a’ is defined by using ‘b’ and ‘c’, ‘ ‘Thus, it can be said that the above statement defines ‘a’ and uses ‘b’ and °c’. _ Live A symbol ora variable ora name is known as a live symbol or name if'its value is used in future or from that point. Dead ; A symbol or name is known as a dead symbol, ifits value is not going to be used in therest of the program, = WARNING: Xerox/Photocopying of this book is a CRIMINAL act. Anyone found guilty is| LIABLE to face LEGAL proceedings, UNIT-4 Run- Q13. How can you identify the leader in a basic block? Answer # March-16(R13), (4) A single statement isa basic block. However, find out the first statement that is going to be the leader i Sane eae () — The first statement isa leader statement. (i) Mastatementisthe targetofia cont jf conditional or uncodition jump, then te sutemen isa lederstemeat (ii) Every immediate statement after a jump (conditional or unconditional isa leader statement. G14, What is a flow graph? OR Write in brief about flow graphs. May-16(R15), a3(h) Answer 3 © dec.17/R15), 21(n) ‘A flow graph is a graphical representation of three- address statements, It is used to show the flow of control information to the set of basic blocks of a program. It onsists of nodes and edges, A node of a flow graph is a basic block that performs some computations, An initial node consists of a block whose leader is the first statement. There isa directed dae from one node to another representing the flow of control petween blocks. There is an edge from block BI to block B2. Inthe execution sequence B2 immediately follow BI. The last statement of BI contains a conditional or unconditional jump to the leader (frst statement) of B2 It is said that'a predecessor of block B2 is block BI and a successor of BI is B2, * G15. What Is the role of flow graph optimizing a compiler? Dee. Answer = (R16), O40) Flow graphs are used to indicate the flow of control from one point to another point. The flow graph provides loop. optimization for a compiler. These are the optimizations that cre carried out within a single basic block and do not require the information regarding the data and flow of control 16, What is algebraic transformation? * pes -17(R15), 10) Answer : “The transformations that can be applied for optimizing asic blocks are called as algebraic transformation. One ofthe important class of optimizations is algebrale entities. Fos example we can apply the following arithmetic identities ajl=a ati=ita a-0=a ato=0+ a+0or igorithms often produce inated easily’ through To statements such as Intermediate code generation al such statements which can be el Peephole optimization. - « specrRUM @LL-N-ONE JOURNAL FOR ENGINEERING STUDENTS | © program? ec-A71R15), 2100) Q17. What are the forms of a targ ‘Answer # ‘The various forms of a target program are, ‘Absolute Machine Code * ‘An absolute machine language program places the £&. crated code in memory at some fixed location and exeevieS program immediately. eed (b)___Relocatable Machine Code oe as relocatable-machine language ‘of subprograms separately. It also 7 jbject mod () Producing an output program allows compilation llows calling already compiled programs from an tle in other languages. (©). Assembly language code ‘An assembly language program makes the code Benera= tion process easier. Assembly language code is mainly used it nachines having less memory where complierfequires Several ‘asses to execute them, Q18. What is a DAG? Mention its applications. May-1(Rt5), 10) OR cts ae Give the application of DAG. —_bec-19(R16), 210) Answer # DAG Directed Acyclic Graph, also called as DAG, is a directed graph with no cycles. ADAG is a data structure used to implement transformations of basic blocks. It shows how = subsequent statements of the block use the valies computed by each statement in a block. Applications of DAG 1, = We can detect the'commn subexpressions (expressions ” that are computed more than once) within a black. 2, Wecan determine names evaluated outside the block but are used inside the block. 4 3, We can determine statements whose value is computed | inside the block but ean used outside the block. psi si tie DS DUS een Q19, What are the legal evaluation orders and names for the values at the nodes for the DAG for following? atb Answer : 0 ae The DAG for the basic block d= b + ¢; Fova:ee-dis,- { Scanned with CamScanner partes an Figae sug ata i ~The Evaluation onder depend on the associativity and precedence of operators in aigiven language: ‘This, based on assumption associativity and precedence the evaluation ordér should baie ; Compute b * cand store in B as **has the’ highest precedence among *, + ~ ae Compute a + b and store in‘e ag" le associative, Compute 4 4eand store in d. a Compute ¢ =< and storé the result ina, ets Fut, the computation of 6 * cenn’t be done first as the original value of b is used in the com ‘Thorefore, the order should be (2), (3). (4), (1). me) G20, How to allocate registers to Instruction? we grees Answer t ; Register Allocation ° nr hae “The decision about what variables will reside ina register at which point in the program is done during register chile sth * Register allocation ean be done with the help of following, Reserve Registers’ 2" , is ‘This approach reserve certain registers to hold specific values in an object program. For example, a gro holding base addresses, another register holding results of arithmetic expressions a fixed register holding time stnck and so on, a i reomi (b) Allocate Registers Globally ‘ " mieten This approach keep frequently used variables of each inher loop in some fixed registers throughout a loop and registers aecossible globally. Registers that are not allocated can be used to hold local values ofa block, Usage Count of Varlable i 5d Sox wena By allocating a register to a yariable x for the duration of loop Z we save one unit of cost far each reference known that when the variable is assigned a value in the block and its live til the end of the block, then it register. With this fact two units of cost can be saved for each block of loop Z in which x is assigned a atthe end of the block: ’ t 2 Q2i, What is meant by register descriptor and address descriptor? (a) © Answer ¢ } _ Register Descriptor : A register descriptor keeps the information about each register. It associates With each registe i 3 ister a | ales are eld a tater nly al reyer ina regi descriptor ae empy As tbe Fett block progresses, each register holds a value of zero ot more variables &t any instant of time, The information stored: a The ink i riptor is needed whenever there i8 a need of & new register: Riny Hn it aie cal Address Descriptor An address descriptor also know! ‘able dé information about locati ities be ca te og coors a ita ae blestes ue lon aaa into register and its value his not changed. This information can be stored in 22. What is meant by register allocation and assignment? : ‘Answer + Register Allocation * The de Register Assignment 5 ‘The decision about which specific register will hold a variablé should be taken during register assignment WARNING: xerox/Photocopying ofthis Book it a CRIMINAL’ act! ‘Anyone found Quill is LIABLE fo face LEGAL Scanned with CamScanner " (PARETIA) sHonT uesTIONs WITH SOLUTIONS ai, Wilt is machine independent code optimization?:5.° ” #2 ( Grade = cot tid , RAR nde optimization is independent of target machine, Bit depends on the sour ee ‘This optimization technique uses appropriate program structure in order to improve’ independeHt Code optimization techniques are, (a) Local optimization | (b) Global optimization. @2._ Discuss briefly about, ; : <1 -() Local optimizations ~ (ii) Global optimizations. Answer #7 © 2 (Local Optimizations Local optimizations are caried out within a single basic block. This te ‘the'data and flow of control. Thus, implementation of this technique is simple. ~ (ii) Global Optimizations eh : “wei Global optimizations are carried ut across basic blocks, instead of single basic block. This analysis is also knoy data-flow analysis. In ths technique, additional analysis is requitéd across basi blocks. Thus, implementation of this is complex. —— Q3.__ Distinguish between machine dependent and machine independent optimization, schnique do not require the information Answer : Machine Dependent Optimization 1, ]Itis dependent on the instruction set and addressing | 1 modes to be used. 2. | The efficiency of the program is improved by allocating | 2. | The efficiency of the target code i improved by! appropriate program structure. sufficient number of resources, 3, | Intermixed instructions with data increases the speed | 3. | Elimination of dead code increases the execution, i 1s are used wherever necessary. | 4. | Identical computations are moved to one place, t ofexecution. , 4, | Intermediate instru Q4. - What is common sub-expression elimination? Explain. Answer = ‘The code can be improved by eliminating common subexpressions ftom the code, An expression whose value Was| ‘computediand thé values of variables in the expression are not changed, since its computation éan be avoided to recom using the,eaclier computed Yall <9.) Joon. i ‘ Example, owtiatis $10! “ite simin 1 : i Consider the.following sequence, of code, bre an pede 4 Nie iufbhiow ef satel Wa8ea ne 0 nto vedmun ert Orisibs ok aCSK aN Inthe above code the assignment to z have the common subexpression b* c, Since its value is not changed after it was cofipiited)/and its use in the expression 2, We caf avoid Fecomputing it by replacing the above code as follows: a bas citeisimitadrpet ane > ni» poten zrt,+d-c° as ; wl ‘Anya found gully is LIABLE to face LEGAL proceedings © WARNING: xerouhctscopig of ie book! CRIMINAL act Scanned with CamScanner for identifying the common sub expression In an expres ae Soy gree Marehet (R13), 10) Adon grok sued racine , : sare tere 864 fr ieniyng the common subexpression nan expression, Iisa graphical representation of GE Itconsists of nodes and edges, consists of a block whose leader is the control between blocks. There is an ed 6, , What is dead code elimination and reduction in strength? > Answer: oe namin Sb Mare 470819), Dead Code Elimination : ae Apiece of code which snot reachable thatthe values it computes is never used anywherein he roe aa ar to be a dead code and can bé removed from the program safely. An. eee to ayariable results in dead code, iftheval a this variable is not used in the subsequent program. Also.an.aSsignment to a variable is a dead code if there is always anolls assignment tothe same variable before its valuc is used in the subsequent program. Reduction in Strength 4.920) soot chine. Strength reduction isthe process of replacing expensive operations by equivalent cheaper operations on the farBet (On many machines a multiplication operation takes more time than addition or subtraction. On such machines the peed of he object code can be increased by replacing a multiplication by a subtraction. This is called reduction in strength 17 G7. Briefly explain live variable analysis, youth Answer ‘variable (say a) is said to be alive at point p if, ()_Itscurrent value is used in the flow graph beginning atthe point p. © (ji) There exist a path (say p) from start point p to end point (E) otherwise: said to beinidéad states y Example tM? AAR Consider the following figure, : y a ab initial node ‘Anode ofa flow graph isa basic block that performs sofne-compitations. An initial frst statement There is directed edge fom one node to anotier representing the low Of, ize from block BI to block B2, er erode 4 vetin at 3 ae nine oars aoiiegaqort awning’? By : . ave] [a By fo eosnigageagguenel m.tdorn ol ote barca Rial ome ieare again ae 43 vote Figure: Flow Graph e/g a0 od robe Itean be noticed from above figure, that a variable as live fom block , to Block B, and Block B, ands killediat block B,- + Q8. Whatis @'semilattice? ee ane, Answer : i ‘A semilatice can be defined as algebraic structure (S, A) with set of values ‘Sand a ‘meet operator ‘0° Such that for all elements of, and in 'S Itholds the following Properties, | sys Foo tle a () + Idempotent : x Ax => t i) Commutative :xAy=¥A% ae (ii) “Associative 2x 002) AYAZ 00» ‘ ‘Asimilatiicecomains top element TV xeS,z AT =x anda bottom element “LV xe, |, x : SPECTRUM ALLIN-ONE JOURNAL FOR ENGINEERING STUDENTS ids Maas an =e ee Scanned with CamScanner 54 G9. What are the properties of transfer functions In a data flow framework? Answer In a data flow framework, the set of transfer functions F:§ +5 includes the following properties, (@ Frinchudes identity function I such that V xe, 1(3) =x. wo Fis closed under composition of functions. In other words, ¥ fg € F there exists function h defined by Hs) ~ (fe) in F. Q10. Write: ort note on monotone framewor Answer? . ~ Adata-flow framework (D, S, is said to be monotone if the result generated from the first member is less than the | second member after ipplying transfer'function to any two | ‘members of set S. | In other words, data-flow framework is said to’ be monotone xy=9fls) @ ‘Therefore, unrolling the loop once i.¢., replicating the body once saves 50% of the total possible executions. Unrolling can be done as many number of times." 9" WARNING; Xerox/Photocopying of this Book ls @ CRIMINAL’act Anyone found guity is LIABLE to face LEGAL proceedings. Ee Scanned with CamScanner

    You might also like