Compilers

Question 1

What is a compiler?

Answer 1

A language processor that translates a program written in some language into efficient, executable code.

Source language -> Target language - an undecidable problem!

Question 2

What is a compiler responsible for?

Answer 2

Generate target program equivalent to source - preserve semantics.
Report errors.

Question 3

What is the structure of a compiler?

Answer 3

Source program -> Preprocessor
Modified source program -> Compiler
Target assembly program -> Assembler
Relocatable machine code + Library files, relocatable object files -> Linker/Loader

-> Target machine code

Question 4

What does the analysis (frontend) part of the compiler do?

Answer 4

Read + analyse source code.
Generate intermediate representation of code.

Errors reported at any stage.
Information gathered during process (e.g. type information) is stored in a symbol table.

Question 5

What does the synthesis (backend) part of the compiler do?

Answer 5

Turns intermediate representation into target program, using symbol table.

Question 6

What parts make up the frontend of the compiler?

Answer 6

Lexical Analysis
Syntax Analysis
Semantic Analysis
Intermediate Code Generation

Question 7

What is lexical analysis?

Answer 7

Reads source code as stream of characters, grouping to lexemes.
Extracts tokens (name, value) from lexemes and stores in symbol table.

Question 8

What is syntax analysis?

Answer 8

Parsing - reads stream of tokens and produces syntax tree.

Question 9

What is semantic analysis?

Answer 9

Checks syntax tree is semantically correct w.r.t. language definition (e.g. type checking) - type info stored in symbol table.

Question 10

What is intermediate code generation?

Answer 10

Generates low-level representation of code from syntax tree.
Representation must be easy to produce and generate to translate to target code.

Question 11

What parts makeup the backend of the compiler?

Answer 11

Intermediate code optimization (some compilers)
Code generation
Code optimization

Question 12

What is intermediate code optimization?

Answer 12

Machine-independent, e.g. eliminate type castings.

Question 13

What is code generation?

Answer 13

Generate sequence of machine instructions from intermediate representation.
Typically includes selecting memory locations or registers for variables.

Question 14

What is code optimization?

Answer 14

Tries to improve the performance of the generated code.

Question 15

What are lexemes?

Answer 15

A sequence of characters.

Question 16

What is a symbol table?

Answer 16

Data structure storing information about symbols (e.g. names and types of identifiers.)

Question 17

How do lexers find the longest match for a lexeme?

Answer 17

Keep track of the word the last time the Finite Automata was in a final state.

Question 18

How is a lexer built?

Answer 18

Given an ordered list of REs e1,…,en (capturing lexemes), and a
word w:
- Find longest prefix of w.
- Repeat until w is fully read.