Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Programming Language Principles, Design, and Implementation

Assignment 2

Compilers

1. Consider the following grammar for Boolean expressions, with non-terminal symbols A and B, start non-terminal symbol B, and terminal symbols ||, &&, true and false:

B ::= B || B | A

A ::= true | false | A && A

(a) Execute the high-level Bottom-Up parsing algorithm seen in the lectures on the following Boolean expression: true || false && true.

(b) Explain what shift-reduce problems could be encountered in this parsing.

[6 marks]

2. Consider the following language for programs as seen in the lectures:

P ::= S

S ::= S; S | [S] | id := E | if (B) S | if (B) S else S | while (B) S

E ::= E + E | E ∗ E | num | id

B ::= true | false | E < E | E > E | E == E | E ! = E | B || B | B && B |!B

(a) Add statements of the form until (B) S, which execute S until B is true, i.e., S is executed before B is checked, and extend the tac function, which generates TAC instructions, to support such statements.

(b) Use this extended tac algorithm to generate TAC instructions for the following program P: until (x > 10) x := x + 1, assuming that lookup(x) = p.

[6 marks]