Q1. The following grammar describes a function declaration for a C-like language and recognises inputs such as:
function float fred (int bert, jim, char first, last);i.e. fred takes two integer parameters, bert and jim, and two character parameters, first and last, and returns a float. The grammar is written in a version of BNF similar to that used with Yacc:
declaration : 'function' type id '(' paramlist ')' ';'
;
paramlist : params | paramlist ',' params
;
params : type id | params ',' id
;
type : 'char' | 'int' | 'float'
;
a) What is the associativity of ',' in the rules for "paramlist" and "params"? Rewrite the BNF above for "paramlist" and "params" using the "%left", "%right" and "%nonassoc" facility of Yacc to give the correct associativity to ','. [3 marks]
b) Write a suitable piece of Lex code to go with this Yacc, given that an "id" starts with an alphabetic character, possibly followed by alphanumeric or underline characters.
Show how you would modify the Yacc code to communicate correctly with your Lex code.
Remember that, although you should ignore this in part a) of this question, Yacc cannot actually handle predefined words such as 'char' without help from Lex, and your answer to this part should take this into account. You do not need to give code for common routines such as yywrap, yyerror and main. [8 marks]
c) Modify your answer to part b) to show how you would build a parse tree for a "declaration". You should give the complete code needed in the actions in your Lex and Yacc code, but you need not write functions to build each node in the parse tree. Give an example of a "declaration" as defined above, and draw the corresponding parse tree that you intend your code to build. [5 marks]
d) Unfortunately, the grammar above is ambiguous - Yacc reports two shift-reduce conflicts (one for each of the alternative rules for "paramlist") when it sees a ','. Suggest how the language (and its grammar), or just the grammar, could be modified to remove the ambiguity. [4 marks]
Q2.a) What is meant by the (static) scope of identifiers and the (dynamic) extent of variables? [2 marks]
b) What are the different kinds of scope and extent in typical computer languages? You should include any relevant details relating to nested and/or anonymous blocks, records (structs) and unions and their component fields, abstract data types (modules), anonymous variables, and the exact start of a scope for an identifier. Illustrate your answer with examples. [10 marks]
c) What are the different meanings of "list" in the following ANSI C program? Is allowing multiple meanings in a single scope like this a good or a bad idea, and why? [4 marks]
typedef struct list *list;
struct list {
int field;
list list;
};
int length (list l)
{
int i= 0;
list:
if (l) {
i++;
l= l->list;
goto list;
} else
return i;
}
d) Describe how the organisation of the data structure(s) that represent a dictionary and the function(s) that access it, in a typical ANSI C compiler, are designed to deal with nested scopes and multiple definitions in a single scope. [4 marks]
Q3.
Describe the different ways in which typical imperative computer
languages provide arrays and strings for use in programs, how these
data structures can be implemented, and the relative merits of the
various alternatives. You should discuss multi-dimensional arrays,
as well as one-dimensional arrays (vectors) and strings. Concentrate
on semantic differences rather than syntactic differences. Illustrate
your answer with examples. Include any relevant details relating to:
declarations, including index types, bounds, and initialisation,
operations applicable to arrays or strings as a whole rather than to
individual elements, including slicing,
type checking, particularly when used as parameters,
bound checking,
call by value and by reference,
how strings may vary in length, and how this length is determined,
when and how the space for the elements of an array is calculated,
and how the address of a particular element is calculated.
[20 marks
Q4. Write brief notes about THREE of the following, giving examples where appropriate (each part is of equal weight): [20 marks]
a) What are Dijkstra's three control structures? Why are they sufficient to represent any program? What other control mechanisms might we want to include in a computer language, and what are the advantages and disadvantages of including them?
b) Describe the variation in the form of expressions found in different programming languages, in terms of fix, number of operands, overloading, precedence, associativity, and evaluation order. Define these terms, and any others that you use, giving example expressions for each.
c) Give examples of, define what is meant by, and explain the advantages and disadvantages of: strong typing, weak typing, name equivalence, structure equivalence, type coercions, widening and narrowing.
d) How do regular expressions, as used with Lex, and BNF, as used with Yacc, represent different forms of choice and repetition in grammar rules? Give examples of how some grammar rules can be translated between the two notations. What are the essential differences between the representational power of the two notations, and what implications does this have for compiler implementation?