Compilers, Interpreters and Grammars

Question 1

How does a compiler work?

Answer 1

Takes a source program and translates the whole thing into machine code.
The translation and execution are separate

Question 2

How does an interpreter work?

Answer 2

Takes one instruction at a time from source code and does it.
No binary code is generated.
Source program analysis and execution are interlaced

Question 3

Which executes code faster, compiler or interpreter?

Answer 3

Compiler

Question 4

Which is better for keeping source code hidden, compiled or interpreted?

Answer 4

Compiled

Question 5

Which is better for rapid prototyping (changes are frequently made), compiled or interpreted?

Answer 5

Interpreted

Question 6

Which is better for moving between platforms, compiled or interpreted?

Answer 6

Interpreted

Question 7

Why are interpreters sometimes called virtual machines?

Answer 7

Because they take 1 instruction at a time and execute it (similar to a CPU)

Question 8

Is Java compiled or interpreted?

Answer 8

Both, it’s compiled into machine-independent virtual machine code then interpreted when run.
javac generated virtual bytecode, JVM interprets this.

Question 9

What is translation?

Answer 9

The act of turning source code into binary (machine) code which the CPU can understand

Question 10

What kinds of programs do translation?

Answer 10

Compilers (translate HLL into machine code)
Assemblers (translate mnemonics like MOV into binary code)

Sometimes compiling requires a compiler and assembler as 2 steps

Question 11

What are the steps to making then running a program?

Answer 11

Edit -> Compile -> Link (to external libraries) -> Load/Run

Question 12

What are the 3 components of a coding language?

Answer 12

Lexical (the tokens)
Syntactical (the structure)
Semantic (the meaning)

Question 13

What does a lexicon contain?

Answer 13

All the legal words (elementary expressions) in a language together with the information about them.
In Java, these are things like “import”, “public”, “else”, etc.

Question 14

What does syntax define?

Answer 14

It defines the correct form legal expressions of the language must take.
For example, “double private x” is lexically correct but “private double x” is the syntactically correct version with the tokens in the correct order.

Basically, syntax means tokens are in the correct order

Question 15

What does the semantic component define?

Answer 15

It defines what an expression actually means.
if (m < n) { doSomething(); } is correct lexically and syntactically but unless we define how if statments work in the semantics, this has no meaning.
Semantics require are statments to have meaning which makes sense

Question 16

Why does a programming language need a precise description?

Answer 16

In order for the translator to analyse it and generate unambiguous code, a description as to how it works is needed

Question 17

What is a grammar?

Answer 17

A grammar is a set of syntactic rules which define how statements are constructed in a language.

Question 18

What does a grammar consist of?

Answer 18

A grammar consists of rules which are either:
Terminal - they contain no other rules in their definition
Non-terminal - a rule which contains another rule in its definition
Most rules are non-terminal

Question 19

In a syntax diagram (see notes for image), what is the difference between circles and ovals?

Answer 19

circles show terminal expressions

ovals show non-terminal expressions

Question 20

What is the Backus-Naur form (sometimes called Backus-Normal form)?

Answer 20

The BNF is a way of describing the grammar of a langauge. It’s similar to the syntax diagram but in a more text-based way a computer may find easier to understand.

Question 21

What is the notation for BNF?

Answer 21

-> rule definition
| or
 non-terminal symbol
symbol (in italics) terminal symbol
[tokens] optional symbols
{tokens} symbols repeated 0+ times
* symbols repeates 0+ times (suffix)
\+ symbols repeated 1+ times (suffix)

See notes for better structured version of the above

Question 22

What is Parsing?

Answer 22

Parsing is looking through a program and comparing it to its grammar to see which parts of the grammar apply to which parts of the program.
If the program doesn’t fit the grammar rules then its incorrect (there’s syntax mistakes)

Question 23

What are the 5 steps of the compilation process?

Answer 23

Lexical analysis (scanning)
Syntax analysis (parsing)
Semantic analysis
Code generation
Code optimisation

Question 24

What is scanning (lexical analysis)?

Answer 24

Scanning involves converting the text of a program into a sequence of tokens which represent distinct parts of the program.
As tokens are encountered, identifiers get put into a symbol table.

Question 25

What does a symbol table contain?

Answer 25

Variable names
Class names
Function names

Basically any name created by the programmer which isn’t a reserved legal word in the lexicon

Question 26

What happens in semantic analysis?

Answer 26

Information in the symbol table gets built up about the data items being declared (whether they’re functions, variables, arrays, etc.) and memory locations are assigned where necessary.
Checks are performed for type inconsistencies (in a strongly-typed language)

Question 27

What happens during code generation?

Answer 27

Code is generated for each of the constructs identfied during parsing and semantic analysis.
Everything found and put in the parse tree is walked through and low-level code is generated for each aspect of the tree.