Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Compilers > Final Vocab > Flashcards

Final Vocab Flashcards

1
Q

absolute code

A

computer program code that is executable without
further processing: all addresses in the code are absolute.
cf. relocatable code.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

abstract syntax tree (AST)

A

a tree representation of a program
that is abstracted from the details of a particular programming
language and its surface syntax.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

accepting state

A

a state of a finite automaton in which the input string is accepted
as being a member of the language recognized by the automaton.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

actual parameter

A

a parameter used in a call to a subprogram. cf. formal parameter.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

address alignment

A

see storage alignment.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

adjacency matrix

A

a method of representing a graph by a Boolean
matrix M , where M_{ij = 1 iff there is an arc from node i
to node j in the graph.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

aliasing

A

the creation of an alternate name for data, either in the definition of
a program or during its operation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

alphabet

A

a set of symbols used in the definition of a language.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

ambiguity

A

a case where more than one interpretation is possible.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

ambiguous grammar

A

a grammar that allows some sentence or string to be generated
or parsed in more than one way (i.e., with distinct parse trees).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

antisymmetric

A

a relation * is antisymmetric iff
forall a, b . a b and b a –> a = b .
Example <=

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

arity

A

the number of arguments of a function.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

associativity

A

a specification of the order in which operations should be performed
when two operators of the same precedence are adjacent. Most operators
are left-associative, e.g. the expression A - B - C
should be interpreted as ((A - B) - C).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

augmented transition network (ATN)

A

a formalism for describing parsers, especially for natural language.
Similar to a finite automaton, but augmented in that arbitrary tests may be
attached to transition arcs, subgrammars may be called recursively, and
structure-building actions may be executed as an arc is traversed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

automatic programming

A

synthesis of a program that satisfies a
specification, where the specification is higher-level than ordinary
programming languages.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

available

A

an expression is available if it has been computed previously in the
computation path preceding the current location and has not been killed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

AVL tree

A

self-balancing binary search tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

backpatching

A

filling in the address of a label, which has just become defined, in preceding parts of the program that made forward references to it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

backward referencing

A

a reference to an earlier statement in the program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

base address

A

the address of the beginning of a data area. This address is added to a relative address or offset to compute an absolute address.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

basic block

A

a sequence of program statements such that if any of them is executed, all
of them are; a sequence of statements that has a label (if any) only at the
beginning and a branch (if any) only at the end.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

basic type

A

a data type that is implemented in computer hardware
instructions, such as integer or real.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

bit vector

A

a sequence of Boolean values (0 or 1) represented as the
bits of one or more computer words. It is an efficient representation
for sets that are subsets of a fairly small finite set of possible elements.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

BNF

A

Backus-Naur Form, a syntax for writing context-free grammars
that describe computer languages.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Boolean matrix

A

a matrix whose elements are Boolean values, 0
or 1.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

bottom-up parsing

A

a parsing method in which input words are matched against the right-hand
sides of grammar productions in an attempt to build a parse tree from the
bottom towards the top.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

boxed number

A

a form of number storage that contains type information as well as a numeric value, e.g. Integer in Java.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

BSS

A

a pseudo-operation for some assemblers, used to specify the
reservation of a block of storage, perhaps initialized to some constant
value. (an abbreviation of Block Starting with Symbol.)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

busy

A

describes a variable whose value will be needed later during
program execution. Also, live.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

cache prefetch

A

an instruction that causes the contents
of a specified memory address to be fetched from main memory into the cache
memory so that it will be available for fast access when needed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

call by name

A

a form of parameter transmission in which the effect of a textual
substitution of the actual parameter for the formal parameter is achieved

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

call by reference

A

a form of parameter transmission in which the address of the actual
parameter is transmitted to the subprogram. Any changes to the parameter
made by the subprogram will change the argument as seen by the calling
program.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

call by value

A

a form of parameter transmission in which the value of the actual
parameter is transmitted to the subprogram. Changes to the parameter
made by the subprogram will not be seen by the calling program.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

callee-saved

A

registers whose value must be preserved by a subprogram. The subprogram can either not use those registers, or save their values and restore them before exiting. Also, nonvolatile.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

caller-saved

A

registers whose value may be destroyed by a subprogram. If the calling program wants to save those values, it must do so. Also, volatile.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

canonical form

A

a standardized form of expressions or data. If all programs put their
expressions into a canonical form, the number of cases that will have
to be considered by other programs is reduced.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Cartesian product

A

if A and B are sets, the Cartesian product
A X B is the set of ordered pairs (a, b) where
a in A and b in B .

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

cascading errors

A

a situation, e.g. in compiling a program, where one error causes many
reported errors. For example, failure to declare a variable may cause
an error every time that variable is referenced.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

cast

A

to coerce a given value to be of a specified type.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Chomsky hierarchy

A

the hierarchy of formal language types: regular, context free, context
sensitive, and recursively enumerable languages, each of which is a proper
subset of the following class.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

CKY parser

A

a kind of parser, due to Cocke, Kasami, and Younger, that efficiently produces all possible parses of an input. Also written CYK.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

class

A

in object-oriented programming, a description of a set of similar objects.
For example, Fido, an object or instance, might be a member of the class Dogs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

code generation

A

the phase of a compiler in which executable output code is generated
from intermediate code.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

code motion

A

the movement of code by a compiler to a place other than where it appears
in the source program. For example, an expensive but unchanging
computation might be moved outside a loop.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

collision

A

in a hash table, a case in which a symbol has the same
hash function value as another symbol.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

column-major order

A

a method of storing arrays in which values in a column of the array
are in adjacent memory locations. cf. row-major order.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

computed

A

of a subexpression, having its value computed within a given block of code.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

concatenation

A

making a sequence that consists of the elements of a first sequence
followed by those of a second sequence.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

condition code register

A

A CPU register that describes the result of the last arithmetic operation
or comparison. It typically contains bits for <0, =0,
>0, carry, and overflow.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

constant folding

A

performing at compile time an operation whose
operands are constant, giving a new constant result.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

context-free grammar

A

a grammar in which the left-hand side of each production consists of a
single nonterminal symbol.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

control flow analysis

A

analysis of the possible paths that control flow
may take in a program during execution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

dangling reference

A

in execution of a program, a reference, usually by means of a pointer,
to storage that has been deallocated. For example, in a recursive
language, a pointer to storage that is allocated on the execution stack
could be retained after the routine associated with that stack frame has
exited, resulting in errors.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

data area

A

a contiguous area of memory, specified by its base address and size.
Data within the area are referenced by the base address of the area and
the offset, or relative address, of the data within the area.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

data flow analysis

A

analysis of places in the programs where data
receive values and the places where those data values can subsequently be used.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

dead code

A

parts of a program that cannot be reached during execution and therefore
can never be executed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

declaration

A

a statement in a programming language that provides
information to the compiler, such as the structure of a data record,
but does not specify executable code.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

defined

A

of a variable, having received a value prior to a given point in a program.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

definition-use chain

A

the portion of a program flow graph across which a
variable is both defined and live (busy), beginning at the point where
the variable receives a value and ending at the last place that value is used.
Also, du-chain.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

derivation

A

a list of steps that shows how a sentence
in a language is derived from a grammar by application of grammar rules.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

deterministic finite automaton

A

a finite automaton that has at most one transition from a state for each
input symbol and no empty transitions. Abbreviated DFA.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

disambiguating rules

A

rules that allow an ambiguous situation to be resolved to a single
outcome, e.g. rules of operator precedence.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

dominator

A

a basic block of a program is a dominator of a second block if every
path from the entry of the program to the second block passes through it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

dynamic

A

refers to things that happen or can only be determined
during actual execution of a program. cf. static.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

dynamic memory

A

memory that is assigned during execution of a program, especially heap
memory.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

dynamic type checking

A

testing of the types of the values of variables at runtime, as is done
in Lisp and object-oriented languages. cf. static type checking.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

enumerated type

A

a scalar type consisting of a finite set of
enumerated values, e.g. type boolean = (false, true);.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

epilogue

A

a section of code that is executed just before leaving a subprogram
to restore register values, transfer the result of the subprogram to
the calling program, and branch to the return address.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

equivalent grammars

A

grammars that denote the same language.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

error production

A

a grammar production, as in a Yacc grammar,
that is executed if no other production matches the input.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
71
Q

finite automaton

A

an abstract computer consisting of an alphabet of symbols, a finite
set of states, a starting state, a subset of accepting states, and
transition rules that specify transitions from one state to another
depending on the input symbol. The machine begins in the starting
state; for each input symbol, it makes a transition as specifies by the
transition rules. If the automaton is in an accepting state at the end
of the input, the input is recognized. Also, finite state machine.
Abbreviated FA.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
72
Q

formal parameter

A

a parameter specified in the argument list of a procedure definition.
cf. actual parameter.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
73
Q

forward reference

A

reference to a label in a program that has not yet appeared in the program
text.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
74
Q

fragmentation

A

the breaking up of memory into blocks that are too small to be of use.
cf. internal fragmentation, external fragmentation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
75
Q

garbage

A

storage that can no longer be accessed because no pointer to it exists.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
76
Q

garbage collection

A

the identification of unused storage and collection of it so that it can
be placed back on the heap for reuse.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
77
Q

global optimization

A

optimization based on analysis of the entire
program or procedure.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
78
Q

grammar

A

a formal specification of a language, consisting of a set of nonterminal
symbols, a set of terminal symbols or words, and production rules that specify
transformations of strings containing nonterminals into other strings.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
79
Q

graph

A

a (directed) graph is a pair ( S, Gamma ) where S is a set of
nodes and Gamma subset S X S is a set of transitions between
nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
80
Q

graph coloring

A

an algorithm for assigning a minimal number of ``colors’’ to nodes of
a graph such that no two nodes that are connected have the same color.
Used in compilers as a method of register assignment: colors correspond
to registers, nodes to variables or def-use chains, and connections to
variables that are simultaneously live.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
81
Q

hash function

A

a deterministic function that converts converts a
symbol or other input to a ``randomized’’ integer value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
82
Q

hash table

A

a table that associates key values with data by use of
a hash function.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
83
Q

hash with buckets

A

a form of hash table in which the hash code denotes a bucket or set of entries whose keys hash to that value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
84
Q

heap

A

an area of contiguous memory and/or a set of unused storage records that
can be allocated to the running program as dynamic memory upon request;
the address of the record is returned and assigned to a pointer variable.
new in Pascal, malloc in C, and cons in Lisp allocate
heap memory.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
85
Q

infix

A

an expression written with an operator between its operand,
e.g. a + b . cf. prefix, postfix.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
86
Q

implicit parameter

A

a parameter that is passed to a subprogram without being specified directly
by the programmer, e.g., the return address.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
87
Q

induction variable

A

a variable that is incremented during a loop and used to perform a similar
action on multiple data; also, loop index.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
88
Q

inherit

A

to use a method defined in a superclass.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
89
Q

inherited attribute

A

an attribute of a node in a parse tree that is derived from the context
in which the node appears. cf. synthesized attribute.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
90
Q

inlining

A

inserting code of a subprogram directly into the code compiled for the
calling program, rather than compiling a subroutine call to an external
procedure.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
91
Q

insertion

A

placement of a new data item in its proper position in an ordered sequence, such as a list, array, or symbol table

92
Q

instance

A

in object-oriented programming, an individual data object
that is an instance of a class of similar objects. Also, object.

93
Q

instance variable

A

a data field in an instance.

94
Q

intermediate language

A

an internal language used as the representation of a program during
compilation, such as trees or quadruples. The source language is
translated to intermediate language, then to the object language.

95
Q

interpreted code

A

a form of program that is read and executed by an interpreter program.
The interpreter reads an instruction, determines its meaning, and executes it.

96
Q

interval

A

a set of basic blocks of a program that comprise a sequence of statements or
simple loop.

97
Q

keyword

A

a special word that is used to indicate the structure of a language,
such as the reserved words of computer languages.

98
Q

killed

A

of a subexpression, having any previously computed value invalidated
by redefinition of a component of the subexpression. Note that the term
``killed’’ cannot properly be applied to a program variable.

99
Q

Kleene closure

A

zero or more occurrences of a grammar item;
indicated by a superscript *

100
Q

language denoted by a grammar

A

L(G), the set of strings that can
be derived from a grammar, beginning with the start symbol.

101
Q

left-associative

A

an operator in an arithmetic expression such that if there are two adjacent
occurrences of the operator, the left one should be done first.

102
Q

left factoring

A

a method of modifying a grammar to eliminate left recursion.

103
Q

left recursion

A

in top-down parsing, a grammar rule whose right-hand side begins with the
nonterminal symbol on the left-hand side will cause an infinite recursion,
called left recursion. Also, describes such a production.

104
Q

leftmost derivation

A

a derivation in which the leftmost nonterminal of the string is replaced
at each step.

105
Q

lexeme

A

a basic symbol in a language; e.g., a variable name would be a lexeme for
a grammar of a programming language.

106
Q

lexer

A

lexical analyzer. (a program that performs lexical analysis, reading characters and producing the internal form of lexemes.)

107
Q

lexical analysis

A

parsing and conversion to internal form of the simplest elements of a
language, usually specified by a regular grammar, such as variable
names, numbers, etc.

108
Q

lexical scoping

A

a convention in a block-structured programming language that a variable
can only be referenced within the block in which it is defined and
blocks contained within that block; thus, the scope of a variable is
completely determined at compile time. cf. dynamic scoping.

109
Q

link editor

A

a program that combines relocatable code modules to form an executable
absolute code file. The link editor assigns memory locations for each
relocatable module, relocates relative addresses to form absolute
addresses, finds library modules whose names are referenced as external
symbols and includes those modules in the loading process, and fills in
absolute addresses for external references between modules.

110
Q

live variable

A

a variable whose value will be used at a later point during execution.

111
Q

loader

A

a program in the operating system that executes an absolute program by
allocating storage for it in main memory, reading the program into memory,
and jumping to its entry point. Sometimes link-editing is performed prior
to loading.

112
Q

local optimization

A

optimization that can be done correctly taking
into account only a small part of the program.

113
Q

location counter

A
  1. a counter that denotes the next location in memory for code or
    data during assembly or compilation of a program.
  2. a numeric value that denotes the location of the beginning of a data
    area, which is added to addresses during relocation.
114
Q

loop unrolling

A

conversion of a loop into straight-line code by repetition of the code inside the loop with successive values of the loop index substituted into the code. for ( i = 0; i < 3; i++) x[i] = y[i]; could be unrolled to { x[0] = y[0]; x[1] = y[1]; x[2] = y[2]; }

115
Q

macro

A

a statement in a programming language that is expanded into
one or more statements in the same language, by substitution of
arguments into a language pattern or by construction of the statements
by a program.

116
Q

mark-and-sweep

A

a method of garbage collection in which all storage that is in use is
marked, then all storage that is not marked is swept up for reuse.

117
Q

materialization

A

to store in memory as a discrete data value; to make a copy in memory of
otherwise transient data, such as a value in a register.

118
Q

memory hierarchy

A

a hierarchy of different kinds of computer memory, in which there is a
small amount of costly fast memory (such as registers or cache) and
increasing amounts of slower kinds of memory.

119
Q

memory leak

A

failure to return dynamic memory that is no longer in use; eventually
causes the program to run out of memory.

120
Q

message

A

in object-oriented programming, an indirect function call.
A message is sent to an object; the selector of the message
(an abstract procedure name) is looked up in the class to which the
object belongs to determine the method that is the actual function
that is called.

121
Q

method

A

in an object-oriented system, a procedure associated with a class that performs
the action associated with a message.

122
Q

multiple inheritance

A

in an object-oriented system, the ability of a
class to have multiple superclasses and to inherit methods from all of them.

123
Q

name equivalence

A

type equivalence testing in which two types are considered equal only if
they have the same name. cf. structural equivalence.

124
Q

NaN

A

Not a Number, a floating-point value that does not represent a valid number. This could result from use of uninitialized data (if memory is initialized to NaN’s), arithmetic performed on a NaN, or an undefined operation such as 0/0. A NaN may be quiet, or signalling, in which case its generation or use generates a CPU exception.

125
Q

nondeterministic finite automaton

A

a finite automaton that has multiple state transitions from a single state
for a given input symbol, or that has a null transition, not requiring an
input symbol. Abbreviated NFA.

126
Q

nonterminal

A

a symbol that names a phrase in a grammar.

127
Q

nonvolatile register

A

a register whose value must be preserved across a procedure call.

128
Q

object

A

in an object-oriented programming system, a data structure containing
instance variables and a pointer to the class to which the object belongs.

129
Q

object language

A

the output language of a compiler.

130
Q

object-oriented programming

A

a style of programming based on the use of
objects and messages, as opposed to data structures and procedure
calls.

131
Q

observability

A

the ability to observe the state of a system. For software, the provision of built-in code to allow the internal operations of a program to be easily observed.

132
Q

offset

A

the location of data relative to the start of a data area.

133
Q

operand

A

a data value upon which an operation is performed.

134
Q

operator

A

a symbol that denotes an operation to be performed on data in an expression.

135
Q

optimization

A

transformation of a program to produce a program whose input-output
behavior is equivalent to that of the original program, but that has lower cost,
e.g. faster execution time.

136
Q

overloading

A

the assignment of multiple meanings to an operator, depending on the type
of data to which it is applied; e.g., the symbol + could represent
integer addition, floating-point addition, or matrix addition.

137
Q

padding

A

insertion of an area of unused storage in order to achieve storage alignment.

138
Q

Pareto distribution

A

informally, a distribution in which most of a phenomenon is accounted for by a fraction of a population: 90% of execution time is spent in 10% of code.

139
Q

parametric polymorphism

A

polymorphism in which type expressions
are parameterized, e.g. list of T where T is a type parameter.

140
Q

parse tree

A

a data structure that shows how a statement in a language is derived from
the context-free grammar of the language; it may be annotated with additional
information, e.g. for compilation purposes.

141
Q

parsing

A

the process of reading a source language, determining its structure,
and producing intermediate code for it.

142
Q

partial evaluation

A

optimization of a program by evaluating parts of the program that are
constant at compile time. This may include unrolling loops and algebraic
optimization of operations involving constant data; the resulting program
may be larger, but faster and more suitable for parallel execution.

143
Q

partition

A

a division of a set into disjoint subsets whose union
is the set. A partition corresponds to an equivalence relation

144
Q

pass

A

a phase of a compiler or assembler in which the entire source program
(in its original form or some later representation) is processed.

145
Q

peephole optimization

A

a kind of optimization, performed on generated code by a compiler,
in which a linear pass is made over the code examining a small region
of code to see if it can be improved; e.g., a jump instruction to the
next sequential location can be eliminated.

146
Q

polymorphic function

A

a function that can operate on data of more than one type.

147
Q

postamble

A

see epilogue.

148
Q

postfix

A

a way of writing expressions in which an operator appears
after its operands: ab+.

149
Q

postincrement

A

a CPU feature in which the value of an index register is automatically
incremented by a fixed amount after its use, thus pointing to the next data
in an array.

150
Q

preamble

A

see prologue.

151
Q

precedence

A

an ordering of operators that specifies that certain operators should
be performed before others when no ordering is otherwise specified.

152
Q

prefix

A
  1. a contiguous set of symbols at the beginning of a
    string. 2. a way of writing expressions in which an operator appears
    before its operands: +ab.
153
Q

preorder

A

an order of visiting trees, in which a node is examined first, followed
by recursive examination of its children, in left-to-right order, in
the same fashion

154
Q

production

A

a rule of a context-free grammar, specifying that a nonterminal symbol
can be replaced by another string of symbols.

155
Q

prologue

A

a section of code that is executed immediately upon entry to a subprogram
to save register values, save the return address, and transfer parameters
to the subprogram.

156
Q

quadruples

A

a form of intermediate program code used in compilers, equivalent to
a small assignment statement'' of the formR = X op Y’’ where R
is the result, X and Y are operands, and op is the operation.

157
Q

recognizer

A

a program or abstract device that can read a string of symbols and decide
whether the string is a member of a particular language.

158
Q

record

A

a data area consisting of contiguous component fields,
which may be of different types.

159
Q

recursive descent

A

a method of writing a parser in which a grammar rule is written as a
procedure that recognizes that phrase, calling subroutines as needed for
sub-phrases and producing a parse tree or other data structure as output.

160
Q

reduce-reduce conflict

A

in a grammar for a shift-reduce parser,
a case in which an input might be reduced by more than one production.

161
Q

reduction in strength

A

an optimization in which an operator is changed to a less-expensive
operator; e.g., x * 2 becomes x + x

162
Q

reduction step

A

in shift-reduce parsing, the reduction of items at the top of the stack
to a phrase that encompasses those items.

163
Q

referenced

A

of a variable, having its value read within a sequence of
code.

164
Q

reflexive transitive closure

A

in a graph, the mapping from each node to the set of nodes that can be
reached from it in 0 or more steps.

165
Q

register windows

A

a technique used in the SPARC architecture in which the CPU has a stack of registers and a stack frame or window of these registers is used by a given procedure.

166
Q

regular expression

A

an algebraic expression that denotes a regular language.

167
Q

regular grammar

A

a grammar that denotes a regular language; its productions can only have
on the right-hand side either a terminal string or a terminal string
followed by a single nonterminal.

168
Q

regular language

A

a language described by a regular grammar, or recognizable by a finite
automaton, e.g. a simple item such as a variable name or a number in a
programming language.

169
Q

rehash

A
  1. in a hash table storage scheme, to calculate a new hash value for an item when the previous hash value caused a collision with an existing item. 2. the algorithm used to calculate the new hash value.
170
Q

relation

A

a subset of the Cartesian product of two sets.

171
Q

relocatable code

A

program code that can be relocated to run in different locations in
computer memory. Addresses within the program are specified relative to
location counters; external addresses are specified by symbolic names.

172
Q

relocation

A

the process performed by a link editor to convert relocatable code
into absolute code that can be executed, by adding the absolute starting
address of a data area to relative addresses of data within that data area.

173
Q

reserved word

A

a word in a programming language that is reserved for
use as part of the language and may not be used as an identifier.

174
Q

restore registers

A

to load nonvolatile registers with the saved values that the registers
had upon entry to a subprogram.

175
Q

return address

A

the address immediately following a call to a subprogram; the subprogram
returns when finished by branching to this address.

176
Q

reverse Polish

A

an unambiguous, parenthesis-free notation for expressing an arithmetic
expression. Operators appear after their operands.

177
Q

right-associative

A

an operator in an arithmetic expression such that if there are two adjacent
occurrences of the operator, the right one should be done first.

178
Q

RISC

A

reduced instruction set computer. A CPU in which only a basic set
of instructions is provided and in which extra responsibilities may be
placed upon the compiler, e.g. not using the result of an instruction
until after a certain amount of time has passed.

179
Q

row-major order

A

a method of storing a multi-dimensional array, such that elements of a row
of the array are adjacent in memory. cf. column-major order.

180
Q

save registers

A

to save the values of nonvolatile registers upon entry to a subprogram
so that the values can be restored before the subprogram exits.

181
Q

scalar type

A

a data type that occupies a fixed amount of storage.

182
Q

selector

A

in object-oriented programming, an abstract procedure name or
name of a message action. The class describes the association between the
selector and the corresponding method that performs that action for objects
in the class.

183
Q

semantics

A

the meaning of a statement in a language. cf. syntax.

184
Q

send a message

A

the action of sending a message to (calling a method on) an object.

185
Q

shadowing

A

a case where a name that is closer to the point of use prevents finding the same name in a different context that is farther away. For example, a method name such as .hashCode() that is defined for a Java class will shadow and override the .hashCode() that is defined for Object

186
Q

shift-reduce conflict

A

in a grammar for a shift-reduce parser,
a case in which an input might either be shifted onto the stack or reduced.

187
Q

shift-reduce parser

A

a parser that operates by alternately shifting input elements onto the
top of a stack or reducing a group of elements from the top of the stack to
a larger element representing a phrase.

188
Q

significand

A

the fractional part of a floating-point number; also, mantissa

189
Q

sound type system

A

a type system of a programming language in which it is guaranteed that
the value of a variable at runtime can only be of the type that was
determined for that variable at compile time; i.e., there can be no
runtime type errors.

190
Q

spill code

A

code to store the values of some registers into main memory so that the
registers can be used for other purposes.

191
Q

stack frame

A

a collection of the local variables of a procedure, as well as return
address, saved register values, etc. that are put on the execution
stack for each invocation of a procedure. Also, activation record

192
Q

stack pointer

A

a CPU register that points to the start of the current stack frame and
is used as an index register to access data within the stack frame.

193
Q

start symbol, S

A

he initial, or ``sentence’’ nonterminal symbol S of a grammar.

194
Q

static

A

refers to things that can be determined or performed
prior to execution of a program, e.g., at compile time.
cf. dynamic.

195
Q

static analysis

A

analysis of a program by examining it, but without running it.

196
Q

static type checking

A

checking or determination of the types of variables in a language at
compile time. This eliminates the need for dynamic type checking, but
requires that a variable have only a single type.

197
Q

storage allocation

A

the assignment of memory locations to data
and program code.

198
Q

string

A

a sequence of symbols or characters.

199
Q

strong typing

A

a system of static type checking in which the types of all variables must
be declared and correct use of types is enforced by the compiler.

200
Q

structural equivalence

A

a form of type checking in which two types are considered to be equivalent
if they have the same basic data type, or if they have the same
kind of structure whose components are structurally equivalent.
cf. name equivalence.

201
Q

subrange

A

a contiguous subsequence of a sequence, e.g. 1..10
is a subrange of integer.

202
Q

substring

A

a sequence of symbols that matches a contiguous subsequence of another string.

203
Q

suffix

A

a sequence of symbols at the end of a string.

204
Q

superclass

A

in object-oriented programming, a superset of other
classes. A superclass can provide methods that are inherited by its
subclasses. Mammal might be a superclass of Dog.

205
Q

superscalar

A

a type of CPU design in which, although there is only a single instruction
stream, certain operations that are nearby in that stream can be
executed concurrently using independent functional units in the CPU.

206
Q

symbol table

A

a data structure that associates a name (symbol) with
information about the named object.

207
Q

syntax

A

the rules by which legitimate statements can be constructed.
cf. semantics.

208
Q

syntax directed translation

A

in parsing a programming language, building the translation of a statement
or construct in a mechanical way from the translations of its syntactic
components.

209
Q

synthesized attribute

A

an attribute of a structure, e.g. a phrase in a programming language
statement, that is derived from the attributes of its components. For
example, the sum of two floating-point quantities will also be
floating-point.

210
Q

synthesized translation

A

a method of translating statements, e.g. in a programming language,
such that the translation of a phrase is built up from the translations
of its components.

211
Q

tag

A

a small-integer field that is attached to data to describe its type

212
Q

terminal

A

a symbol in a phrase structure grammar that is a part of the language
described by the grammar, such as a word or character of the language.
cf. nonterminal symbol.

213
Q

token

A

a word, name, or sequence of characters having a meaning as a unit
in a language.

214
Q

top-down parsing

A

a predictive form of parsing, such as recursive descent, in which the
parse tree of a statement is constructed starting at the root (sentence
symbol).

215
Q

transitive closure

A

a relation formed from another relation by making it transitive.
Beginning with the original relation, if a b and b c ,
then a * c is added.
In a graph, the mapping from each node to the set of nodes that can be
reached from it in one or more steps.

216
Q

triples

A

a form of intermediate code used in a compiler, consisting of an operator and two operands. Also called two-address code.

217
Q

type

A

a description of a kind of variables, including a set of
possible values and a set of operations.

218
Q

type coercion

A

the automatic conversion of data from its existing type into the type
required for an operation.

219
Q

type constructor

A

an operator that makes a type from other types,
e.g. array or record.

220
Q

type hierarchy

A

. in an object-oriented system, the hierarchy of data types formed
by the class-superclass relationships.
2. in general, a lattice of data types formed by containment
by higher types, e.g., integers are a subset of reals, which are
a subset of complex numbers.

221
Q

type lattice

A

a lattice structure that shows which types are higher or derivable from others, e.g. float is higher than integer. When an operation is specified on different types, the arguments may be coerced to the least upper bound of the two types in the lattice.

222
Q

type signature

A

type signature
a specification of the argument types and result type of a function or
procedure, e.g. push: item X stack –> stack

223
Q

union type

A

a type formed by the union of other types, i.e. a member of the
union type can have the type of any one of its component types.

224
Q

unreachable code

A

program code that cannot be executed because it is
impossible to get to it.

225
Q

variable

A

an element of computer memory that can hold a value.

226
Q

volatile register

A

a register whose value may be destroyed during a subroutine call.

Compilers (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions