16.2 Translation Software

#### Compliation and Interpreter
#### Stage of compilation
###### Lexical analysis
converting a sequence of characters into a sequence of tokens
###### Syntax analysis
using parsing algorithms to interpret the meaning of a sequence of tokens
- It takes input from the lexical analyser in the form of token streams.
- The source code is analysed / parsed against the rules of the language to detect any errors in the code.
-  Syntax errors are reported
-  The output from this phase is a parse tree.
###### Code generation
converting an intermediate representation of source code into an executable form
###### Optimisation
minimising a program's execution time and memory requirement
##### How an interpreter executes a program

- An interpreter examines source code one statement at a time
- Check each statement for errors
- ...lf no error is found the statement is executed
- ...If an error is found this is reported and the interpreter halts
- Interpretation is repeated for every iteration in repeated sections of code/in loops
- Interpretation has to be repeated every time the program is run
##### Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions.

- Reverse Polish Notation provides an unambiguous method of representing an expression
- .. reading from left to right 
- ...without the need to use brackets
- ...with no need for rules of precedence
##### Data structure that could be used to evaluate an expression in RPN.
###### Binary tree
-  A (binary) tree allows both infix and postfix to be evaluated (tree traversal)
###### Stack
- The operands are popped from the stack in the reverse order to how they were pushed
##### Describe the main steps in the evaluation of this RPN expression using a stack.
- Working from left to right in the expression
- PUSH data onto the stack
- PUSH the following numbers onto the stack
- When the first operator is reached
- ... POP the top two numbers,and apply the operation
- PUSH result back onto stack
- Continue to the end of the expression
##### State two other uses of a stack.
- recursion
- implementation of ADTs e.g. linked lists
- procedure calls
- interrupt handling (storing contents of registers etc)