Brainscape's Knowledge GenomeTM

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


See full index

Systems Software > Midterm > Flashcards

Midterm Flashcards

1
Q

… enables running programs on a computer

A

Systems Software

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

Compilers, interpreters, assemblers, linkers, loaders, and OS are examples of…

A

Systems Software

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

Translates a (high-level) language into a form that can be (more easily) executed by a computer.

A

Compiler

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

It allows several abstraction mechanisms, to help programs be as close to the language of the domain as possible, such as subroutines and data types, perhaps allowing for new control mechanisms.

A

What it means for a programming language to be “high-level”

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

Executes a programming language direct without translating it into some other language first. However, it may do some translation into an internal format (e.g., a virtual machine language)

A

Interpreter

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

What are some examples of languages with interpreters?

A

Python, Java (to some extent)

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

Only compiles programs into machine code as needed, and interprets seldom used code.

A

just-in-time compiler

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

Translates a low-level language that is close to machine code into machine code. Uses human-readable names for instructions and macros. Typically there is a one-to-one ratio to the translated machine code

A

Assembler

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

combines parts of a program into a single executable file, resolving external names (e.g., for library functions)

A

Linker

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

Why is a linker needed in C?

A

Because C programs can use external functions (e.g., libraries)

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

Puts a program in a computer’s memory turning relative addresses within a program into (more) absolute addresses

A

Loader

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

Allows the state of a program’s execution to be investigated, typically by displaying the computer’s state and allowing execution to be traced or stopped.

A

Debugger

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

A program that manages a computer’s resources. It provides abstractions of the various resources (e.g., files and directories), security, and helps use resources efficiently

A

Operating System

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

What are some examples of interpreted programming languages?

A

Python, Lisp, Scheme, Java (to some extent)

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

What are the advantages of using a VM (vs. direct execution)?

A

Faster: as can do just-in-time compilation, some simple optimization…
More portable: only the VM needs to be rewritten for portability
Flexibility: the VM can support better linking and debugging

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

What is a computer’s memory like (as a data structure)?

A

A (big) one-dimensional array

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

Holds the compiled code of a program module. It can be linked into a complete program.

A

Object File

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

What information must be stored in an object file?

A
  • code (compiled, sometimes called the “text” of the program)
    - data space (and initial values for some data –static data
    and just space reservations for uninitialized data)
    - metadata about the file (sizes of text and data, header)
    - symbols for linkage to other modules (exported, imported)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

If you were designing a format for object files, what information would you put first?

A

Metadata

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

What are the four sections of an object file?

A

Header, text section, data section, symbol table

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

What are the main parts of a computer CPU?

A

Memory, ALU, PC, registers

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

A register that holds the address of the next instruction to be executed

A

PC (Program Counter)

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

Holds the address to be read or written to in the memory

A

MAR (Memory Address Register)

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

Can the program be altered once it is in MEMORY?

A

Yes, that is needed for linking/loading and is also a security problem!

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

Stores data that is being sent to the memory or received from it. (This could be either code or data.)

A

MDR (Memory Data Register)

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

Executes arithmetic and logical instructions.

A

ALU

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

It communicates with the Control unit to tell the ALU and other parts of the CPU what to do, based on the op-code from the IR.

A

Decoder

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

The user-visible register in tiny machine.

A

ACCUM (Accumulator)

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

The design of a computer CPU (or a VM)

A

ISA (Instruction Set Architecture)

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

What are the steps of the instruction cycle?

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

What happens during the fetch step of the instruction cycle?

A

IR <- MEMORY[PC]

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

What happens during the execute step of the instruction cycle?

A
  1. Advance the PC
  2. Decode and execute instruction in IR
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

When does the program counter get incremented in a VM’s cycle?

A

After the execution of each instruction

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

How can one tell if an ISA has enough instructions?

A

When the set of instructions is “Turing Complete” (i.e., can write a Turing machine simulation); As a practical matter, when we can use it to compile/run any program (written in a Turing complete language)

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

