11.1 Compilers

Question 1

What is the purpose of a compiler

Answer 1

Translates source code into machine code

Question 2

What are the 3 components of a compiler (and their functions)

Answer 2

Pipeline as follows:

Question 3

Why may it be useful to break up a compiler into separate parts

Answer 3

Allows it to be maintained separately and reused on different platforms etc.

Question 4

What are the 2 parts of a compiler front-end and their function

Answer 4

1. Lexer => Tokens (symplify parsing stage)
2. Parser => builds AST (intermediate representation) and symbol table

Question 5

What is the lexer responsible for (and what are tokens)

Answer 5

• Lexer: Breaks program into semantic tokens (reading character by character, ignoring whitespace and comments)
• Tokens: smallest unit of meaning within program (ie words of the language)
• Tokens may be labeled based on meaning

Question 6

What is the Parser responsible for (and what is the difference between statement and expression)

Answer 6

• Parser: Builds abstract syntax tree from tokens
• Statement: No return val ie while. Expressions ie arithmatic expr.

Question 7

What would the AST for this look like

Answer 7

Question 8

How does a recursive decent parser work?

Answer 8

• Program is a series of statements
• Recursively expand statement into parts
• Build AST

Question 9

What is some example psuedocode for a recursive descent parser

Answer 9

Question 10

What is a symbol table and its use (parser)

Answer 10

• Keep track of variable names and scope to avoid context

Question 11

What is the purpose of the compiler backend / what does it do

Answer 11

• Intermediate rep (ie AST) => Machine Code (object files in binary, use linker to link together)
• Optimisations (best ISA instructions, ordering etc.)
• Memory allocation

Question 12

What are some potential compiler backend optimisations

Answer 12

• Pipelining
• Ordering
• Instruction choice

Question 13

What is the concept of bootstrapping (compilers)?

Answer 13

• Creating a compiler that can compile itself
• Ie how to make the first compiler for lang / arch

Question 14

What is a Tombstone diagram (for bootstrapping)

Answer 14

• Shows source to output process (using compiler written in implementation

Question 15

How would you bootstrap a compiler for hex-8 (show using tombstone diagram)

Answer 15

• Create minimal compiler in Hex 8 assembly (perhaps only subset of features)
• Use that to compile the X compiler
• Use X compiler to compile itself (good for testing and self optimisation)
• Can now create new versions of X compiler to add more features using itself.
• Can now compile from X to Hex-8

Question 16

Outline how cross compiling works (use Tombstone diagrams)

Answer 16

• Cross-compiling is used for new atchitectures
• Cross compiler runs on old architecture and builds compiler binary for new architecture
• Can then use that compiler to recompile itself