Flashcards
312 - Terminology
Cards in this deck (43)
- 1What is a formal language?Set of all grammatically correct sentences of a language, that have been written or will ever be written
- 2What is considered an alphabet?Finite set of atomic symbols (no duplicates)
- 3What is considered a string?Sequence of atomic symbols taken from the alphabet
- 4What is considered a language?Complete set of strings that can be formed from the symbols of the alphabet
- 5What is considered a sentence?A string that is a member of a language
- 6What are the four operations, and their denotions?Length - | x |- means number of symbols in string
Concatenation - xy - string formed by x followed by y (order matters)
Power - x^n - string formed by writing down n copies of string x
Index - Xvn - nth symbols in string x - 7What does a decision program tell us?whether or not a string belongs to a language
- 8What is a grammar?Set of rules for defining which strings are grammatically correct/not
Prescribes the structure of the string - 9What are the steps when generating a derivation tree?- Begin with the distinguished symbol
- Search for a sequence in the current string that matches the left hand side of the rule
- Replace the sequence with the right hand side of the rule
- Continue till valid string/stuck
(top-down) - 10What are the steps when generating a parse tree?- Begin with a string in the language
- Search for a sequence in the string that matches the right hand side of the rule
- Replace with left hand side of the rule
- Continue until distinguished symbol/stuck
(bottom-up) - 11What are the four things that make up a phrase-structure grammar?1- Terminals
2- Non-terminals
3- Distinguished/start symbol
4- Production rules - 12What is the sentential form?Intermediate form between the distinguished symbol and the final form
- 13What are the 4 classes of grammars, and how can they be expressed?Regular - type 3 - FSR, SCA, Regex
Context free - type 2 - PDR's
Context sensitive - type 1 - LBTM
Unrestricted - type 0 - TM, UTM - 14What are the production rules of a regular grammar?Non-terminal -> terminal Non-terminal
Non-terminal - terminal
e.g X -> xC, X -> v - 15What is 'language of the grammar'?The set containing each and every string of terminal symbols (terminal string) that can be generated by a grammar - L(G)
- 16What is the subset construction algorithm and what are the steps?Used to convert ND-FSR -> D-FSR
- Mark the start state
- For each rule (or set) group together all the non-terminals that are preceded by the same terminal
- New state formed by the set of non-terminals
- Repeat step 2
- Re-label - 17What is a regular expression, and what are the 3 terms?Set of rules that describe a generalised string
* - Zero or more
+ - One or more
? - Zero or one - 18What are the production rules of context-free grammars?X -> RHS
Where X = single non-terminal
RHS = any mixture of terminals/non-terminals (can be empty) - 19What are the production rules of context-sensitive grammars?LHS -> RHS
Where LHS = Any mixture of terminals/non-terminals, but there must be at least one symbol
Where RHS = Same as LHS but can't be empty string and is ATLEAST as long as LHS - 20What are the production rules for unrestricted grammars?LHS -> RHS
Where LHS = any mixture of terminals/non-terminals, but there must be at least one symbol
Where RHS = LHS rules - 21What does no type checking provide, and whats an example language that doesn't type check?Total freedom - compiler will do literally whatever you ask
Total responsibility - compiler will do LITERALLY whatever you ask
e.g. assembler - 22What is a weakly-typed language and strongly-type language?Weakly-typed language - compiler does not enforce a typing discipline/can be easily undone
Strongly-typed language - does not allow you to use one type as another (unless explicitly indicated) - 23What is static type checking?Type checked by the compiler at compile time
- 24What are the two varieties of semantic checking (we're concerned with in this module)?Static type checking
type equivalence - 25What is type equivalence?Checking whether two entities have the same type (e.g. left and right hand side assignment)
- 26What is explicit type conversion?Where the programmer explicitly tells the compiler that the value is going to be this type (aka casting)
- 27What is implicit type conversion?Done by type coercion, which is where the compiler automatically inserts the code to do the conversion (e.g. might be done when an integer is passed, but expects a float)
- 28What are the two ways we check type equivalence?Name equivalence - reference to type name in symbol table, check two variables in question against their names in the table
Structure equivalence - use type names to access type definitions, and walk two trees to check equivalence - 29What is statically typed language and what are dynamically typed languages?Static - programmer defines the type of a variable e.g. java
Dynamic - when value assigned to a variable, the type is implied e.g. python - 30How does a turing machine work?By successively reading symbols from the input string (tape), and changing between states, similar to an FSR
e.g. an arc = x/bL
x = symbol read from input string
b = new symbol to write to the square
L = direction to move read/write head (L/R) - 31What is split-stage compilation?Compilation that exists in two forms;
compilers with and intermediate language
compilers which export code intended for an interpreter - 32What does an intermediate language (IL) allow?The compilation of code in one language, and the use in another
- 33What are problems which occur when using an IL?May lead to over-optimisation on the front-end compiler
May lead to lengthy code in the back-end compiler
Lack of communication between layers can lead to lost semantics between front-end compiler and back-end compiler
May break down due to back-end workings being different - 34What are the advantages to using an IL?Provides a good degree of freedom - allowing the creation of code in one language, and being exported to another
Prevents the internals of the compiler becoming convoluted - 35What is Just-In-Time (JIT) compilation?Where the final stage of compilation is a part of the execution environment
- 36What is the 'dangling else problem'?A problem which occurs when there are multiple else statements to a single if (it's ambiguous and produces different parse trees depending on which else it chose)
- 37Why would we separate the lexical analyser (LA) stage from the the syntax analyser (SA) ?In order to simplify the input for the syntax analyser
Allows tokens to be specified as a regular grammar, meaning it can be small and efficient - 38What are problems that can occur when you separate the LA and SA stages?Semantic ambiguity - that being the meaning of the parse
Can only be resolved by a syntax analyser, meaning some languages can't have this separation - 39How does syntactic analysis work?A parse tree is built
- Root = distinguished symbol
- Leaves = sequence of tokens from LA
- Branches = rules from the grammar - 40What are LL(k) and LR(k) parsers, and what does each letter mean?First L/R = input stream of tokens is processed from L(eft) to R(ight)
Second L/R = type of tree produced by the parser L (left-most e.g. derivation)
R (right-most e.g. parsing)
K = number of symbols we can look ahead of - 41What is the criteria for a good parsing strategy?Powerful enough for the language being parsed (power)
Back-tracking - aka unwind, traverse backwards through tree to take different paths
Look-ahead - instead of back-tracking, saves a lot of cpu cycles as no back tracking is needed, as correct decision can be made
Efficient - 0(n) n = length of program
Size - - 42What are the 5 things we include in a quintuple for a UTM?1. Current state
2. Symbol being read
3. Symbol to write
4. Move (L/R)
5. New state - 43—
Information
- Description
- Flashcards on 312 - Terminology, created by Mac Howarth on 05/05/2018.
- Created by
- Mac Howarth
- Views
- 1
- Rating