iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiProb 1 2 3 4 ΣiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiMax 25 25 25 25 100iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiScoreiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiccccccccccccccccccccccccccccccccccccccccccCSc520 midterm exam 27 March 2006DUE Monday 3 April in classInstructions: Do all the problems.NAME____________________________________GRADE_________Submit your solutions using a typesetting program such as TeX or troff, that is capable of handling appropriatetype faces and equations. Start each solution on a new page, identify the problem clearly, and number eachpage. Use one side of the paper only. Submit answers in the envelope provided.Clarity and conciseness will earn points, so revise your work before submission, and consider how your work ispresented.Some problems require you to describe syntax or semantics of a language. Your syntactic/semantic descriptionsshould include thorough comments to explain the ideas behind each specification in clear technical English; theexistence of a formalism does not relieve you of this responsibility, any more than it does in writing code.When precise semantics is called for, divide your solution into (1) syntax changes (2) semantic domain changes(3) semantic function changes. Under (1), describe any contextual constraints (static semantics) informally—there is no need to formalize these. Under (3), give signatures for all semantic functions and auxiliary functionsintroduced.Important: You are reminded of the provisions regarding academic dishonesty in the Code of AcademicIntegrity, and in the syllabus of this course. Work in this course is to be done by individuals only, not ingroups. The sharing of answers from another student in this course, or from another student with notes fromearlier versions of this course, is prohibited. All work is expected to be that of each student alone, without con-sultation with others, and not the product of team efforts or collaboration with other authors. Plagiarism or theincorporation of another person’s words or ideas constitutes theft of intellectual property, and will be dealt withas such. Use of a current or previous student’s notes, solutions or materials is a prohibited activity.1. Pointers in IMPWe want to add pointers to the imperative language IMP (Example 3.6, p. 66 of the Watt text, called IMP0inclass). The new language will be called IMPp. To this end, we change the syntax of the language as follows:1. The following productions for Expression are added to allow the creation and use of pointers. Thebehavior of these constructs is as in C:Expression ::=. . .| & Identifier| * Identifier2. The following production for Command is added to allow assignments through pointers:Command ::=. . .| *Identifier := Expression3. The syntax and semantics for declarations must be changed to allow the declaration of pointers—this ispart of the problem posed below.Pointers follow the following rules and restrictions:(i) A pointer can be stored in a location. Thus, the following program is legal (assuming the appropriatedeclarations), and should assign to the location of w the value 2.mid - 1 -let ... inx := &y ;*x := 1 ;w := y + *x ;(ii) Only expressions that denote locations may be assigned to. Thus, the following is illegal (you need toconsider only legal programs):let const x ˜ 10 in *x := 1 ;(iii) The only pointer arithmetic that is permitted is the adding of an offset to a pointer value. The follow-ing is legal, assuming p is of type ‘‘pointer to integer’’ and y is of type ‘‘integer’’.let ... in p := &y + 3 ;(a) Provide any further extensions of the language syntax needed, including the extended syntax of declarationsand expressions. Allowance must be made for pointers to integers as well as pointers to booleans.(b) Give all required semantic domains for this language, and explain how such domains have been changedfrom IMP0to accommodate pointers in IMPp.(c) Provide signatures for all semantic functions, and explain how they have changed from those for IMP0.(d) Provide all needed semantics for this extension of IMP0. Give only the extensions that are necessary toaccommodate the new syntax.2. Denotational Semantics of caseAdd the following case control structure to the language IMP (use the simplest IMP, called IMP0in class andfound in Watt, Example 3.6)The command case E of N1:C1;. . .; Nn:Cnend has the effect of executing whichever subcom-mand Ciis labeled by a numeral Niwhose value matches the (integer) value of E. In the absence of such amatch, the case command executes a skip.(a) Describe an abstract syntax for this extensionCommand ::= ... |(b) What are the contextual constraints, if any?(c) Give the semantic function or functions for handling this construct. Your semantic functions must use recur-sion, and should not have an ellipsis (. . .) anywhere in them. (See comments on this subject in Homework4).(For simplicity, do not extend the language to accommodate a break command.)(d) Describe in words what your semantics implies is the meaning of a case when the value of E matchesmore than one of the Nivalues. Your semantics should always give an unambiguous result, and differentreasonable possibilities exist. State what your semantics in (c) does, and explain why.(e) In some programming languages, such as C, after the code for one of the cases is executed, control ‘‘fallsthrough’’ to the following case and continues execution. In other languages, such as ADA, executionresumes at the end of the case command, and skips all other cases. Describe in words what your seman-tics does, and explain how your semantic functions achieve your intended result.(f) Briefly, discuss how the semantics of case would be affected if side-effects were allowed in expressionevaluation. (Do not give a full semantics, but describe the main difference in the semantics from (c) in anon-formal but clear and precise way).mid - 2 -3. Indexed Loops in IMPMost languages have an "indexed loop" command with a syntax similar tofor j :first, last, step do comm endwhere j is an identifier, first, last, step are integer-valued expressions and comm is an command (which mayinvolve j). Languages differ considerably in the semantics of indexed loops. For example:gIn most languages, the
View Full Document