=========================preview======================
(COMP251)07-midterm.pdf
Back to COMP251 Login to download
======================================================
COMP251L2:2007FallSemesterMidtermExam


DateTuesday,Oct30,2007 Time7:00-8:30pm Instructions:(a)Thisexamhas
questions.Youhave90minutes. (b)AttemptALLquestions. (c)Thetotalmarkis100. (c)WriteALLanswersintheexambook.Donotuseanyotherpapers.
Name: Question Mark
StudentID: 1.
LabSection: 2.
3.
4.
5.
6.
7.
8.
9.
10.
Total:

Problem1(8pts)Whatisthevalueofaineachofthefollowingexpressions.
(a)vala.1::[2,3]@[5]
(b)val(_,a::_).([1,2,3],[4,5,6]).
(c)funfoo1fv[].v
|foo1fv(head::tail).f(head,foo1fvtail). funfoo2(x,y).2*x+y. vala.foo1foo21[1,2,3].
(d)vala.let funfoo(x). letvalx.x*x valy.x*x inx*yend in foo2end.
2

Problem2(8pts)Whatisthetypeofeachofthefollowingfunctions. (a)funfoo1x.iftruethenxelse1. (b)funfoo2(x,y).[x,y]. (c)funfoo3xy.x(y,y+1). (d)datatypemy_color.red|yellow|blue. funfoo4(x).ifxthenredelseyellow.
Problem3(6pts)WriteanSMLfunctionMax.fn:intlist-.intthatreturnsthe maximuminanon-emptylistofintegers.(Wedon'tcareaboutMax[].)
3

Problem4(10pts)WriteanSMLfunctionInsert.fn:int*intlist-.intlistthat insertanintegerintoasortedlistofintegerssothattheresultinglistisstillsorted. Noticethatifanumberisalreadyinthelist,thendon'tinsertit.Forexample, Insert(5,[1,2,6,7]).[1,2,5,6,7]andInsert(5,[1,2,5,6,7]).[1,2,5,6,7]
Problem5(10pts)Considerthefollowinggrammar:
.S.::.a.S.b|a.S.bb|.empty.
(a)Provethatthisgrammarisambiguous.
(b)Generateallstringsoflengthlessthan10usingthisgrammar. (c)Whatlanguagedoesthisgrammargenerate.
Problem6(5pts)Generateallstringsoflengthlessorequalto3accordingtotheregular
expression[cd]*b.a+.
Problem7(8pts)WritearegularexpressionforrealnumbersoftheformX.Y,whereXis eitherempty,0,orasequenceofdigitsthatdoesnotbeginwith0,andYisanon-emptysequenceofdigits.So0.1,1020.120,and.0980arerealnumbersbut01.2and 1.arenot.
Problem8(10pts)Considerthefollowinggrammar:
.S.::.(.S.)|.S..S.|.empty.
Itgeneratessequencesofbalancedparantheseslike(),(())(),(()(()))(()). However,thisgrammarisambiguous.Findanunambiguousgrammarthatwill generatethesamelanguage.
Problem9
(18pts)WriteanSMLfunctionPerm.fn:'alistlist-.'alistlist thatconvertatwo-dimensionalarrayfromrowrepresentationtocolumnrepresenta-tion:assumethatthegivenlisthasnelements,eachofwhichisalistwithexactly kelements:
x.[[a 11 .a 12 .:::.a 1k].:::.[an1 .an2 .:::.ank]]
Permxwillbealistwithkelements,eachofwhichisalistwithexactlynelement:
x.[[a 11 .a 21 .:::.an1].:::.[a 1k.a 2k.:::.ank]]
Forexample,
Perm[[1,2,3,4],[5,6,7,8],[9,11,56,20]].[[1,5,9],[2,6,11],[3,7,56],[4,8,20]]
Perm[[a,b,c]].[[a],[b],[c]]
Problem10(17pts)ConsiderallBooleanexpressionsthatcanbeconstructedfromtwovari-ablesandyusingtheoperatorsgivenbelowinthedecreasingorderofprecedence:
x
()(parenthesis) :(unarynegationoperator) ^._(binary\and"and\or"operators,leftassociative) !(binaryimplicationoperator,rightassociative) $(binaryequivalenceoperator,rightassociative)
(a)Writeanunambiguousgrammarforthesebooleanexpressionssuchthatits parsetreeshavethesamestr