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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- transcription and translation practice test
- dna transcription and translation simplified
- transcription and translation of dna
- replication transcription and translation key
- dna transcription and translation worksheet
- transcription and translation lab activity
- transcription and translation steps
- transcription and translation activity pdf
- transcription and translation online activity
- transcription and translation worksheet pdf
- programming languages and their uses
- transcription and translation simulation