Does a halt instruction need any address?

A

No

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

What does these tasks?

  • translate mnemonic opcodes into numeric ones (bit patterns)
  • track names for locations and translate those names into location numbers when they are used (either in jumps or in loads/stores)
  • arrange for initialization of named data locations
A

Assembler

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

What is the memory heirarchy?

A

The memory hierarchy refers to the organization of memory in a computing system, where memory is organized into different levels, each with varying capacities, access speeds, and costs. The levels of memory hierarchy can be categorized based on their proximity to the processor, with faster and more expensive memory located closer to the processor.

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

Describes a name’s type (or usage) with enough information to check how it is to be used (its specification); describes attributes of a name (e.g. type)

A

Declaration

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

Describes the details of an implementation; Allocates storage, or provides an implementation of a function.

A

Definition

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

In C, you can’t use “extern” on a ___.

A

Definition

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

There must be only one ___ of a name in a scope, but there can be multiple ___ of a name, as long as they are all the same.

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

The scope of a ___ extends to the end of the file or block.

A

Declaration

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

Why is only one definition allowed for a name?

A

How would the compiler pick the right one?

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

What does a compiler say about:

void parseExpr() {
        /* ... */
        parseTerm();
        /* ... */
    }

    void parseTerm() {
        /* ... */
        parseExpr();
        /* ... */
    }
A

an error for the first call to parseTerm(), as it’s not declared where it is first used!

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

Flag to compile each .c file to an object file

A

-c

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

Brings together several separately compiled files into one executable; Matches declarations and definitions for each name.

A

Linker

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

The set of strings of characters from some alphabet

A

Language

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

Languages can be classified by the kind of ___ needed to recognize them.

A

Grammar

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

Consists of a finite set of rules (called “productions”) and a start symbol (a nonterminal).

A

A Grammar

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

A language consists of strings of ___ symbols.

A

Terminal

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

BNF is a type of notation for

A

Grammars

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

In BNF, means “produces” or “can become”

A

::= (or ->)

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

In BNF, means “or”, which separates alternatives.

A

|

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

How to represent a terminal symbol in BNF.

A

Not in angled brackets

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

How to represent a non-terminal symbol in BNF.

A

Inside angled brackets.

56
Q

What question does a production game answer?

A

Can you produce this string with a given grammar?

57
Q

What question does a recognition/parsing game answer?

A

Is this string in the language?

58
Q

What question is this answering?

A

Could you win the production game and produce the string “Johnny is good”?

59
Q

What question is this answering?

A

Could you win the recognition game on the string “Johnny is good”?

60
Q

What does the recognition game have to do with parsing in a compiler?

A

The parser determines if the program is in the language.

61
Q

A finite set of nodes connected by directed edges that is connected and has no cycles

A

Tree

62
Q

A tree that represents how the symbols in a grammar can be transformed into a sequence of terminal symbols.

A

Parse (Derivation) Tree

63
Q

What is this an example of?

Example Grammar:
      <Sentence> -> <Noun> <Verb> <Adj>
      <Noun> -> Johnny | Sue | Charlie
      <Verb> -> is | can be
      <Adj> -> good | difficult

String to parse: "Johnny is good"

         <Sentence>
         /    |   \
        /     |    \
       v      v     v
    <Noun> <Verb> <Adj>

    Johnny   is    good
A

Parse (Derivation) Tree

64
Q

In Extended BNF (EBNF)

How to write 0 or more repeats of x

A

{ x }

65
Q

In Extended BNF (EBNF), what is equivalent to:

A 
<N> ::= { <Z> }

{ <Z> } could also be written as <Z>* or [ <Z> ] ...

66
Q

In Extended BNF (EBNF)

How to write 0 or 1 occurences of x

A

[ x ]

67
Q

In Extended BNF (EBNF)

How to write 1 or more repeats of x

