The Middle End

Question 1

What is a statically checked programming language?

Answer 1

A programming language that performs type checking at compile time

Question 2

What is a dynamically checked programming language?

Answer 2

A programming language that performs type checking at run time

Question 3

What is the symbol table often stored as?

Answer 3

A hash table

Question 4

A lot of programming languages allocate and initialise a symbol table for each scope

Question 5

What are the different types of Internal Representation (IR) ?

Answer 5

• Graphical (structural)
• Linear

-Hybrid

Question 6

What is a graphical internal representation?

Answer 6

Uses a node and edge structure to create the internal representation, tends to be close to source code

Question 7

What is linear internal representation?

Answer 7

An internal representation that uses pseudo code for some abstract machine. Typically close to target code.

Question 8

What is a hybrid internal representation?

Answer 8

A combination of a graphical and linear approach to internal representation

Question 9

How would you convert a parse tree to an abstract syntax tree?

Answer 9

1. Traverse the parse tree in post order
2. Remove non-terminal symbols

Question 10

Why do we convert from a parse tree to an abstract syntax tree?

Answer 10

The parse tree contains a lot of unnecessary information

The AST is a near source-code level representation

Easily generate source code, perform an in order traversal

Question 11

What are some issues with abstract syntax trees?

Answer 11

• They use a lot of pointers for traversals and transformations
• memory intensive

Question 12

How does a linear representation work?

Answer 12

We use three address codes,

where every statement is a single operator, and contains at most three operands

Question 13

What are auxilliary graph representations?

Answer 13

These representations do not represent the full code, instead they represent properties of the code.

Question 14

Name 3 auxiliary graph representations

Answer 14

Control Flow Graph
- models the way that the code transfers control as a result of conditional or loop statements

Data Dependence Graph
- encodes flow of data

Call Graph
- shows dependencies between procedures, which functions may be calling other functions

Question 15

What do the nodes and edges of a control flow graph represent?

Answer 15

Node = a single basic block (a maximal straight line of code)

Edge = a transfer of control between basic blocks

Question 16

What do the nodes and edges of a data dependence graph represent?

Answer 16

Node = a program statement

Edge = connects two nodes if one uses the result of the other