These are some of the programming languages portions of old MSCS comprehensive exams. See the file "read-me.txt" for more information. M.S. Computer Science Comprehensive Exam - Fall, 1989 SYNTAX AND SEMANTICS OF PROGRAMMING LANGUAGES Do four of five. Each problem is worth 25 points. 1) a) Describe the dangling-else problem in defining the syntax of a programming language. Describe how the problem is solved in Pascal and Ada. b) Rewrite the following BNF for expressions to agree with the APL rules of precedence and associativity: all oper- ations have the same precedence and are right associative. ::= + [ ::= * | ::= ( ) [ NUMBER 2) What is meant by binding? Describe three possible pieces of information that might be bound to a variable, and when these bindings might occur. Pick two programming languages you know and describe the variable binding conventions they possess. 3) In the management of a dynamic storage area such as a "heap", two problems that occur are dangling references and garbage. Describe the difference, and write two Pascal procedures, one which generates garbage and one which generates dangling references. Describe a method for preventing dangling references and a method for performing garbage collection. 4) a) Describe the difference between structural and name equivalence of data types. b) Given the following code (in Pascal form), state which variables are type equivalent under name and structural equivalence, and why: type table = array [1..10] of integer; table2 = table; var x,y: array[1..10] of integer; z: table; w: table2; 5) What is a coroutine? Describe an implementation for the activation of a coroutine. What restrictions, if any, are necessary for this implementation to work? Describe the steps necessary for the execution of a resume instruction. M.S. Computer Science Comprehensive Exam - 2-25-89 Syntax and Semantics of Programming Languages Do 4 of 5 problems. Each problem is worth 25 points. 1. Use the following grammar to answer the questions below: := or | := and | := not | ( ) | true | false a) Rewrite the grammar using syntax diagrams. b) From the syntax diagrams, write procedures to parse the grammar by recursive descent. You may assume that a procedure GetToken puts the next lexical unit from the input file into the global variable 'Token.' State any other assumptions that you make. c) Revise the original grammar so that or and and have the same precedence. 2. a) The solution to the Producer-Consumer problem given below contains an error. How does the system behave? mutex := 1; recin := 0; space := buffersize procedure Producer procedure Consumer while more input records do begin read a record loop wait(space) wait(recin) wait(mutex) wait(mutex) write a record into buffer read a record from buffer signal(mutex) wait(mutex) signal(recin) signal(space) repeat output record end repeat end b) Briefly describe and compare these other methods of concurrency:. i) message passing ii) monitors iii) tasks in Ada 3. a) What is an abstract data type? b) Compare the data abstraction facilities of Simula 67 and those of Ada (or Modula, or Modula-2). How does each separate specification from implementation? Is it possible to create several objects of an abstract data type? c) Give an abstract (algebraic) specification for the abstract data type Stack. 4. a) Describe four methods of parameter passing. Give an example of a language using each. b) Show the output of the program below using each method. program params(input, output); var i : integer; a : array[1..2] of integers- procedure p( x,y : integer); begin x := x + 1; i := i + 1; y := y + 1; end; begin { main progam } a[l] := 1; a[2] := 1; i := 1; p(a[i],a[i]) ; writein(a[l]) ; writeln(a[2]) ; end, 5. a) What is a functional programming language? How does it differ from an imperative language? b) Define scope and extent and distinguish between them. Give an example of a language in which they differ and an example of a language in which they are the same. c) Define aliasing and side effects and distinguish between them. Give an example of each. M.S. Computer Science Comprehensive Exam Syntax and Semantics of Programming Languages Do 4 of 5 1) Give as many examples as you can of tradeoffs between speed and flexibility in the design of programming languages. 2) What is the difference between information hiding and encapsulation? What are the advantages and disadvantages of each? 3) What is the difference between call by value, call by reference, and call by name? Describe at least one implementation of each. 4) What are the difficulties in implementing a top-down parser? How can these difficulties be overcome? Are there any remaining difficulties in your proposed solution. 5) What is the difference between static and dynamic non-local referencing? Under what situations is each appropriate for a programming language? Describe two possible implementations of each. Programming languages Do 4 of 5 1. There are a number of complications to the translation of even as simple an expression as X+Y in a compiled language. What are some of those complications? Do the same complications arise when interpreting instead of compiling? 2. What problems would be involved in interpreting Pascal or Ada instead of compiling it? What about compiling APL or Lisp instead of interpreting it? 3. Choose several high-level languages and discuss how well abstract data types can be implemented in each language. 4. What is aliasing? What problems can arise as a result of aliasing? 5. Discuss the restrictions on languages and grammars required for various parsing strategies (e.g., top-down, limited lookahead, no backtracking). MASTERS COMPREHENSIVE EXAMINATION PART IV: COMPILERS [S83] l. Descrlbe in general terms at what stage and how a compiler translates source code into intermediate code. Why is this done? 2. Design a grammar for a replacement statement language that contains these binary operators: + - * / ^ AND OR := and parenthesizing. The precedences are highest: AND OR ^ * / (* and / have equal precedence) + - (+ and - have equal precedence) lowest: := Also ^ and := are to associate from right to left; all the other operators are to associate from left to right. Justify your design using a parse tree. 3. a) Define a SELECTION SET of a production. b) Suppose all sentences of a language L end with $, and L follows a context-free grammar G whose productions are: E -> ES ES -> AS T ES | epsilon T -> F TS TS -> MD F TS | epsilon F -> [ E ] | a | b | c | d AS -> + | - MD -> * | div Find the selection set of each production. 4. Under the grammar G, defined in problem 3, show that the expression a + [ b div c ] * d is derivable starting from E. At each step of the derivation you must show the contents of the push down automaton stack.