LP

Question 1

What is a language?

Answer 1

A language is a set of symbols/tokens and a set of (possibly empty) strings and tokens.

Question 2

What is the purpose of formal grammar?

Answer 2

The purpose of formal grammar is to generate languages. Using formal grammar, we can verify whether a sentence is in the language and synthesize legal problems.

Question 3

What is V in formal grammar?

Answer 3

In formal grammar, V stands for vocabulary, which is a set of symbols.

Question 4

How is V partitioned in formal grammar?

Answer 4

V is partitioned into two subsets of terminal and nonterminal symbols in formal grammar.

Question 5

What is V* in formal grammar?

Answer 5

In formal grammar, V* is the set of all strings of elements of V, including the empty string. This is called the closure of V.

Question 6

What is the set + in formal grammar?

Answer 6

In formal grammar, + is the set of non-empty strings of elements of V.

Question 7

What does ε represent in formal grammar?

Answer 7

In formal grammar, ε represents the empty string, often informally written as ‘ ’ or “ “.

Question 8

Can you give an example of a vocabulary V in formal grammar?

Answer 8

Sure. A vocabulary V could be {0, 1, +, -, *, (, ), <exp>}, where <exp> is a non-terminal symbol, and all other symbols are terminal.</exp></exp>

Question 9

Can you give an example of sentences in a vocabulary V in formal grammar?

Answer 9

