Brainscape's Knowledge GenomeTM

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


See full index

P4 (SPO)Sprog og oversættere > Exam > Flashcards

Exam Flashcards

1
Q

What is an Interpreter?

A

Analyses syntactics and semantics.

  • Execute programs without much translation.
  • Allows for interactive debugging:
    • Breakpoints.
    • Viewing of variables during run-time.
  • Provides a significant degree of machine independence:
    • (Able to run on a variety of computers).

Interpreters can be up to 100 times slower than compiled code.

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

What is a Language processor?

A

A language processor is a hardware device used to perform tasks, such as processing program code to machine code.

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

What is machine code?

A

Code the machine can directly read.

Consisting only of 0’s and 1’s.

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

What is Target code?

A

The output code after a compilation.

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

What is Syntax?

A

The structure of symbols in programs.

Defines sequenses of symbols that are legal.

Is not concerned with what the symbols mean.

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

What is Semantics?

A

The meaning of symbols in programs.

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

The semantics of a programming language are commonly divided into two classes.

What are they?

A
  1. Static semantics.
  2. Runtime semantics.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is Static semantics?

A

Provides a set of rules that specify which syntactically legal programs are actually valid.

To specify the rules it is required that:

  • Used variables are declared.
  • Operators and operands are type-compatible.
  • Procedures are called with the proper number of parameters.

Static semantics can be expressed in two ways:

  • Expressed informally using everyday speech like in most language specifications. (less precise)
  • Expressed formally using a variety of notations. (very precise)
    • One kind of notation: Attribute Grammars:
      • Attribute grammars augment CFG since it cannot express the rules.
      • E -> E + T is a production in a CFG.
      • This is the production augmented with a type attribute for E and T:
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is Runtime semantics?

A

Specifies what a program computes.

Runtime semantics are often described informally.

But there are ways to describe them formally, this is three of them:

  • Natural (structural operational semantics):
    • Describe how the overall results of the executions are obtained.
  • Axiomatic:
    • Based on mathematical logic to proving the correctness of computer programs.
  • Denotational:
    • Defines that specifies the meaning of a construct (e.g addition).
    • Relys on notation and terminology from mathematics, so they are often very compact.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the different kinds of machine code?

A

There are three different kinds of machine code:

  1. Pure Machine Code.
  2. Augmented Machine Code.
  3. Virtual Machine Code
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is pure machine code?

A

Code generated on the assumption that it doesn’t require an operating system or other libraries. (It can run purely on its own)

Rarely used, but when used it’s often for things like building operating systems.

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

What is augmented machine code?

A

Code generated for a machine architecture that is augmented with an operating system.

  • Requires the particular operating system it was developed for to be present.
  • Is often used.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is virtual machine code?

A

Virtual machine code is composed entirely of virtual instructions.

  • Good technique for producing code that can be run easily on a variety of computers.
    • You create a Virtual Machine to accompany the code.
    • The code can then be run on any machine with the VM installed.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the different formats of target code?

A

There are three different formats of target code:

  1. Assembly or other source formats.
  2. Relocatable binary format.
  3. Absolute binary format.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does a syntax-directed compiler consist of?

A
  1. Scanner
  2. Parser
  3. Type Checker
  4. Translator
  5. Optimizer
  6. Code generator
  • Symbol tables, which are connected to all of the above.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How is an Abstract Syntax Tree drawn?

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

What is IR?

A

An Intermediate representation (IR) is a data structure that is constructed from input data to a program.

Can occour between the Translator and Code generator in a syntax-directed compiler. (not always, some compilers generate target code directly)

When an intermediate representation of the program is created it serves as input to the code generator.

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

What is tokens?

A

A token is a structure representing a lexeme that explicitly indicates its categorization for the purpose of parsing.

  • Identifiers.
  • Integers.
  • Reserved words.
  • Delimiters.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a Scanner?

A

It is the 1st phase in a syntax-directed compiler.

It reads the source code as a text file and produces a stream of tokens. The tokens are then encoded (as integers) and served onto the parser.

  • It makes the program a compact and uniform format (stream of tokens).
  • It removes unnecessary information (like comments).
  • Can also be called: lexical analyzer, lexer, or tokenizer.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is a Parser?

