compiler

ThissamplemidtermisthemidtermfromSpring2008.Ifyouseeanyerrors inthesampleanswer,pleaseemailmeortellmeonPiazza.Goodluckon yourmidterms! 1.“Irelandhasleprechaunsgalore.”isanexampleofaparticularkindof syntacticconstructinEnglish.CanyouconstructasimilarexampleinC++, OCaml,orJava?Ifso,giveanexample;ifnot,explainwhynot – Artificiallanguagesaregenerallymorecarefully-designedthan naturallanguages.Thus,thesekindsofexceptionsshouldberare,if theyexistatall. 2. a)WriteanOCamlfunction‘twice’thatacceptsafunctionfandreturnsa functiongsuchthatg(x)equalsf(f(x)).Forsimplicity’ssake,youcan assumethatfisfreeofsideeffects,andyoucanimposeother restrictionsonfandx.Trytokeeptherestrictionsasminoraspossible, andexplainanyrestrictionsyouimpose.Or,if‘twice’cannotbewritten easilyinOCaml,explainwhynot. – lettwicef x=f(f(x)) – restrictionisthatfis‘a->‘a b)Sameasa)exceptwriteafunction‘half’thatacceptsafunctionfand returnsafunctiongsuchthatf(x)equalsg(g(x)). – Itisdifficult,sinceitsimplementationmustdependonthespecific functionfused. – Forexample,iffisidentityfunctionf(x)=x,thengiseasy– alsotheidentityfunction. – However,iffisthesinefunction,thengissuperdifficult–given x,g(g(x))=sin(x)??? – Therestriction,likea),isthatfis‘a->’a c)Givethetypesof‘twice’and‘half’ – twice:(‘a->’a)->‘a->‘a – half:(‘a->‘a)->‘a->‘a 3.ConsiderthefollowinggrammarforasubsetoftheC++language. expression: expression?expression:expression expression!=expression expression+expression !expression INTEGER-CONSTANT (expression) Forexample,(!!0+1!=2?3:4)isreadas“ifnot-not-0plus1doesnot equal2,then3else4,andevaluatesto4. a)WhatarethetokensofthissubsetofC++? ?:!=+!INTEGER_CONSTANT() b)Showthatthisgrammarisambiguous Drawthetwoparsetreesforexpression1+2+3 c)Rewritethegrammarsothatitisnolongerambiguous,resolvingany

ThissamplemidtermisthemidtermfromSpring2008.Ifyouseeanyerrors inthesampleanswer,pleaseemailmeortellmeonPiazza.Goodluckon yourmidterms! 1.“Irelandhasleprechaunsgalore.”isanexampleofaparticularkindof syntacticconstructinEnglish.CanyouconstructasimilarexampleinC++, OCaml,orJava?Ifso,giveanexample;ifnot,explainwhynot – Artificiallanguagesaregenerallymorecarefully-designedthan naturallanguages.Thus,thesekindsofexceptionsshouldberare,if theyexistatall. 2. a)WriteanOCamlfunction‘twice’thatacceptsafunctionfandreturnsa functiongsuchthatg(x)equalsf(f(x)).Forsimplicity’ssake,youcan assumethatfisfreeofsideeffects,andyoucanimposeother restrictionsonfandx.Trytokeeptherestrictionsasminoraspossible, andexplainanyrestrictionsyouimpose.Or,if‘twice’cannotbewritten easilyinOCaml,explainwhynot. – lettwicef x=f(f(x)) – restrictionisthatfis‘a->‘a b)Sameasa)exceptwriteafunction‘half’thatacceptsafunctionfand returnsafunctiongsuchthatf(x)equalsg(g(x)). – Itisdifficult,sinceitsimplementationmustdependonthespecific functionfused. – Forexample,iffisidentityfunctionf(x)=x,thengiseasy– alsotheidentityfunction. – However,iffisthesinefunction,thengissuperdifficult–given x,g(g(x))=sin(x)??? – Therestriction,likea),isthatfis‘a->’a c)Givethetypesof‘twice’and‘half’ – twice:(‘a->’a)->‘a->‘a – half:(‘a->‘a)->‘a->‘a 3.ConsiderthefollowinggrammarforasubsetoftheC++language. expression: expression?expression:expression expression!=expression expression+expression !expression INTEGER-CONSTANT (expression) Forexample,(!!0+1!=2?3:4)isreadas“ifnot-not-0plus1doesnot equal2,then3else4,andevaluatesto4. a)WhatarethetokensofthissubsetofC++? ?:!=+!INTEGER_CONSTANT() b)Showthatthisgrammarisambiguous Drawthetwoparsetreesforexpression1+2+3 c)Rewritethegrammarsothatitisnolongerambiguous,resolvingany