A

x+

Could also be written as x …

68
Q

In Extended BNF (EBNF), what is equivalent to

<N> ::= <Xs>
   <Xs> ::= <X> | <X> <Xs>
A 
<N> :: = <X>+
69
Q

In Extended BNF (EBNF), what is equivalent to

<N> ::= <Y-opt>
     <Y-opt> ::= <empty> | <Y>
A 
<N> ::= [ <Y> ]
70
Q

Relating to the words of a language.

A

Lexical

71
Q

A goal of lexical analysis is to simplify the parser, so it need not handle…

A
  • Whitespace and comments
  • details of tokens (numbers, identifiers, etc.)
72
Q

Why is “ident” a single token instead of “i”, “d”, etc.?

A

Because the lexer recoginzes the longest match.

73
Q

A grammar is ___ iff all its productions have one of these forms:

       <B> ::= c <D>
     or
       <B> ::= c
A

regular

74
Q

Write a regular expression that represents the empty string.

A

ε

75
Q

Write a regular expression that represents a’s and b’s without consecutive a’s.

A

b*(abb*)*(a|ε)

76
Q

Write a regular expression that represents even binary numerals.

A

(0|1)*0

77
Q

Regular expression equivalent to a|c|e|z

A

[acez]

78
Q

Regular expression equivalent to h|i|j|k|l|m

A

[h-m]

79
Q

Regular expression equivalent to x|ε

A

x?

80
Q

Regular expression equivalent to y(y*)

A

y+

or yy*

81
Q

What would be the regular expression for identifiers in PL/0?

(Note that this has no underbars)

A

[a-zA-Z][a-zA-Z0-9]*

82
Q

Regular expression that makes sure expressions have balanced parentheses.

A

Impossible. Needs recursion.

83
Q

A ___ grammar (N, T, P, S) has start symbol S in N and each production (in P) has the form:

<M> -> g
where <M> is a Nonterminal symbol, and g in (N+T)*
</M></M>

A

Context-free

84
Q

What type of grammar allows for recursion?

A

Context-free grammars

85
Q

What is this an example of?

A

Leftmost Derivation

86
Q

A CFG is ___ if it can generate more than one parse tree for an input string.

A

Ambiguous

87
Q

A context free grammar is defined using
(N, T, P, S)
What do these letters stand for?

A

Non-terminals
Terminals
Productions
Start symbol

88
Q

Is ambiguity a property of a language or its grammar?

A

The grammar

There may be non-ambiguous grammars for the same language.

89
Q

How to make a grammar non-ambiguous?

A

Bake operator precidence into grammar.

90
Q

Grammer that can be parsed left-to-right in one pass using one token of lookahead to decide between alternatives.

A

LL(1)

91
Q

What type of grammar is necessary for a recursive-decent parser?

A

LL(1)

92
Q
A

Left Recursion Problem

Generates infinite loop!

93
Q

Eliminate left recusion issue

<Exp> ::= <Exp> + <Number> | <Number>
A 
<Exp> ::= <Number> { <PlusExp> }
<PlusExp> ::= + <Number> <PlusExp>
94
Q

What is the technique for eliminating left recursion?

A

Change to right recursion using a new nonterminal.

95
Q

How to solve:

A 
<S> ::= if <E> then <S> <ME>
<ME> ::= <empty> | else <S>

Left Factoring

96
Q

For what process are these the goals for?

  • Protect back end from extra cases
  • Catch problems to improve programmer productivity
  • Gather information to improve programs
A

Static Analysis

97
Q

What does static mean?

A

Before runtime

98
Q

A ___ maps each (declared) name to its atributes.

A

Symbol Table

99
Q

For a symbol table, what operations are needed?

A
  • look up the attributes of a name
  • check if a name has a mapping (avoid duplicates)
  • add a maping (name -> attributes) to the table
100
Q

What is an attribute (in the context of symbol tables)?

A

