Languages and Translation



Languages and TranslationCS 362 Exam 1Fall 2011 9/29/11 (100 points)Name ___________Key_______________True/false on programming languages basics, etc.[10 pts]__T__ Languages are designed for two audiences: machine and the human programmer.__T__ Computer languages fall into the context-free language realm.__F__ Object-oriented is the latest paradigm brought to us in C++.__T__ Functional language paradigm is also implementable in procedural and OO languages.__T__ Turing complete languages minimally include sequential and iteration structures.__T__ Turing complete languages minimally require integer arithmetic.__F__ The logical language paradigm is included in object-oriented language paradigm.__T__ Church’s thesis states that it is not possible to build a machine inherently more powerful than a Turing machine.__F__ The Java language’s virtual machine is based on specific computer hardware.__F__ All computer languages trace their genealogy back to FORTRAN./*java*/ { FooObject x = new FooObject(m*2); // instantiate[8 pts]Fill in the blanks for this statement that is both _declarative_ and imperative. Identifier x is bound to its R-value at _run______ -time, but its type is bound at ___compile_-time, while its L-value is bound at ____ run ____-time. Constant 2 has its value bound at ___ compile _. Identifier FooObject has two purposes as a ____type_______ and a _____constructor_________; both are bound at ___ compile __-time.List all the lexical tokens in the Java statement in question #2.[4 pts]{ FooObject x = new FooObject ( m * 2 ) ; Given the Pascal two dimensional array declarationVAR M: Array [10..20,1..5] of Real;show an effective address calculation for element M(i,j). Assume M[10,1] is at address 2000 and that row-major storage is used (rightmost subscript varies the fastest; leftmost the slowest).[6 pts]EA = 2000 + (i-10)*5*4 + (j-1)*4 = 2000 + i*20 – 540 + j*4 – 4 = 1456 + i*20 + j*4Language design criteria.[10 pts]a. Explain the conflict between the “readability” and “writability” criteria in language design. [5]Readability is the ease of reading which usually requires the language to be more verbose and close to mathematical symbolism; programs tend to be larger in text size. Writability is the ease of writing which tends to make languages terse and cryptic using symbols. Programs are much smaller and difficult to read.b. Explain the “orthogonality” criterion. Give an example in Java that portrays a violation of orthogonality. [5]Two or more features that are independent, when combined provide more usable features. When the orthogonality criterion is adhered, then the programmer only needs to learn the sum of the independent features providing a product of their interaction. The exceptions to the product list have to added to the items to be learned. We want this sum to be much less than the total interaction of features for it to be worthwhile. Java primitive types and classes are not treated equally. Relational operators for numbers cannot be equally used on Strings.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.[8 pts]347332782310334300792390328936779430Semantic analysisOptimizationCode generationSyntactic analysis (parser)Intermediate code generationLexical analysis (scanner)Symbol table32339279225314752711025296860725785287788717145275872777852518247812252558207-519752992727-2795287068721325275980727445266116732125256180717005249124715205237712780052214767-1493153327527103155316660711431530737271099953074087685952959607811952606807311551169327-1717752900207-216552557487-353352989487418152751887464952689967349752612207382152495927346152345447-769852395487-503451602047700051573247-531153679967772053611207862053464687782853472967-171153222047905253178487107805308128711140529876877828530056871027652673767397651233407-789251161047690351009847-461658582873951574812752835608087157552618687200751555967-249515876471465419807-235415491807-248375992207110570348770945737327-27695471244721985310576772253181007525853118727687853040967551052842967-213527281277454526399278102525924071245852449487795852425727957852337527705852238887651852165807-7845549162072461548391674297547009274225543610876097543211276889542181678149538740075175374116710489536702479445533048471057529513271210952729207537751356527164451581527-440351637687-26351557407-674354128887-829153141047-350352669087-911528260475939526608077343524365271241952411327622752495927647952173727-306051374887-286455155992746185422464764905383440710342538729271351053802727793053672047537452740007728254107647-221054137887-311053748727-7705348736713535340024784953262367279353194687131753239687-156253094607477352861687693352884007-44652948087-1670526557674161524890877520526939276800524509271245252517167658452213327154452131607-389153058247-283652847287-272852815247-118052605367-19365256072754752361287-326852295767-352538016471222253677447689453722087-13135354424755985346216710062531205274266530100071089052921447927052696447-163752641367-159054666007-525154606607220054519487259654295207335254326887-705154256687371254132847558454033847-201154021967576453905687-463953794807443253242927-71552646407277652357327-132752274167421652177687202052056367-59355Back ends and front ends.[5 pts]Which modules constitute the front end of a compiler? What is significant about the front end?40216787199Scanner, parser, semantic analysis – dependent on the source language, other modules not soWhich modules constitute the back end? What is significant about the back end?[optimizer], code generator – dependent on the hardware/target machine, other modules not soTypes and subtypes.[15 pts]What are the two major components that define a datatype? That is, what must be specified to define a type?domain or set of legal values and the operations on those valuesWhy is a strongly typed language desirable?catches more programming errors by requiring variables to be bound to a type. Misuse can be caught by compiler.Give an example of a subtype. You do not need to use a specific language.May have a subrange of integers, e.g., 1..100What are the issues of assigning values back and forth between a subtype and its base type?subtype assignment to base type is no problem since subtype is a subset. Base to subtype may be a problem since the value may not be in the subtypeHow are the issues above similar to assigning integers and floats back and forth?All integers are representable by float but the converse is not true. What to do with fractional part?Scoping rules.[9 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 ___Sub1____Sub2 uses X declared in ___Sub2____Sub3 uses X declared in ____Main__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 ___Sub1____Sub2 uses X declared in ___Sub2____Sub3 uses X declared in ____Main__Procedure Main is X : Integer; Procedure Sub3; -- a header declaration Procedure Sub1 is X : Integer; Procedure Sub2 is Begin … End; --of Sub2 Begin -– of Sub1 …24003550b. Assuming dynamic scoping butMain calls Sub1,Sub1 calls Sub2 andSub2 calls Sub3Sub1 uses X declared in ___ Sub1____Sub2 uses X declared in ___ Sub1____Sub3 uses X declared in ___ Sub1____4000020000b. Assuming dynamic scoping butMain calls Sub1,Sub1 calls Sub2 andSub2 calls Sub3Sub1 uses X declared in ___ Sub1____Sub2 uses X declared in ___ Sub1____Sub3 uses X declared in ___ Sub1____ End; -- of Sub1 Procedure Sub3 is Begin … End; --of Sub3 Begin –- of Main … End; -- of MainAssume the set of productions representing simple variable declarations in a pseudo-Pascal.[25 pts]dcl SYMBOL 174 \f "Symbol" VAR list : type ;list SYMBOL 174 \f "Symbol" list , idlist SYMBOL 174 \f "Symbol" idtype SYMBOL 174 \f "Symbol" CHAR | NUM id SYMBOL 174 \f "Symbol" i | j | kThe alphabet or set of terminals is ___VAR : , CHAR NUM i j k__ [3]The set of nonterminals is ___dcl list type id_______ [3]The start symbol is ____dcl_____ [1]Show a top down, left-most derivation for var i,k : Char; starting with the start symbol. [5]Draw the corresponding parse tree. [5]Top Down DerivationParse treeDcl -> Var list : type ;Var list , id : type ;Var id , id : type ;Var i , id : type ;Var i , j : type;Var i , j : Char ; 91030720086838588272067723903827178260377854715234039088671554003791507160980384946713646431704827145284316493871534203169546712595232501147128580324115071298403229342711788832154827122676320813878635231688987107556316825071061523162490711104831209827112380312533871123803789347116700391174712152439625071168083835067123144378106712325236619071119843119002787756311767078887238429878498436791877893635549877882834311477098032329427466083190678745348322883877627232376947691443192586773644318841077252831727867699723179806764644314978277623631501427696123118354765544312127077090831263467677043117562771700311630277126831076627654363118894736312311270274023631126667417123109966742288356974739192312375471399231102187229563960707152523f) 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. [8]var i,k : Char; StackInput remainingShift or ReduceRule used in reduce$var i,k : Char; Shift$ var i,k : Char; Shift$ var id,k : Char; Reduceid-> i$ var list“ReduceList -> id$ var list ,k : Char ;Shift$ var list , k: Char ;Shift$ var list , id“ReduceId ->k$ var list“ReduceList -> list , id$ var list :Char ;Shift$ var list : Char; Shift$ var list : type;ReduceType -> Char$ var list : type ;$Shift$ dcl$ReduceDcl AcceptEmpty input, start symbol only on stack ................
................

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

Google Online Preview   Download