Programming Language Concepts Test 2

Front 1

lexeme

Back 1

smallest syntactical unit

Front 2

token

Back 2

constant or integer that stands for a group of lexemes

Front 3

lexical analyzer

Back 3

collects input characters into groups (lexemes) and assigns an internal code (a token) to each group. deals with small-scale language constructs, such as names and numeric literals.

Front 4

syntax analyzer/parser

Back 4

check the syntax of a program and create a parse tree from it. deals with large-scale constructs, such as expressions, statements, and program units.

Front 5

state diagram

Back 5

a directed graph. The nodes are labeled with state names. The arcs are labeled with input characters.

Front 6

top-down

Back 6

parsers build the tree from the root downward to the leaves.

Front 7

bottom-up

Back 7

parsers build the tree from the leaves upward to the root.

Front 8

recursive-descent parser

Back 8

parser consists of a collection of subprograms, many of which are recursive; it produces a parse tree in top-down order.

Front 9

handle

Back 9

A given right sentential form may include more than one RHS from the gram- mar. The correct RHS to reduce is called the

Front 10

direct left recursion

Back 10

recursion in which the LHS occurs on the left of the

Front 11

pairwise disjointness test

Back 11

____ is used to test a non-left recursive grammar to determine whether it can be parsed in a top-down fashion

Front 12

left factoring

Front 13

handle

Back 13

leftmost simple phrase

Front 14

phrase

Back 14

___is a string consisting of all of the leaves of the partial tree that is rooted at one particular internal node of the whole parse tree

Front 15

simple phrase

Back 15

__is a phrase that is derived from a nonterminal in a single step

Front 16

shift reduce algorithm

Back 16

Bottom-up parsers are often called _____because shift and reduce are their two fundemental actions

Front 17

pushdown automaton

Back 17

A bottom-up parser can be modeled by a simple theoretical machine know as _________

Front 18

canonical LR

Back 18

____algorithm was not widely used because producing the parsing table required large amounts of computer time and memory

Front 19

name

Back 19

identifier

Front 20

identifier

Back 20

name

Front 21

keyword

Back 21

is a special word that cannot be used as a name only in certain contexts

Front 22

reserved word

Back 22

is a special word that cannot be used as a name.

Front 23

attributes of a variable (6)

Back 23

name, address, value, type, lifetime, scope

Front 24

l-value

Back 24

that which can appear on the left side of an equal sign

Front 25

r-value

Back 25

A variable’s value is sometimes called its

Front 26

lifetime

Back 26

of a variable is the time during which the variable is bound to a specific memory location.

Front 27

scope

Back 27

The _ of a program variable is the range of statements in which the variable is visible.

Front 28

visible

Back 28

A variable is _ in a statement if it can be referenced in that statement.

Front 29

nonlocal

Back 29

variables that are visible within a program unit or block but are not declared there.

Front 30

static scoping

Back 30

With _ scoping, the scope of a variable can be determined prior to execution.

Front 31

static parent, static ancestors

Back 31

When a program contains a reference to a variable, the attributes of the variable can be determined by finding the variable’s declaration.
The search begins in the subprogram containing the reference to the variable. The search then continues to the enclosing subprogram (the _ _), its
static parent, and so on, through all the _ _ of the subprogram.

Front 32

block

Back 32

Many languages allow new static scopes to be defined in the middle of execut- able code by a type of statement called a _.

Front 33

block-structured language

Back 33

Blocks explain the origin of the term _ _ _

Front 34

referencing environment

Back 34

The _ _ of a statement is the collection of all variables that are visible in the statement.

Front 35

active subprogram

Back 35

A subprogram is _ if its execution has begun but has not yet terminated.

Front 36

binding static

Back 36

A binding is _ if it occurs before run time and remains unchanged through- out program execution.

Front 37

binding dynamic

Back 37

If the binding first occurs during run time or can change in the course of program execution, it is called _.

Front 38

binding time

Back 38

The time at which a binding takes place is called the _ time.

Front 39

explicit declaration

Back 39

A statement that lists variable names and specifies that they are a particular type.

Front 40

implicit declaration

Back 40

A rule that associates variables with types through default conventions. The first appearance of a variable name in a program constitutes its _ declaration.

Front 41

declaration