A

It is the 2nd phase in a syntax-directed compiler.

It reads tokens and groups them into phases according to the syntax.

  • The parser verifies correct syntax.
  • The Parser then builds an AST.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is a Type checker?

A

It is the 3rd phase in a syntax-directed compiler.

  • It checks for static semantics for each AST node.
    • Meaning it checks that all identifiers are declared, that types are correct and so on.
  • It adds information to the AST node.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is a Translator? (Program synthesis)

A

It is the 4th phase in a syntax-directed compiler.

Translates all the AST nodes that has been evaluated correct from the type checker into IR code.

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

What is an Optimizer?

A

It is the 5th phase in a syntax-directed compiler.

It analyzes and transforms the IR code from the Translator into improved IR code.

This process can be complex and take a long time. Often involving numerous subphases.

Some compilers have the option to turn off the optimization phase to speed up compilation time.

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

What is a Code generator?

A

It is the 5th or 6th phase in a syntax-directed compiler. (depending on the compiler having an Optimizer)

  • Assumes that program has been thoroughly checked and is well formed (scope & type rules)
  • It requires detailed information about the target machine and its machine specific optimization such as register allocation and code scheduling.
  • It maps the IR code to the target machine code.

So it is often coded by hand and not generated.

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

What is Symbol Tables?

(Sometimes called Identification tables)

A

It is an information table that can be accessed by all phases in a syntax-directed compiler.

  • Allows information to be associated with identifiers which can be shared among different compile phases.

Each time an identifier/variable is declared or used, the symbol table provides information collected about it.

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

What is a compiler writing tool?

A

It is often packaged as a compiler compiler. (SableCC, antlr)

  • Includes scanner and parser generators.
  • Some also include symbol table managers, and code-generation tools.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

How is a Context-free grammar written?

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

What are the terminal and nonterminal symbols?

A

They are the lexical elements used in specifying the production rules constituting a formal grammar.

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

What is a terminal symbol?

A

A grammar symbol that cannot be rewritten.

(By convention written in lowercase)

(On the picture it’s the id, assign and $ symbols.)

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

What is a nonterminal symbol?

A

Nonterminal symbols are those symbols which can be replaced.

(By convention written in uppercase)

(On the picture it’s the Val and Expr symbols)

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

How can production rules define a grammar?

A

They specify which symbols may replace which other symbols.

The rule z0 → z1 specifies that z0 can be replaced by z1.

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

What is a the CFG Start Symbol?

A

A special nonterminal. It’s usually the symbol on the left-hand side of the grammars first rule.

(On the picture the start symbol is “Prog”)

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

What is a regular expression?

A

A regular expression is a sequence of characters that forms a search pattern, mainly for use in pattern matching with strings, or string matching,

“find and replace”-like operations.

Written like this: ab*(c|ε)

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

How is the formal specification of a language’s tokens typically accomplished?

(token specification)

A

By associating a regular expression with each token.

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

What is a Recursive decent parser?

A

One of the simplest parsing techniques used in practical compilers.

This is a top-down process in which the parser attempts to verify that the syntax of the input stream is correct as it is read from left to right.

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

What is a parse tree?

A

A Parse tree (sometimes called a derivation tree) visualizes how a string is structured by a grammar.

It has the following characteristics:

  • The root is the grammar’s start symbol S.
  • Each node is either a grammar symbol or λ.
  • Its interior nodes are nonterminals.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What is Symbol Table construction?

A

A semantic processing activity that traverses the AST to record all identifiers and their types in a symbol table.

Symbol table:

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

In the Type-Checking phase, in which order does it check the types?

A

It walks the AST bottom up from its leaves towards the root.

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

What is a Tombstone diagram

A

Tombstone diagrams consist of a set of “puzzle pieces” representing compilers and other related language processing programs.

They are used to illustrate transformations from a source language to a target language realised in an implementation language.

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

Tombstone diagram: What does the diagram describe?

A

A program P implemented in the language L.

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

Tombstone diagram: What does the diagram describe?

A

A Translator/Compiler implemented in the language L, that can translate the language S into the language T.

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

Tombstone diagram: What does the diagram describe?

