DOC PREVIEW
UMD CMSC 330 - Exam #2

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Name (printed):University ID #:Circle your TA’s name: Guilherme NirCircle your discussion time: 12:00 1:00CMSC 330 Exam #2 Fall 2006Do not open this exam until you are told. Read these instructions:1. This is a closed book exam. No notes or other aids are allowed.2. You must turn in your exam immediately when time is called at the end.3. This exam contains 7 pages, including this one. Make sure you have all the pages. Each question’spoint value is next to its number. Write your name on the top of all pages before starting theexam.4. In order to be eligible for as much partial credit as possible, show all of your work for each problem,and clearly indicate your answers. Credit cannot be given for illegible answers.5. If you finish at least 15 minutes early, bring your exam to the front when you are finished; otherwise,wait until the end of the exam to turn it in. Please be as quiet as possible.6. If you have a question, raise your hand. If you feel an exam question assumes something that is notwritten, write it down on your exam sheet. Barring some unforeseen error on the exam, however, youshouldn’t need to do this at all, so be careful when making assumptions.7. If you need scratch paper during the exam, please raise your hand. Scratch paper must be turned inwith your exam, with your name and ID number written on it. Scratch paper will not be graded.8. Small syntax errors will be ignored in any code you have to write on this exam, as long as the conceptsare correct.9. The Campus Senate has adopted a policy asking students to include the following handwritten statementon each examination and assignment in every course: “I pledge on my honor that I have not given orreceived any unauthorized assistance on this examination.” Therefore, just before turning in yourexam, you are requested to write this pledge in full and sign it below:Good luck!1 2 3 4TotalName: 21. [15 pts.] Short Answer.a. [5 pts.] List the free variables in the following C function. In one to two sentences, define what thefree variables of a scope are in general.void foo(int a, int b) {int c;c = a + b;d = c * 2;return d;}Answer: The only free variable in this function body is d. The free variables in ascope are those that are not bound by some definition or declaration.b. [10 pts.] The following OCaml function is not tail recursive. Briefly explain why not, and transformit into a tail recursive function.(* returns 0 + 1 + ... + n *)let rec sum n =if n = 0 then 0else n + (sum (n-1))Answer: The function is not tail recursive because after the recursive call to sum,more work happens in the function (namely, the result of the recursive call is addedto n).Here is a tail recursive version:let sum n =let rec sum_helper acc m =if m = 0 then accelse sum_helper (acc+m) (m-1)insum_helper 0 nName: 32. [25 points] Parameter passing. Suppose you are developing a new, statically-scoped language thathas the following fairly obvious syntax:integer n;integer i;integer array A[5];function f(integer array x, integer y, integer z)beginn = z-2;z = y-1;x[y] = x[z]+1;print(x[1], x[2], x[3], x[4], y, z);end;n = 5;for (i = 0; i < n; i++)A[i] = i;endcall f(A, n, n)print(A[1], A[2], A[3], A[4], n);Fill out the following table showing what would be printed if the language used either call-by-value orcall-by-reference for all parameters. Under call-by-value, assume the entire array is passed by value (thisis different than C, which would pass a pointer to the array).x[1] x[2] x[3] x[4] y zCall-by-value 1 2 3 4 5 4A[1] A[2] A[3] A[4] nCall-by-value 1 2 3 4 3x[1] x[2] x[3] x[4] y zCall-by-reference 1 3 3 4 2 2A[1] A[2] A[3] A[4] nCall-by-reference 1 3 3 4 2Name: 43. [25 pts.] Grammars.Consider the following two grammars for expressions, where i stands for any integer.E ::= E + T | TT ::= T * P | PP ::= (E) | iE ::= E * T | TT ::= T + P | PP ::= (E) | i(G1) (G2)a. [5 points] For both grammars G1 and G2, give the leftmost derivations for the string 2+3*4Answer:(G1) E ⇒ E+T ⇒ T +T ⇒ P +T ⇒ 2+T ⇒ 2+T ∗P ⇒ 2+P ∗P ⇒ 2+3∗P ⇒ 2+3∗4(G2) E ⇒ E ∗T ⇒ T +P ∗T ⇒ P +P ∗T ⇒ 2+P ∗T ⇒ 2+3∗T ⇒ 2+3∗P ⇒ 2+3∗4b. [10 points] Do both G1 and G2 accept the same set of strings? Explain why or why not.Answer: They generate the same strings.The two E productions in G1 generate the strings T+T+...+T and the two T pro-ductions generate the strings P*P*...*P so these four productions generate the stringsP?P?P?P...?P where ? can either be + or *.Similarly in G2 the E productions generate T*T*...*T and the T productions generateP+P+...+P. So tehse four also generate the strings P?P?P?P...?P where ? can eitherbe + or *.This is just the regular expression: (P (+|*)) ∗ P which is the same in both grammars.The P productions are the same in both grammars, so the resulting strings generatedby G1 and G2 are the same.Name: 5c. [10 points] Give a context-free grammar for the set {anbmcn|m, n ≥ 0}.Answer: Here is a grammar for the set:S ::= a S c | TT ::= b T | εName: 64. [35 pts.] OCaml. Consider the following OCaml type describing a grammar:type word =Term of char (* a terminal symbol *)| Nonterm of char (* a non-terminal symbol *)type prod = char * (word list) (* a production *)type grammar = prod list (* a grammar *)We use char to name both terminals and non-terminals. For example, the OCaml code below definesg1 to be the grammar G1 from problem 3:let (p1 : prod) = (’E’, [Nonterm ’E’; Term ’+’; Nonterm ’T’])let (p2 : prod) = (’E’, [Nonterm ’T’])let (p3 : prod) = (’T’, [Nonterm ’T’; Term ’*’; Nonterm ’P’])let (p4 : prod) = (’T’, [Nonterm ’P’])let (p5 : prod) = (’P’, [Term ’(’; Nonterm ’E’; Term ’)’])let (p6 : prod) = (’P’, [Term ’i’])let g1 = [p1; p2; p3; p4; p5; p6]In the following problems, you may use any standard OCaml library functions you like.a. [5 pts.] Write a function start : grammar -> char that returns the start symbol of the grammar.As in our formal notation, we assume that the left-hand side of the first grammar production inthe list is the start symbol. Your function may do anything if the grammar has no productions.Answer:let start ((c, _)::_) = cb. [15 pts.] Write a function terms : grammar -> char list that returns a list containing theterminal symbols used in strings produced by the grammar. You may list the terminals in anyorder, and duplicates are OK.Answer:let rec terms (g:grammar) =let add_term acc = functionTerm c -> c::acc| _


View Full Document

UMD CMSC 330 - Exam #2

Documents in this Course
Exam #1

Exam #1

6 pages

Quiz #1

Quiz #1

2 pages

Midterm 2

Midterm 2

12 pages

Ocaml

Ocaml

7 pages

Parsing

Parsing

38 pages

Threads

Threads

12 pages

Ruby

Ruby

7 pages

Quiz #3

Quiz #3

2 pages

Threads

Threads

7 pages

Quiz #4

Quiz #4

2 pages

Exam #2

Exam #2

6 pages

Exam #1

Exam #1

6 pages

Threads

Threads

34 pages

Quiz #4

Quiz #4

2 pages

Threads

Threads

26 pages

Exam #2

Exam #2

9 pages

Exam #2

Exam #2

6 pages

Load more
Download Exam #2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Exam #2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Exam #2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?