Back 41

_ specify types and other attributes but do not cause allocation of storage.

Front 42

definition

Back 42

_ specify attributes and cause storage allocation.

Front 43

allocation

Back 43

The memory cell to which a variable is bound must be taken from a pool of available memory. This process is called _

Front 44

deallocation

Back 44

_ is the process of placing a memory cell that has been unbound from a variable back into the pool of available memory.

Front 45

static variable

Back 45

are bound to memory cells before program execution begins and remain bound to those same cells until program termination.

Front 46

history-sensitive

Back 46

When variables retain their values
between subprogram calls they are called

Front 47

stack-dynamic

Back 47

are those whose storage bindings are created when their declarations are elaborated, but whose types are statically bound.

Front 48

elaboration

Back 48

of a declaration refers to the storage allocation and binding process that takes place when the code containing the declaration is executed.

Front 49

explicit heap dynamic

Back 49

are nameless (abstract) memory cells that are allocated by explicit run-time instructions.

Front 50

implicit heap dynamic

Back 50

are bound to heap storage only when they are assigned values.

Front 51

type checking

Back 51

is the activity of ensuring that the operands of an operator are of compatible types.

Front 52

compatible types

Back 52

type is one that is either legal for the operator or is allowed under language rules to be implicitly converted to a legal type.

Front 53

coercion

Back 53

automatic type conversion

Front 54

type error

Back 54

is the application of an operator to an operand of an inappropriate type.

Front 55

dynamic type checking

Back 55

Dynamic type binding requires type check- ing at run time, which is called

Front 56

strongly typed

Back 56

A programming language is _ if type errors are always detected,
either at compile time or at run time.

Front 57

name type equivalence

Back 57

Variables have equivalent types if they are defined either in the same declaration or in declarations that use the same type name.

Front 58

structure type equivalence

Back 58

Variables have equivalent types if their types have identical structures.

Front 59

derived type

Back 59

A _ type is _ from an existing type (the parent type). Identical in structure to the parent type, but not equivalent to that type. Inherits all the properties of the parent type. May place range constraints on the parent type. Literals (such as 3.0) can be used with both the parent type and the _ type. e.g. type celsius is new Float;

Front 60

subtype

Back 60

is a possibly range-constrained version of an existing type. e.g. _ Small_Type is Integer range 0..99;

Front 61

unconstrained array types (ADA)

Back 61

Ada’s _ array types allow some flexibility while still enforcing name type equivalence.

Front 62

anonymous types

Back 62

Variables can be declared in many languages without using type names, creating _ types.

Front 63

named constant

Back 63

A _ constant is a variable that is bound to the same value throughout its lifetime.

Front 64

manifest constant

Back 64

Named constants that are statically bound are called _ constants.

Front 65

initialization

Back 65

Binding a variable to a value at the same time it is bound to storage is called _.

Front 66

scalar

Back 66

Datatypes are either _ (structured) or non _

Front 67

data type

Back 67

A _ defines a collection of values and a set of operations on those values.

Front 68

descriptor

Back 68

A _ is a collection of the attributes of a variable.

Front 69

primitive datatypes

Back 69

Data types that are not defined in terms of other types are called _ data types.

Front 70

sign magnitude

Back 70

In _ notation, the sign bit is set to indicate negative and the remainder of the bit string represents the absolute value of the number.

Front 71

two's complement

Back 71

In _ notation, the representation of a negative integer is formed by adding 1 to the logical complement of the number’s absolute value. _ is used by most modern computers. _ is convenient for addition and subtraction.

Front 72

one’s complement

Back 72

In _ notation, a negative integer is stored as the logical complement of its absolute value.

Front 73

floating point

Back 73

_ data types model real numbers, but the floating-point representa- tion of most real numbers is only an approximation.

Front 74

precision

Back 74

In floating point, _ is the accuracy of the fractional part of a value.

Front 75

range

Back 75

In floating point, _ is a combination of the _ of fractions, and, more importantly, the _ of exponents.

Front 76

decimal

Back 76

_ types store a fixed number of _ digits, with the _ point placed at a fixed position.

Front 77

binary coded decimal

Back 77

Decimal types are stored like character strings, using _ _ _, in which each decimal digit is stored in binary. Each digit can be stored in a byte, or two digits can be packed into a single byte.

