ࡱ> vxu@ ;bjbjFF "B,,2222...BAAAA<B\BWnBnBnBnBnBUCUCUCWWWWWWW$XR[t:W].UCQCUCUCUC:W22nBnBWGGGUC<2&nB.nBWGUCWGGVhO@X.,PnBbB p| 0ADPO WW0WOx[F[,PBB2222,Ph[.VUCUCGUCUCUCUCUC:W:WBB"'GBB'Name_____________________________ Compiler Exam Fall 2007 #1. (2 points) Consider the following grammar: S ! A A ! A+A | B++ B ! y a) Draw the parse tree for the input  y + + + y + + b) Show a leftmost derivation of  y + + + y + + #2. (4 points) Consider the following grammar: X ! YaYb | ZbZa Y !  Z !  a) Using the definition of LL(1), explain why the grammar is or is not LL(1). b) Show whether the grammar is or is not SLR(1). (treat  e as a terminal) #3. (6 points) Consider the following grammar with terminals [, ], a, b, c, +, and -: 1 S ! [ S X ] 2 | a 3 X !  4 | + S Y 5 | Y b 6 Y!  7 | - S X c (a) Fill in the table below with the First and Follow sets for the non-terminals in this grammar: First Follow S X Y b) Create the top-down parsing table c) Using your table, parse [a+a-ac] Stack Input Production #4 The following context-free grammar describes part of the syntax of a simple programming language. Nonterminals are given in capitals and terminals in lower case. VAR represents a variable name and CONST represents a constant. The productions for ASSN-STMT are not given, as they do not affect the question. 1 PROGRAM ! Procedure STMT-LIST 2 STMT-LIST ! STMT STMT-LIST 3 | STMT 4 STMT ! do VAR = CONST to CONST { STMT-LIST } 5 | ASSN-STMT (a) (1 Point)Show the parse tree for the following: Procedure do i = 1 to 100 { ASSN-STMT ASSN-STMT } ASSN-STMT (b) (2 Points) Create attribute(s) and add semantic functions to the above grammar that compute the number of executed statements for a program conforming to this grammar. Write them beside the productions above. c) (1 Point) Using the tree from part a, compute the value of your attributes. d) Replacing ASSN-STMT with the terminal a, in the above grammar, create lex and yacc files that will compute the number of occurrences of this terminal a. Use yaccs semantic facilities ($$ etc.). You will not be penalized for small syntax errors. (3 Points) LEX file: (ii) (5 Points) YACC File: #5. (2 points) State why/how worst case insertion in a simple hashed symbol table using chaining can be O(1) #6. (6 points) Identify the cycles in the following and then show which are loops and which are not loops and why or why not. a)  b)  c)  #7. (8 points) Consider the following code which computes the inner product of 2 vectors: prod := 0; i := 1; repeat { prod := prod + a[i] * b[i] i = i+ 1; until i > 20 } Below is possible IR for this program: (1) prod := 0 (2) i := 1 (3) t1 := 4 * i (4) t2 := a[t1] (5) t3 := 4 * i (6) t4 := b[t3] (7) t5 := t2 * t4 (8) t6 := prod + t5 (9) prod := t6 (10) t7 := i + 1 (11) i := t7 (12) if i <= 20 goto (3) bdz|      b |     $ & * < x z ~ ͿͿͿͿͿͿͿͿޮqhkCJOJQJ]^JaJ#hkhkCJOJQJ]^JaJh~nhk&hkhk6CJOJQJ]^JaJ h]6CJOJQJ]^JaJh]CJOJQJ^JaJ h]6CJOJQJ]^JaJh]CJOJQJ^JaJh_zhh]hZhU+DFdxz|~   gd]gdZ$a$gdZ$a$gdU:;           ~ j l n p r t gdkgdZgd]~  f h j z  " $ & . 0 F ίίzvvra hk6CJOJQJ]^JaJh_zhU h]hkCJOJQJ^JaJhUCJOJQJ^JaJhkCJOJQJ^JaJhkh] hwkhkCJOJQJ^JaJhkCJOJQJ^JaJhkCJOJQJ^JaJ hk6CJOJQJ]^JaJ#hkhkCJOJQJ]^JaJ%t v x z          "  D d r 0BCgdZgdk       4 B X b h j p r 0;Lr~צxf#hm+hkCJOJQJ]^JaJhkCJOJQJ^JaJ hk6CJOJQJ]^JaJhUCJOJQJ]^JaJhkCJOJQJ]^JaJ hU6CJOJQJ]^JaJ hm+hkCJOJQJ^JaJ hk6CJOJQJ]^JaJhkCJOJQJ^JaJhkOJQJ^J CEFHIKLqrstuvwxyz{|}~gdZgdk   lq  PR|~ñÍqccRcccc h|zhkCJOJQJ^JaJhkCJOJQJ^JaJhUCJOJQJ^JaJhkCJOJQJ^JaJ#h_zh_zCJOJQJ]^JaJ#hUhUCJOJQJ]^JaJ#hUhkCJOJQJ]^JaJ hU6CJOJQJ]^JaJhkh] hk6CJOJQJ]^JaJ#hk6>*CJOJQJ]^JaJ|~pr&'(\]hzgdk~pr&'(,5\S|~Ŵŕyk]]ŕYUhhkhCJOJQJ^JaJhCJOJQJ^JaJhUCJOJQJ^JaJhUCJOJQJ^JaJh~nCJOJQJ^JaJ hkhkCJOJQJ^JaJ hkhUCJOJQJ^JaJhkCJOJQJ^JaJhCJOJQJ^JaJhkCJOJQJ^JaJ h|zhUCJOJQJ^JaJ}~h^hgd & Fgd~ngdgdZgdklm %3N\iox   !#$½ʴ¬¹ڐhhU5jh0qUh0qhh|z5hhl05 hl06hU hU6hl0h dh|zheh_zhZhh~n hh h6hhCJOJQJ^JaJ8  !$&)+gd5gdZh^hgd$%&()*+,-/01:#8 88888::;;;õ߮߮߮߮߮߮߮ߨߨhn hm+hm+hF)h~nU hr?h5h~nCJOJQJ^JaJh_zCJOJQJ^JaJha@CJOJQJ^JaJh5j7hUUhUhhl0jhUU%"#3@Rdv 8 898:8;8<8=8 & Fgd5gd5(13) Create Basic Blocks and the Control Flow Graph Show Reaching Definitions on the graph Show any optimizations you can find d) Show assembler or pseudo assembler code for the program before and after optimization: Responsible for anything included in the Modules. Emphasis on those topics discussed in class and on the homeworks. Know definitions of and be able to answer questions related to: grammars parse trees derivations (leftmost, rightmost) LL(1) SLR(1) FIRST, FOLLOW top-down parsing (LL(1)) parsing bottom-up (SLR(1)) parsing attribute grammars lex yacc symbol tables run-time systems CFA (basic blocks and CFG's) loops Reaching Definitions Live Variables Available Expressions Very Busy Expressions Code Generation algorithms =8>8?8@8h8i8j888888 9c9d9e999999999:4:G:gdF)h^hgd~ngd~n & Fgd5gd5G:K:P:^:o::::::::::;;;;;;;;; ; ; ; ; ;;gdF);;;;;;gdF) 1h/ =!"#$%Dd >  C Ab;HŪLl]lsD nHŪLl]lsPNG  IHDRsRGB pHYsod IDATx^];sG^9r#P2Ů ?)w@ft")pA)"9RH`B9U-H/8ϣczޏ- z{oq;rl L{ZfZ=-򝟯廔ڃΛ$c?K:͢b1Imac;'6|8' csp`AYֲ[[]DX^=fw4|DxQ`>okcYY>2Gmo_]_7E{7.xryy'0 sE^QzTgYߟ>.nm\xqoWp#{ tf͋7[[Ņ1s+ݢ,R-1,KW-iZ*fY@\l!1_X0{ghQԜHvmK2 9a==-^%ĽR \MWFlʙ52P zeb2qb1^ye뙟%+05Zna\İ]5訍oWrkyDr_3Dxf^! ]Mw)ӝ7I@~Du0Ec;'6|8' `8erpm| Y?؝u\7pA]U7 |YtUHRTii±Ç>% >!n?ZjUAă֒Veoӧ'K訹= .y~\{{÷M%㮧fY֛qF -PTa ʤh9֊~XY7n3;!ПkI:7h$t<~:i~KB.L÷;<9iؿs[ؿS5B|(Is{IENDB`j Dd! >  C Ab 1LV':i:8  n 1LV':i:8PNG  IHDRT{asRGB pHYsod @IDATx^]?o;{%U("AGK =ESD"_%URQ>uRJ JC:"E('7{z"7ۿޚjGH@Z*򡋏1{ݷ&>%&Pߨ\ʇ.CWZ^|>0o+ |0f{@|>"p \(yc[[w&QX?so͵e{՞ ^ uGEo]^\V fw޽sܻ6>_9?dq3eqz:G;\nv|Yիfm98I \mΝ^yZ1!߿߼|^]]u5Cտ~4"E uCVcv hwppxe˫%ī[I-]ztt|1K٢]nM?zAE kd#$ +I` VZ.IGXV>KҰjӒ i0Q2q#IUi|H.&Є5d>]VUԻ3T'Y/m#ZZC PY\3Kw4lj}oǕʇ.t$kW$uǔ*<5-/6P-˝#Jށ d ÇӧOz5䖥 y?`0yvkk |AF %,xgbٙ?Hw (e*1bG{kw~I6.]?8iLMAgTAqV@ʊ2(}'UsDփvY"pƜDS*Z0XP #bꫢK4x|ew.Q^ Mެg)VUzv&`d._Xjs 5ࣸ9k$pg:*Pj!j(ɊN$;6?l ${caJ8,(dT>F֝b:|Lc|4ya1yDN]_-zn)PI't1PU*Ҡ+,vZ%yC*VW.rB^y6T<1[`E%5$>UE؄.ے)(_.)8PbU"2|tAݑmHdϝ q-R堻yx;+o7^!9[ppB3`1V"cm::y镧G1̓uUE+M= :/_@ϟ?p$넒^vS#F* I Dbx?Kޥ85BѺf_I |貙R>y{XW>puS}E6pU>|)U0[qg!3/۬ >*5XcS0jBm#Sg{+|Ȇʇ RZ|DԸ5Y+!; ٙ&GEzgH(!7X M?bSҖh0 q·`·Z+z`|n-UÝ.)">6ڞ/<GߐefI 2Fy||d՝$)%OmN58vww׭I$_3^̉jmhbJ; Wf .eUf|nZ٘$2GNBr0pc'M?ਭl$7p>+p@ID[ aN8/+3W`Yb"3ra>Fezݥ壛H^.8$| _{m"|,iwp}e%04U[0bf%+5+XR[輈zcCwc[JŨ"a'y$kvd5L$\Ry9Q&V<=zl_xsj?~xIX0!Km@w5H'KҰ1SщG3V:)>t9T>JLGh:|LcGOb҈"?ߠpF:=j-[}xU1Sܩ>1.޾*>1.޾ c6࿝ylkZĔ:Ȋ?cd$[Ç?8=޾N#^4.Үn}~y:?sx''>.\'͜[9T[&=l..ړ՛+&LM%^vxiAv𡲾Be)WϟIJ_[ހ Y`|}۞M{R+^ NӦܼ.N#4i3?}5/,K,Ze zW>t[ŇGdbn%>LP5^"QЅT|B@h?UpPuIENDB` Dd  >  C Ab ͊ Q`eo { n ͊ Q`eoPNG  IHDRzUsRGB pHYs.> IDATx^]1o9\uW%Rтt4S@R BEA PJӉ+(r\ 7yg>gֻس`߾=>+WWWUNݘ#fmdwqEiڃfcXm#|x">?^ PG'T=iun0|meSaHxW:Tkds?oJcme֭:Jh|Y[ݹSmnVllTSku| f?=~1>w)'}*1(#37-D0iFCUG 0$|-"%;d7MoAP %>ZfW۝Nk<88|S3ޤ⍀A*n7'Jq7bSѝQ*7'5IVzj/yoJ-Н i7qC OW2M3SOtdžqxMpI9I+$M'>7>5>N4#ۙ414)ޘޕ⨐ ݤ-lZnxTU1;@@v݁3w!H@oζ4i<(-9w7nq>oo}ݞ`'8Ƿ`çtPUCK: w |`'8:NmdcliHci6Vrnx0ye)Yħ6=Lotޖ m2<;fNnOplzo\=|5շC*')f-89M*6N_߶TpBm<}ИoٵwkXW@>6H-k&ˤίkM=pPݘH]m)Gur:}|ׯljnicT^}S+t enҬ0S(ZDmh q<ϠR1Tfd:')|C^.3d Ѝr?uZvT&x{T#V.o1L(JMy+H[f L}ɕ0a갳125rQ"Fђ]d>$c!Ep b4o<5ߍ$(nbkK9'H85sMWE7/a±jjHaxo*jj?xO`o{uds To7nd1X5%FdC<ܤJH!59شSeƝɔ1ɇHvyXKo^`>ͼ;նw{Nj񜊘l 읩~'9s 5qcH7;Kdk~.el3i} @ ]Qe/dOfAp7 :lVyg-",5ltF)ȔKla|OIOmI;*IExP'eKouEgS(!DU3#;"vdqd3@$eI2hoEmq+Hϗݺ2'7\jNv[hbE!ߋȍiR7Z6Ȗ55J1-$1V|@Y-Q߰v=a~ss3u|hEqI04{>a۠"55+Q߶h>^7o«*Kc)ף\q ؀ݻ>|}vd ;=DͧG\ko{tn"eF1n|_^sr:soeX6X[[[ C"QFI|Kcpr;"O#Bӹ;Ttx.JUC([]UC([]UC([]-}j7G엮ơ"-6w7t^ΕXV١QdAI[\v뱕1uwG=V}{I"2+Q G7-ʷ|)=P)hɷUsHMAK!`7 ,끮ǜl">z,EY}[ |gg*Kh$!yV0~^ |^^?~kqO"Ioϡ]Gӽŧ2()onֲ 0zU?yR}Tܼbxv$a5-FN]R~\򘦗$=Z32\hA?k=IlVga{{utqQl N%<ͤiGVZ:8ʇ÷D[gQq()hɷN)Ż7QpIENDB`@@@ NormalCJ_HaJmH sH tH DA@D Default Paragraph FontRi@R  Table Normal4 l4a (k@(No List             B"#2<=>?opv    ?@T\de     klz0BCEFHIKLqrstuvwxyz{|}~>?@hi&'(\]hz}~   ! $ & ) + " # 3 @ R d v 9 : ; < = > ? @ h i j c d e 4GKP^o     0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000x0 000x0x00x0x0x0x000x00000x0x0x000x000000000000000000000000000000000000000 00000000 000 00x0x00\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>0\>00000000000000000000000"#2<=>?opv    ?@T\de     klz0BCEFHIKLqrstuvwxyz{|}~>?@hi&'(\]hz}~  ! $ & ) " # 3 @ R d v 9 : ; < = > ? @ h i j 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000@0@0000@0@0@0@0@0@0@0@0@0@0@0000000000000000000000000000 00000000 000 0@0\>0p\>0\>000~ ~$;  t C=8G:;;  ;867@60(  B S  ?HLOSmykl$(sy 9 : P Q t u W ` GJKO?B RUru  )*hj  / 9 + . ) - 9 : F J X \ j n | "4=GJKOPV^f333333333333333333333333333333333333333333333333EF  ,5     % , / 0 3 3 x | 0 1 `*HUBqk=vӜsf)^`o() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.`Bqk=sf                  @^b^        s>oIkN`I"I `Kg3 Ib g3m g3I1 `F ._yRkyZtUg3tXg3|+` rg3B ._yZW;g3>e`yZB]g3"p`7;g3Ag3JyZ9)`b#I'H1J=FD!g3'!` #IB&g3$'yZI'zA)g3V)`Q3,yZPA-yZQ;.`VC/g3y0I9)"1Ig3! 3`b33g3|[ 5g3i=6 ._Kh9g3+Lk:g3K<g3g%=I1J=1L>g3RVlCyZREg3~Eg3]FEyZ}Eg3sGg3I^[IyZgIg3)J1J=B!0L`zkLyZpM ._}N1J=E OyZuOg32 QyZQ`B(RI'RyZVV`?[+WyZj~Wg3:L[g3e]\ ._y^g3YW_` ._8_1J=i`1J=`#qcIBdg37fg3 h`-;jI.Fk`SlIJlng3z;&pyZHt8pg3"Yq`jq`(wgsIru`q[uyZZgu ._T+vI2awyZ)x`$y`zg3|zIx5{g3A}g3}~I!~`V ._ug3gI ._Z]F)l0 =a@LI dUik~n0q_z<}eU0&5"<wkl|zm+n@W X  @$@p@UnknownGz Times New Roman5Symbol3& z Arial3z Times"qhtڻFtڻF< < !24d3QH)?ZCompiler Exam QuestionsCascadeCascade   Oh+'0x  4 @ LX`hpCompiler Exam QuestionsompCascadeascascNormalCascade2scMicrosoft Word 10.0@V@ j0@ j0< ՜.+,0 hp  Microsoft Corporationu Compiler Exam Questions Title  !#$%&'()*+,-./012345689:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdfghijklnopqrstwRoot Entry F` 0yData ")1Table7[WordDocument"BSummaryInformation(eDocumentSummaryInformation8mCompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q