DOC PREVIEW
UA CSC 520 - Midterm Exam

This preview shows page 1 out of 3 pages.

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

Unformatted text preview:

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

UA CSC 520 - Midterm Exam

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Midterm Exam
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 Midterm Exam 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 Midterm Exam 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?