Front 78

boolean

Back 78

_ types provide only the values true and false.

Front 79

character string type

Back 79

The values of a _ _ _ are sequences of characters.

Front 80

substring reference, slices

Back 80

A _ reference is used to select a portion of a string. In some languages, _ references are _ of arrays.

Front 81

regular expressions

Back 81

Perl, JavaScript, Ruby, and PHP all provide built-in pattern matching operations based on _ _. _ _ evolved from the early UNIX line editor, ed, to become part of the UNIX shell languages.

Front 82

static vs. dynamic length strings

Back 82

_ The length of a string is fixed. _ The length of a string can vary with no maximum. Example: Strings in JavaScript and Perl.

Front 83

limited dynamic length strings

Back 83

The length of a string can vary up to a declared and fixed maximum set by the variable’s definition. Example: Strings in C and “C-style” strings in C++.

Front 84

immutable strings

Back 84

strings that can't be changed

Front 85

ordinal type

Back 85

An _ type is one whose range of possible values can be easily associated with a set of integers.

Front 86

enumeration type, enumeration constant

Back 86

The definition of an _ type defines all possible values of the type by providing a list of _ constants.

Front 87

overloaded literal

Back 87

In Ada, enumeration literals are allowed to appear in more than one declaration in the same scope. These are called _ _.

Front 88

subrange type

Back 88

___ is a contiguous subsequence of an ordinal type

Front 89

array

Back 89

An ____ is a data structure with two properties: 1) all elements have the same type 2) Elements accessed by position

Front 90

subscript

Back 90

Accessing an array element is done by giving the name of the array and a selector that specifiesthe position of the element. The position is specified by ____

Front 91

indices

Back 91

Accessing an array element is done by giving the name of the array and a selector that specifiesthe position of the element. The position is specified by ____

Front 92

static array

Back 92

A __ is an array with subscript ranges that are statically bound and storage allocation is static

Front 93

fixed stack dynamic array

Back 93

A _ is an array with subscript ranges that are statically bound but instead of having statically bound storage locations, allocation is done during execution

Front 94

stack dynamic array

Back 94

arrays declared in functions or procedure or blocks

Front 95

fixed heap dynamic array

Back 95

array in which the allocation is used via malloc or new.

Front 96

heap dynamic array

Back 96

array in which the binding of subscript ranges and the storage allocation is dynamic and can change any number of times.

Front 97

heterogeneous array

Back 97

A _ array is one in which the elements need not be of the same type.

Front 98

aggregate value

Back 98

Collections of values delimited by parentheses are called _ values.

Front 99

elemental

Back 99

Fortran 95 includes a number of array operations that are called _ because they are operations between pairs of array elements.

Front 100

rectangular

Back 100

Some programming languages support only one-dimensional arrays. In these languages, a multidimensional array is treated as an array whose elements are arrays. Other languages provide a “true” multidimensional array, which is sometimes called a _ array.

Front 101

ragged (jagged)

Back 101

Another kind of array found in some languages is the _ array, in which the lengths of rows need not be the same.

Front 102

row major order

Back 102

In _, the elements of the array that have as their first subscript the lower bound of that subscript are stored first, followed by the elements of the second value of the first subscript, and so forth. rightmost variable varies most frequently

Front 103

column major order

Back 103

In _ _ _, the elements of an array that have as their last sub- script the lower bound of that subscript are stored first, followed by the elements of the second value of the last subscript, and so forth.

Front 104

associative array/hash

Back 104

Python’s _ arrays (dictionaries) are similar to Perl’s hashes, except that the values are references to objects.

Front 105

record

Back 105

A _ is a possibly heterogeneous data aggregate in which individual ele- ments are identified by names.

Front 106

dot notation

Back 106

Most other languages use _ _ for field references. An Ada example: Employee_Record.Employee_Name.Middle With _ _, the name of the largest enclosing record comes first; the field name comes last.

Front 107

fully qualified reference

Back 107

A _ _ _ to a record field is one in which all intermediate
record names, from the largest enclosing record to the specific field, are named.

Front 108

elliptical reference

Back 108

COBOL also allows _ references to record fields. In an _ reference, the field is named, but any or all of the enclosing record names can be omitted, as long as the resulting reference is unambiguous.

