CS-415 Midterm 2023 with verified questions and answers

abstraction avoid requiring something to be stated are than once automation automate mechanical, tedious, or error-prone activities defense in depth have a series of defenses so that if an error is not caught by one, it will probably be caught by another elegance confine your attention to designs that look good because they are good impossible error making error impossible to commit is preferable to detecting them after their commission information hiding the language should permit modules designed so that: - the user has all of the information needed to use the module correctly - the implementer has all of the information needed to implement the module correctly, and nothing more labeling - avoid arbitrary sequences more than a few items long - do not require the user to know the absolute position of an item in a list, instead, associate a meaningful label with each item and allow the items to occur in any order localization cost - users should pay only for what they use - avoid distributed costs manifest interface all interfaces should be apparent (manifest) in the syntax orthogonality independent functions should be controlled by independent mechanisms portability avoid features or facilities that are dependent on a particular computer or small class of computers preservation of information the language should allow their representation of information that the user might know and that the compiler might need regularity regular rules, without exception, are easier to learn, use, describe, and implement responsible design do not ask what they want; find out what they need security no program that violates the definition of the language, or its own intended structure, should escape detection simplicity - a language should be as simple as possible. - there should be a minimum number of concepts, with simple rules for their combination structure the static structure of the program should correspond in a simple way to the dynamic structure of the corresponding computations syntactic consistency similar things should look similar, and different things should look different zero-one-infinity the only reasonable numbers are zero, one, and infinity imperative languages are ___ based control object oriented languages are ___ driven event synchronous is ____, asynchronous is not concurrent ____ set up a balance within themselves, whereas ____ do not CFG's, regular expressions what does lexical analysis do? converts source code into tokens what does syntax analysis do? structures tokens into a parse tree ____ is synonymous to parse derivation productions are the ____ rules = indicates.... the derivation of one step =+ indicates... the derivation of one or more steps =* indicates... the derivation of zero or more steps LHS and RHS mean left hand side, right hand side For productions, if not specified, assume that the LHS of the of the first listed production is the start symbol productions with the same LHS are usually combined with | if a production has an empty RHS, it means that the RHS is ε a grammar, G, is ambiguous iff there exists a: w ⋹L(G) such that there are: (3 things) - two distinct parse trees for w - two distinct left-most derivations for w - two distinct right-most derivations for w how to deal with ambiguity? - change the language to include delimiters - change the grammar precedence follows normal PEMDAS, and also is ordered ___ to ___ in grammar lowest, highest a parse tree shows the ___ of an expression as it corresponds to ____ structure, grammar ambiguity in difference in associativity example (a-b)-c vs a-(b-c) ambiguity in difference in precedence example (a-b)*c vs a-(b*c) ambiguity in difference of control flow example if (if else) vs if (if) else LL means _____, and LR means_______, and LL(1) means _____ logical left, logical right, logical left first iteration in some languages, = represents ____ lambda binding is an _______ of a ____ with the ________ association, name, thing it names to make addresses easier in assembly, we use ____ registers there are both ____ and ___ parts of memory static, dynamic libraries: we can either ____ or ____ create our own, use existing ones early binding is more ____ where as late binding is more ______ efficient, flexible dynamic linking is somewhat between static and dynamic binding; the ____ must be known(static), but the ____ is linked and loaded at run time (dynamic) function signature, implementation a ____ is how we maintain bindings, and like a ____, it searches from top to bottom. symbols table, stack how long do bindings for a name hold in a program? as long as they are in scope if a binding is not ended properly.... it will create a memory leak static or dynamic?: type of object fixed at compile time, by the type of variable containing it static static or dynamic?: often results in "case" and "if" statements static static or dynamic?: heterogeneous collections difficult to implement static static or dynamic?: easier to debug static static or dynamic?: no overhead at run time static static or dynamic?: type of object determined at run time, so objects "know what they are" dynamic static or dynamic?: eliminates complex "case" and "if" statements dynamic static or dynamic?: heterogeneous collections greatly simplified dynamic static or dynamic?: harder to debug dynamic static or dynamic?: slower from run-time lookups dynamic 6 components of variables: - name - type - location (or reference, l-value) - value (r-value) - scope - lifetime the scope of a variable is where the variable is ___ and ____ accessible and manipulatable the lifetime of a variable is the ______ in which a ____ is bound to the variable interval of time, location for "N:= N + 1": the first N refers to the ______ and the second N refers to the _____ l-value, r-value dereferencing means obtaining... the value of a variable ___ scoping is used by most languages static ___ scope can be determined by looking at the structure of a program static ____ scope may have holes in the scope of a variable static in static scoping, _____ keeps track of which ______ are currently visible. stack?, declarations symbol table for static scope: when entering a new scope, we _____, and when exiting, we ____ push, pop static scoping is associated with the ____ of the program static text dynamic scope: ______ are associated with declarations at run time non-local variables dynamic scope finds the most recent, currently active ______ frame containing a declaration of the variable run-time stack in dynamic scoping, scope is determined by the _____ execution path in dynamic scoping, ____ is built and maintained at run-time symbols table dynamic scoping: we push when entering scope and pop when exiting, but do so at _____ run-time dynamic scoping is usually associated with _____ dynamic typing dynamic allocation (pointers) use ____ memory heap lifetime in heap memory is determined by ___ and ___ functions new, dispose pointers point directly at _____; this is why its easy to error memory locations _____ uninitialized or nil pointers may cause crashes dereferencing garbage refers to ____ items that may ___ heap memory and which can't be ______ unreachable, clog, recycled lambda expressions: anonymous functions that are used to create delegates or expression tree types for lambda expressions, the compiler uses _____, and if it doesn't have enough ___ to do so, it will return an error type inference, information syntax: determines valid form of a program semantics: behavior of a valid program the convention is that _____ is what can be specified by CFG syntax there is not a clear boundary between static and dynamic ______ semantics the semantic analyzer: (two things) - determines the meaning of a program - enforces semantic rules attribute grammars can be though of as ____ CFG decorated attributes can be associated with the ____ of grammar non-terminals attributes must uniquely identify non-terminal occurrences synthesized attribute: value is only computed when the symbol is on the ________ left-hand side of the production inherited attribute: value is only computed when the symbol is on the ________ right-had side of the production synthesized or inherited? - attributes can be computed independently of context synthesized synthesized or inherited? - attributes computed using context inherited synthesized or inherited? - cannot avoid these in semantic analysis inherited ____ grammar has only synthetic attributes s-attributed attribute flow is the .... pattern of information flow between attributes a grammar is l-attributed if: - each ___ attribute on the left-hand side depends only on ____ attributes of that symbol, or on attributes of the symbols on the right-hand side, and - each ____ attribute of a right-hand side symbol depends only on ____ attributes on the left-hand side symbol or on attributes of symbols to its left in the right-hand side. synthesized, inherited, inherited, inherited LL(1): what does each character (besides parentheses) stand for? - first L stands for scanning the input from right to left - second L stands for producing the leftmost derivation - (1) stands for using one input symbol of lookahead attach step to make parsing action decision which grammars are bottom-up? LR which grammars are top-down? LL LR grammars construct the _____ of a program right-most derivation LR parsers start with the ___ and end with the ___ tokens, start symbol action routines are... semantic functions that the compiler executes during parsing action routines are used in... parser generators in LL parse, action routines... may occur anywhere in the production in LR parse, action routines... must occur at the end of the production since action routines can occur anywhere is LL parse, you should only use production... if you know its correct rational of only allowing action routine at the end of LR parse you don't know if production applies until seeing the full RHS YACC stands for yet another compiler-compiler LALR means ______, which ____ is an example of look ahead left-to-right, YACC AST means Analysis of Abstract Syntax Trees ASTs... (2 things) - describe structure of AST as tree grammar - form attribute grammar from tree grammar instead of CGF flow requires what three things? - initialization - test what is initialized - work toward some kind of completion selection: choice is made among 2 or more statements depending onside run-time condition non-determinacy: ordering/choice among statements is deliberately left unspecified commands or statements change the ___ of the machine state state of computer corresponds to contents of ___ and any ____ memory, external devices (I/O) states are sometimes called store distinction between state and environment: environment is mapping between ___ and ___ (including ____) state includes mapping between ___ and ____ identifiers, values, locations locations, values distinction between state and environment: values in store or memory are _____, as opposed to _____(or ____) storable, denotable, bindable distinction between state and environment: symbol table depends on ____ and ___, which is _____ declarations, scope, static distinction between state and environment: environment tells where to find _____, which is _____ values, dynamic distinction between state and environment: state depends on previous ______, which is _____ computation, dynamic Compiler vs interpreter: if using a compiler, although symbol table can be hard coded into compiled code, ___ and ____ change dynamically environment, state Compiler vs interpreter: if using interpreter, you may have to keep track of ____, ____, and ___ during run-time, although you could avoid using ___ if there is no aliasing in the language) symbol table, environment, state, state in the value model, a variable is a _____, and there is both a ___ and a ____ container l-value, r-value l-value, r-value expression that refers to location, expression that refers to value in the reference model, a variable is a ____, and every variable occurrence is a _____ reference, l-value precedence rules refer to mathematical operator's precedence without parentheses associativity refers to a sequence of equal precedence group assignment means to store a value in a location named by a variable for assignment, the order of evaluation can be important, especially if there is _____, because they can make it difficult to ____ side-effects, predict the value 2 kinds of assignment - assignment by copying - assignment by sharing Polish notation is the same as prefix reverse polish notation is the same as postfix we tend to use ____ notation, since it works well with ____ reverse polish, stack control structures: statements for combining other expressions and statements 3 kinds of control structures: - sequencing - selection - repetition early control structures included (3 things) - goto - if - do early control structures were very close to machine code progress in control structures included _________, which is ______, as well as ____ if then else, hierarchical, switch the switch statement is a cross between ___ and ___ case, computed goto commands are essentially expressions with side effects commands must semantically keep track of ____, and the ______ is part of the result store, modified store exploitation of the fact that AND (&&) does not check the following statement if the first is ____, and OR (||) doesn't check the following statement if the first is ____, allows for the feature called _______ false, true, short-circuit