LP Flashcards

Question

Define DFA:

Answer 1

A DFA describes languages. You input a word and the DFA accepts/rejects it. A DFA A = (Q, Σ, δ, q0, F) is specified by: 1. Finite state set Q 2. Input alphabet Σ. The machine operates over words over Σ. 3. Transition function δ : Q × Σ −→ Q If the machine is in state q and the present input letter is a then the machine changes its internal state to δ(q, a) and moves on to the next input letter. 4. Initial state q0. 5. Set F ⊆ Q of final states specifies which states are accepting. At the end of the input it does not end at a state F, the word is not accepted.

Answer 2

NFA generalise DFA. They allow several (0, 1, more than 1) outgoing transitions with the same label. NFA accepts a word if some choices of transitions take the machine to a finite state. NFA may have different computations for same word

Answer 3

The process of breaking down a stream of input characters into meaningful chunks, called tokens. The main goal of lexical analysis is to identify the basic building blocks of a language, such as keywords, identifiers, constants, and operators, These tokens serve as input to the next stage, which is syntactic analysis.

Answer 4

NFA generalise DFA. They allow several (0, 1, more than 1) outgoing transitions with the same label. NFA accepts a word if some choices of transitions take the machine to a finite state. NFA may have different computations for the same word

Answer 5

The process of analysing the syntax of a sentence to determine its structure and meaning. It involves checking that the order and combination of tokens conform to the grammar rules of the language.

Answer 6

Instruction selection is the process of selecting appropriate instructions from a set of available instructions to implement a given program. In Ocaml, this involves translating the high-level Ocaml code into a lower-level assembly language that can be executed by the computer. The choice of instructions can have a significant impact on the performance of the program

Answer 7

The process of optimizing code at the level of individual expressions or statements, without considering the overall structure of the program. In Ocaml, this can involve simplifying expressions, reordering computations, or eliminating redundant computations to improve performance.

Answer 8

The process of optimizing loops in a program to improve performance. In Ocaml, this can involve techniques such as loop unrolling and loop fusion.

Answer 9

Refers to the area of the program where a variable can be accessed. In Ocaml, the scope of the variable is determined by its declaration and the block structure of the program.

Answer 10

Describes its language L(A)

Answer 11

no DFA accepts{a^p| p∈N is prime}.

Answer 12

To determine whether w is accepted by A, follow the path in A labelled with the input letters of w, starting from the initial state. If this leads you to a final state, the word is accepted. w = abaab leads to state r, which is a final state, so the word is accepted. w′ = abba is rejected because it leads to q, which is not a final state.

Answer 13

are called regular (cf. regexps!).

Answer 14

Extend this to δˆ, giving the state after an arbitrary string of letters is read: ˆδ : Q × Σ∗ −→ Q. For state q and word w,ˆδ(q,w) is the state we reach from q if we input w.

Answer 15

An NFA A = (Q, Σ, δ, q0, F) is specified by: - State set Q - input alphabet Σ - transition function δ - initial state q0 - the final state set F Using the power set notation: 2^Q = {S | S ⊆ Q} we can write δ : Q × Σ −→ 2^Q.

Answer 16

The main difference between lexical analysis and syntactic analysis is that lexical analysis deals with the analysis of individual words or tokens, whereas syntactic analysis deals with the analysis of the structure and organization of these tokens to form meaningful sentences or statements in the programming language.

Answer 17

The main difference between concrete syntax and abstract syntax is that concrete syntax is the actual textual representation of a program in a programming language, whereas abstract syntax is a simplified, language-independent representation of the essential structure of a program.

Answer 18

Type 0 grammars contain productions of the form α ::= β. α is a non-empty string of terminal and/or nonterminal symbols. Type 0 grammars include pretty much anything.

Answer 19

(Context-sensitive): grammars contain productions of the form αAγ ::= αβγ. Here A denotes a single nonterminal and β denotes an arbitrary string of terminal and/or nonterminal symbols. You can ‘expand’ A — subject to it occurring in the context described by α and γ. Generates languages that are context-sensitive.

Answer 20