Front 109

union

Back 109

A _ is a type whose values are chosen from two or more existing types.

Front 110

free union

Back 110

Fortran, C, and C++ provide union constructs that are not fully type checked. Unions in these languages are called _ unions because of the freedom allowed in their use.

Front 111

tag/discriminant/discriminated union

Back 111

In some languages, each union includes a type indicator, known as a _ or _. A union with a discriminant is called a _ union.

Front 112

variant part (Pascal), variant record

Back 112

Pascal records may contain a discriminated union, known as the _ part of the record. A record containing a variant part is known as a _ record.

Front 113

constrained

Back 113

Ada also provides a way to specify that a variable of a variant record type will store only one of the possible variants; the variable is is said to be _. This feature allows static type checking to be performed.

Front 114

safe unions (ADA)

Front 115

pointer

Back 115

The values of a ____ type consist of memory addresses and a special value

Front 116

dereferencing

Back 116

There are two ways to interpret an occurrence of a pointer variable in an expression:
As a reference to the variable itself. As an indirect reference to the memory cell that the variable points to. (Accessing this cell is called _ing the pointer.)

Front 117

implicit dereferencing

Front 118

dangling pointer/reference

Back 118

A _____ is a pointer that contain the address of a heap dynamic vairable that has been deallocated

Front 119

lost heap dynamic variable

Back 119

A _________ is a heap-dynamic variable that is no longer accessible to a program

Front 120

garbage

Back 120

Variables are called ____ because they are no longer useful , yet the space they occupy cannot be reallocated

Front 121

memory leakage

Back 121

The problem of lost heap-dynamic variables is sometimes called ____

Front 122

access types

Back 122

Ada's pointer types are called _____

Front 123

pointer arithmetic

Back 123

C and C++ support three forms of _ _:
Adding an integer to a pointer, Subtracting an integer from a pointer, and Subtracting two pointers For example, if ptr is a pointer variable, then ptr + index is a legal expression. The value of index is first scaled by the size of the memory cell to which ptr is pointing. _ _ is valid only with pointers to array elements.

Front 124

reference type

Back 124

A value of a __ ___ is similar to a pointer, except that it must refer to an object or other value in memory

Front 125

unsafe

Back 125

Subprograms in C# that uses pointers must include the ____modifier

Front 126

tombstone

Back 126

A proposed solution for the dangling pointer problem involves the use of _ All heap-dynamic variables are accompanied by a special cell, called a _, that points to the heap-dynamic variable. Pointer variables point only at _ and never to heap-dynamic variables. When a heap-dynamic variable is deallocated, the _ remains but is set to nil, indicating that the heap-dynamic variable no longer exists.

Front 127

lock and key

Back 127

An alternative to tombstones is the _ and _ approach used in the implementation of UW-Pascal. A pointer is stored as a (_, address) pair, where the _ is an integer value. Each heap-dynamic variable has a header cell that stores an integer _ value.

Front 128

reference counting - eager approach

Back 128

With the _ _ method, each cell contains a counter that keeps track of how many pointers are currently pointing to the cell. When a pointer variable is made to point to a different cell, the _ _ for the old cell (if any) is decremented, and the _ _ for the new cell is incremented. If the _ _ for a cell reaches zero, it means that no pointers are pointing to the cell, so the cell can be returned to the list of available space.

Front 129

mark-sweep - lazy approach

Back 129

_ _ garbage collection begins when there are no free cells (or the num- ber of available cells has dropped below a certain level). Every heap cell has an extra indicator bit or field that is used by the collection algorithm.
Phases of _ _ garbage collection:
1. All cells in the heap have their indicators set to indicate they are garbage.
2. (_ phase) Every pointer in the program is traced into the heap, and all
reachable cells are marked as not being garbage.
3. (_ phase) All cells that have not been marked as still in use are returned
to the list of available space.

Front 130

deferred reference counting

Back 130

The time required to maintain reference counters can hurt the performance of a program. Performance can be improved by _ reference counting, which avoids reference counters for some pointers.

Front 131

incremental mark sweep

Back 131

_ _ _ garbage collection occurs more frequently, long before memory is exhausted. This strategy is more effective at reclaiming storage and reduces the delay in application execution.