Study Guide Jeopardy

Question 1

What is a graphical IR?

Answer 1

representation of structure and semantics of code in a visual way

Question 2

What is a syntax tree(Concrete and Abstract)

Answer 2

Rooted, undirected graph containing no cycles.
Flows from start symbol, to terminal, where state is root and terminals are leaves, interior nodes are all non terminals

Question 3

What is an abstract syntax tree?

Answer 3

A CST, with details abstracted away. Near source level representation.

Question 4

What is a directed acyclic graph?

Answer 4

Directed graph with no cycles, partially ordered.

Question 5

What is a linear IR?

Answer 5

Representation of code as a sequence of instructions.

Question 6

What is postfix notation?

Answer 6

linear IR where expressions are written at the end of the operator (ab+)

Question 7

What is Three Address code?

Answer 7

Linear IR, 4 tuple, closely resembling assembly for modern machines

Question 8

What are the benefits of an intermediate language

Answer 8

Completely decouples front and backends
Useful for debugging

Question 9

Why might you use graphical IR over linear? And vice versa?

Answer 9

Graphical: good for analyzing and optimizing code and showing relationships
Linear: better for code generation and execution, concise and closer to machine code

Question 10

What is the value of utilizing an IR?

Answer 10

Simplifies compiler design by breaking it into modular phases

Question 11

What is syntax-directed translation?

Answer 11

Translation scheme by which the parse of the source program is used to derive the meaning of the program using semantic rules or actions associated with grammar symbols

Question 12

What is a syntax-directed definition?

Answer 12

Context free grammar augmented with a set of attributes and a set of rules which guides semantic analysis

Question 13

Which direction along a parse tree do synthesized and inherited attributes move information?

Answer 13

Synthesized attributes are used to pass information up the parse tree
Inherited attributes are used to pass information down parse tree

Question 14

What is a variable?

Answer 14

A named storage location in a program that holds the value which determines what data it can store.

Question 15

What is type coercion? Is it good or bad?

Answer 15

When a type conversion is initiated by the compiler or runtime environment. Like converting an int into a float

Question 16

What is an expression?

Answer 16

A syntactic entity in a programming language that may be evaluated to determine its value

Question 17

What are two different kinds of expressions?

Answer 17

Arithmetic expressions: has operators, operates, parentheses, function calls
Relational expressions: binary expression that has 2 operants and 1 relational operator, comparing the values of operants
Boolean expressions: consisting of Boolean variables, Boolean constants relational expressions and Boolean operators (AND, OR, NOT)

Question 18

What are design concerns for expressions (know 2)

Answer 18

1. Order of evaluation: sequence in which operators and operants are processed affects the results
2. Type compatibility: ensuring the operants are compatible with the operator to prevent errors or type coercion
3. Precedence and associating: governing operator idea while side effects influence operand order

Question 19

What is a precedence and what does it apply to?

Answer 19

Precedence is applied to expressions and it’s when expressions are governed by orders of evaluation

Question 20

What is a basic block?

Answer 20

Set of TAC instruction that are always executed sequentially form beginning to end.

Question 21

What is the difference between machine-independent and machine-dependent optimization?

Answer 21

Machine-independent occurs IR level and can be done regardless of target machine. Machine-dependent leverages instructions and architecture of the target machine

Question 22

What are two challenges with machine-dependent optimization?

Answer 22

Portability: code optimized for one hardware platform might not run well on other
Maintenance complexity: needing to update and manage code differently for each target hardware architecture

Question 23

Why do we do optimization?

Answer 23

It reduces processing time, aids in space management, saves on memory

Question 24

What is local optimization/what level is it done at?

Answer 24

Transforms basic blocks into DAGs and then utilizes the useful expression properties and structure of DAGs to improve code. On the level of basic block

Question 25

What is global optimization/what level is it done at?

Answer 25

Moving loop invariant computations outside of loops, common subexpression elimination (removing redundant computations) and register allocation. On the level of , multiple blocks/whole program

Question 26

What is the scope of a variable?

Answer 26

Where a variable can be accessed in a program.

Question 27

What is the difference between static and dynamic scope?

Answer 27

Static scope determines scope of a variable at compile time
Dynamic scope: determines scope based on runtime