A property important to the compiler, such as kind of name, type, or size.

101
Q

These are the operations needed for ___:

  • Allocate a data slot (for a given type)
  • Return total allocation (next offset for an allocation)
  • Allocate an instruction (of a given format)
  • Return size of instructions in a piece of code (offsets for jumps)
A

The code manager

102
Q

A tree that represents the essential structure of a parse tree without punctuation or extra levels (terms, factors, etc).

A

Abstract Syntax Tree (AST)

103
Q

A language’s ___ is a grammar that generates the same language, but has a simpler set of rules.

A

Abstract syntax

104
Q

___ syntax allows ambiguity and left recursion.

A

Abstract

105
Q

What characterises terminals and nonterminals in ASTs?

A

Nonterminals are capitalized.

106
Q

What is the output of a lexical analyzer?

A

Token Stream

107
Q

What is the output of a parser?

A

Parse Tree (AST) + Symbol Table

108
Q

Strings that would be identifiers but always represent something special.

A

Reserved words

109
Q

Strings that would be identifiers but only play a special role in some contexts.

A

Key words

110
Q

What part of a compiler should populate the symbol table?

A

The parser

111
Q

Does each scope have its own symbol table?

A

Yes

112
Q

Information kept about a name in a compiler.

A

Attribute

113
Q

An area of a program’s text where a declaration is effective.

A

Scope

114
Q

Is a block a scope?

A

Yes

115
Q

What happens to a VM’s PC register if no halt (HLT) instruction is executed?

A

Goes into an infinite loop!

116
Q

What is a lexical address?

A

A pair of numbers, (scopes, offset)

117
Q

Lexical address = (scopes, offset)

What is meant by scopes here?

A

Number of static links to follow

118
Q

Lexical address = (scopes, offset)

What is meant by offset here?

A

Word address in that AR.

119
Q

For a word-addressed VM:

What is the lexical address of the variable “q” at the point of the second comment?

A

(0,2)

120
Q

For a word-addressed VM:

What is the lexical address of “y” at the point indicated by the first comment?

A

(0,1)

121
Q
A

1

(There is a list of 4 statement ASTs inside the begin statement’s AST)

122
Q
A

False
There should be no “;” before the “end” token

123
Q
A

Reserved words: if, define, quote
Other tokens: <ident>, <number>, (, )

124
Q

Consider C-style comments: /* … */ in a lexical analyzer.

What would be a regular expression for such comments?

A

/[*].*[*]/

[*] means the actual * character
. means any character

125
Q

What kind of errors are checked for during declaration checking?

A
  • duplicate declarations within a scope
  • undeclared identifier uses
126
Q

Besides declaration checking, what other kinds of checking of PL/0 programs should be done statically?

A

checking that constants are never assigned or read into.

127
Q

What is static scoping?

A

A rule that makes each name refer to the closest textually surrounding declaration of that name.

128
Q

What is dynamic scoping?

A

A rule that makes each variable name refer to the most recent declaration of that name during a programs execution.

129
Q

Why is static scoping useful for programming?

A

Makes names used in code refer to declarations that are evident in the program text.

130
Q

How are static links used with lexical addresses in a VM?

A

The first component of a lexical address indicates how many static links to traverse.

131
Q

What is a part of PL/0 that could NOT be parsed using regular expressions?

A

Matching parenteses begin and end

132
Q

Could we write a parser for PL/0 without using a stack or recursion?

A

No

133
Q

Is the following a legal program?

Practice :- true.

A

Yes

134
Q

Is the following a legal program?

ancestor(A,C) :- parent(B,C), ancestor(A,B).
ancestor(C,C).

A

No

135
Q

What compiler component stores information about identifiers?

A

Symbol table

136
Q

What should be done to change a parser that just recognizes a language into one that returns ASTs?

A

Change the void return types to return the type AST*, build and return an AST in each parsing function.

Systems Software (3 decks)

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