Sure. Example sentences in a vocabulary V {0, 1, +, -, *, (, ), <exp>} could be ε, 1 + 1, (1 + 1) and (1 + (1)), ((((, and (()) * --.</exp>

Question 10

What do alpha, beta, and gamma range over in formal grammar?

Answer 10

In formal grammar, alpha, beta, and gamma range over strings.

Question 11

What is a production rule in formal grammar?

Answer 11

A production rule is a pair alpha ::= beta, where alpha is a nonterminal symbol, and beta is a string of terminals and/or nonterminals.

Question 12

What is an example vocabulary V in formal grammar?

Answer 12

An example vocabulary V in formal grammar could be {0, 1, +, -, *, (, ), <exp>}.</exp>

Question 13

What are some example production rules for the given vocabulary V?

Answer 13

Some example production rules for the given vocabulary V {0, 1, +, -, *, (, ), <exp>} are:</exp>

<exp> ::= 0
<exp> ::= 1
<exp> ::= -<exp>
<exp> ::= (<exp>)
<exp> ::= <exp>+<exp>
<exp> ::= <exp>*<exp>
</exp></exp></exp></exp></exp></exp></exp></exp></exp></exp></exp></exp>

Question 14

Definition of regular grammar:

Answer 14

Regular grammar is formal grammar that generates only regular languages, which can be recognised by a DFA or NFA.
Rules in form A -> aB or A -> a where A and N are non-terminals and a is terminal.
Regular grammars are of type 3.

Question 15

Definition of context-free grammar:

Answer 15

Formal grammar in which each production rule has a single non-terminal symbol on its left-hand side and on the right-hand side 0 or more terminals or non-terminals.
Used to describe the syntax of programming and natural languages.
A language is context-free if there exists a cfg that generates it.
CFG grammars are of type 2.
S -> NP VP
NP -> Det N
VP -> V NP
Det -> the
N -> cat | mouse
V -> chased

Question 16

Left-regular grammar:

Answer 16

When Terminals are on the left:

1. A -> a
2. A -> Ba
3. A -> e

Question 17

Right-regular grammar:

Answer 17

When non-terminals are on the right:

1. A -> a
2. A -> aB
3. A -> e

Question 18

Write grammar that generates the following language, over the alphabet {0, 1}:
{0}.

Answer 18

S -> 0

Question 19

Write grammar that generates the following language, over the alphabet {0, 1}:
{1, 10, 100, 1000, . . .}

Answer 19

S -> 1T | 1
T -> OT | e

Question 20

Write grammar that generates the following language, over the alphabet {0, 1}:
The set of strings over 0 and 1 that contain at least three consecutive repeated characters. So 100110 and ϵ are not in the language,
and 000 and 111 and 01000110 are in the language.

Answer 20

S → 0SS | 1SS | A
A → 000A | 111A | B
B → 000B | 111B | ε

Question 21

Write grammar that generates the following language, over the alphabet {0, 1}:
The set of strings over 0 and 1 that contain no three consecutive
repeated characters. So 100110 and ϵ are in the language, and
000 and 111 and 01000110 are not.

Answer 21

S → 0A | 1A | ε
A → 01B | 10B | 0S | 1S
B → 01C | 10C | ε
C → 0B | 1B | ε

Question 22

write a regular grammar to
recognise ( {a3^n| n ≥ 0}

Answer 22

S → aB | ε
B → aC
C → aS

Question 23

write a regular grammar to
recognise {(abba)∗}

Answer 23

S -> aB | ε
B -> bC
C -> bD
D -> aS

Question 24

Write a grammar for the language of properly bracketed high school
arithmetic over single binary digits. So:
* the set of terminal symbols is {0, 1, +, ×,(,)}, and
* 0 and 1 and (0) and 1+1 and 1+0×1 and 1+ (0×1) and (1+1)×1
are in the language, and
* 01 and 1 + (1 and () are not in the language.

Answer 24

<exp> ::= <term> | <term> + <exp> | <term> - <exp>
<term> ::= <factor> | <factor> × <term>
<factor> ::= <digit> | (<exp>)
<digit> ::= 0 | 1
</digit></exp></digit></factor></term></factor></factor></term></exp></term></exp></term></term></exp>

Question 25

Define DFA:

Answer 25

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.

Question 26

Define NFA:

Answer 26

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

Question 27

Describe Lexical Analysis

Answer 27

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.

Question 28

Define NFA:

Answer 28

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

Question 29

Describe Syntactic Analysis

Answer 29

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.

Question 30

Describe instruction selection

Answer 30

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

Question 31

Local Optimization

Answer 31

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.

Question 32

Loop Optimization

Answer 32

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

Question 33

Variable Scope

Answer 33

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.

Question 34

DFA A

Answer 34

Describes its language L(A)

Question 35

Not every language can be defined by a DFA

Answer 35

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

Question 36

Transition Diagrams

Answer 36

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.

Question 37

Languages that can be recognised by DFA

Answer 37

are called regular (cf. regexps!).

Question 38

Extended transition function

Answer 38

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.

Question 39

The precise definition of NFA A = (Q, Σ, δ, q0, F):

Answer 39

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.

Question 40

Difference between Lexical and Syntactic Analysis

Answer 40

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.

Question 41

Difference between Concrete Syntax and Abstract Syntax.

Answer 41

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.

Question 42

Define Type 0 grammar.

Answer 42

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.

Question 43

Define Type 1 grammar.

Answer 43

(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.

Question 44

Define Type 2 grammar.

Answer 44

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

Question 45

Define Type 3 grammar.

Answer 45

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

Question 46

Example Regular grammar

Answer 46

Type 3 grammar:

S -> aS| b

Question 47

Example (Context-free)

Answer 47

Type 2 grammar:

S -> aSb | ε

Question 48

Example Context Sensitive

Answer 48

Type 1 grammar:

S -> aA
A -> aA | bB
B -> bB | ε

Question 49

Ambiguity description and why it is undesirable in programming languages

Answer 49

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.

Question 50

1. Describe precisely the language corresponding to the regular expression
   a∗.

Answer 50

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 | ε

Question 51

2. Describe precisely the language corresponding to the regular expression (a).

Answer 51

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

Question 52

3. Describe precisely the language corresponding to the regular expression (a|b).

Answer 52

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

Question 53

Describe abstract syntax

Answer 53

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

Question 54

describe instruction selection

Answer 54

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

Question 55

describe local optimisation

Answer 55

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.

Question 56

Describe loop optimisation

Answer 56

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.

Question 57

Describe Variable Scope

Answer 57

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.

Question 58

Define Compiler

Answer 58

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

Question 59

Define Interpreter

Answer 59

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.

Question 60

Define Single-pass complier

Answer 60

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

Question 61

Define Multi-pass Compiler

Answer 61

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

Question 62

Describe Local Code optimization

Answer 62

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

Question 63

Describe Global code optimization

Answer 63

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.

Question 64

Stack Definition

Answer 64

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.

Question 65

Describe Heap memory

Answer 65

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.

Question 66

You are given a function myfun(int a) which takes one (integer) parameter a.
A call x := myfun(3+2) is made where x is stored in register $s0.

(i) Describe how the above function call is made when arguments
are passed using stack-based parameter passing.

Answer 66

(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.

Question 67

When arguments are passed using register-based parameter passing in the MIPS architecture, the caller stores the argument in a designated argument register before calling the function. In this case, the caller would store the value 5 in a register, such as $a0. Inside the function, the value of a would be accessed directly from the argument register. After the function returns, the value of x would be stored in register $s0.

Answer 67

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.

Question 68

Describe stack-based parameter passing:

Answer 68

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.

Question 69

Describe register-based parameter passing:

Answer 69

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.

Question 70

Describe Stack Frame

Answer 70

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.

Question 71

Describe call-by-value

Answer 71

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.

Question 72

Describe call-by-reference

Answer 72

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.

Question 73

Describe 3 different ways to store a variable in a runtime environment. Give
one advantage and a typical use for each of them.

Answer 73

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.

Question 74

The difference between Source-code optimisation and target-code optimisation

Answer 74

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.