CS2112 Exam June 1996 - Answer any 3 questions

Q1. The following grammar describes a declaration for a C-like language. It is written in a version of BNF similar to that used with Yacc.

  declaration	: decl_specs declarator ';'
  decl_specs	: decl_spec | decl_specs decl_spec
  decl_spec	: 'static' | 'typedef' | 'char' | 'int' | 'float' | id
  declarator	: '*' declarator | direct_decl
  direct_decl	: id | '(' declarator ')'
		| direct_decl '[' number ']' | direct_decl '[' ']'

a) If we were to consider '*' and '[' ']' to be operators, are they infix, prefix, postfix or something else? Also, what would be their associativity and relative precedence, and what is the relative precedence of '(' ')'?
[3 marks]

b) Rewrite the BNF above for "declarator" and "direct_decl" using the "%left", "%right" and "%nonassoc" facility of Yacc to give the correct associativity and precedence to '*' and to '[' ']'.
[3 marks]

c) Write a suitable piece of Lex code to go with this Yacc, given that "number"s are one or more digits, and "id"s start 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 parts a) and b) of this question, Yacc cannot actually handle predefined words such as 'static' 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.
[10 marks]

d) Suppose we now modify the BNF to be more C-like, by making the "declarator" in a "declaration" optional:

  declaration	: decl_specs declarator ';' | decl_specs ';'
Unfortunately, this makes the grammar ambiguous. Give an example of a "declaration" that can now be parsed in more than one way, and show what the different parses are by giving the corresponding parse trees. You may find the following information from y.output helpful ("." shows the current position in the parse, and ". . ." replaces omitted information):
[4 marks]
  . . .
  state 8
	declaration : decl_specs . declarator ';' (1)
	declaration : decl_specs . ';' (2)
	decl_specs : decl_specs . decl_spec (4)

	id shift 10
  . . .
  10: reduce/reduce conflict (reduce 10, reduce 13) on ';'
  state 10
	decl_spec : id .  (10)
	direct_decl : id .  (13)
  . . .


a) What kinds of data structures are commonly found in general-purpose, imperative programming languages? What are the relative merits of pointers and recursive data structures for more complex data structures? Briefly describe some other kinds of data structures that have been proposed and their advantages and disadvantages.
For each of the common data structures, including pointers, describe one way in which their declaration and/or use can differ in different programming languages and state the advantages and disadvantages of these different versions.
[10 marks]

b) Describe how data structures are processed in the semantic analysis phase of a typical compiler, giving examples.
[10 marks]


a) Describe the different methods for altering the flow of control (control structures) found in imperative programming languages, giving an example of each. Concentrate your answer on fundamentally different methods rather than minor syntactic and semantic differences.
What subset(s) of these do you consider to be essential, and why?
[10 marks]

b) Describe in detail how you would modify the design of ANSI C to include completers and repeaters, giving examples.
What facilities of C might become redundant if it included completers and repeaters, and why? What would be the advantages and disadvantages of removing these redundant facilities from your new version of C?
[10 marks]

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

a) What is meant by the "scope" and "extent" of declarations? Give examples of declarations in any programming languages you happen to know, to illustrate the differences between scope and extent, and the different kinds of scopes and extents used in computer languages.

b) Code generation for expressions, for computers with a set of arithmetic registers.

c) Under what circumstances would you use parse trees? What is meant by "concrete" and "abstract" parse trees? Give as many examples as you can of typical differences between concrete and abstract parse trees.

d) What are Abstract Data Types (Modules)? Give an example of an Abstract Data Type. How do they differ from data types and functions in a language like ANSI C? What are their advantages and disadvantages? What extra facilities are found in Objects (Classes)?