Karteikarten
Semantic Analysis
Karten in diesem Stapel (28)
- 1Regular Expressions use in Compilers...A way of formally describing the set of lexemes (strings) associated with each token. Specifying finite and infinite languages
- 2An alphabet in Regular ExpressionsAn alphabet is a set of characters. E.g.
{1, 4, 7}, {a,b,..., z} and an empty set are all alphabets - 3What is a string over an alphabet?A string over an alphabet is a finite sequence from A. E.g.
A = {a,b,....,z}
A string over A would be "helloworld" - 4What is a language over an alphabet?A language over an alphabet is a set of strings over the alphabet. E.g.
A = {a, b, .... , z}
∅ is the empty language
{""}
{"helloworld"}
{"hello", "world"} - 5How do you decide, given a string S and a regular expression R, if S ϵ lang(R)?FSA as algorithms to decide the language defined by REs
- 6FSA : Deterministic vs Non-DeterministicDeterministic : Each of its transitions is uniquely determined by its source state & input symbol & reading an input symbol is required for each state transition
Non-deterministic : States may one or two or more possible states - 7Why do we use non-deterministic FSA'sNon-deterministic FSAs can be converted to DFSA so we are not loosing anything by using them.
NFSA are usually smaller (fewer states) than the DFSA accepting the same language - 8What is an ɛ-automaton?Usually non-deterministic FSA with alphabet including ɛ. Used to move between states without consuming an input
- 9Translation of RE to FSA : Basic RuleDon't need details of each FSA in the translation, we are only manipulating the initial and final state.
- 10Translation of RE to FSA : Translation of ∅
- 11Translation of RE to FSA : Translation of ɛ
- 12Translation of RE to FSA : Translation of 'c'
- 13Translation of RE to FSA : Translation of A
- 14Translation of RE to FSA : Translation of A + B
- 15Translation of RE to FSA : Translation of AB
- 16Translation of RE to FSA : Translation of A*
- 17Stack Machine PropertiesMain Memory : addressed 0 to some limit
Temporary Register : holds int
Program Counter (PC) : points to the next command in memory
IR/CI : current inst register, holding instruction executed next
Stack pointer (SP): points to the top of the stack - 18Advantages of stack machines...a) Simple Compilers : Code Gen for stack machines is much simpler than registers (no need for register allocation)
b) Compact object code saving memory. Machine commands have no or one arg unlike register
c) Simple CPUs : easy, cheap to manufacture - 19Disadvantages of Stack MachinesMemory Access is very slow in comparison with CPU operations.
Register's are fast, temporary, addressable storage in the CPU but more complex - 20Dealing with registers by 'divide & conquer'To generate efficient code for register machines, we spilt the code generation problem into 3 simpler sub-problems:
1) Assume unlimited registers when generating code
2) Modify translator to evaluate expressions in an order that minimises the no of registers needed
3) Invent a scheme to handle cases where we run out of registers - 21Why do we use stack operations in a Register Machine?Used for procedure/method invocation.
- 22Which register should we use as the first register when starting code generation?If registers are finite use the lowest possible because code generators will not use registers below the target, so any target below the initial register will be wasted and not used.
- 23Is an accumulator?A single register. Operations take of their arguments from the accumulator and stores the result in the accumulator.
- 24What happens when we reach the register limit for code generation?When one register is left, revert to the accumulator strategy, using the last register as the accumulator. Until then use any remaining registers using the register machine strategy for compilation
- 25Accumulator Machine : Basic DescriptionIt has a stack and one register (the accumulator). The stack is used for intermediate values as in the stack machine but arithmetic etc instructions are always of the form
Acc := Acc + Store[SP]
SP := SP+1 - 26Stack Machine : Basic DescriptionUses a pushdown stack rather than registers to evaluate each sub expression in the program. Implements registers w/ a stack. The ALU are always the top 2 registers of the stack & the result of the ALU is stored on the top of the stack. Stack = LIFO to hold short lived temp values. Machines with limited stack values need to dynamically renumber registers when the limit is reached.
- 27Register Machine : Basic DescriptionA register machine uses a fixed number of registers for storing intermediate values for computation. For example the "add" instruction could add the values in two specific registers and store the result in another register.
- 28MIPS : Basic DescriptionMips uses RISC and we use it as an accumulator machine. First arg is assumed to be in the accumulator, all the remaining args sit on the top of the stack, the result in the accumulator and after finishing all args are removed from the stack.
Informationen
- Beschreibung
- Karteikarten am Semantic Analysis, erstellt von ms660 am 12/01/2015.
- Erstellt von
- ms660
- Aufrufe
- 4
- Bewertung