Languages and Translation cs 362 Exam 1 Fall 2015 10/1/15 (100 points) Name

Languages and Translation

CS 362 Exam 1

Fall 2015 10/1/15 (100 points)

Name _________________________________

1. 
   True/false on programming languages basics, etc.
   

[10 pts]

_____ Languages are designed for two audiences: the computer system and the human programmer.

_____ Computer languages fall into the regular expression language category only.

_____ The object-oriented paradigm is inclusive of procedural and much of the functional paradigms.

_____ Functional language paradigm is not concerned so much with the state of the machine.

_____ Turing complete languages minimally include sequential and selection structures.

_____ Turing complete languages minimally require integer arithmetic and strings and dates.

_____ The logical language paradigm expresses more about how something is done than just declaring what needs to be done.

_____ Church’s thesis states that it is not possible to build a machine inherently more powerful than a Turing machine.

_____ The Java language’s virtual machine supports the compile-once, run-anywhere feature.

_____ Most computer languages today have elements of the Algol language.

2. 
   True/false on variables: /*C++*/ int m=5; int * x = &m; //
   

[8 pts]

_______ The both statement are both declarative and imperative.

_______ The r-value of x is the l-value of m.

_______ The l-values of both x and m are bound at runtime.

_______ The constant 5 theoretically has only an r-value.

_______ The identifier x is a pointer to an integer.

_______ The notation *x is a pointer to an integer.

_______ The output of cout << x; would print 5.

_______ Variables x and m are aliases.

3. 
   The number of lexical tokens in the C++ statements in question #2 that would be passed to the parser: ________.
   

[4 pts]
List the first two tokens of the line: _____________ and ___________. The last token is _____________

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

[4 pts]

_______________________________________ _____________________________________

_______________________________________ _____________________________________

5. 
   Language design criteria.
   

[10 pts]

a. Explain how Pascal meets “readability” criterion. [3]

b. Name a language that could be claimed as “writable”. Why? [2]

b. Explain the “orthogonality” programming design criterion by discussing two features of Java and how they are or are not orthogonal. [5]

6. 
   Draw a 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.
   

[7 pts]

Semantic analysis Optimization Code generation

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

Symbol table

7. 
   Back ends and front ends.
   

[3 pts]

If we want to alter a great compiler to accept a different high level language, what module(s) above would need to be rewritten?

Which module(s) would we need to change to cross compile to a different machine?

8. 
   Types and subtypes.
   

[12 pts]

1. 
   What are two major aspects that define a data type?
   
   
2. 
   Give two advantages of a strongly typed language?
   
   
3. 
   Give two advantages of being able to specify a subtype.
   
   
4. 
   What is coercion? Give an example.
   
   

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

PROGRAM M; Real a,c,x; .... PROCEDURE P(Int a,c); .... END P; PROCEDURE Q(Real x); Real c; .... PROCEDURE R(Int a); .... 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. [7 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

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

[25 pts]

S V := E

E E + T | T

T T * F | F

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

1. 
   The alphabet or set of terminals is ____________________________________ [3]
   
2. 
   The set of nonterminals is ___________________________________ [3]
   
3. 
   The start symbol is ____________ [2]
   
4. 
   Show a top down, left-most derivation for j := i *( k + 1 ) starting with the start symbol. [5]
   
5. 
   Draw the corresponding parse tree. [5]
   

Top Down Derivation	Parse tree

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. [7]

j := i * ( k + 1 )

Stack	Input remaining	Shift or Reduce	Rule used in reduce
$ j	:= i * ( k + 1 )	Shift
$ V	:= i * ( k + 1 )	Reduce	V-> j
$ V :=	i * ( k + 1 )	Shift

11. 
    Consider the language of US phone numbers. The format can be 800-555-1234 or (800)555-1234.
    

[12 pts]

a) Give a regular expression to define this language of phone numbers. Hint, it may be easier to do the FSM first. [5]

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

c) Write a corresponding BNF grammar [3]

FSM	BNF

Directory: faculty -> rhodes
faculty -> Course overview
faculty -> Curriculum vitae wei chen professor
faculty -> Digital image warping
faculty -> Samples of Elements Exam Question III contains All Prior Exam Qs III except
faculty -> 【Education&Working Experience】
faculty -> References Abe, M., A. Kitoh and T. Yasunari, 2003: An evolution of the Asian summer monsoon associated with mountain uplift —Simulation with the mri atmosphere-ocean coupled gcm. J. Meteor. Soc. Japan, 81
faculty -> Ralph R. Ferraro Chief, Satellite Climate Studies Branch, noaa/nesdis
faculty -> Unit IV text: Types of Oil, Types of Prices Grammar: that/those of, with revision
rhodes -> Languages and Translation cs 362 Exam 1 Fall 2003 9/25/03 (100 points) Name
rhodes -> Languages and Translation cs 362 Exam 1 Fall 2015 10/1/15 (100 points) Name key