A

A machine M implemented in hardware.

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

Tombstone diagram: What does the diagram describe?

A

A language interpreter written in L that interprets the language M.

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

When would you want to compile a compiler?

A

When you have created a compiler you want to run on a machine that cannot run on the code it’s currently written in. (see image for an example)

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

What is Bootstrapping?

A

A way to compile a compiler written in it’s own language.

The first compiler has to be compiled by a compiler in another language.

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

What is a recognizer?

A

A recognition device that reads input strings over the alphabet of the language and decides whether the input strings belong to that language.

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

What is Backus-Nair Form (BNF)?

A

BNF is a notation techniques for context-free grammars.

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

What is Extended Backus-Nair Form (EBNF)?

A

EBNF is an adds extra features to BNF:

  • ? which means that the symbol (or group of symbols in parenthesis) to the left of the operator is optional (it can appear zero or one times)
  • * which means that something can be repeated any number of times (and possibly be skipped altogether)
    • which means that something can appear one or more times
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

When is a grammar ambiguous?

A

When it generates a sentential form that has two or more distinct parse trees.

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

What is a Throws analysis visitor?

A

Throws Visitor is a specialized visitor used to collect information about throws that may ”escape” from a given construct.

These visitors compute the throwsSet field, which records exceptions that may be thrown.

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

What is a Semantic analysis visitor

A

Semantics Visitor is used to check that the type rules imposed on language
constructs are satisfied.

This includes checking that control expressions are Boolean-valued, that parameters have correct types in calls, that expected types are returned from calls, and so forth. This analysis, often called static semantics, is a necessary part of all compilers.

52
Q

What is a Reachability analysis visitor?

A

Reachability Visitor is a specialized visitor used to analyze control structures for reachability and proper termination.

These visitors set two flags, isReachable and terminatesNormally, used for error analysis and optional code optimization.

53
Q

Subprogram: Specification

A
  1. Name
  2. Signature
  3. Actions.
54
Q

Subprogram: Signature/protocol

A
  • Number of I/O.
  • Types of I/O.
55
Q

Subprogram: Action

A

Det der ændre input værdier til output værdier, ændre på indre tilstande og eventuelt påvirker globale variabler.

56
Q

What is a Relocatable Binary format for target code?

A
  • Code that most assemblers generate.
  • External references, local instruction addresses, and data addresses are not yet bound.
  • Instead, addresses are assigned relative either to the beginning of the module or to some symbolically named locations.
57
Q

What is a Absolute Binary format for target code?

A

Some compilers generate an absolute binary format that can be directly executed when the compiler is finished.

This process is usually faster than the other approaches. However, the ability to interface with other code may be limited.

In addition, the program must be recompiled for each execution unless some means is provided for archiving the memory image.

58
Q

How is a precedence table written?

A
59
Q

How can you control statement execution?

A
  • Sequential.
  • Conditional Selection.
  • Looping Construct.

Must have all three to provide full power of a Computing Machine.

60
Q

What is a subprogram?

A

A subprogram is a program called by another program to perform a particular task or function for the program.

When a task needs to be performed multiple times, you can make it into a separate subprogram.

  1. A subprogram has a single entry point.
  2. The caller is suspended during execution of the called subprogram.
  3. Control always returns to the caller when the called subprogram’s execution terminates.
61
Q

Explain subprogram as an abstraction:

A
  • Subprograms encapsulate local variables, specifics of algorithm applied
    • Once compiled, programmer cannot access these details in other programs.
  • Application of subprogram does not require user to know details of input data layout (just its type)
    • Form of information hiding.
62
Q

What are the parameters of a subprogram?

A
  • Formal parameters:
    • Names (and types) of arguments to the subprogram used in defining the subprogram body.
  • Actual parameters:
    • Arguments supplied for formal parameters when subprogram is called.

Actual/Formal Parameter Correspondence:

  • Attributes of variables are used to exchange information:
    • Name – Call-by-name.
    • Memory Location – Call-by reference.
    • Value.
    • Call-by-value (one way from actual to formal parameter).
    • Call-by-value-result (two ways between actual and formal parameter).
    • Call-by-result (one way from formal to actual parameter).
