CS2112 Exam June 1995

(I have reworded the questions slightly.)

Answer any 3 questions

Question 1

a) Design a grammar to describe a boolean expression consisting of the C-like operators "^", "&", "|", "&&", "||", "!", "==", "!=", "~", the conditional operators "?" and ":", and brackets "(" and ")". The only operands are C-like identifiers (including the constants "TRUE" and "FALSE").
Write the grammar in any convenient version of BNF or EBNF. Clearly state the precedence, associativity and number of operands you have given to these operators and explain how your grammar contains this information.
[5 marks]

b) Write Lex and Yacc code to recognise a series of expressions separated by semicolons, each expression as described by your answer to part a. You should not try to evaluate or translate the expressions. You do not need to give code for common routines such as yywrap, yyerror and main. (If any significant part of your answer is unchanged from part a, you do not need to repeat it.)
[5 marks]

c) As the language includes identifiers, you may need to process them further. Under what circumstances would you need to use a dictionary in:
* a translator, that converts the input to another form
* an interpreter, that obeys the input
Briefly describe a typical implementation of the name-list part of a dictionary and show how you would interface it to the code in your answer to part b.
[5 marks]

d) The design of this little language of boolean expressions has several defects (for example, it has no mechanisms for binding meanings to identifiers). How would you improve it?
[5 marks]

Question 2

a) What is meant by the "scope" and "extent" of identifiers, such as variables?
[4 marks]

b) Describe how TWO of the following high-level imperative languages control the scope and extent of identifiers and variables:
[16 marks]

Question 3

a) Describe two significant ways in which the programming language ANSI C could be improved, giving examples. (would these improvements require any other compensating changes in ANSI C?)
[6 marks]

b) What would be the advantages and disadvantages of making these changes in a new version of C.
[3 marks]

c) You have been asked to create a translator that can convert your version of C to the current version of ANSI C. What would be the advantages and disadvantages of using:
* Cpp only (i.e. #define, #if, #include etc.)
* Lex only
* Lex and Yacc together
You may assume that fragments of C code may be used as necessary in any of the three alternatives.
[6 marks]

d) Pick ONE of the three alternative implementation methods in part c that you consider to be most appropriate, and briefly describe how you would implement the translator.
[5 marks]

Question 4

Write brief notes about THREE of the following, giving examples where appropriate (each is of equal weight):
[20 marks]

a) We can create various data structures using pointers (and structures and unions etc.) in ANSI C, and using recursive data types in a language like SML. Give an example of list creation in both styles. What other operations are possible on pointers in ANSI C? What is it about ANSI C that makes automatic garbage collection very difficult, if not impossible?

b) Describe Dijkstra's three mechanisms for composing programs. Can they be used to represent any program structure, and if so at what cost? How are these three mechanisms represented in ANSI C programs? What are repeaters and completers, and how are they represented in ANSI C programs? What other mechanisms are found in imperative languages to direct the flow of control?

c) Describe the legal forms and meanings of one-dimensional and multi-dimensional array declarations and accesses in ANSI C. How does this differ from the declaration and use of arrays in other imperative languages?

d) Describe the various methods for passing function parameters found in imperative languages, including call by value, by reference, by copy/copy back, by procedure and by name. Which of these mechanisms are actually present in ANSI C, and which can be simulated?