Chapter 16.2

Question 1

interpreter

Answer 1

an interpreter examines source code one statement at a time
executes code line by line before producing a completely translated version of it.
also produces intermediate code but executes per line.

Question 2

how does an interpreter execute a program

Answer 2

an interpreter examines and
checks each line for errors,
if no error is found the line is executed
if an error is found this is reported and the interpreter halts,
interpretation has to be repeated every time the program is run

interpretation is repeated for every iteration in loops

Question 3

compiler

Answer 3

takes the whole code in as input and translates high-level language programs into object code. produces an executable file
has front-end analysis and back-end analysis stages.

Question 4

assembler

Answer 4

translates assembly language into machine language

Question 5

compilation stages

Answer 5

lexical analysis
syntax analysis
(intermediate) code generation
code optimisation

Question 6

lexical analysis

Answer 6

first stage
converts a sequence of characters into a sequence of tokens

removes comments and whitespace
tokenises code (changes each line into a series of tokens) and categorizes lexemes (e.g. keywords and identifiers) by checking against a predefined set of rules

a symbol table (keeps track of variables and their meanings) and a keyword table is created (see respective pages) to create a sequence of tokens

Question 7

symbol table

Answer 7

records the names and attributes of an identifier
identifier name, data type, role (variable, constant, procedure etc.)
identifier value or location

Question 8

keyword table

Answer 8

used to recognize certain keywords in a language
- the reserved words used
- the operators used
- their matching tokens

Question 9

syntax analysis

Answer 9

second stage
uses parsing algorithms to interpret the meaning of a sequence of tokens

• constructs parse tree
• check syntax or grammar through syntax diagram
• produce error report - if errors are found, each token is output but code generation is not run

Question 10

syntax diagram

Answer 10

breaks down the grammar and syntax rules of a variable or constant

rectangle = variable/identifier
rectangle with repeated arrow going around = can be repeated as many times
circle = a value which cannot further be broken down

Question 11

code generation

Answer 11

converts the intermediate code produced by previous stages into an executable form

Question 12

code optimisation

Answer 12

produces an efficient object program, aims to use the minimum amount of resources

to have fewer instructions, occupy less space in memory, reduce execution time.

Question 13

BNF notation

Answer 13

another way to represent syntax/grammar rules. a set of recursive rules

<> = surrounds each variable
(letters or numbers by themselves do NOT have <>)
::= means “is defined as”
|= separates individual options. “or”

Question 14

Reverse Polish Notation (RPN)

Answer 14

a postfix notation which never requires brackets and has no rules of precedence

Question 15

why is RPN used to carry out the evaluation of expressions?

Answer 15

RPN provides an unambiguous method of representing an expression,
reads from left to right,
without needing brackets,
without precedence rules.

Question 16

why are stacks used to evaluate an expression in RPN

Answer 16

• the operands are popped from the stack in the reverse order to how they were pushed
• evaluates from left to right
• pushes each element of the expression onto the stack until it comes across an operator
• pops the last two elements and applies the operator
• push the result onto the stack
• repeats and effectively evaluates the whole expression

Question 17

back-end analysis

Answer 17

takes the intermediate code as input and produces the object code

Question 18

front-end analysis

Answer 18

performs analysis of source code and produces intermediate codes expressing completely the code’s semantics - its meaning