操作系统代写 | COMP3021 (Spring 2021) Programming Language Paradigms

本次香港代写主要为操作系统限时测试

Question 1    Scope and Lifetime [50 marks]

1(a)  [30 marks]

entire program execution

entire program execution

from the declaration statement to the termination of funF()

from the malloc statement to the deallocation statement

Lines 7-8 (the access to that variable’s address is lost at line 9)

Marking scheme:   2 marks per cell

1(b) [20 marks]

Example code:

void fun() {

static int counter = 0;

counter ++;

printf(“%d\n”, counter);

Explanation: In the above function, the static local variable counter is used to collect usage statistics, i.e., count how many times that function is called.

Marking scheme: 8 marks for the code, 12 points for explanation.
We accept any meaningful code example.

Question 2    BNF Grammar                                          [50 marks]

intval denotes the token for integer literal (e.g., 12345).

+ denotes the addition operator, and ´ denotes the multiplication operator.

Consider the following BNF grammar:

<expr> à intval  |  + <expr> <expr> | ´ <expr> <expr>

2(a)  [35 marks]

Marking scheme:   deduct 5 marks per each missing/incorrect tree node

2(b)  [15 marks]

Marking scheme:

This grammar is unambiguous.

We call a sequence of tokens to be a valid expression if it can match with the given grammar. To show that this grammar is unambiguous, we need to prove that,

given any valid expression E, there is only one parse tree of E.

Case I:     E has exactly 0 operators.

In this case, E must be an integer literal; otherwise, E is not a valid expression.

It is trivial that there is only one parse tree of E.

Case II:    E has exactly 1 operator.

In this case, E must be an operator (+ or ´) followed by two integer literals;
otherwise, E is not a valid expression.

It is trivial that there is only one parse tree of E.

Case III:   E has more than 1 operators.

In the given grammar, each operator (+ or ´) takes its operands on its right-hand-side only, but not on its left-hand-side. Thus, we will examine operators in E one-by-one from right to left, and show how to construct a unique parse tree. We name operators in E from left to right as op_n, op_n-1, …, op₂, op₁, where n denotes the number of operators in E.

Initially, we convert each integer literal in E to an expression (say, E_x), which corresponds to a unique subtree according to Case I.

Next, we examine operators in the order (op₁, op₂, …, op_n-1, op_n), as discussed above.

When we evaluate an operator op_i, there is only one way to get its operands (i.e., the next two expressions on the right-hand-side). Then, we replace op_i and its operands by an expression (say, E_i‘), which corresponds to a unique subtree according to Case II.

By repeating the above procedure, the expression E will be converted to a unique tree.