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):
. . . 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) . . .
Q2.
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]
Q3.
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)?