(Context-free): grammars contain productions of the form A ::= γ. A denotes a single nonterminal. BNF is a language for describing Type 2 languages.

Answer 21

Type 3 or regular grammars contain productions of the form A ::= aB A ::= b A ::= ε

Answer 22

Type 3 grammar: S -> aS| b

Answer 23

Type 2 grammar: S -> aSb | ε

Answer 24

Type 1 grammar: S -> aA A -> aA | bB B -> bB | ε

Answer 25

When a sentence can be parsed in two different ways, each with a different meaning. In a computer programming language, ambiguity is generally undesirable because it can lead to unexpected behaviour and make programs harder to understand and maintain. Programming languages strive for unambiguous syntax to ensure that programs are executed as intended and to facilitate program comprehension and debugging.

Answer 26

Corresponds to the language that has 0 or more occurrences of a i.ie, L {ε, a, aa, aaa,....} . Where ε is the empty string. Production rule could be: S -> aS | ε

Answer 27

Corresponds to the language that only matches 1 a. i.e., L = {a}

Answer 28

Corresponds to the language that matches either 1 a or 1 b i.e., L = {a, b}

Answer 29

Abstract syntax is a way of representing the essential elements of a program or a language using a simplified and standardized notation.

Answer 30

Instruction selection is the process of selecting appropriate machine instructions to implement a given intermediate code or high-level language construct. The goal is to generate efficient code that correctly captures the behaviour of the source code. Here is an example of instruction selection for a simple expression: a = b + c * d Assuming a target architecture with the following instructions: MOV reg, mem: Move data from memory to a register ADD reg1, reg2: Add the contents of reg2 to reg1 MUL reg1, reg2: Multiply the contents of reg1 by reg2

Answer 31

Local optimization is a compiler optimization technique that focuses on improving the performance of small sections of code, typically a single basic block or a small sequence of basic blocks. The goal of local optimization is to transform code in a way that produces equivalent or better results, while improving the performance of the generated machine code. Examples: Dead code elimination: Removing instructions that have no effect on the program's behaviour, such as those that operate on values that are never used.

Answer 32

The goal of loop optimization is to transform loop code in a way that produces equivalent or better results while improving the performance of the generated machine code. Example: Loop fusion and fission: Loop fusion involves combining two or more loops into a single loop, while loop fission involves splitting a single loop into two or more loops. These techniques can be used to reduce the overhead of loop control instructions and improve locality of reference in memory access patterns.

Answer 33

Variable scope refers to the region of a program in which a variable can be accessed or referenced. In most programming languages, variables are declared within a specific scope, such as a function or a block of code, and are only accessible within that scope or nested scopes. Global scope: Variables declared outside of any function or block of code have global scope and can be accessed from anywhere in the program. Global variables are often used to store program-wide data that needs to be accessed by multiple functions or modules. Local scope: Variables declared within a function or block of code have local scope and are only accessible within that function or block, as well as any nested functions or blocks. Local variables are often used to store temporary data or to isolate data that is only needed within a specific part of the program.

Answer 34

A compiler is a program that translates the entire source code of a program into machine code or byte code before execution, generating an executable file that can be run directly by the operating system

Answer 35

An interpreter, on the other hand, executes the source code directly, line by line, without generating an executable file. Instead, it translates each line of code into machine code or bytecode at runtime, and then executes it.

Answer 36

A single-pass compiler reads the source code only once, from beginning to end, and generates the object code in one pass.

Answer 37

A multi-pass compiler reads the source code multiple times, performing several analyses and optimizations before generating the object code.

Answer 38

Local code optimization applies to a single function or procedure, optimizing the code within the function to improve its performance.

Answer 39

Global code optimization, on the other hand, applies to the entire program, optimizing the code across multiple functions or procedures to improve the program's overall performance.

Answer 40

In a stack, memory is allocated and deallocated in a last-in-first-out (LIFO) manner. It is typically used for storing local variables, function call frames, and return addresses.

Answer 41

In a heap, memory is dynamically allocated and deallocated in a more flexible manner, using algorithms such as malloc() and free(). It is typically used for storing objects and data structures whose size and lifetime are unknown at compile time.

Answer 42

