CS2111 Exam January 1998 - Answer question 1 in Section A and two questions from Section B

Section A - Answer Question 1

Q1. a) The following Yacc-like grammar describes a boolean expression (exp) consisting of operators "&", "|", "!", "==", "!=", brackets "(" and ")", and identifiers.

	exp   : exp_2 | exp '&' exp_2 ;
	exp_2 : exp_3 | exp_3 '|' exp_2 ;
	exp_3 : exp_4 | exp_4 '==' exp_4 | exp_4 '!=' exp_4 ;
	exp_4 : exp_5 | '!' exp_5 ;
	exp_5 : identifier | '(' exp ')' ;

What is meant by the precedence and associativity of operators? [2 marks]

Write down the precedence and associativity that this grammar gives to each of these operators and to brackets, and explain how the precedence and associativity is encoded in the grammar. (Note that the grammar does NOT necessarily give the operators the same precedence and associativity as in C.) [6 marks]

Give example expressions that unambiguously demonstrate the precedence and associativity of each of these operators, by showing the order in which the operators in them would be evaluated. Give the parse trees for each of your example expressions. [6 marks]

b) Write Lex and Yacc code to recognise a series of expressions, each on a new line. Each expression is as described in part (a), but you must rewrite the grammar to use "%left", "%right" and "%nonassoc" to give associativity and precedence to all the operators. Identifiers are as defined in C. Any white space (space, tab or newline) separates tokens and, apart from newlines, can otherwise be ignored.

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. [6 marks

Section B - Answer TWO questions

Q2. The phases of a typical compiler are lexical, syntactic and semantic analysis, and code generation and optimisation. Explain in detail how the following fragment of ANSI C code is processed in each phase. You should include a description of any intermediate forms or other data structures it may be transformed into, such as lexemes, parse trees and the dictionary. [20 marks

	float a, b, c;

	void f (int a, e)
	  float c, d;
	  a = a + e;
	  c = a + b;
	  b = c * a * d;

Q3. Answer TWO of the following, giving examples where appropriate. Each part is worth 10 marks:

a) Describe the various methods for passing function parameters found in computer languages, including call by value, by reference, by copy/copy back, by procedure and by name. Give an example of each, to show how it differs from the others.

b) What is meant by the "scope" and "extent" of declarations? Give examples of as many different kinds of scope and extent found in computer languages as you can, including those for Abstract Data Types (also known as modules or objects).

C) In what ways do the integers and reals (floats) found in imperative programming languages usually differ from the corresponding mathematical concepts?

What is strong typing, and what are the advantages claimed for it? Describe the different kinds of user-defined primitive (scalar, simple) types found in programming languages, such as enumerations and subranges, giving examples of each. Compare the usefulness of these types in strongly typed languages and in languages with no type checking.

Q4. Answer TWO of the following, giving examples where appropriate. Each part is worth 10 marks:

a) Some programming languages are described by an ambiguous grammar, requiring extra rules to resolve the ambiguity. For example, a common problem is the "dangling else". Explain what is meant by this, giving the ambiguous grammar rule(s) and an example program fragment. Explain the extra rule needed to resolve the ambiguity, and show how it applies to your program fragment.

How does yacc warn the user when it detects an ambiguity in a grammar, and how does it attempt to resolve it? In particular, what happens in the case of the dangling else? Briefly outline how to check the output from yacc to make sure that you understand the source of the ambiguity.

Show how the problem of the dangling else can be resolved by changing the design of the programming language.

b) Describe two significant ways in which the programming language ANSI C could be improved, other than by simply removing the dangling else, giving examples.

Explain either why it would or why it would not be possible and/or sensible to implement each of your improvements by using a pre-processor to convert programs in your version of C back to ANSI C.

c) For each of arrays, records (structs), unions, and pointers, describe one significant way in which their declaration and/or use can differ between different programming languages. For each data structure, give an example of both versions and state their relative advantages and disadvantages.

For ONE of these data structures, describe how the run-time implementation of the two versions will differ, and describe any corresponding changes necessary in the compiler.