(I have reworded the questions slightly.)
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:
* COBOL
* FORTRAN
* ANSI C
[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?