CMSC 330 Fall 2007Homework 2: Grammars, OCAMLPosted on: Saturday, Oct. 20, 2007Due: Tuesday, Oct. 30 9:20A M, 2007Homework should be submitted in my office (4115 AVW) BEFORE 9:20AM (slip themunder my door if it is closed). Homework will not be accepted after 9:20AM as the homeworkproblems may be reviewed in class that day. No late homework is accepted. Late home-work will receive no credit. Be sure to label the problem you are solving clearly withthe problem number and subsection. Typing your homework is not required, but homeworkshould be legible. Illegible solutions will receive no credit. Be sure to put your nameon the homework.Remember, you must do this homework on your own, without any external sources. Ifyou are unsure what is allowed, please contact the instructor.1. Creating GrammarsWrite unambiguous grammars for the following languages:(a) {anbn|n ≥ 0 and n is odd}(b) All valid OCaml lists created using ::. Make sure your construction correctlyshows the right association of this operator. Use v(′a) to indicate a value of type′a. Examples of valid strings in this language: 1 :: [], [], “hi” :: “there” :: [](c) All valid OCaml guards for if statements in the abbreviated language containingterminals:(, ), ||, &&, <, >, =. Parenthesis must be appropriately matched with every open-ing left parenthesis followed by a closing right par enthesis. ( and ) have thehighest precedence, followed by && and || and the lowest precedence is given to<, >, = etc. Use v(′a) to indicate a value of type of type′a. Note: Yo u don’tneed to worry about type compatibility. Assume that this is done separately.2. Ambiguity ProofsProve that the following grammar is ambiguous. Note: In class, we did not constructformal “proofs” for unambiguous grammars; however, for ambiguous grammars, weused example strings and the definition of a mbiguity.1S → ST |SU |cT → Ub|bU → aT |a3. OCaml Types(a) What is the type of the following OCaml function? Explain why this type iscorrect. (Yes, you can get the answer to the first part by typing this into acomputer... but you will need to know how to do this without a computer for theexam, so think about it anyway.)let rec func (f, l1, l2) = match l1 with[] -> []| (h1::t1) -> match l2 with[] -> [f h1]|(h2::t2) -> [f h1; f h2](b) Make a function that has the following type:func : (’a -> ’b) * (’c * ’c -> ’a) * ’c -> ’bYou may check your answer using your computer, but make sure you can do itwithout this
View Full Document
Unlocking...