CS 362 Fall 2017 Exam #1 Page 5

Languages and Translation

CS 362 Exam 1

Fall 2017 9/28/17 (100 points)

Name ______

  1. Fill in the blanks on programming languages basics, etc.

[10 pts]

Programming languages are designed for two audiences, the computer and the ______. Computer languages fall into the ______grammar/language category. Procedural, ______, and ______are 3 of the 4 language paradigms. Turing complete languages minimally require, among others ______and ______structures and ______arithmetic. Church’s thesis states that it ______(is/isn’t) possible to build a machine more powerful than a ______machine. Of the earliest languages (pre- 1960), ______probably has the most elements still in today’s languages.

2.  Tokenizing, binding, etc.: /*C++*/ double s = 3.14; double * p = s; // initialize

[8 pts]

a.  What parts of the statement above are declarative? Draw boxes around that code.

b.  What parts of the statements are imperative? Draw circles around that code. Overlap is ok.

c.  The r-value of s is ______; the r-value of p is the ______of s ; the r-value of *p is ______

d.  The number of lexical tokens in all of the code above that the parser receives is ______

e.  The first two tokens are ______and ______; the last two tokens are ______and ______.

  1. Language design criteria.

[9 pts]

a.  Choose a language other than Java and compare its designed readability to Java. Clearly make your case with several examples from the language. [3]

b.  How is Java extensible? Give examples. [3]

c.  If a language’s features are fully orthogonal by design, what problems can you envision in learning or using such a language? Give a couple examples. [3]

  1. We have seen a number of uses for user-defined identifiers in a language. List 4 different uses.

[4 pts]


______

______

5.  Draw a flow diagram that connects these 7 modules of a compiler by the theoretical data flow of data. Label the flow lines with the content of data that are streamed from one stage to the next.

[8 pts]

Semantic analysis Optimization Code generation

Syntactic analysis (parser) Intermediate code generation Lexical analysis (scanner)

Symbol table

  1. In the above diagram, draw a box around the front end elements. Similarly draw a circle around the back end elements.

[3 pts]

  1. Binding.

[6 pts]

a.  Name three static bindings that can be made to an identifier. Name your language of reference.

b.  Name two dynamic bindings that can be made to an identifier. Name your language of reference (can be different from a).

  1. Static and dynamic scoping. Base your answers on the module nested Algol-like program below.

PROGRAM M;
Real a, x;
....
PROCEDURE P(Int c);
....
END P;
PROCEDURE Q(Real x);
Real a;
....
PROCEDURE R(Int c);
....
END R;
....
END Q;
....
END M; / a) Assume static scoping rules and that each module refers to a, c, and x. Fill in the table such that for each module show from which module each referenced identifier is declared.
[6 pts]
a c x
M
P
Q
R

[6 pts]

b) Assume dynamic scoping rules and that each module refers to a, c, x. Fill in the table such that for each called module show which module each referenced variable is declared.
a c x
M calls P
then P calls Q
then Q calls R
then R calls P
  1. Symbol tables. For each of the scenarios in a strongly typed language, what is outcome? Write OK or Error.

[4 pts]

______First encounter of an identifier and the compiler is in declaration mode.

______Second encounter of an identifier and the compiler is in declaration mode.

______The second encounter of an identifier and the compiler is in imperative mode.

______The first encounter of an identifier and compiler is in imperative mode.

  1. Assume the set of productions representing simple algebraic expressions.

[24 pts]

S ® V = E

E ® E + T | T

T ® T * F | F

F ® V | ( E ) | 0 | 1
V ® i | j | k

a)  The alphabet or set of terminals is ______[3]

b)  The set of nonterminals is ______[3]

c)  The start symbol is ______[1]

d)  Show a top down, left-most derivation for i = (j + 1) * k starting with the start symbol. [5]

e)  Draw the corresponding parse tree. [5]

Top Down left-most Derivation / Parse tree
S ->

f) Show the sequence of bottom up parser actions (shift and reduce) for the same above input that ultimately leads to the start symbol. It is started for you. Continue on the back of this page or previous one. You may have to guess at a stage or two and backtrack to lead to the correct shift reduce sequence. [7]

i = (j + 1) * k

Stack / Input remaining / Shift or Reduce / Rule used in reduce
$ i / = (j + 1) * k / Shift
$ V / = (j + 1) * k / Reduce / V-> i
$ V = / (j + 1) * k / Shift
  1. Consider the pattern of email addresses. The format can be in, where computer is optional. Assume all 4 names can include letters, digits, ‘.’ and ‘_’. Don’t worry about obscure variations either!

[12 pts]

a)  Give a regular expression to define this language of email addresses. It may be easier to do the FSM first. You may define some additional, simplifying regular expressions to make categories for your final expression. [5]


______

b)  Draw an equivalent FSM for this regular expression [4]

c)  Write a corresponding BNF grammar from your FSM [3]

FSM / BNF