Languages and Translation



Languages and Translation

CS 362 Exam 1

Spring 2006 2/21/06 (100 points)

Name _________________________________

1. What is a programming language?

[4 pts]

A notational system for describing computation in machine readable and human readable form

2. Which of the following are minimum requirements for a language to be Turing complete:

[4 pts]

_____ Sequential execution

_____ Floating point variables and arithmetic

_____ Integer variables and arithmetic

_____ Loop structure

_____ Threads

_____ Selection structure

_____ Assignment operation

_____ Object orientation

3. Identify and describe 4 different bindings in the following C/C++/Java type of declaration/initialization statement for the given tokens.

double x = sqrt(n*3.14); //sqrt is a square root library function

[8 pts]

|Token |Attribute to be bound |Binding time |

| | | |

|x | | |

| | | |

|x | | |

| | | |

|sqrt | | |

| | | |

|3.14 | | |

4. List all the tokens in the C/C++/Java statement above.

[5 pts]

5. Language design criteria.

[10 pts]

a. Explain how the “write-ability” and “maintainability” criteria may be in conflict. [3]

b. How does Java support the “security” criterion in its array referencing? Contrast that with C/C++. [3]

c. C++ permits the overloading of its operator set so that, for example, you can define ATDs or classes such as complex numbers or dates to permit code to be expressed with +, -, ++, --, etc on objects of these types. Critique this feature against the “orthogonality” and “readability” criteria. [4]

6. Draw a diagram that connects these 7 modules of a compiler by the theoretical data flow of data:

[5 pts]

Syntactic analysis (parser) Intermediate code generation Semantic analysis

Lexical analysis (scanner) Optimization Code generation

Symbol table

7. Compiler front ends and back ends.

[4 pts]

a. Which of the module(s) constitute a compiler’s front end?

b. Which of the module(s) constitute a compiler’s back end?

8. Why is this grammar for nested selection statements considered ambiguous? Be sure to explain how a parse tree is used in defining ambiguity, or show an example.

→ if then

| if then else

| =

[5 pts]

9. Consider the language that represents the range of cells you can reference in Excel. A cell reference is one or two letters followed by a string of digits. A range is a pair of cell references separated by a colon. You may use refer to letter and digit for those classes of characters.

[15 pts]

a) Give a regular expression to define this language of cell ranges: [5]

b) Draw a FSM from this regular expression [5]

c) Write a corresponding BNF grammar limited to the form A(xB | y [5]

|FSM |BNF |

| | |

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

[28 pts]

S V := E

E E + T | T

T T * F | F

F V | ( E )

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 ____________ [2]

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

e) Draw the corresponding parse tree. [5]

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

j := ( i + k ) * j

|Stack |Input remaining |Shift or Reduce |Rule used in reduce |

|$ j |:= ( i + k ) * j |Shift | |

|$ V |:= ( i + k ) * j |Reduce |V-> j |

|$ V := |( i + k ) * j |Shift | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

11. For each of the following language features or components below, which run time environment (static, stack or dynamic) best supports the feature (Static, Stack and dynamic/heap).

[6 pts]

________________ Constant definition values

________________ Methods’ bodies of code

________________ Local variables of blocks

________________ Recursive method calls

________________ Instantiation of objects

________________ Concatenation of strings

12. Fill in the table with “Expected” if the combination of mode and scanner encounter of the symbol is appropriate. If unexpected, explain what the error is.

[6 pts]

|Mode |New encounter of symbol |Second encounter of symbol |

|Declarative Mode | | |

|Imperative Mode | | |

13. For each of the languages below, designate which generation of computing machines they were created: 1st, 2nd, 3rd, or 4th.

[6 pts extra credit]

______ FORTRAN

______ Pascal

______ Smalltalk

______ Algol

______ Ada

______ LISP

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download