May-2014 Principles of Compiler Design Semester - VI (CSE) Time : Three Hours] [Maximum : 100 Marks Answer ALL Questions PART A - (10 x 2 = 20 Marks) State any two reasons as to why phases of compiler should be grouped. __ (Refer Two Marks Q.15 of Chapter - 1) Why is buffering used in lexical analysis ? What are the commonly used buffering methods ? (Refer Two Marks Q.17 of Chapter - 2)\ Define lexeme. (Refer Two Marks Q.18 of Chapter - 2) ‘Compare the feature of DFA and NFA. (Refer Two Marks Q.19 of Chapter - 2) What és the significance of intermediate code ? (Refer Two Marks Q.13 of Chapter - 6) Write the various three address code form of intermediate code ? (Refer Two Marks Q.14 of Chapter - 6) m0) D table. (Refer Two Marks Q.7 of Chapter - 5) techniques in loop optimization. 0 Marks Q.26 of Chapter - 8) | mean by cross-compiler ? (Refer Two Marks Q.11 of Chapter - 1) ‘you represent the dummy blocks with no statements indicated in global lysis ? (Refer Two Marks Q.27 of Chapter - 8) _ PART B - (5 x 16 = 80 Marks) terms : compiler, interpreter, translator ‘and differentiate 2 ke [6] token and patter. (Refer section 22.1) {61 ln? eter sstion 23) @ @ etaConsider the following grammar 5 AS |b SA | @ i ’ Bin the SLR parse table for the grammar. Show the actions of the parser for the input string “abab". (Refer example 3.9.9 and 3.9.10) {16 OR ib) i) What isan ambiguous grammar ? Is the following grammar ambiguous ? Prove E>E+E|E*E | CE) | id. The grammar should be moved to the next Hine, centered. (Refer section 3.5) [8] i) Draw NFA for the regular expression ab*/ab. (Refer example 2.1316) [6] 43 a) How would you convert the following into intermediate code ? Give a suitable example. i) Assignment statements (Refer section 6.6) {8} ii) Case statements (Refer section 6.9) [3] OR b) i) Write notes on backpatching. (Refer section 6.11) [3] ii) Explain the sequence of stack allocation processes for a function call. (Refer section 5.4.2) Is] 14 a) Discuss the various issues in code generation with examples. (Refer section 7.4) tél OR Define a directed acyclic graph. Construct a DAG and write the sequence of instructions for the expression a + a * (b~c) + (b-c) *d. (Refer section 7.11.8) le) Discuss in detail the process of optimization of basic blocks. Give an example. "(Refer section 8.5) v Sa 1 fe) OR at is data flow analysis ? Explain data flow abstraction with examples. r section 8,8) tel Q00 L PUBLICATIONS” An up thrust for knowledgeyo suonson) SHEN OAL, wloI} 9'D JO JOMSUE (9 saideyp Jo suonsand) HEN OAL sappy ¢98enSuey aimpouuzyiy Susjuaszides fo. shom (c- saideyp 30 suey om mors <1 Jo rMsue royoy) “souiaxa] pun swayed ‘suRjo} 2ueC suonson ‘Ty Jomsuy ‘EW OT # ume]Explain with exampre, uveres one patching with an example. (Refer section 6.11) ia ii) Explain about back OR 4B) B Write down the translation scheme to generate three address code for the assignment statement. (Refer section 6.6) i ig Hows wouta you generate intermediate code for the flow of control statements? (Refer section 6.11.2) oN @.14 a) i) Discuss briefly about simple code generation algorithm. (Refer section 7) {s] G) For the fom graph: shown teow, crite the three address statements a ct the DAG. ‘December-2012 sign Principles of Compiler De: Semester - VI (CSE) +: Three hours] [Maximum : 100 Marks nan ‘Answer ALL questions PART A - (10x 2 = 20 Marks) Qt Wiite the regular expressions for identifier and number (R from Two Marks Questions of Chapter - 2) 2 tree, (Refer answer of 0.16 fro fefer answer of Q.14 Compare syntax tree and pars m Two Marks Questions of Chapter - 3) a Write the rue to eliminate lft recursion im. STamnlr (Refer answer of Q.17 from Two Marks Questions of Chapter - 3) Mention the role of semantic analysis. (Refer answer © Questions of Chapter - 4) y £ Q.4 from Two Marks =p" —c+b*-c. (Refer example 62.2) Draw syntax tree for the expression Q.6 from Two Marks Questions of Define backpatching. (Refer answer of Chapter - 6) List the advantage of DAG. (Refer answer Questions of Chapter - 7) What are the uses of register and address descriptors in code generation ? (Refer answer of 0.17 from Two Marks Questions of Chapter - 7) Define live variable. (Refer answer of Q.22 from T i eo Q.22 from Two Marks Questions of What is data flow analysis? (Refer answer of % f Q.18 fro ks ‘Questions of Chapter - 8) i aN PART B - (5 x 16 = 80 Marks) in detail about the phases of comy ipiler and translate tl = init + rate'60, (Refer section 1,4) OS a el OR NFA and DFA. Construct a DFA di (efnb'). (Refer example Pye on peers a of Q.16 from Two MarksCea. saa. ‘of Compiler Design S-13 Solved Paper December-2012 2 2) Construct non recursive predictive parsing table for the following grammar, ~ ESE or E\E and E\not E| (E)|0|1. (Refer example 3.7.11) 6] OR b) Construct SLR parsing table for the grammar lel ESEsT|T T+ TF|F F>F*|a|b (Refer example 3.9.5) j) Translate the following switch statement into intermediate code. [8] Switch E begin case V1 : S1 case V2 : S2 case Vn-1 : Sn-1 default : Sn end (Refer section 6.9) 1) Generate three address code for the boolean expression a What are the types of three address statements ? (Refer Two Marks Q.3 of Chapter - 6)process. W: the construction of lexical analyzer. | jokens: In this chapter: we owas \ fe will also discuss the method of identifying tokens trom svuree:progran Pally we will lea a tool, LEX which automates ) EE] Role of Lexical Analyzer Explain in detail the role Gidea onayser ith possible error recat actions oa ) > Dae the role of lesa! onober in dea _ ia Lexical analyzer is the first phase of compiler. The lexical analyzer reads the input source program from left to right one character at a time and generates the sequence of Ly tokens. Each token is a single Jogical cohesive unit such as identifier, keywords, to determine the syntax of the source operators and punctuation marks, Then the parser ole of levical analyzer in the’ process of compuaton\/ $4240] Jo uoneowloeds EFA /+ Paureos 0} sey indur Sururewior [HS «/ “+g este I! ages eqeuruue3, 43 aestring over Y= (al. has to built for the language L = {a, aa, aaa, .. | This set indicates that there is no null string. So we can write, The + is called positive closure. in with ; (SEIZED Desion regular expression for the language o containing all the strings | ‘any number of a’s and b's. g me sia lution : The RE. will be RE. -= (a+b) The set for this RE will be - L = {eaerrs “Suns yynu & ydaoxo sq pue se faa gum uowssaidxo zener Sy z ST RHRAS Trad 241 sdooxa 5,9 pun 5,» fo soquima Ras imjuoo aBynSuvy ay sof uosssaadxa avjnSou v jansysuoy i 5 ‘Biseq v09di00 70 Serge 2o4. @amncs On> Sam 103 7G) SHS -x raged nd 1 “aden wos spe ne 70 FAHY ED ia (4-08 95.) admeg fo soge> & RENIN BEY -ejeoine sy fo yun ap puns copes nwo on = foil mUOIN aH 20(NSA) SUNPUHY HES AML PV “aud mekqou omy ae Seve suoRDUNY YO OE LS AS suopouny oon 30 sme yc oy pds sap (eu sag hogs gnu pes or Pailbp 1 vowpuny © “VAN JP me Xow sa Sy am ag (WAN oon ayes >peuTUAnOp-UON wo LH} ans UNH SET Seether any eur aa of esome vy soeaade aeeRay asap oad AMS ‘spy Bapuodsnns soy ang ase events seat pur s9ynq andur mo peek S| LID AL SEAMS -ayng yy wr nda yas siaseue (EITPrinciples of Compiler Design 2-24 Lexical Analysis aa eee ‘ransition table can be read as : when current state is Sy, on input 0 ee State will be Sz and on input 1 the next state will be S;. The arrow marked to So indicates that it is a start state and circle marked to S, indicates that it is a final state. CRU Sake FA which accepts odd number of 1's and any number of 0's. Solution : In the problem statement, it is indicated that there will be a state which is meant for odd number of 1's and that will be the final state. There is no condition on number of 0's. At the start if we read input 1 then we will go to state S, which is a final state as we have read odd number of 1's. There can be any number of zeros at any state and therefore the self loop is applied to state S) as well as to state S,. For example, if the input is 10101101, in this string there are any number of zeros but odd number of ones. The machine will derive this input as follows - Fig. 2.8.4(a) 1__Input ends here pein oputenshe jn Which isa final stateSep wotsen van a0 oe EES == GEE wee ec A Hoaggo sat state Setinion ws «= sere Fis a set of al states such that Pe ‘The €- closure (P) isa set o ‘e-transitions such that I) e= closure (p) = p where i) there exists ¢- closure Find © cl © closure (qo) = {4 © closure (q3) = (4 4 closure (q2) = (9 EEREES conversion of nFf this method we ty to 1 dl out all the © tar closure {4,} where g)w os 7 vA Lexical Anaiysis nips of Compiler Design 8 (qo,tbbee) 8(41,bbce) F 8(qi, bec) F 8(qi, cc) F B(ar-ecc) £8 2,0) F 8(a2,0) F 8(a2,e) ‘Thus we reach to accept state, g after scanning the complete input string, Definition of ¢ - closure Thee closure (p) is a set ofall states which are reachable transitions such that 4) €- closure (p) = p where p € Q. Jf there exists €- closure () = {q) and 8 (4.2) =r then e = closure (p) = {qn WED i ie re ftsng WEA ein c from state pon iy palition: © closure (qo) = {90-41, & dlosure (91) = 4, a} means sel state + ¢ - reachable tate, a} means qi a self tate and a is a state obtained from 4) with ¢ input # dlnure (42) = {a3} BIDET conversion of NFA with © to NFA without ¢ Jn this method we remove al Wipe “NO We ty to remove ll thee transitions from given NFA. The method L Rnd out an FcosSrey “sy principles of Compiler Desion 2-31 Lexical Analysis. = + 8 (qo,ebbcc) W + 8(q1/bbec) F 8(a1,bec) F 8(q41,¢0) 8(a1 ec) F 8 (a2,¢0) F 842-9) F 8(42-€) Thus we reach to accept state, after scanning the complete input string. Definition of e - closure The e- closure (p) is a set of all states which are reachable from state p on ¢ -transitions such that : i) e - closure (p) = p where pe Q. ii) If there exists € - closure (p) = {q} and 5 (q£) = r then € - closure (p) = (q, 1)- Find © Giosiire for the following NFA with &. (i) [ktrns atk et dein E Fig. 2.10.3 Postion : e - closure (qo) = {40/41/42} means self state + € - reachable states. There e cs. e- closure (41) = {41/42} means q; is a self state and q> is a state obtained from q, with € input. €- closure (q2) = {2} Conversion of NFA with ¢ to NFA without « In this method we try to remove all the € transitions from given NFA. The method will be "1 Find out all the € transitions from each state from Q. That will be called as | €-closure {q;} where qj € Q. ‘TECHNICAL PUBLICATIONS” An up thrust for knowledge. ~ osm vacate € = clostite Se (41) and € - closure (q3) contains final Alternate method This is direct method to convert NFA with ¢ to FA without e.ty 20j VIN p= yap sn i714 = 2 BU PR aes erPl yonzjsuo> pur 2 an sed “ge of sleanto van mH oo a Gna veymnna say yeambo van uo 30} yan aze prsHOD ASN) SAL sere Oyanalyzer and syntax analyzers, us first go for un section procedure section faction;} {action,}tants can be done. Some 4 to LEX ee i tion declaration of variable const « In the declaration sec a Ree regular definitions ca" als0 ve writen in ti section. THe regular definitions Rone eseally components of BUT expressions appearing i" the rule section: | pet Ste ale section consists of TRL pressions with assaaied AHO cen in the form a5 ~ translation rules can be & R, {action} Ry, {actiong} R, _{action,} ‘and each action, is a program fragment These actions gular expression Where each R; is 2 Te be taken for corres} describing what action is to ee by piece of C code. Te And third section is a auxiliary procedure section in which all the required procedures are defined. Sometimes these procedures are required by the actions in rule section. The lexical analyzer or scan ponding regular expression. er works in co-ordination with parser. When activated parser, the lexical analyzer begins reading its remaining input, character by = When the string is matched with one of the regular get executed and this action, returns er at a tim sR, then corresponding action, will to the parser.Principles of Compiler Design TW FI’ TOT*F|F STS le F3() | id = F3@) | id fp cxancle 371} Consider the following grammar \ A ABd|Aala B- Be\b | remove left recursion. | Solution : Consider the rule, A ABd|Aala AsAalB We map this grammar with the rule Je a This can be eliminated by re-writing the production 74 ara Bal? + ty A Aggie NAN ee Al Ag Al ot BdA’ A’ => 8 A eee For Aa Aala tees A AaB “This left recursion can be eliminated a8 - yA > BA’ A > ad’ Mey APF oNioz) A’ > aA! NM = © ASABd|Aala => A > aA’ A’ + BdA‘|aA’ Woe B > Be|b grammar with the rule A — Ao. |B . "TECHNICAL PUBLICATIONS”. An up thust for knowledge: is left factored then it becomes suitable for the use. Basically left Be cn dan al wc of he (wo seas OS rnon-terminal. By left ractoring we may be able to rewrite the production q ok unt enough oe input ssn to mae he SE 183| 082 i Frei not possible fr us fo take a decision whether to choose Bt d Tr such a situation the above grammar can be let factored a IS | iBtSeS | aPDET|T —x The left factored grammar becomes, i map the above rule as S = iBtss'|a Sse soi E>b AKG a Knee Eliminate the ion from the following grammar» AE A> AclAnd|ba|e. i Car Soittion + To liminate left rerursion we have a rule : when A= /A G/B rule th convert it to 7 ee © bons Ee A’ saa 2 TOT*F|F map the above rule as Tors PPM Aha ) | id is not a left recursive after eliminating left recursion. Tr> SE A ean 208 Syntax a, ony) is principles of 00 = 3-57 << | 3.3] Bottom-up Parsing a What do you mean by handl Define handle. a for each of top down parser and bottom up parser. In this section, we will discuss "How an i compilers, the task is done by a program «: sither it checks the input string completely ‘on syntactically input strings. In bottom-up es ee fist and we try to reduce this string with the o obtain the a sat symbol |The process of parsing halts su reacthee Note a"design a DFA for above set of items as follows ie DFA every state is final state, The state Ip is initial state, Note that the Viable prefixes, TECHNICAL PUBLICATIONS”. An up tt for Anowcgeopel Pn aac unum spp sn Bund pop eyeipaurt 12can be written a pd ia ao sed [eo operands ite of polish notation hich is used using post A yeren pons notalhy wl There is representation Consider that t ath +a, he input expression 18 = then the required posix form is - Gastric syntax spilas ee td posix notation for the foil ow ing expres sion MiGHeo)T d-e/ (+8) Sahin : Syntax Tree | 97) Nd-e/tep 1d-e/(t+g) Hg)Now backward substituting the values of temporary varSean, copter DOS fone Code con oe ifch=1 goto L1 eo ifch=2 goto L2 Tate! ey, ti=arb ao e eat | 6 goto Last ee ae [ne a | oat ge ue Ia intermedi code for ‘te eli Sle Sema ASRS RTD required syntax directed translation scheme Dit (a > 2b) f x=a+d & else x=a-b Where a & x are of real and b of int type data i int a,b; foat ¢ a=10; ‘switch (a) { caso 10:0 case 20: ¢ = wah } | ApriUMav-08. Marks 16 | #H)ifa>b goto Li ‘Goto L2- u: {1 := inttoreal b =a+tl 2 {1 inttoreal b Qiza-tl x=o TEHNCAL PUBLICATIONS”. An wp rus er krownigeis Ug to ply i nN basic block = Dae Pe ante Constructed fo, thar Peleg a Pr, vttled by ‘dentition or yy, peat recor T-values, le nodes store 9 ter in ee Values, id flow gra DAG an The PAS are tg aie meee’ "Presented by Dag flow the jc block, basic: Tepr “ASE each Nog Clg MU B Bra Ey Considerpaw ee ON "pan tn ate on be Hc floa rh toes ; Ho Soompltn te = compa of ern on tne the vale op Ts dove dng ea i PEN BY 316 Ad by 5 then ‘common sub expression t= ue of iis not been changes from Teen