• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key

image

Play button

image

Play button

image

Progress

1/131

Click to flip

131 Cards in this Set

  • Front
  • Back
lexeme
smallest syntactical unit
token
constant or integer that stands for a group of lexemes
lexical analyzer
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.
syntax analyzer/parser
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.
state diagram
a directed graph. The nodes are labeled with state names. The arcs are labeled with input characters.
top-down
parsers build the tree from the root downward to the leaves.
bottom-up
parsers build the tree from the leaves upward to the root.
recursive-descent parser
parser consists of a collection of subprograms, many of which are recursive; it produces a parse tree in top-down order.
handle
A given right sentential form may include more than one RHS from the gram- mar. The correct RHS to reduce is called the
direct left recursion
recursion in which the LHS occurs on the left of the
pairwise disjointness test
____ is used to test a non-left recursive grammar to determine whether it can be parsed in a top-down fashion
left factoring

handle
leftmost simple phrase
phrase
___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
simple phrase
__is a phrase that is derived from a nonterminal in a single step
shift reduce algorithm
Bottom-up parsers are often called _____because shift and reduce are their two fundemental actions
pushdown automaton
A bottom-up parser can be modeled by a simple theoretical machine know as _________
canonical LR
____algorithm was not widely used because producing the parsing table required large amounts of computer time and memory
name
identifier
identifier
name
keyword
is a special word that cannot be used as a name only in certain contexts
reserved word
is a special word that cannot be used as a name.
attributes of a variable (6)
name, address, value, type, lifetime, scope
l-value
that which can appear on the left side of an equal sign
r-value
A variable’s value is sometimes called its
lifetime
of a variable is the time during which the variable is bound to a specific memory location.
scope
The _ of a program variable is the range of statements in which the variable is visible.
visible
A variable is _ in a statement if it can be referenced in that statement.
nonlocal
variables that are visible within a program unit or block but are not declared there.
static scoping
With _ scoping, the scope of a variable can be determined prior to execution.
static parent, static ancestors
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.
block
Many languages allow new static scopes to be defined in the middle of execut- able code by a type of statement called a _.
block-structured language
Blocks explain the origin of the term _ _ _
referencing environment
The _ _ of a statement is the collection of all variables that are visible in the statement.
active subprogram
A subprogram is _ if its execution has begun but has not yet terminated.
binding static
A binding is _ if it occurs before run time and remains unchanged through- out program execution.
binding dynamic
If the binding first occurs during run time or can change in the course of program execution, it is called _.
binding time
The time at which a binding takes place is called the _ time.
explicit declaration
A statement that lists variable names and specifies that they are a particular type.
implicit declaration
A rule that associates variables with types through default conventions. The first appearance of a variable name in a program constitutes its _ declaration.
declaration
_ specify types and other attributes but do not cause allocation of storage.
definition
_ specify attributes and cause storage allocation.
allocation
The memory cell to which a variable is bound must be taken from a pool of available memory. This process is called _
deallocation
_ is the process of placing a memory cell that has been unbound from a variable back into the pool of available memory.
static variable
are bound to memory cells before program execution begins and remain bound to those same cells until program termination.
history-sensitive
When variables retain their values
between subprogram calls they are called
stack-dynamic
are those whose storage bindings are created when their declarations are elaborated, but whose types are statically bound.
elaboration
of a declaration refers to the storage allocation and binding process that takes place when the code containing the declaration is executed.
explicit heap dynamic
are nameless (abstract) memory cells that are allocated by explicit run-time instructions.
implicit heap dynamic
are bound to heap storage only when they are assigned values.
type checking
is the activity of ensuring that the operands of an operator are of compatible types.
compatible types
type is one that is either legal for the operator or is allowed under language rules to be implicitly converted to a legal type.
coercion
automatic type conversion
type error
is the application of an operator to an operand of an inappropriate type.
dynamic type checking
Dynamic type binding requires type check- ing at run time, which is called
strongly typed
A programming language is _ if type errors are always detected,
either at compile time or at run time.
name type equivalence
Variables have equivalent types if they are defined either in the same declaration or in declarations that use the same type name.
structure type equivalence
Variables have equivalent types if their types have identical structures.
derived type
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;
subtype
is a possibly range-constrained version of an existing type. e.g. _ Small_Type is Integer range 0..99;
unconstrained array types (ADA)
Ada’s _ array types allow some flexibility while still enforcing name type equivalence.
anonymous types
Variables can be declared in many languages without using type names, creating _ types.
named constant
A _ constant is a variable that is bound to the same value throughout its lifetime.
manifest constant
Named constants that are statically bound are called _ constants.
initialization
Binding a variable to a value at the same time it is bound to storage is called _.
scalar
Datatypes are either _ (structured) or non _
data type
A _ defines a collection of values and a set of operations on those values.
descriptor
A _ is a collection of the attributes of a variable.
primitive datatypes
Data types that are not defined in terms of other types are called _ data types.
sign magnitude
In _ notation, the sign bit is set to indicate negative and the remainder of the bit string represents the absolute value of the number.
two's complement
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.
one’s complement
In _ notation, a negative integer is stored as the logical complement of its absolute value.
floating point
_ data types model real numbers, but the floating-point representa- tion of most real numbers is only an approximation.
precision
In floating point, _ is the accuracy of the fractional part of a value.
range
In floating point, _ is a combination of the _ of fractions, and, more importantly, the _ of exponents.
decimal
_ types store a fixed number of _ digits, with the _ point placed at a fixed position.
binary coded decimal
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.
boolean
_ types provide only the values true and false.
character string type
The values of a _ _ _ are sequences of characters.
substring reference, slices
A _ reference is used to select a portion of a string. In some languages, _ references are _ of arrays.
regular expressions
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.
static vs. dynamic length strings
_ The length of a string is fixed. _ The length of a string can vary with no maximum. Example: Strings in JavaScript and Perl.
limited dynamic length strings
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++.
immutable strings
strings that can't be changed
ordinal type
An _ type is one whose range of possible values can be easily associated with a set of integers.
enumeration type, enumeration constant
The definition of an _ type defines all possible values of the type by providing a list of _ constants.
overloaded literal
In Ada, enumeration literals are allowed to appear in more than one declaration in the same scope. These are called _ _.
subrange type
___ is a contiguous subsequence of an ordinal type
array
An ____ is a data structure with two properties: 1) all elements have the same type 2) Elements accessed by position
subscript
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 ____
indices
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 ____
static array
A __ is an array with subscript ranges that are statically bound and storage allocation is static
fixed stack dynamic array
A _ is an array with subscript ranges that are statically bound but instead of having statically bound storage locations, allocation is done during execution
stack dynamic array
arrays declared in functions or procedure or blocks
fixed heap dynamic array
array in which the allocation is used via malloc or new.
heap dynamic array
array in which the binding of subscript ranges and the storage allocation is dynamic and can change any number of times.
heterogeneous array
A _ array is one in which the elements need not be of the same type.
aggregate value
Collections of values delimited by parentheses are called _ values.
elemental
Fortran 95 includes a number of array operations that are called _ because they are operations between pairs of array elements.
rectangular
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.
ragged (jagged)
Another kind of array found in some languages is the _ array, in which the lengths of rows need not be the same.
row major order
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
column major order
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.
associative array/hash
Python’s _ arrays (dictionaries) are similar to Perl’s hashes, except that the values are references to objects.
record
A _ is a possibly heterogeneous data aggregate in which individual ele- ments are identified by names.
dot notation
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.
fully qualified reference
A _ _ _ to a record field is one in which all intermediate
record names, from the largest enclosing record to the specific field, are named.
elliptical reference
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.
union
A _ is a type whose values are chosen from two or more existing types.
free union
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.
tag/discriminant/discriminated union
In some languages, each union includes a type indicator, known as a _ or _. A union with a discriminant is called a _ union.
variant part (Pascal), variant record
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.
constrained
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.
safe unions (ADA)

pointer
The values of a ____ type consist of memory addresses and a special value
dereferencing
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.)
implicit dereferencing

dangling pointer/reference
A _____ is a pointer that contain the address of a heap dynamic vairable that has been deallocated
lost heap dynamic variable
A _________ is a heap-dynamic variable that is no longer accessible to a program
garbage
Variables are called ____ because they are no longer useful , yet the space they occupy cannot be reallocated
memory leakage
The problem of lost heap-dynamic variables is sometimes called ____
access types
Ada's pointer types are called _____
pointer arithmetic
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.
reference type
A value of a __ ___ is similar to a pointer, except that it must refer to an object or other value in memory
unsafe
Subprograms in C# that uses pointers must include the ____modifier
tombstone
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.
lock and key
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.
reference counting - eager approach
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.
mark-sweep - lazy approach
_ _ 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.
deferred reference counting
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.
incremental mark sweep
_ _ _ 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.