63
Q

What is call-by-name?

A

The parameter passed isn’t evaluated before it is used in the function.

E.g

int func(a) { return a + 1; }

func(2 + 3)

The return statement in the body of func will read

return 2 + 3 + 1

instead of

return a + 1; (call by value).

64
Q

What is call-by-reference?

A

No new variable is declared at call-time, instead the parameter is used directly.

E.g.

int x = 2 + 3;

int func(a) { a = a + 1; }

func(x);

Print(x); // x = 6

65
Q

What is call-by-value?

A

The actual parameter is evaluated at call time.

E.g.

int func(a) { return a + 1 }

func(2 + 3)

Behind the scenes this happens: a = 5

So the return statement reads return a + 1;

66
Q

What is call-by-value-result?

A

A parameter passing mode, used in Ada language to handle “IN OUT” parameters.

In CallByValueResult, the actual parameter supplied by the caller is copied into the callee’s formal parameter; the function is run; and the (possibly modified) formal parameter is then copied back to the caller.

This allows a function to modify the state of its caller, similar to what you get with Call By Reference.

The (semantic) differences between Call By Reference and Call By ValueResult are:

  • No alias is created between the formal and actual parameters. If lexical scoping is used, the difference can be apparent.
67
Q

What is call-by-result?

A

Pass-by-result is an implementation model for out-mode parameters.

  • No value is transmitted to the subprogram.
  • The corresponding formal parameter acts as a local variable
  • Just before control is transferred back to the caller, its value is transmitted back to the caller’s actual parameter.
68
Q

What are the design considerations for parameter passing?

A

You have to consider two things:

  1. Efficiency.
  2. One-way or two-way.

These two are in conflict with one another!

  • Good programming –> limited access to variables, which means one-way whenever possible
  • Efficiency –> pass by reference is fastest way to pass structures of significant size
  • Also, functions should not allow reference parameters.
69
Q

What is a side effect for a function or expression?

A

A function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

For example, a function might modify a global variable or static variable.

70
Q

What is the difference between implicit and explicit sequence control?

A

Sequence control: the control of the order of execution of the operations both primitive and user defined.

  • Implicit:
    • Determined by the order of the statements in the source program or by the built-in execution model.
  • Explicit:
    • The programmer uses statements to change the order of execution (e.g. uses If statement).
71
Q

Name the three different operator types:

A
  1. Prefix
    1. !x
  2. Infix
    1. x + y
  3. Postfis
    1. x++
72
Q

What are the main types of loops?