(i) When arguments are passed using stack-based parameter passing, the caller pushes the argument onto the top of the stack before calling the function. In this case, the caller would push the value 5 onto the stack, and then call the function. Inside the function, the value of a would be accessed by first moving the stack pointer to the top of the stack, and then accessing the value at the appropriate offset from the stack pointer. After the function returns, the caller would pop the argument off the top of the stack. Here's a step-by-step breakdown of the process: 1. The caller pushes the argument 5 onto the stack. 2. The caller jumps to the function myfun. 3. Inside myfun, the function prologue is executed, which saves the old stack pointer and sets the new stack pointer. 4. The function myfun accesses the value of a by moving the stack pointer to the top of the stack and accessing the value at the appropriate offset from the stack pointer. 5. The function myfun performs its computation using the value of a. 6. The function epilogue is executed, which restores the old stack pointer and returns control to the caller. 7. The caller pops the argument off the top of the stack.

Answer 43

Here's a step-by-step breakdown of the process: The caller stores the argument 5 in a designated argument register, such as $a0. The caller jumps to the function myfun. Inside myfun, the function prologue is executed, which saves the old frame pointer and sets the new frame pointer. The function myfun accesses the value of a directly from the argument register, such as $a0. The function myfun performs its computation using the value of a. The function epilogue is executed, which restores the old frame pointer and returns control to the caller. The caller stores the return value of myfun in register $s0.

Answer 44

Stack-based parameter passing: In stack-based parameter passing, parameters are pushed onto the stack before a function call. The function then accesses the parameters from the stack using offsets from the stack pointer ($sp). This approach is typically used when the number of parameters exceeds the number of available registers.

Answer 45

Register-based parameter passing: In register-based parameter passing, parameters are passed in registers. The MIPS architecture has designated argument registers, which are used for this purpose. The function then accesses the parameters directly from these registers.

Answer 46

A stack frame is a data structure used by a computer program at runtime to store information about a subroutine or function call. It is typically implemented as a contiguous block of memory on the program's call stack, and contains the data necessary to execute the subroutine or function and to return to the caller.

Answer 47

Call by value involves passing a copy of the argument value to the function. This means that any changes made to the argument inside the function do not affect the original value of the argument. In other words, the function can only modify its local copy of the value, and not the original variable that was passed as the argument.

Answer 48

Call by reference, on the other hand, involves passing a reference to the original argument variable to the function. This means that any changes made to the argument inside the function affect the original value of the argument.

Answer 49

1. Stack-based allocation: In stack-based allocation, variables are stored on a stack data structure in a contiguous block of memory. Each function call creates a new stack frame, and local variables are allocated within that frame. This method is fast and useful for managing the call stack and storing local variables. Stack-based allocation: Allocating variables on a stack is fast and useful for local variables and managing the call stack. 2. Heap-based allocation: In heap-based allocation, variables are stored on the heap, a larger area of memory managed by the operating system. This method is useful for storing dynamically-allocated data structures such as arrays and linked lists, as well as large objects that cannot fit on the stack. Heap-based allocation allows for dynamic resizing of memory. Heap-based allocation: Allocating variables on the heap is useful for dynamically-allocated data structures and allows for dynamic resizing of memory. 3. Register-based allocation: In register-based allocation, variables are stored directly in the processor's registers. Registers are small, fast storage locations that can be accessed very quickly. This method is useful for frequently accessed variables such as loop counters and function return values, as it can result in significant performance improvements due to the faster access times compared to memory-based storage. Register-based allocation: Storing variables directly in the processor's registers is fast and useful for frequently accessed variables such as loop counters and function return values.

Answer 50

Source-code optimization involves optimizing the code before it is compiled into machine code. This can include techniques such as removing redundant code, simplifying expressions, and reducing function call overhead. The goal of source-code optimization is to produce more efficient and faster code. Target-code optimization, on the other hand, involves optimizing the machine code itself after it has been generated by the compiler. This can include techniques such as loop unrolling, instruction scheduling, and register allocation. The goal of target-code optimization is to produce code that runs faster and more efficiently on the target hardware.

LP Flashcards

(74 cards)