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

Languages and Translation

CS 362 Exam 1

Fall 2015 10/1/15 (100 points)

Name _____________KEY_________________

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

[10 pts]

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

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

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

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

__T__ Turing complete languages minimally include sequential and selection structures.

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

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

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

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

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

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

[8 pts]

__T__ The both statement are both declarative and imperative.

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

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

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

__T__ The identifier x is a pointer to an integer.

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

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

__F__ 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: ___12___.
   

[4 pts]
List the first two tokens of the line: ____int______ and _____m_____. 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]

variables, constant names, types, procedure/function/method, class, fields, parameters

_______________________________________ _____________________________________

5. 
   Language design criteria.
   

[10 pts]

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

keywords are spelled out. Clear sections for constants, types, variables, and procedures. Other?
b. Name a language that could be claimed as “writable”. Why? [2]
any language can be claimed depending on reason, e.g. arithmetic expressions mimicking algebra

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

discussion could revolve around primitives versus objects and their inconsistency, or that use of object oriented approach to everything else is orthogonal.

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?

Lexical analyzer, parser and semantic actions. Some tweaks to the symbol table
Which module(s) would we need to change to cross compile to a different machine?

Only the code generator, maybe a little in the optimizer that would be specific to the new machine.

8. 
   Types and subtypes.
   

[12 pts]

1. 
   What are two major aspects that define a data type?
   the values and their operations
   
2. 
   Give two advantages of a strongly typed language?

   minimized risk of misspelling a variable. Ensuring that the variable is properly used. Efficient code can be generated

   
   
   
3. 
   Give two advantages of being able to specify a subtype.
   Smaller space needed possibly. More refined type definition to ensure that variables interact properly or that two variable of different subtypes are not accidently put together.
   
   
4. 
   What is coercion? Give an example.
   forced type conversion
   double x = 3.66;
   int k = (int) x; //4 is assigned
   

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 M M M P P P M Q M Q Q R R Q M

[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 P P M then P calls Q P Q Q then Q calls R R Q Q 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 ______:= + * ( ) 1 i j k_______ [3]
   
2. 
   The set of nonterminals is ______S E T F V_________ [3]
   
3. 
   The start symbol is ____ S ______ [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
S => V := E => j := E => j := T => j := T * F => j := F * F => j := V * F => j := i * F => j := i * ( E ) => j := i * ( E + T ) => j := i * ( T + T ) => j := i * ( F + T ) => j := i * ( V + T ) => j := i * ( k + T ) => j := i * ( k + F ) => j := i * ( k + 1 )

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
$ V := i	* ( k + 1)	Shift
$ V := V	“	Reduce	V ->j
$ V := F	“	Reduce	F -> V
$ V := T	“	Reduce	T -> F
$ V := T *	( k + 1 )	Shift
$ V := T * (	k + 1 )	Shift
$ V := T * ( k	+ 1)	Shift
$ V := T * (V	“	Reduce	V -> k
$ V := T * (F	“	Reduce	F -> V
$ V := T * (T	“	Reduce	T -> F
$ V := T * (E	“	Reduce	E -> T
$ V := T * (E +	1)	Shift
$ V := T * (E + 1	)	Shift
$ V := T * (E + F	“	Reduce	F -> 1
$ V := T * (E + T	“	Reduce	T -> F
$ V := T * (E	“	Reduce	E -> E + T
$ V := T * (E)	$	Shift
$ V := T * F	$	Reduce	F -> ( E )
$ V := T	$	Reduce	T -> T * F
$ V := E	$	Reduce	E -> T
$ S	$	Reduce	S -> V := E
		accept

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]

d = [0-9]

pn = ( d d d ’-‘ | ‘(‘ d d d ’)’ ) d d d ‘-‘ d d d d

b) Draw an equivalent FSM for this regular expression [4]
c) Write a corresponding BNF grammar [3]

FSM	BNF
Quite detailed	-> ‘-‘ | ‘(‘ ‘)’ -> ‘-‘ -> ‘0’ | ‘1’| …| ‘9’

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