Brainscape's Knowledge GenomeTM

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


See full index

Compilers > Midterm Vocab > Flashcards

Midterm Vocab Flashcards

1
Q

absolute address

A

the numeric address of a location in memory.
cf. relative address.

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

address alignment

A

see storage alignment.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
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
6
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
7
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
8
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
9
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
10
Q

abstract syntax tree

A

AST

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
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
12
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
13
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
14
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
15
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
16
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
17
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
18
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
19
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
20
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
21
Q

compiler

A

a program that translates a source language into an
object language that is executable on a computer.

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

compiler-compiler

A

a program that produces a compiler for a language from a specification
of the syntax and semantics of the language, e.g. yacc.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
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
24
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
25
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
26
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
27
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
28
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
29
Q

DFA

A

deterministic finite automaton.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
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
31
Q

dynamic scoping

A

a convention in a language, such as Lisp, that a variable can be referenced
by any procedure that is executed after it has become bound and before
it becomes unbound; thus, the scope of the variable can depend on the
execution sequence.

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

enumerate

A

to generate all of the members of a set.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
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
34
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
35
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
36
Q

FA

A

finite automaton.

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

FAR

A

finite automaton recognizable.

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

field

A

a component part of a data record.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
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
40
Q

finite automaton recognizable

A

a language that is regular. Abbreviated FAR.

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

finite state machine

A

see finite automaton.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
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
43
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
44
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
45
Q

identifier

A

a symbol that is used as the name of a variable, type,
constant, procedure, etc.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
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
47
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.

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

Kleene closure

A

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

49
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.

50
Q

left-associative operator

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.

51
Q

left factoring

A

a method of modifying a grammar to eliminate left recursion.

52
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.

53
Q

leftmost derivation

A

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

54
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.

55
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.

56
Q

lexical analyzer

A

a program that performs lexical analysis and outputs the internal form
of lexemes.

57
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.

58
Q

local ambiguity

A

a case in which a language construct might be parsed
in more than one way; the correct parsing is determined by examining the
wider context of the construct. Example: 3.14 vs. 3..14

59
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.

60
Q

nonterminal symbol

A

a symbol that names a phrase in a grammar.

61
Q

object language

A

the output language of a compiler.

62
Q

offset

A

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

63
Q

operand

A

a data value upon which an operation is performed.

64
Q

operator

A

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

65
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.

66
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.

67
Q

padding

A

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

68
Q

parser

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.

69
Q

parsing

A

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

70
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.

71
Q

phase of compiler

A

a major section of the compilation process, generally involving examination
of the entire program, e.g., syntax analysis, optimization, or code
generation.

72
Q

postfix

A

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

73
Q

postorder

A

an order of visiting trees, in which the children of a node are examined
first, in left-to-right order, followed by examination of the node itself.

74
Q

precedence

A

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

75
Q

precedence relations

A

a specification of the relative precedence of a set of operators,
i.e., that one operator is less, equal, or greater in precedence
than another.

76
Q

predictive parsing

A

a form of parsing in which the grammar rule to be used for later input
is predicted, e.g., on the basis of a keyword that begins a statement.

77
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.
78
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.

79
Q

production

A

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

80
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.

81
Q

record

A

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

82
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.

83
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.

84
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.

85
Q

regular expression

A

an algebraic expression that denotes a regular language.

86
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.

87
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.

88
Q

relative address

A

an address specified by an offset relative to some other address.

89
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.

90
Q

right-associative operator

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.

91
Q

rightmost derivation

A

a derivation in which the rightmost nonterminal in the string is replaced
at each step. Also, canonical derivation.

92
Q

scalar type

A

a data type that occupies a fixed amount of storage.

93
Q

semantics

A

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

94
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.

95
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.

96
Q

start symbol

A

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

97
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.

98
Q

static analysis

A

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

99
Q

static data

A

data whose address in memory is constant during execution of a program

100
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.

101
Q

storage alignment

A
  1. the requirement of some CPU’s that certain data have addresses
    that fall at even memory word boundaries, so that the data will be
    contained in whole memory words.
  2. in a compiler or assembler, the adjustment of memory addresses
    so that data will be properly aligned.
102
Q

storage allocation

A

the assignment of memory locations to data
and program code.

103
Q

string

A

a sequence of symbols or characters.

104
Q

subrange

A

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

105
Q

substring

A

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

106
Q

suffix

A

a sequence of symbols at the end of a string.

107
Q

symbol table

A

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

108
Q

syntax

A

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

109
Q

syntax analysis

A

1.the analysis of the form of a statement, such as a programming
language statement or command, to determine its component parts; parsing.
2. the syntax analysis phase of a compiler.

110
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.

111
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.

112
Q

terminal symbol

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.

113
Q

token

A

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

114
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).

115
Q

type

A

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

116
Q

type coercion

A

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

117
Q

type constructor

A

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

118
Q

variable

A

an element of computer memory that can hold a value.

Compilers (2 decks)

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