Compilers, Interpreters and Grammars Flashcards
Week 11 Stuff
How does a compiler work?
Takes a source program and translates the whole thing into machine code.
The translation and execution are separate
How does an interpreter work?
Takes one instruction at a time from source code and does it.
No binary code is generated.
Source program analysis and execution are interlaced
Which executes code faster, compiler or interpreter?
Compiler
Which is better for keeping source code hidden, compiled or interpreted?
Compiled
Which is better for rapid prototyping (changes are frequently made), compiled or interpreted?
Interpreted
Which is better for moving between platforms, compiled or interpreted?
Interpreted
Why are interpreters sometimes called virtual machines?
Because they take 1 instruction at a time and execute it (similar to a CPU)
Is Java compiled or interpreted?
Both, it’s compiled into machine-independent virtual machine code then interpreted when run.
javac generated virtual bytecode, JVM interprets this.
What is translation?
The act of turning source code into binary (machine) code which the CPU can understand
What kinds of programs do translation?
Compilers (translate HLL into machine code)
Assemblers (translate mnemonics like MOV into binary code)
Sometimes compiling requires a compiler and assembler as 2 steps
What are the steps to making then running a program?
Edit -> Compile -> Link (to external libraries) -> Load/Run
What are the 3 components of a coding language?
Lexical (the tokens)
Syntactical (the structure)
Semantic (the meaning)
What does a lexicon contain?
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.
What does syntax define?
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
What does the semantic component define?
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
Why does a programming language need a precise description?
In order for the translator to analyse it and generate unambiguous code, a description as to how it works is needed
What is a grammar?
A grammar is a set of syntactic rules which define how statements are constructed in a language.
What does a grammar consist of?
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
In a syntax diagram (see notes for image), what is the difference between circles and ovals?
circles show terminal expressions
ovals show non-terminal expressions
What is the Backus-Naur form (sometimes called Backus-Normal form)?
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.
What is the notation for BNF?
-> 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
What is Parsing?
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)
What are the 5 steps of the compilation process?
Lexical analysis (scanning) Syntax analysis (parsing) Semantic analysis Code generation Code optimisation
What is scanning (lexical analysis)?
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.
What does a symbol table contain?
Variable names
Class names
Function names
Basically any name created by the programmer which isn’t a reserved legal word in the lexicon
What happens in semantic analysis?
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)
What happens during code generation?
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.
