DOC PREVIEW
UVA CS 415 - CS 415 Midterm

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 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 9 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 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS415 Anderson – Spring 2005 Page 1 of 9 CS 415 Midterm Exam – Spring 2005 - SOLUTION Name _____________________________________________________ Email Address _________________ Student ID # ___________________ Pledge: This exam is closed note, closed book. Questions will be graded on quality of answer. Please supply the best answer you can to each question. Good Luck! Score Fortran & Algol 60 Compilation Names, Bindings, Scope Functional Programming Total /94CS415 Anderson – Spring 2005 Page 2 of 9 Fortran and Algol 60 (28 points) 1. [2 points] Early Fortran had recursion. TRUE or FALSE (circle one) 2. [4 points] What effect did your answer to question #1 have on the implementation of Fortran? No recursion meant that there would only be one instance of a subroutine/function active at a time. So local variables could be stored in a fixed location – did not need to use the stack to allocate local variables. 3. [4 points] a) Describe the scoping rules in Fortran. global scope and for variables local to a subroutine, local scope. b) Fortran had: static scoping or dynamic scoping (circle one) 4. [8 points] a) Describe how call by name worked. foo(int x) { print x i = i +1 print x } int i = 0; call foo (A[i]) Every time the formal parameter x is accessed inside of foo, the actual parameter, in this case A[i], is re-evaluated. In this example first A[0] will be printed, then A[1]. One way of thinking of this is as if the body of the subroutine foo was pasted into the call site with all the occurrences of x replaced by A[i]. b) Give the name of AND describe the technique used to implement call by name. Call by name was not implemented with the cut and paste method described above, instead a thunk – an anonymous procedure, was used. When the parameter was needed inside of a procedure, the thunk was called to get the correct address.CS415 Anderson – Spring 2005 Page 3 of 9 5. [4 points] a) Describe the scoping rules in Algol 60. Algol 60 allowed nested scopes. You could nest procedures or blocks. You resolved a reference by looking for the closest nested scope. Nested scopes in Algol 60 were also an example of an open scope, variables did not have to be explicitly imported in from other scopes. b) Algol had: static scoping or dynamic scoping (circle one) 6. [6 points] In Algol 60, when did binding of names to memory locations occur? on entrance to a procedure/block What effect does this have on memory management? Arrays were allowed to have varying size, and thus their storage needs could not be known at compile time. Arrays (and other local variables) were allocated on entrance to a procedure. A stack was used to allocate local variables, which allowed efficient re-use of memory. (As opposed to the error-prone methods of re-use in Fortran – equivalence, and re-use of memory in common blocks for multiple purposes.)CS415 Anderson – Spring 2005 Page 4 of 9 Compilation [24 points] 1. [6 points] Describe what happens during the scanning phase of a compiler. (what is the input, what is the output, what happens inside). The scanning phase (lexical analysis) is the first phase of compilation. A stream of characters is provided as input, and a stream of tokens is produced as output, often a token at a time as the parser requests a token. The scanner attempts to recognize the characters passed in according to the regular expressions used to specify the tokens in the language. Other tasks performed during scanning include the removal of whitespace or comments and the recognition of keywords. 2. [2 points] What is the principle of longest match? Give an example? When scanning, recognize the longest sequence of characters that can be recognized as a token. For example, when seeing != in the code, the scanner should recognize this as a NOTEQUAL token as opposed to a NOT token followed by an EQUAL token. 3. [6 points] Why are compilers often separated into a front end and a back end? The front end is generally thought of as machine-independent. The back end is thought of as containing features that apply to a particular hardware platform. Thus by separating a compiler into a front end and a back end, you can retarget your compiler to a new platform by merely re-writing the back end. Similarly you could write a front end for a new language and have it use an already existing back end for a particular platform. In general what is the purpose of the front end? Take a stream of tokens and convert it to an intermediate format (IR). The front end does analysis, attempting to understand the structure and meaning of the program. Generally scanning, parsing, and semantic analysis/IR generation/machine independent optimization are considered part of the front end. In general what is the purpose of the back end? Take a program in intermediate format and convert it into the target language (often this is the assembly language of a particular machine). Machine specific optimization and code generation are considered part of the back end. 4. [2 points] A pushdown automata is to a _context free grammar_ as a finite automata is to a regular expression.CS415 Anderson – Spring 2005 Page 5 of 9 5. [4 points] Write a regular expression for an identifier in the cs415 language. Identifiers must start with cs415, followed by one or more upper or lowercase letters. The c and the s in cs415 can be either upper or lowercase. Examples of valid identifiers include: “CS415rocks” and “cS415isEARLY”. [Cc][Ss]415[A-Za-z]+ 6. [4 points] Draw a finite automaton for the regular expression you gave in the previous question above. Be sure to properly denote the accepting states.CS415 Anderson – Spring 2005 Page 6 of 9 Names, Scopes, and Bindings (18 points) 1. [6 points] What does the function test print if the language uses static scoping? What does it print with dynamic scoping? (otherwise assume C++ syntax and semantics, e.g. call by value). int n = 1; // global print_plus_n(int x) { cout << x + n; } increment_n() { n = n + 2; print_plus_n(n); } test() { int n; n = 200; print_plus_n(7); n = 50; increment_n(); cout << n; } With Static Scoping: 8 6 50 With Dynamic Scoping: 207 104 52CS415 Anderson – Spring 2005 Page 7 of 9 2. [2 poinst] Define: referencing environment The set of bindings in effect at a given


View Full Document

UVA CS 415 - CS 415 Midterm

Download CS 415 Midterm
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 CS 415 Midterm 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 CS 415 Midterm 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?