Flashcards
SCC 312 - Languages and Compilation
Cards in this deck (80)
- 1what is sentential form in phase grammars?the intermediate stage between the start symbol and the final sentence
e.g. the man VERB NOUN-PHRASE - 2why not use deterministic FSR?- Have to try each alternative in turn
- This could lead to further alternatives
- Could be a lengthy procedure - 3what is equivalence?Gives the same result in some aspect?
e.g. two FSR's that produce that verify the same language - 4What is a regular expression?a set of rules that describe a generalised string
- 5What does the regular expression * mean?Zero or more instances of the atom
- 6What does the regular expression + mean?One or more instances of the atom
- 7What does the regular expression ? mean?Zero or one instances of the atom
- 8What is TAC?Three-Address Code is a form of representing intermediate code used by compilers
Each instruction in TAC can be described as a 4-tuple (also occasionally known as a 'quad')
(operator, operand1 operand2, result) - 9How does TAC generate instructions with more than three operands?TAC will decompose it into an equivalent series of instructions
e.g.
p := x + y * z
t1 := y * z
p := x + t1 - 10What are the key features of three-address code?Every instruction implements exactly one fundamental operation
The source and destination may refer to any available register - 11What is the Literal Table?The literal Table is similar to the Symbol Table, expect it's entries are any literal representations of values that appear in the input stream
- 12Why are Literal Tables used?By holding these in a table, the compiler can reference them using their address in the table, rather than use the literal directly
- the same way it references symbols via their address in the symbol table
The Literal Table can be populated by the syntax analyser - 13What is an advantage to TAC?The TAC representation is easier to optimise than the parse tree representation
- 14What are some design problems in the Intermediate Language Compiler design?Constraints in the IL language may lead to over-optimisation in the front-end
Constraints in the back-end may lead to overly verbose code for some targets
The lack of communication between the layers can lead to lost semantics between the two halves
- The parse tree is gone by the time we reach the back-end
- no token metadata is available - 15What are the benefits of IL compilers?the design provides a good degree of freedom, and prevents the internals of the compiler becoming too convoluted
- 16What is a JIT compiler?Rather than Split-Stage Compilers, a JIT compiler does its final stage as part of the execution environment
- the intermediate language becomes a merge of high-level and low-level opcodes - 17How do LR(0) parsers generate their tree?Push token onto a stack
Sanction rules by popping the components off the stack and replacing them with the non-terminal - 18What is the formal definition of a language?The set of all grammatically correct sentences
A language is the complete set of strings that can be formed from the symbols of an alphabet
e.g. in programming
The set of all syntactically valid Java source file programs - 19what are the 3 ways to define a language?Set definitions -type 1
Decision programs -type 2
Grammars -type 3 - 20What is an alphabet?A finite set of symbols
- symbols are atomic
- no duplicate symbols
e.g.
{0,1,2,3,4}
{a, e, r, g} - 21Define a stringA string a sequence of atomic symbols taken from a finite alphabet
- 22Define a sentenceWhen a string is a member of the language it is called a sentence of the language
- 23What is the |x| operation?Length operation
output is the length of x
e.g
|abcd| = 4
|(epsilon)| = 0 - 24What is the concatenation operation?The string formed by one string followed by another
written as: xy
where x and y are to different strings - 25What is the power operation?The string formed by writing down n copies of the string x
written as: x^n - 26What is the index operation?An operation to give the nth symbol in string x
written as: Xn (subscript n)
e.g. x = abca
X1 = a
X3 = c - 27What is a set definition?Decides if a string is the member of a language or not
If a language is such that the string follow certain patterns we are able to specify it by providing a set definition - 28What is a Decision Program?You input a string and the program tells you if the string belongs to the language
The language specified by the decision program is the set of all strings for which the program says 'yes' - 29What is a grammar?A set of rules for defining which strings are grammatical and which are not
For grammatical strings is prescribes the structure of the string - 30Examples of grammar uses in computer science?To process human language by computer
To process computer languages (compilers)
A general way of specifying an input format such as an aid to processing the input data - 31What is Derivation Tree?Top down derivation of a string
Start with first symbol, e.g. sentence
Searches for a sequence in the current string that matches the left hand side of the rule
Replaces the sequence with the right hand side of the rule
Continues until it gets stuck or has a valid string
This is a top-down, depth-first search - 32What is a Parse Tree?Bottom up parse to build the tree
Given a string, what productions would we need to derive it from the first symbol? - 33What are the 4 parts that Phrase Structure Grammars made up of?1. A set of basic objects of the language
- terminals
2. A set of things Non-Terminals
3. A particular Non-Terminal with which we always start the derivation of a valid sentence
e.g. SENTENCE
4. A set of production rules of the grammar. They have the form:
e.g. X -> y - 34What is the sentential form?The intermediate stage between the start symbol and the final sentence is called a sentential form
e.g. The man VERB NOUN-PHRASE - 35What is Backus-Naur Form (BNF)Another form of notation for specifying a grammar
::= terminal | terminal... - 36What type are Regular Grammars?type 3
- 37What are the different types of phrase structure grammars?Unrestricted
Context Sensitive
Context Free
Regular - 38What is the form of Regular Grammars?NON-TERMINAL -> terminalNON-TERMINAL
NON-TERMINAL -> terminal
e.g.
X -> yZ
Z -> b - 39What is the language of the grammar?The set containing each and every string terminal symbols (terminal string) that can be generated by a grammar is called the language generated by the grammar
If the grammar is G, then the language generated by G is denoted by L(G) - 40What is an FSR?Finite State Recogniser
determines what is part of the grammar
- called 'finite state' because there are only a finite of states in the machine
Consists of:
- a set of states
- one state designated the start state
- one state designated the finish state
- a set of arcs from one state to another each labelled with a symbol from the input alphabet - 41What is a non-deterministic FSR?A FSR that has two arcs coming from one state that have the same label
- 42How do we convert a non-deterministic FSR to a deterministic FSR?Use the Subset Construction Algorithm
- 43What are the steps in the subset construction algorithm?Step 1: mark the start state
Step 2: for each rule (or set of rules) group together all the non-terminals (including halt state) that are proceeded by the same terminal. The new set of non-terminals forms a new state on the FSR
Step 3: repeat step 2 until complete - 44What is the Repeat State Theorem?The string that is accepted can be expressed as 3 concatenated sub-strings
- VWX
Used to determine is a language is regular
V is the string accepted before the repeat state(s)
W is the repeated string
X is the string accepted after the repeat state(s)
Applies to any infinite regular language - 45What can't FSR's do?Count
- 46What can't PDR's do?Handle palindromes
- 47What machine defines a Context Free Language?Pushdown Recogniser - PDR
- 48What is a PDR?Its an FSR with a stack
- 49What are the two procedures of a PDR?Push
Pop
- cannot pop an empty string - 50What is the format of a PDR arc?read/pop/push
e.g
a/b/c
when read an 'a' on the input string
pop 'b' from the top of the stack
and push on 'c'
if 'b' is not on top of the stack, then an error occurs - 51Steps in constructing a PDR?(oh hi)Mark 3 states, 1, 2, and H
1 -> 2 is labelled - empty/bottom/Sbottom
e/T/ST
2 -> H is labelled - empty/bottom/bottom
e/T/T
for each production rule X -> Z, we have
empty/X/Z
for each terminal a, b we have
a/a/e
b/b/e - 52What causes non-determinism in PDR's?read/pop/.. values
e.g.
e/S/aS
e/S/aB - 53How to convert a non-deterministic PDR into a deterministic one?No formula for this
General rule of thumb:
- for every terminal t that can start the string there is an arc labelled
t/empty/t-empty
- for numerical relations between characters e.g. a^i b^i, push on a and pop off an a for every b
- ends with empty/bottom/bottom - as usual - 54Why are palindromes hard to handle?The only to way be sure that it is a palindrome is to see how many character there are to the end of the string, and identify where the middle is
- 55A context free language has a characteristic, what is this, and how does this effect the set of all context free languages?Many context free languages are only non-deterministic
So the set of all context-free languages is divided into
- a set which there is a deterministic PDR to parse them
- a set for which there is no deterministic PDR - 56How can you find if a language is poperly context free?Use LR(k) parsing
- 57What does ambiguity mean in languages?One or more sentences can be parsed into more than one structure
- 58When is grammar ambiguous?A grammar is ambiguous if there is at least one ambiguous sentence according to the grammar
- 59What is weak equivalence?The grammars agree as to which strings are grammatical and which are not
- 60What are semantic implications?With ambiguity, what matters is if the semantics of two syntactic structures for the same statement are different
e.g. order of precedence - 61What is the uvwxy theorem?The string that is accepted can be expressed as 5 concatenated sub strings: uvwxy
- applies to all infinite context free languages
u and y are the strings accepted before and after the repeated states. They may be empty
v and x are the repeated strings (NON-EMPTY)
w is the string accepted in the middle, NON-EMPTY - 62What is the format of context sensitive grammars?LHS -> RHS
LHS = any mixture, but there needs to be at least one symbol
RHS = any miixture but cannot be empty
RHS is at least as long as LHS - 63What is the format of unrestricted grammars?LHS -> RHS
LHS = any mixture, but at least one symbol
RHS = any mixture, and can be empty
no length restriction on the RHS - 64What are the characteristics of the tape?Infinite in both directions
Divided into squares
Each square contains a symbol from the alphabet of the language
Most contain the blank symbol B
Has a r/w head that points to the current symbol and also shows the current state - 65What are the TM arc instructions ?a/bD
where a is the symbol read from the input tape square
b is the new symbol to write
D is the direction to move the r/w head - L or R - 66What is the Linear Bounded Turing Machine?When a TM only requires the space on the tape taken by the input string plus a fixed number of extra squares
- 67What machine does an unrestricted grammar need?A Turing Machine, with unbounded extra space of the tape
- 68What is an FST?Finite State Transducer
A FSR that also produces output
- so an FSR is a restricted FST
For every read symbol it outputs a symbol - 69What can FST's be used for?Simple tasks life shift operations
Add operations
Subtract operations - 70What is a UTM?Universal Turing Machine
A UTM effectively runs any TM as if it were a program
A UTM models the behaviour of a TM
It received as input a coded version of the TM and a coded version of the input string
It produces as output a coded version of the output that would be produced by the original machine - 71How do we code a UTM?1. current state
2. symbol being read
3. symbol to write
4. move (L or R)
5. new state - 72What is on the UTM tape?The quintuples of the machine we want to simulate
The start state of the simulated machines (could be 0)
The contents of then (non-blank) part of the data
A mark on the simulated tape is to show where the simulated r/w head is - 73Outline the UTM process?1. Find an arc
2. Match the arc
3. Follow the arc - 74What does a LR(0) parser use to parse?Input buffer
A stack on which it keeps a list of states is has been
An action table to tell it what new state to move to
A goto table that tell it which grammar rule it should use given the state it is currently in - 75What is the Action table indexed by?A state of the parser and
A terminal - 76An Action table contains what actions?A shift, written as sn, where n is the next state
A reduce, rn, n is the grammar rules used to sanction
An accept, acc, means string has been accepted - 77What is the Goto Table?The Goto Table is indexed by the state of the parser and a non-terminal
It simply indiactes what the next state of the parser will be if it has recognised a certain non-terminal - 78How does the Aciton Goto parsing algorithm work?The stack is initialised with [ 0 ]. The current state will always be the state that is on top of the stack
Given the current state and the current terminal on the input stream an action is looked up in the action table - 79What are the two equivalence types?Name equivalence
Structure equivalence - 80—
Information
- Description
- Flashcards on SCC 312 - Languages and Compilation, created by Lewis Stones on 05/04/2018.
- Created by
- Lewis Stones
- Views
- 8
- Rating