A
  • Counter-controlled iterators. (A counter (int i; i
  • Logical-test iterators. (A logical expression (true))
  • Recursion.
73
Q

Loops: What are counter-controlled iterators?

A

For-loops:

  • Controlled by loop variable of scalar type with bounds and increment size.
  • Scope of loop variable?
    • Extent beyond loop?
    • Within loop?
  • When are loop parameters calculated?
    • Once at start.
    • At beginning of each pass.
74
Q

Loops: What are logic-test iterators?

A
  • While-loops
    • Test performed before entry to loop
  • repeat…until and do…while
    • Test performed at end of loop
    • Loop always executed at least once
  • Design Issues:
    1. Pre-test or post-test?
    2. Should this be a special case of the counting loop statement (or a separate statement)?
75
Q

What are the three main phases of a compiler?

A

The different phases can be seen as different transformation steps to transform source code into object code.

The different phases correspond roughly to the different parts of the language specification:

  • Syntax analysis Syntax
  • Contextual analysis Contextual constraints
  • Code generation Semantics
76
Q

TODO What is a multi pass compiler?

A

A multi pass compiler makes several passes over the program. The output of a preceding phase is stored in a data structure and used by subsequent phases.

(Nævn noget om:)

Issues in language design

Issues in code generation

77
Q

What is a single pass compiler?

A

A single pass compiler is a compiler that passes through the parts of each compilation unit only once, immediately translating each part into its final machine code.

This is in contrast to a multi-pass compiler which converts the program into one or more intermediate representations in steps between source code and machine code, and which reprocesses the entire compilation unit in each sequential pass.

  • An issue with single pass compilers is that identifiers have to be declared before they are used, as it only makes a single pass where it reads the code chronologically.
78
Q

How is an informal definition of an language written?

A

An Informal Definition of the ac Language

  • ac: adding calculator.
  • Types:
    • integer.
    • float: allows 5 fractional digits after the decimal point.
    • Automatic type conversion from integer to float.
  • Keywords:
    • f: float.
    • i: integer.
    • p: print.
  • Variables:
    • 23 names from lowercase Roman alphabet except the three reserved keywords f, i, and p.
  • Target of translation: dc (desk calculator)
    • Reverse Polish notation (RPN).
79
Q

How is a syntax specification written?

A

By using a CFG or a parse tree.

80
Q

Describe the Contextual Analysis phase of a compiler:

A

Contextual analysis:

  • Scope checking: verify that all applied occurrences of identifiers are declared
  • Type checking: verify that all operations in the program are used according to their type rules.
81
Q

How is type checking implemented?

A

Example:

The ac language offers two types: integer and float, and all identifiers must be type-declared in a program before they can be used.

The type checking process walks the AST bottom-up from its leaves towards the root and checks that it corresponds with the above rules.

82
Q

What are the different visitor approaches for tree traversal?

A

Visitor approach

  • GOF
    • The Gang of Four defines the Visitor as: Represent an operation to be performed on elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.
  • Using static overloading
  • Reflective
    • By using reflection, we can view node types on a per-visitor basis and avoid the need to specify visit methods for every node type. Reflection is a programming language’s ability to inspect, reason about, manipulate, and act upon elements of the language, such as object types. The method visit(AbstractNode n) does not call n.accept(this) to perform the second dispatch. Instead, the dispatch method is invoked to determine the best match for visiting the supplied node n.
  • (dynamic)
  • (SableCC style)
83
Q

Explain the “Traditional” Object orientated approach for tree traversal:

A

Since it is OO you probably have an abstract node that all other nodes inherit from.

Create an abstract method for how handle the node.

Then overwrite this method for every subnode.

84
Q

What is mutual recursion?

A

Mutual recursion is a form of recursion where objects, are defined in terms of each other.

Example:

A forest is a list of trees. A tree is a value and a forest.

forest: [tree[1], … , tree[i]]
tree: value forest

forest and tree are mutual recursive data structures since they both contain eachother.

85
Q

What does Syntax Analysis contain?

A
86
Q

What is lexical scoping?

A

Lexical scoping (a.k.a. static scoping) is a convention used with many programming languages that sets the scope of a variable so that it may only be called from within the block of code in which it is defined.

The scope is determined when the code is compiled.

A variable declared in this fashion is sometimes called a private variable.

87
Q

TODO Grammar tranformations: What is Left Factorization?

A
88
Q

Grammar tranformations: What is Left Recursion ?

A

If you have a production rule:

stmt –> stmt expr

Then you have left recursion since the name of the rule stmt is also the first (left most) nonterminal in the rule.

This is a problem if you don’t have lookahead, then the parser will infinitely enter stmt and never get to expr.

89
Q

What is a LL and a LR grammar?

A

An LL grammar is a formal grammar that can be parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser that constructs a Rightmost derivation).

90
Q

What does k mean in LL(k) or LR(k)?

A

A LL/LR parser is called a LL(k)/LR(k) parser if it uses k tokens of lookahead when parsing a sentence.

91
Q

What is lookahead?

A

Lookahead establishes the maximum incoming tokens that a parser can use to decide which rule it should use.

92
Q

What is a LALR parser?

A

A Look-Ahead LR parser is a simplified version of a LR parser.

  • LALR parser has more language recognition power than the LR(0)
  • LALR parser requires the same number of states as the LR(0).
93
Q

What does it mean when a grammar is ε-free?

A

A regular grammar is said to be ε-free if it has no ε-productions except possibly for the production S–>ε.

94
Q

Bottom-up parsing: What is a handle?

A

When a parent node N has not yet been constructed, but its children have, the children of N is called the handle of N.

95
Q

Bottom-up parsing: What is reducing?

A

Creating a parent node N and connection the children in the handle to N is called reducing to N.

96
Q

Parsing: What is shift?

A

A Shift step advances in the input stream by one symbol. That shifted symbol becomes a new single-node parse tree.

97
Q

What is a Simple LR (SLR) parser?

A

A Simple LR or SLR parser is a type of LR parser with small parse tables and a relatively simple parser generator algorithm.

As with other types of LR(1) parser, an SLR parser is quite efficient at finding the single correct bottom-up parse in a single left-to-right scan over the input stream, without guesswork or backtracking.

The parser is mechanically generated from a formal grammar for the language.

98
Q

What is scope rules?

A

Scope rules regulate visibility of identifiers. They relate every applied occurrence of an identifier to a binding occurrence.

99
Q

What are the differences between dynamic and static binding?

A

Dynamic binding:

  • The method being called upon an object is looked up by name at runtime.

Static binding:

  • Types of variables and expressions fixed at compilation time. Stored in the compiled program as an offset in a virtual method table (“v-table”)
100
Q

What is block structured scope?

A

There are different kinds of Block structure.

The C-based languages allow any compound statement (a statement
sequence surrounded by matched braces) to have declarations and thereby
define a new scope. Such compound statements are called blocks.

101
Q

What is implicit binding?

A

The binding is invisible to the programmer.

C# has implicit binding since you just say y = 2 and the compiler does the binding behind the scenes.

102
Q

What is explicit binding?

A

In explicit binding the programmer has to specify where to bind the value.

C uses explicit binding with the malloc where you have to free the space when you no longer use the variable.

103
Q

What is nested block structure?

A
104
Q

What is shift-reduce?

A
  • A shift-reduce parser scans and parses the input text in one forward pass over the text, without backing up. (That forward direction is generally left-to-right within a line, and top-to-bottom for multi-line inputs.)
  • The parser builds up the parse tree incrementally, bottom up, and left to right, without guessing or backtracking.
  • At every point in this pass, the parser has accumulated a list of subtrees or phrases of the input text that have been already parsed.
  • Those subtrees are not yet joined together because the parser has not yet reached the right end of the syntax pattern that will combine them.
105
Q

What is a reduce/reduce conflict?

A

A Reduce-Reduce error is a caused when a grammar allows two or more different rules to be reduced at the same time, for the same token.

When this happens, the grammar becomes ambiguous since a program can be interpreted more than one way. This error can be caused when the same rule is reached by more than one path.

106
Q

Runtime organization: What are Routines?

A

How to implement procedures, functions

  • Value vs. reference.
  • Recursion.

(and how to pass their parameters and return values)

107
Q

Runtime organization: What are the important issues in data representation?

A
  • Constant-size representation:
    • The representation of all values of a given type should occupy the same amount of space.
  • Direct versus indirect representation.
108
Q

Runtime organization: What is direct and indirect representation?

A

Is the value of a type given directly or indirectly (pointers)

109
Q

What is the difference between a static and a dynamic array?

A
  • Static arrays:
    • their size (number of elements) is known at compile time.
  • Dynamic arrays:
    • their size can not be known at compile time because the number of elements may vary at run-time.
110
Q

What is static allocation?

A
  • Compilation data is bound to a fixed location in the memory.

Compiler can:

  • Compute exactly how much memory is needed for globals.
  • Allocate memory at a fixed position for each global variable.
111
Q

What is stack allocation?

A
  • Procedure calls and their activations are managed by means of stack memory allocation.
  • It works in last-in-first-out (LIFO) method.
  • The local variables “live” as long as the procedure they are declared in.
  • Is very useful for recursive procedure calls.
112
Q

What is heap allocation?

A
  • Local variables are allocated and de-allocated only at runtime.
  • Both stack and heap can grow and shrink dynamically and unexpectedly.
113
Q

TODO What are displays?

(It has something to do with static links)

Exam-6 slide 17:

An alternative to using static links to access frames of enclosing methods is the use of a display. Here, we maintain a set of registers which comprise the display. (see Fig. 12,7)

A

A display generalizes our use of a frame pointer.
Rather than maintaining a single register, we maintain a set of registers which
comprise the display.

114
Q

What is the Heap?

A

The heap is memory set aside for dynamic allocation.

Unlike the stack, there’s no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time.

This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.

115
Q

What is a direct garbage collector?

A

A record is associated with each node in the heap.

The record for node N indicates how many other nodes or roots point to N.

116
Q

What is an indirect/tracing garbage collector?

A

Usually invoked when a user’s request for memory fails because the free list is exhausted.

The garbage collector visits all live nodes, and returns all other memory to the free list.

If sufficient memory has been recovered from this process, the user’s request for memory is satisfied.

117
Q

Type of garbage collector: Explain the “classic” algorithm Reference counting.

A

As a collection algorithm, reference counting tracks, for each object, a count of the number of references to it held by other objects. If an object’s reference count reaches zero, the object has become inaccessible, and can be destroyed.

118
Q

Type of garbage collector: Explain copying garbage collection:

A
  • Start from a set of roots, and traverse all of the reachable memory-allocated objects, copying them from one half of memory into the other half.
  • Old space and new space.
  • When we copy the reachable data, we compact it so that it is in a contiguous chunk.
  • Contiguous area of memory in new space can quickly and easily be allocated freed.
119
Q

Type of garbage collector: Explain Incremental tracing garbage collection

A

Tracing garbage collection consists of determining which objects should be deallocated, by tracing which objects are reachable by a chain of references from certain “root” objects, and considering the rest as “garbage” and collecting them.

120
Q

Type of garbage collector: Explain generational garbage collection

A
  • Disadvantage of mark-sweep garbage collection is that it introduces very large system pauses.

Generational garbage collection is based on the following observations:

  • Most objects die young.
  • Over 90% garbage collected in a GC is newly created post the previous GC cycle.
  • If an object survives a GC cycle the chances of it becoming garbage in the short term is low.

Algorithm:

  • Consider a newly created object to be in Gen 0 and then if it is not collected by a cycle of garbage collection then it is promoted to the next higher generation, Gen1.
  • If an object in Gen1 survives a GC then that gets promoted to Gen2.
  • Lower generations are collected more often.
  • The higher generation collection is triggered fewer times.
121
Q

Type of garbage collector: Explain the “classic” algorithm Mark and sweep.

A
  • The first tracing garbage collection algorithm
  • Garbage cells are allowed to build up until heap space is exhausted (i.e. a user program requests a memory allocation, but there is insufficient free space on the heap to satisfy the request.)
  • At this point, the mark-sweep algorithm is invoked, and garbage cells are returned to the free list.
  • Performed in two phases:
    • Mark: identifies all live cells by setting a mark bit. Live cells are cells reachable from a root.
    • Sweep: returns garbage cells to the free list.
    • Compaction: we push live cells to one end of the heap
      • We can add a compaction phase as shown in Fig. 12.17.
122
Q

What are dangling pointers?

A

Dangling pointer and wild pointers in computer programming are pointersthat do not point to a valid object of the appropriate type. These are special cases of memory safety violations.

Cause of dangling pointers:
In many languages (e.g., the C programming language) deleting an object from memory explicitly or by destroying the stack frame on return does not alter associated pointers.

123
Q

What is a stalled pipeline?

A

If result from previous instruction is needed but not yet ready then we have a stalled pipeline.

124
Q

What are contextual constraints?

A

Contextual constraints are those aspects of a programming language’s syntax that are inexpressible by a CFG, for example scope rules and type rules.

125
Q

TODO Organize storage for variables: What are static links?

Exam-6.pdf slide 3

A
126
Q

What are activation records?

A

An activation record is another name for Stack Frame. It’s the data structure that composes a call stack.

It is generally composed of:

  • Locals to the callee
  • Parameters of the callee
  • Return address to the caller

The Call Stack is thus composed of any number of activation records that get added to the stack as new subroutines are added, and removed from the stack (usually) as they return.

127
Q

Explain visitor pattern:

A

A way of separating an algorithm from the object structure on which it operates.

  • Allows one to add new virtual functions to a family of classes without modifying the classes themselves.
  • One creates a visitor class that implements all of the appropriate specializations of the virtual function.
  • The visitor takes the instance reference as input, and implements the goal through double dispatch.

P4 (SPO)Sprog og oversættere (2 decks)

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