GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

OOP Langs Test 2 part b

James Herd Organization of Programming Langs 2 English 117 cards

Cards in this deck (117)

  1. 1[Sebesta04] The ____ part in LR parser specifies what the parser should do, given the state symbol on top of the parse stack and the next token of input.action
  2. 2[Sebesta04] Most compiler uses an efficient parser to implement syntax analyzers for programming language, working on subclasses of unambiguous grammars, and having complexity ___.O(n)
  3. 3[Sebesta04] Every parser for a context-free programming language is a ____, because this is a recognizer for a context-free language.push-down automaton
  4. 4[Sebesta04] The top symbol on the LR parse stack is always a ____ symbol that represents all of the information in the parse stack that is relevant to the parsing process.State
  5. 5[Sebesta04] The ____ table in LR parser is used to determine which state symbol should be placed on the parse stack after a reduction has been done.goto table
  6. 6[Sebesta04] For CFG, parsers that work for all unambiguous grammars have complexity ____ in gerenal.O(n^3)
  7. 7[Sebesta04] _____ is a pattern matcher that isolates the small-scale parts (of a program) which are called lexemes.Lexical Analyzer
  8. 8[Sebesta04] _____ parser is an LL parser that is implemented by writing code directly from the grammar of the source language. EBNF is ideal as the basis for this type of parsers and much easier and simpler to implement.recursive-descent
  9. 9[Sebesta04] LR parsers use two parsing tables: action and ____.go-to
  10. 10[Sebesta04] A ____ parser is called a shift-reduce algorithm, because in most cases it either shifts the next lexeme of input onto the parse stack or reduces the handle that is on top of the stack.LR parser
  11. 11[Sebesta04] _____, which is also called (or in) BNF, is the most common approach for describing syntax.Context-free grammar
  12. 12[Sebesta04] Syntax analyzers are either ____, meaning they construct leftmost derivations and a parse tree in top-down order, or ____, in which case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order.top-down, bottom-up
  13. 13[Sebesta04] Some grammars that fail the pairwise disjointness test often can be modified to pass it, using ____.left-factoring
  14. 14[Sebesta04] Two distinct grammar characteristics prevent the construction of a recursive-descent parser based on the grammar. One is _____.left recursion
  15. 15[Sebesta04] _____ is normally based on a formal syntax description of the language being implemented.Syntax analysis
  16. 16[Sebesta04] Two goals of syntax analyzers are: (1) to detect syntax errors in a given program and (2) to produce a/an _____.parse tree
  17. 17[Sebesta04] The original LR algorithm was designed by ____ in 1960's.Knuth
  18. 18Consider the following grammar and LR parse table, and the current stack-content and input-string to be processed (as we discussed in the class). Current Stack Content: 0E1+6T9*7 Current Input: ) $ The Next stack-content and input-string will be:None of the above
  19. 19Consider the following grammar and LR parse table, and the current stack-content and input-string to be processed (as we discussed in the class). Current Stack Content: 0 Current Input: id + id * id $ The Next stack-content and input-string will be:Stack: 0id5
    Input: + id * id $
  20. 20Consider the following grammar, its LL parsing table, current stack-content and input-string (as we discussed in the class). Current Stack: $ exp' term' Current Input: + n $ The next stack-content and input-string will be:Stack: $ exp'
    Input: + n $
  21. 21Consider the following grammar, its LL parsing table, current stack-content and input-string (as we discussed in the class). Current Stack: $ exp' term Current Input: $ The next stack-content and input-string will beNone of the above
  22. 22Consider the following grammar, its LL parsing table, current stack-content and input-string (as we discussed in the class). Current Stack: $ exp' term Current Input: n $ The next stack-content and input-string will be:Stack: $ exp' term' factor
    Input: n $
  23. 23What is the primary task of lexical analyzer?Identifies substrings of the source program that belong together - lexemes, associate a token to each lexeme
  24. 24What are two distinct goals of syntax analyzer?Check the input program to find all syntax errors; for each, produce an appropriate diagnostic message and recover quickly
    Produce the parse tree, or at least a trace of the parse tree, for syntactically correct input.
  25. 25What is a phrase of a sentential form?Def: is a phrase of the right sentential form
    if and only if S =>* = 1A2 =>+ 12
  26. 26defines a collection of data objects and a set of predefined operations on those objectsdata type
  27. 27is the collection of the attributes of a variabledescriptor
  28. 28Those not defined in terms of other data typesPrimitive data types
  29. 29Java's signed byte, short, int, long There may be as many as eight different types in a language What is this type?Integer
  30. 30Model real numbers, but only as approximationsFloating Points
  31. 31Type description: Each value consists of two floats, the real part and the imaginary part Python: (7 + 3j), where 7 is the real part and 3 is the imaginary part Used in C99, Fortran, and PythonComplex
  32. 32For business applications (money) Essential to COBOL Advantage: accuracy Disadvantages: limited range, wastes memoryDecimal
  33. 33Range of values: two elements, one for "true" and one for "false Advantage: readabilityBoolean
  34. 34Stored as numeric codings Most commonly used, 8-bit coding: ASCII An alternative, 16-bit coding: Unicode (UCS-2) 32-bit Unicode (UCS-4)Character
  35. 35Assignment and copying Comparison (=, >, etc.) Catenation Substring reference Pattern matchingOperations
  36. 36compile-time descriptor COBOL, Java's String classStatic length
  37. 37may need a run-time descriptor for length (but not in C and C++) C and C++ In these languages, a special character is used to indicate the end of a string's characters, rather than maintaining the lengthLimited Dynamic Length
  38. 38need run-time descriptor; allocation/deallocation is the biggest implementation problem SNOBOL4, Perl, JavaScript, STL in C++ requires overhead of dynamic storage allocation/deallocation, but provides highest flexibilityDynamic Length
  39. 39is one in which the range of possible values can be easily associated with the set of positive integers Java: interger, char, booleanOrdinal Type
  40. 40All possible values, which are named constants, are provided in the definition Ex ([type] days {mon, tue, wed, thu, fri, sat, sun};)Enumeration Types
  41. 41data elements in which an individual element is identified by its position in the aggregate, relative to the first element.homogeneous aggregate
  42. 42one in which the elements need not be of the same typeheterogeneous array
  43. 43is a mapping from indices to elements Fortran and Ada use parentheses Most other languages use bracketsIndexing
  44. 44subscript ranges are statically bound, and storage allocation is static (before run-time) Advantage: efficiency (no dynamic allocation)Static array
  45. 45subscript ranges are statically bound, but the allocation is done at declaration time Advantage: space efficiencyFixed stack-dynamic array
  46. 46similar to fixed stack-dynamic: storage binding is dynamic but fixed after allocation (i.e., binding is done when requested and storage is allocated from heap, not stack)Fixed heap-dynamic array
  47. 47binding of subscript ranges and storage allocation is dynamic and can change any number of times Advantage: flexibility (arrays can grow or shrink during program execution)Heap-dynamic array
  48. 48is a multi-dimensioned array in which all of the rows have the same number of elements and all columns have the same number of elementsrectangular array
  49. 49has rows with varying number of elements C, C++, and Java support thisjagged matrix
  50. 50Sliceis some substructure of an array; nothing more than a referencing mechanism
  51. 51Column major order is used in which programming langFortran
  52. 52is an unordered collection of data elements that are indexed by an equal number of values called keysAssociative array
  53. 53is a possibly heterogeneous aggregate of data elements in which the individual elements are identified by namesrecord
  54. 54a data type that is similar to a record, accept that the elements are not named array = (3, 5.8, ′apple′);tuple
  55. 55is a type whose variables are allowed to store different type values at different times during executionUnion
  56. 56C and C++ provide union constructs in which there is no language support for type checking; the union in these languagesfree union
  57. 57Type checking of unions require that each union include a type indicatorDiscriminant
  58. 58type variable has a range of values that consists of memory addresses and a special value, nilPointer
  59. 59used to set a pointer variable's value to some useful addressAssignment
  60. 60yields the value stored at the location represented by the pointer's valueDereferencing
  61. 61A pointer points to a heap-dynamic variable that has been deallocatedDangling pointers
  62. 62An allocated heap-dynamic variable that is no longer accessible to the user program (often called garbage)Lost heap-dynamic variable
  63. 63The process of losing heap-dynamic variablesMemory leakage
  64. 64C++ includes a special kind of pointer type type that is used primarily for formal parametersreference type
  65. 65extra heap cell that is a pointer to the heap-dynamic variableTombstone
  66. 66Pointer values are represented as (key, address) pairslocks-and-keys
  67. 67(eager approach): reclamation is gradualReference Counters
  68. 68(lazy approach): reclamation occurs when the list of variable space becomes emptyMark-sweep
  69. 69maintain a counter in every cell that store the number of pointers currently pointing at the cell Disadvantages: space required, execution time required, complications for cells connected circularly Advantage: it is intrinsically incremental, so significant delays in the application execution are avoidedReference counters
  70. 70the activity of ensuring that the operands of an operator are of compatible typesType checking
  71. 71is one that is either legal for the operator, or is allowed under language rules to be implicitly converted, by compiler- generated code, to a legal typecompatible type
  72. 72the application of an operator to an operand of an inappropriate typeType Eror
  73. 73means that two variables have equivalent types if they are in either the same declaration or in declarations that use the same type name Advantage: Easy to implement Disadvantage: Highly restrictiveNames type equivalence
  74. 74What are these types: PHP: all variable names must begin with dollar signs Perl: names of scalar variables: $ names of array variables: @ names of hashes (associative arrays, like a map): %Special Characters
  75. 75a word that is special only in certain contexts and can be redefinedKeyword
  76. 76is a special word that cannot be used as a user-defined name, cannot be redefinedreserved word
  77. 77is an abstraction of a memory cellvariable
  78. 78the memory address with which it is associatedAddress
  79. 79determines the range of values of variables and the set of operations that are defined for values of that type; in the case of floating point, type also determines the precisionType
  80. 80the contents of the location with which the variable is associatedValue
  81. 81is an association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbolBinding
  82. 82is the time at which a binding takes place.Binding time
  83. 83if it first occurs before run time and remains unchanged throughout program execution.the binding is static
  84. 84if it first occurs during execution or can change during execution of the programThe binding is Dynamic
  85. 85the type may be specified by either an explicit or an implicit declarationwith Static Binding
  86. 86is a program statement used for declaring the types of variablesexplicit declaration
  87. 87is a default mechanism for specifying types of variables through default conventions, rather than declaration statementsimplicit declaration
  88. 88is the time during which it is bound to a particular memory cell:lifetime of a variable
  89. 89of a variable is the range of statements over which it is visiblescope
  90. 90of a program unit are those that are declared in that unitlocal variables
  91. 91of a program unit are those that are visible in the unit but not declared therenonlocal variables
  92. 92are a special category of nonlocal variablesGlobal variables
  93. 93of a statement is the collection of all names that are visible in the statementreferencing environment
  94. 94A(n) ___ defines a collection of data objects and a set of predefined operations on those objectsData type
  95. 95A(n) ___ is the collection of the attributes of a variableDescriptor
  96. 96Variables can be characterized by the sextuple of attributes. Which is not one of these six attributes?storage
  97. 97Arrays can be ___, as with Java's objects.fixed heap dynamic
  98. 98To store a fixed number of decimal digits, in coded form (BCD), it uses ___ bits for a decimal digit.4
  99. 99Consider the following program (Javascript). // ... beginning of the program var x; function sub1( ) { document.write("x = " + x + " "); // the value of x? } function sub2( ) { var x; x = 1; sub1( ); } x = 5; sub2( ); // ... end of the program What is the value of x printed in sub1 if dynamic scoping is used?1
  100. 100A(n) _____ array is an unordered collection of data elements that are indexed by an equal number of values called keysAssociative
  101. 101Arrays can be ___, as in C++ arrays whose definition includes the static specifier.Static
  102. 102Arrays can be ___, as in C functions (without the static specifier).fixed stack-dynamic
  103. 103Array ___ is a mapping from indices to elements.indexing
  104. 104Static scoping is a central feature of ___ and some of its descendants.ALGOL 60
  105. 105In general, ___ binding allows greater flexibility but at the expense of readability, efficiency, and reliability.dynamic
  106. 106A(n) ____ is a possibly heterogeneous aggregate of data elements in which the individual elements are identified by namesrecord
  107. 107For length option(s) of string data type, some languages (e.g., COBOL, Java's String class), it is ___.Static length
  108. 108Consdier the following JavaScript program (as we discussed in the class). What value of x is displayed in function sub1? Select all correct answer(s). var x; function sub1( ) { document.write("x = " + x + " "); } function sub2( ) { var x; x = 10; sub1( ); } x = 5; sub2( );5 under static scoping
    10 under dynamic scoping
  109. 109With this binding, array subscript ranges are dynamically bound and the storage allocation is dynamic (done at run-time). The advantage is flexibility as the size of an array need not be known until the array is to be used.Stack-dynamic
  110. 110With this binding, array subscript ranges are statically bound, but the storage allocation is done at declaration time. The advantage is space-efficiency.fixed stack-dynamic
  111. 111The ___ environment of a statement is the collection of all of the variables that are visible to that statement.referencing
  112. 112A(n) ___ is a homogeneous aggregate of data elements in which an individual element is identified by its position in the aggregate, relative to the first element.Array
  113. 113Scalar variables can be separated into four categories by considering their lifetimes. Which is not one of them?dynamic
  114. 114Binding can be ___.static or dynamic
  115. 115For length option(s) of string data type, some languages (e.g., Perl, JavaScript), it is ___Dynamic length (no max)
  116. 116For length option(s) of string data type, some languages (e.g., C and C++), it is ___. In these languages, a special character is used to indicate the end of a string's characters, rather than maintaining the length.Limited Dynamic Length
  117. 117In several languages that support object-oriented programming, records are supported with ___.objects

Information

Description
2 Organization of Programming Langs Flashcards on OOP Langs Test 2 part b, created by James Herd on 28/03/2019.
Created by
James Herd
Views
8
Rating

Feedback

What is it about?

What do you think of the new look?

How do you like it?