Languages and Translation



Languages and TranslationCS 362 Exam 1Fall 2013 9/26/13 (100 points)Name __________Key__________________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 context-sensitive language category.__ 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 and floating point arithmetic.__ T __ The logical language paradigm expresses more about what is to be done than how.__ 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 FORTRAN language. /*C++*/ int * x = &m; m=5; // [8 pts]Fill in the blanks for these statements that are both declarative and __imperative_. Identifier x is bound to its R-value at ___tun___ -time, but its type is bound at __compile____-time, and its L-value is bound at __compile___-time. The constant 5 has its value bound at ___ compile __. We can say variable x in C is of type __int *____ but *x is of type ____int___. After the statements have executed, x contains the value ____address of m_________.List all the lexical tokens in the C++ statement in question #2, in order, that would be passed to the parser.[4 pts]int * x = & m ; m = 5 ; We have seen a number of examples of uses for user-defined identifiers in a language. List 4 different uses.[4 pts]__________variables, type names___________________________method names____________________enumerations_________________________class names, parameters, etc._____________Language design criteria.[8 pts]a. Explain how well Java meets the “readability” and the “writability” criteria. [4]Java is writable and readable regarding equations, and instance method calls. Much depends on the naming style of the classes and methods, however. Readability can be difficult with the cryptic brackets and braces usage. Style is not part of the language per se and the programmer style will contribute to readability more than anything.b. Explain the “orthogonality” criterion by discussing where Strings and the int type in Java are handled consistently and an example in Java where they are not handled in a consistent manner. [4]While we consider both int and Strings as built in data types, Java immediately treats them differently as primitive and class, respectively. Most String operations are methods based, while int use built in operators. The Math class gives other functionality for int. Both share the use of + for add and concatenation. Both are treated similarly for input and output.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 analysisOptimizationCode generationSyntactic analysis (parser)Intermediate code generationLexical analysis (scanner)Symbol tableBack ends and front ends.[4 pts]If we want to alter a great compiler to accept a different high level language, what module(s) would need to be rewritten?Lexical analyzer, parser and semantic actions. Some tweaks to the symbol tableWhich 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.Types and subtypes.[12 pts]What are two major aspects that define a data type? the values and their operationsGive two advantages of a strongly typed language?minimized risk of misspelling a variable. Ensuring that the variable is properly used. Efficient code can be generatedGive two advantages of being able to specify a subtype.Smaller space needed possiblty. More refined type definition to ensure that variables interact properly or that two variable of different subtypes are not accidently put together.What is coercion? Give an exampleforced type conversiondouble x = 3.66;int k = (int) x; //4 is assigned Scoping rules.[6 pts]Consider the following Ada skeletal program:373570574930Assuming static scoping, which is the declaration of X that is the correct one for each of the procedure bodies?Sub1 uses X declared in ___Main_____Sub2 uses X declared in ____Sub2___Sub3 uses X declared in ____Sub3___4000020000Assuming static scoping, which is the declaration of X that is the correct one for each of the procedure bodies?Sub1 uses X declared in ___Main_____Sub2 uses X declared in ____Sub2___Sub3 uses X declared in ____Sub3___Procedure Main is X : Integer; Procedure Sub3; -- a header declaration Procedure Sub1 is Procedure Sub2 is X : Integer; Begin … End; --of Sub2 Begin -– of Sub12400300106680b. Assuming dynamic scoping butMain calls Sub3,Sub3 calls Sub2 andSub2 calls Sub1Sub3 uses X declared in ___Sub3____Sub2 uses X declared in ____Sub2____Sub1 uses X declared in _____Sub2___4000020000b. Assuming dynamic scoping butMain calls Sub3,Sub3 calls Sub2 andSub2 calls Sub1Sub3 uses X declared in ___Sub3____Sub2 uses X declared in ____Sub2____Sub1 uses X declared in _____Sub2___ … End; -- of Sub1 Procedure Sub3 is X : Integer; Begin … End; --of Sub3 Begin –- of Main … End; -- of MainAssume the set of productions representing simple algebraic expressions.[25 pts]S SYMBOL 174 \f "Symbol" V := EE SYMBOL 174 \f "Symbol" E + T | TT SYMBOL 174 \f "Symbol" T * F | FF SYMBOL 174 \f "Symbol" V | ( E ) V SYMBOL 174 \f "Symbol" i | j | kThe alphabet or set of terminals is _____:= + * ( ) i j k____ [3]The set of nonterminals is _________S E T F V______________ [3]The start symbol is ____S_______ [2]Show a top down, left-most derivation for j := i * k + j starting with the start symbol. [5]Draw the corresponding parse tree. [5]DerivationParse treeS => V := Ej := Ej := E + Tj := T + Tj := T * F + Tj := F * F + Tj := V * F + Tj := i * F + Tj := i * V + Tj := i * k + Tj := i * k + Fj := i * k + Vj := i * k + jf) 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 + jStackInput remainingShift or ReduceRule used in reduce$ j:= i * k + jShift$ V:= i * k + jReduceV-> j$ V :=i * k + jShift$ V := i* k + jShift$ V := V* k + jReduceV -> i$V := F“ReduceF -> V$V := T“ReduceT -> F$V := T *k + jShift$V := T * k + jShift$ V := T * V“ReduceV -> k$V := T * F“ReduceF -> V$V := T“ReduceT -> T * F$V := E “ReduceE -> T$ V := E +jShift$V := E + j$Shift$V := E + V$ReduceV -> j$V := E + F$ReduceF -> V$V :- E + T$ReduceT -> F$V := E$ReduceE$V := E$AcceptConsider the language of 12 hour time format. For example 3:15 AM, 12:05 PM, 9:59:59 AM are legal time expressions. Note that seconds are optional. A leading 0 for the hour is not necessary. You need to try to rule out 14:75 as a legal expression.[12 pts]a) Give a regular expression to define this language of time. Hint, it may be easier to do the FSM first. [5]d = [0-9]s = [0-5]time = 1(0|1|2) | <d> ‘:’ <s> <d> ( ‘:’ <s> <d> )? [AP]M b) Draw an equivalent FSM for this regular expression [4]c) Write a corresponding BNF grammar [3]FSMBNFTime -> hours : minsec | hours : minsec : minsecHours -> 1 ( 0 | 1 | 2) dMinsec -> d sd -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9s -> 0 | 1 | 2 | 3 | 4 | 5 ................
................

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

Google Online Preview   Download