Section 1
Preview this deck
top down
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
0
All-time users
0
Favorites
0
Last updated
6 years ago
Date created
Mar 1, 2020
Cards (196)
Section 1
(50 cards)
top down
A ___ ____ parser produces the parse tree, beginning at the root. The order is that of a leftmost derivation. This traces or builds the parse tree in preorder.
inherited
Syntax <assign> -> <var> = <expr> <expr> -> <var> + <var> | <var> <var> A | B | C actual_type: ___________ for <var> and <expr> expected_type: _________ for <expr> What is the blank for expected type?
terminal
For any rule with multiple definitions, the FIRST set is the first ________ symbol that appears in each definition
Denotational
___________ Semantics: The process of building a ____________ specification for a language: - Define a mathematical object for each language entity. - Define a function that maps instances of the language entities onto instances of the corresponding mathematical objects.
left factoring
You can use ____ ________ to remove pairwise disjointness. Example: replace <variable> -> ident | ident[<expression>] with <variable> -> ident <new> <new> -> eplison | [<expression>]
rule
(In BNF)A ____ has a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and or nonterminals.
abstraction
A variable is an ___________ of a memory cell.
table
LR parsers are _____ driven, where the _____ has two components: an ACTION _____ and a GOTO _____.
Operational
In ___________ semantics, the state changes are defined by coded algorithms.
Token
This is a category of lexemes.
sentential form
(In BNF) Every string of symbols in a derivation is a __________ ____.
Lexeme
This is the lowest level syntactic unit of a language.
repetition or iteration
In Extended BNF form, what does the metasymbol {}, {}+ stand for?
Syntax
The form or structure of the expressions, statements, and program units.
Type
Variables can be characterizes as a sextuple of these following attributes: - Name - Address - Value - _____ - Lifetime - Scope
choose one
In Extended BNF form, what does the metasymbol (choices | separated | by | or bar) stand for?
Pairwise Disjointness
________ ____________ is when more than one RHS of a rule begins with the same terminal identifier Example: <variable> → identifier | identifier[<expression>]
attributes
Variables are characterized by _____________. To design a type, you must consider scope, lifetime, type checking, initilazition, and type compatibility.
Terminals
_________ are lexemes or tokens in BNF.
Axiomatic
__________ Semantics: Axioms or inference rules are defined for each statement type in teh language. The logic expressions are called assertions. An assertion before a statement states the relationships and constraints among variables that are true at that point in execution.
goto
The ____ table specifies which state to put on top of the parse stack after a reduction action is done.
Repetition
What is this an example of in Extended BNF? <ident> -> letter {letter | digit}
Lifetime
Variables can be characterizes as a sextuple of these following attributes: - Name - Address - Value - Type - ________ - Scope
leftmost
(In BNF) A ________ derivation is one in which the leftmost nontermainal in each sentential form is the one that is expanded.
attribute grammar
An ___________ _______ is a context-free grammar G = (S, N, T, P) with the following additions. - For each grammar symbol x, there is a set A(x) of attribute values. -Each rule has a set of functions that define the nontermainals in the rule. - Each rule has a (possibly empty) set of for attribute consistency.
parser
The ______ finds all syntax errors; for each, produce and approximate diagnostic message and recover quickly. Produce the parse tree, or at least a trace of the parse tree for the program.
Value
Variables can be characterizes as a sextuple of these following attributes: - Name - Address - _____ - Type - Lifetime - Scope
closure
A _______ represents all possible configurations for a given state. If the next symbol (after the .) is a non-terminal, then all productions of that non-terminal are included in that _______.
sentence
(In BNF) A ________ is a sentential form that has only terminal symbols.
Semantics
The meaning of the expressions, statements, and program units.
Backus-Naur Form
This was invented by John Backus to describe the syntax of Algol in 1958.
derivation
(In BNF) A _________ is a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols)
left
Why is left recursion a problem for a LL (top-down) parser? If a grammar has ____ recursion, either direct or indirect, it cannot be the basis for a top-down parser. You can get stuck in a loop forever.
angle brackets
In BNF, nonterminals are usually enclosed in _____ _________.
lexer
A _____ is a pattern matcher for character strings. It is the "front end" for the parser.
bottom-up
The LR parser is a _____ ____ parser. Given a right sentential form, A, it determines what substring of A is the right-hand side of rule in the grammar and then reduces it to produce the previous sentential form in the right most derivation.
action
The ______ table specifies the action of the LR parser, given the parser state and the next token.
denotational
In ____________ semantics, the state changes are defined by rigorous mathematical functions.
Scope
Variables can be characterizes as a sextuple of these following attributes: - Name - Address - Value - Type - Lifetime - _____
synthesized
In an attribute grammar, Functions of the form S(X0) = f(A(X1), ... , A(Xn)) define ____________ attributes.
Optional or repeated
In Extended BNF form, what does the metasymbol [] stand for?
ambiguous
A grammar is __________ if and only if it generates a sentential form that has two or more distinct parse trees.
Lexer
The _____ goes through the program source code and tries to identify all the lexemes.
Operational
___________ Semantics: This describes the meaning of a program by executing its statements on a machine, either simulated or actual. The change in the state of the machine (memory, registers, etc) defines the meaning of the statement. A virtual machine is needed for this type fo semantics.
synthesized
Syntax <assign> -> <var> = <expr> <expr> -> <var> + <var> | <var> <var> A | B | C actual_type: ___________ for <var> and <expr> expected_type: _________ for <expr> What is the blank for actual type?
bottom up
A ______ __ parser produces the parse tree, beginning at the leaves. The order is that of a rightmost derivation.
inherited
in an attritube grammar Functions of the form I(Xj) = f(A(X0), ... , A(Xn)), for i <= j <= n, define _________ attributes
LR
Advantages of __ Parsers: - They will work for nearly all grammars that describe programming languages. - They work on a larger class of grammars than other bottom-up algorithms but are as efficient as any other bottom-up parser. - They can detect syntax errors as soon as it is possible. - The __ class of grammars is a superset of the class parsable by the LL parsers.
top-down
the LL parser is a ___ ____ parser, it uses a table-driven implementation. This type looks from left to right, and uses the next character to determine what the next sentential form is.
Address
Variables can be characterizes as a sextuple of these following attributes: - Name - ________ - Value - Type - Lifetime - Scope
Section 2
(50 cards)
Enumeration
The ____________ type is a type where all possible values, which are named constants, are provided in the definition. Ex enum days {mon, tue, wed, thurs, fri, sat, sun};
Integer
An _______ is almost always an exact reflection of the hardware so the mapping is trivial. Primitive Data Type
data type
A ____ ____ defines a collection of data objects and a set of predefined operations on those objects.
nonlocal
The _______ variables of a program unit are those that are visible in the unit but not declared there.
allocation
Storage __________ is getting a cell from some pool of available cells.
dynamic
A binding is _______ if it first occurs during execution or can change during execution of the program.
Explicit
________ heap dynamic-- allocated and deallocated by explicit directives, specified by the programmer, which take effect during execution. These are referenced only through pointers or references.
Abstract memory cell
________ ______ ____: The physical cell or collection of cells associated with a variable.
deallocation
Storage ____________ is putting a cell back into the pool to be selected from.
descriptor
A __________ is the collection of the attributes of a variable.
array
An _____ is a homogeneous aggregate of data elements in which an individual element is identified by its position in the aggregate, relative to the first element.
local
the _____ variables of a program unit are those that are declared in that unit.
Language implementation time
________ ______________ ____: Type of binding time where floating point types are bound to a represenetation.
Heap-Dynamic
________ array: binding of subscript ranges and storage allocation is dynamic and can change any number of times.
Dynamic
_______ Scope: Based on calling sequences of program units, not their textual layout. references to variables are connected to declarations by searching back through the chain of subprogram calls that forced execution to this point.
Value
Variable _____ is the contents of the location with which the variable is associated. The I-_____ of a variable is its address. The r-_____ of a variable is its value.
lifetime
Consider the following function void myf(){ static int x; } _______ = begin to end of program life?
Language Design Time
________ _______ ____: Type of binding time where the operator symbols are bound to operations.
Stack-Dynamic
_________ Storage bindings are created for variables when their declaration statements are elaborated. (A declaration is elaborated when the executable code associated with it is executed) Advantage: allows recursion Disadvantages: Overhead of allocation and deallocation Subprograms cannot be history sensitive.
Binding time
_______ ____ is the time at which a binding takes place.
address
Variable _______: The memory address with which it is associated.
Name
Variables can be characterizes as a sextuple of these following attributes: - ______ - Address - Value - Type - Lifetime - Scope
Primitive
________ Data types: These are data types that are not defined in terms of other data types.
binding
A _______ is an association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbol.
static
A binding is ________ if it first occurs before run time and remains unchanged throughout program execution.
object
An ______ represents an instance of a user-defined data type.
implicit declaration
An ________ ____________ is a default mechanism for specifying types of variables through default conventions, rather than declaration statements.
Global
______ variables are a special category of nonlocal variables.
Runtime
_______: Bind a non static local variable to a memory cell.
Fixed heap-dynamic
______ array: similar to fixed stack-dynamic: storage binding is dynamic but fixed after allocation ( binding is done when requested and storage is allocated from the heap, not the stack). Ex malloc()
local
The referencing environment of a static-scoped language is the _____ variables plus all the visible variables in all of the enclosing scopes.
Static
______ Scope is based on program text. To connect a name reference to a variable, the compiler must find the declaration. _____ Scope looks for the declaration first locally, then in increasingly larger enclosing scopes, until one is found for the given name.
ordinal
An ________ type is one in which the range of possible values can be easily associated with the set of positive integers.
ancestors
Enclosing static scopes (to a specific scope) are called its static _________; the nearest static ancestor is called a static parent.
static
______ Binding happens when the variable is bound to memory cells before execution begins and remains bound to the same memory cell throughout execution.
explicit declaration
An ________ ___________ is a program statement used for declaring the types of variables
scope
Consider the following function void myf(){ static int x; } _______ = function body?
lifetime
The ________ of a variable is the time during which it is bound to a particular memory cell.
Type
Variable ____ determines the range of values of variables and the set of operations that are defined for values for that type; in the case of floating point, the ____ also determines precision.
name
Variable ____: not all variables have these.
Implicit
________ heap-dynamic -- Allocation and deallocation caused by assignment statements. All variables are dynamic.
referencing environment
The _________ _________ of a statement is the collection of all names that are visible in the statement.
named constant
A _____ _______ is a variable that is bound to a value only when it is bound to storage.
Load Time
____ ____: time in C or C++ then a static variable is bound to a memory Cell.
Static
______ Subsbscript ranges are statically bound and storage allocation is static.
dynamic
_______ Type binding is specified through an assignment statement. example in javascript list = [2, 4.33, 6, 8] list = 17.3 This offers flexibility.
aliases
If two variable names can be used to access the same memory location, they are called ________. These are created by pointers.
scope
The _____ of a variable is the range of statements over which it is visible.
Compile Time
_______ ____: Type of binding where a variable is bound to a type in C or java.
Fixed stack-dynamic
________ array: subscript ranges are statically bound, but the allocation is done at declaration time.
Section 3
(50 cards)
mixed-mode
A _____-____ expression is one that has operands of different types.
referential transparency
A program has the property of ___ ___ if any two expressions with the same value can be substituted for each other without affecting the program's behavior.
strongly
A programming language is ________ typed if type errors are always detected.
ternary
A _______ operator has three operands: ;choice = (x < y)? "yes" "no"
associative
An ____________ array is an unordered collection of data elements that are indexed by an equal number of values called keys.
keyword
Actual/Formal Parameter Correspondence: _______: The name of the formal parameter to which an actual parameter is to be bound is specified with the actual parameter. Advantage: Parameters can appear in any order, thereby avoiding parameter correspondence errors.
unary
A _____ operator has only one operand: i++
Name Type equivalence
_____ _____ ___________ means the two variables have equivalent types if they are in either the same declaratino or in declarations that use the same type name.
point
Jagged arrays are arrays that _____ to other arrays, while Rectangular arrays are represented as a single matrix.
subprogram header
A _________ ______ is the first part of the definition, including the name, the kind of subprogram, and the formal parameters.
Jagged
A ______ matrix has rows with varying number of elements.
Mark Sweep
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.
Dangling Pointer
This happens when a pointer points to a heap-dynamic variable that has been deallocated.
Heterogeneous Array
A _____________ ______ is one in which the elements need not be the same type.
Reference Counter
A managed memory technique that tracks the number of references to allocated memory, so that the memory can be freed when the count reaches zero
Type error
A _____ _____ is the application of an operator to an operand of an inappropriate type.
narrowing conversion
A conversion from one data type into another in which information could be lost. Converting from "double" to an "int" is a _________ _________-
positional
Actual/formal parameter Correspondence: __________: THe binding of actual parameters to formal parameters is by position: The first actual parameter is bound to the first formal parameter and so forth.
Tombstone
This is an extra heap cell that is a pointer to the heap-dynamic variable. The actual pointer variable points only at __________
Locks and Keys
pointer values are represented as (key, address) pairs
binary
A ______ operator has two operands: x + y
constants
Operand evaluation order: 1.) Variables: fetch the value from memory. 2.) _________: sometimes a fetch from memory; sometimes the constant is in the machine instruction. 3.) Parenthesized expressions: evaluate all operands and operators first. 4.) The most interesting case is when an operand is a function call: ex: a = b + c (evaluate b or c first)?
Widening conversion
A conversion between one data type and another in which information is not lost. ex int to float
tuple
A _____ is a data type that is similar to a record, except that the elements are not named.
parameter profile
The _________ _______ (aka signature) of a subprogram is the number, order, and types of its parameters.
Boolean Expressions
Evaluates to either true or false; used in the conditional of an if-structure. One odd characteristic of C's expressions: a<b<c is a legal expression, but only the left operator is evaluated, producing a 0 or a 1.
pointer
A _______ type variable has a range of values that consists of memory addresses and a special value, nil.
union
A ______ is a type whose variables are allowed to store different type values at different times during execution (but only one at a given time).
Type checking
____ ________ is the activity of ensuring that the operands of an operator are of compatible types.
coercion
A ________ is an implicit type conversion.
operator precedence
The ______ __________ rules for expression evaluation define the order in which "adjacent" operators of different precedence levels are evalueted.
operator overloading
Use of an operator for more than one purpose is called ________ __________-
record
A ______ is a possibly heterogeneous aggregate of data elements in which the individual elements are identified by names.
Rectangular
A __________ array is a multi-dimensioned array in which all of the rows have the same number of elements and all of the columns have the same number of elements.
protocol
The ________ is a subprogram's parameter profile and, if it is a function, its return type.
Assignment
__________ is used to set a pointer variable's value to some useful address.
Dereferencing
_______________ yields the value stored at the location represented by tht pointer's value. C++ ex j = *ptr;
variables
Operand evaluation order: 1.) _________: fetch the value from memory. 2.) COnstants: sometimes a fetch from memory; sometimes the constant is in the machine instruction. 3.) Parenthesized expressions: evaluate all operands and operators first. 4.) The most interesting case is when an operand is a function call: ex: a = b + c (evaluate b or c first)?
formal parameter
A ______ _________ is a dummy variable listed in the subprogram header and used in the subprogram.
actual parameter
An ______ _________ represents a value or address used in the subprogram call statement.
parenthesized expressions
Operand evaluation order: 1.) Variebles: fetch the value from memory. 2.) COnstants: sometimes a fetch from memory; sometimes the constant is in the machine instruction. 3.) ___________ ___________: evaluate all operands and operators first. 4.) The most interesting case is when an operand is a function call: ex: a = b + c (evaluate b or c first)?
Compatible type
A ___________ ______ is one that is either legal for the operator, or is allowed under language rules to be implicitly converted, by compiler-generated code, to a legal type.
Short Circuit Evaluation
An expression in which the result is determined withouut evaluating all of the operands and/or operators.
subprogram definition
A _________ __________ describes the interface and the actions of the subprogram abstraction.
slice
A _____ is some substructure of an array; nothing more than a referencing mechanism.
Procedures
____________ are collections of statements that define paremeterized computations.
control structure
A _______ _________ is a control statement and the statements whose execution it controls.
Structure Type Equivalence
__________ ____ ____________ means that two variables have equivalent types if their tyypes have identical structures.
selection statement
A _________ ________ provides the means of choosing between two or more paths of execution.
subprogram call
A _________ _____ is an explicit request that the subprogram be executed.
Section 4
(46 cards)