CSc 262 Test 2 Suggested Answers 1. (20 pts) Suppose that Algol allowed parameters to be passed in three ways, by value, by reference, and by name. What would be the output of the following program if, in procedure M, x is passed by value, y by reference, and z by name? begin integer i; integer array R[6:8]; procedure M(x,y,z); integer x,y,z; begin z:=z+4; print(x); print(y); print(z); i:=i+1; y:=y+1; print(x); print(y); print(z); end R[6]:=1; R[7]:=2; R[8]:=3; i:=6; M(R[i], i, R[i]); ******* prints 1 6 5 1 8 3 print(R[6]); print(R[7]); print(R[8]); print(i); *********** prints 5 2 3 8 R[6]:=1; R[7]:=2; R[8]:=3; i:=7; M(i, R[i], R[i]); ********* prints 7 6 6 7 7 3 print(R[6]); print(R[7]); print(R[8]); print(i); end ********** prints 1 7 3 8 2. (15 pts) a) Given the (extended) BNF equations ::= 0 | 1 | 2 | 3 ::= a | b | c * ::= { | } (the * is a superscript) + ::= { . } (the + is a superscript) which of the following six strings satisfies the syntax of ? 1 a .a .1 .a1a11.ba1 .aaa.ba1022b.11c *******The string .1 is the only one to satisfy b) Write the (extended) BNF equation(s) for strings of decimal digits that must start with three or more 1s two or more 0s and are then followed by any number of pairs of even digits and any number of triples of odd digits in any order. For example, the following satisfy these rules, 1111111467533596828379973 00, 00099724664280, but the following do not, 44777, 144777, 00102. ::= 1 | 3 | 5 | 7 | 9 ::= 0 | 2 | 4 | 6 | 8 * * * * * ::= { 1111 | 000 } { {} {} } 3. (35 pts) Compare and contrast the data structures of Algol and the data structures of Pascal. The three primitives of Algol are REAL, INTEGER, and BOOLEAN, while Pascal has these three, plus the primitive CHAR. Algol has a structured type ARRAY, and a structure STRING which can only be used as arguments to procedures. In contrast, Pascal has a rich collection of structured types, SET, RECORD, POINTER, and ENUMERATION. Both the Algol ARRAY and the Pascal ARRAY let the programmer define both lower and upper bounds for the indices. The Pascal ARRAY is more general than the Algol ARRAY in at least three ways: (1) The indices of an Algol ARRAY are restricted to the integers, while the indices of a Pascal ARRAY can be integers, chars, booleans, elements of an enumerated type, or elements of a subrange. (2) The base type for an Algol ARRAY is restricted to the primitives, while the base type for a Pascal ARRAY may be any structured type. (3) Technically, the Pascal ARRAY is limited to one dimension, while the Algol array can have any number of dimensions, but, in practice, in Pascal the programmer obtains multi- dimensioned arrays by creatings ARRAYs of ARRAYs. While Pascal does not have a STRING primitive, it can create an ARRAY of CHAR which has more flexibility and power than Algol's STRING. Pascal's ENUMERATION types facilitate the writing of readable code, because the programmer can have the values of an enumerated type correspond to the possible values that the variable(s) represent. Similarly, the RECORD type abstracts the collections of heterogeneous data that belong to a given entity. The POINTER allows the dynamic allocation of space. The SET provides a representation that saves space and makes for very fast computations. Algol lacks all these amenities. 4. (20 pts) Compare and contrast the control structures of Algol and the control structures of Pascal. The IF-THEN statements of Algol and Pascal are very similar, except that Algol explicitly resolves the "dangling else" problem by requiring any conditional statement inside an IF-THEN statement be enclosed in a block. Both languages have GO TO statements, but Pascal makes their use quite painful, requiring the declaration of LABELs, etc. Algol has a switch statement, which is an elaboration of the FORTRAN computed GOTO. It is about as clumsy. Pascal has the corresponding CASE statement which is more straightforward, more structured, and more closely abstracts the decision process. For repetition, Algol has the single FOR statement, which has a very elaborate, indeed overly elaborate, syntax meant to cover all kinds of possibilities, and then some. In contrast, Pascal has three structures for repetition, the FOR, WHILE, and REPEAT statements. Each is simple and straightforward to use, each design for a specific purpose. Finally, while Algol passes its parameters to procedures by value or name, Pascal passes its parameters by value or by reference. While pass by name is very powerful, it is much more dangerous to use than pass by reference. Pass by name does allow the easy passing of functions, but Pascal does provide that facility as a separate feature of passing parameters. 5. (10 pts) Compare and contrast the keyword name structure of Algol and the keyword name structure of Pascal. Pascal uses reserved words for its keywords. That is, the given word (independent of the case of the letters) cannot be used for anything else. Algol uses special symbols for its keywords (e.g., boldface, or prefixing #, etc.). The very same words can be used in an Algol program, the compiler distinguishing between words spelled with special symbols and words spelled with normal characters. This can lead to very confusing code.