CS 415 Midterm Exam – Spring 2002ScoreTotalproc firstCS415 Anderson – Spring 2002 Page 1 of 10 CS 415 Midterm Exam – Spring 2002 Name ________________KEY __________________________________ Email Address _________________ Student ID # ___________________ Pledge: This exam is closed note, closed book. Good Luck! Score Fortran Algol 60 Compilation Names, Bindings, Scope Functional Programming Total /100CS415 Anderson – Spring 2002 Page 2 of 10 Fortran (10 points) 1. [5 points] Describe how common blocks allowed the sharing of information. What were the drawbacks of using common blocks. Was there any other way to share information in Fortran? Common Blocks allowed subroutines to share access to the same block of memory. In this way values stored in that memory were shared between subroutines. A drawback to the use of common blocks was that although each subroutine explicitly “imported” the common block, each subroutine was allowed to create its own names for that memory. This could cause aliases, as in the case below where the first location in /stuff/ is referred to as the int I in subroutine A, but as the real values(1) in subroutine B. subroutine A(n) common /stuff/ i, values(100), j subroutine B(n) common /stuff/ values(100), i, j Another way of sharing variables is by passing parameters, as could be done using the parameter n and m above – the same value could be passed to each subroutine. 2. [1 point] Fortran was originally proposed by __John Backus at IBM ___ 3. [4 points] Describe the design of Fortran. Why did it turn out like it did? What were the constraints? In your opinion was it a success or a failure? Why or why not? Fortran was based on the assembly language of the IBM 704. As a result, many of the instructions in early Fortran were merely another way of saying a particular assembly instruction – rather than a language design focused on appropriate constructs for expressing algorithms. One of the main constraints was that a compiler for the language had to produce code that would be competitive with hand-coded assembly programs. Other constraints include small memory sizes at the time, which lead to space-saving techniques that re-used memory such as common blocks and equivalences. Success – still used today, served as a proof of concept for other high level languages and compilers, with all its faults it was still an improvement over writing assembly code directly. Algol 60 (10 points) 1. [3 points] What does BNF stand for? When specifically was it first introduced? What is it used for? Backus-Naur Form was originally introduced in the Algol 60 Report. It is used to specify language syntax.CS415 Anderson – Spring 2002 Page 3 of 10 2. a) [3 points] List the three storage allocation areas where values are typically allocated in memory. (Another way of saying this is to list three storage management mechanisms.) (hint: you learned this in cs201) stack, heap, static or global area b) [3 points] Early versions of Fortran allocated all of its variables in only one of these areas. Algol 60 made use of an additional area that was not used in Fortran. List two new features of Algol 60 that forced it to allocate variables in this area. Which area was it? Early versions of Fortran did not have recursion so variables were allocated statically. Algol 60 introduced recursion and dynamically-sized arrays which made use of the stack. 3. [1 point] Give a one-sentence description of own variables in Algol 60? Local variables that retain their value between procedure calls, similar to static variables in C++. Compilation (30 points) 1. [10 points] List the phases a typical compiler uses in converting a program into assembly language. Indicate what is passed from one phase to the next. I would expect you to have at least 5 phases. character stream ! Scanner (Lexical Analysis) ! token stream ! Parser (Syntax Analysis) ! parse tree (concrete syntax tree) ! Semantic Analysis & ! abstract syntax tree intermediate code generation or other intermediate form ! Machine-Independent Code ! modified intermediate form Improvement (optional) ! Target Code Generation ! assembly code or other target language ! Machine-Specific Code ! modified target language Improvement (optional)CS415 Anderson – Spring 2002 Page 4 of 10 2. [3 points] Give two advantages and two disadvantages of interpretation (as compared to compilation). What is an advantage of compilation over interpretation? Advantages of Interpretation: more flexible, better error messages, good for rapid response (no compilation) Advantages of Compilation: better performance 3. [3 points] What would the tokens be in the following statement: if (a < 5) then b = a IF LPAREN ID(A) LT NUM(5) RPAREN THEN ID(B) ASSIGN ID(A) 4. [4 points] What does lex take as input? What does it produce? What does yacc take as input? What does it produce? regular expressions ! lex ! scanner context free grammar ! yacc ! parser 5. [3 points] Write a regular expression for an unsigned integer. (It is o.k. for an unsigned integer to begin with one or more zeroes.) [0-9]+CS415 Anderson – Spring 2002 Page 5 of 10 6. [4 points] Do a top down leftmost derivation of the following string given the grammar listed below: a = b * (c + a) (For partial credit do any sort of derivation.) Write each step in the derivation on a separate line. Be careful not to skip any steps! S ! ID = E ID ! a | b | c E ! E + E | E * E | ( E) | ID S ! ID = E ! a = E ! a = E * E ! a = ID * E ! a = b * E ! a = b * (E) ! a = b * (E + E) ! a = b * (ID + E) ! a = b * (c + E) ! a = b * (c + ID) ! a = b * (c + a) 7. [3 points] Is the grammar from above ambiguous or not? Why or why not? If it is ambiguous, give an example. Yes. An expression such as: a + b * c can generate two different parse trees: + * / \ / \ a * + c / \ / \ b c a bCS415 Anderson – Spring 2002 Page 6 of 10 Names, Scopes, and Bindings (20 points) 1. [1 point] Define scope the textual region of a program where a binding is active 2. [2 points] Define static scoping vs. dynamic scoping. static scoping – scope defined in terms of physical (lexical) structure of