The University of New South Wales Final Examination
Term 1, 2021 COMP3131/COMP9102 Programming Languages and Compilers
1. Time Allowed: 3 hours (including 10 min reading time)
2. Total Number of Pages: 8 (including cover page and Appendix A)
3. Total Number of Questions: 5
4. Total Marks Available: 100
5. Marks available for each question are shown in the examination paper.
6. The questions are not of equal value.
7. Answer all questions.
8. Submit your answers via give or Webcms3.
9. The answers to Q1 can be submitted as jpeg/gif/tiff/png/pdf files but the an- swers to Q2 – Q5 must be submitted as ASCII text files:
• Q1: *.suffix, where suffix is jpeg, gif, tiff, png, or pdf • Q2: *.txt
• Q3: *.txt
• Q4: *.txt
• Q5: *.txt
10. No examination materials allowed.
Page 1 of 8
浙大学霸代写 加微信 cstutorcs
Question 1. Regular Expressions to Finite Automta [18 marks] Consider the following regular expression:
(a|b)∗a(a|ǫ)
(a) Use Thompson’s construction to convert this regular expression into
(c) Convert the DFA of (b) into a minimal-state DFA.
You are required to apply exactly Thompson’s construction algorithm in (a) and the subset construction algorithm in (b) to solve those two problems.
Accepted files to submit via give or Webcms3: *.jpeg, *.gif, *.tiff, *.png or *.pdf.
(b) Use the subset construction to convert the NFA of (a) into a DFA.
Page 2 of 8
[7 marks] [7 marks] [4 marks]
Question 2. Context-Free Grammars [15 marks] Assume that arithmetic expressions are built up from the following terminals:
• Binary infix operators: @, #, +, − • Unary prefix operator: ∼
• Variables: X, Y, Z
• Brackets: [, ]
Operator ∼ has the highest precedence, followed by @ and #, which have equal precedence. Operators + and − have the lowest precedence. Operators @, # and + are left associative but − is right associative. Brackets are used to group expressions in the usual manner.
Write a context-free grammar for this language.
You are not allowed to use the regular operators, ∗, +, and ?, in your grammar.
Accpeted file to submit via give or Webcms3: *.txt.
Page 3 of 8
Question 3. Recursive-Descent LL(1) Parsing Consider the following context-free grammar:
1. S → BA 2. A → aBA 3. |ǫ
4. B → DC 5. C → cDC 6. |ǫ
7. D → xSf 8. |gCg
[20 marks]
where the set of nonterminals is {S, A, B, C, D} and the set of terminals is {a,c,x,f,g}.
(a) Compute the FIRST sets for all nonterminal symbols.
(b) Compute the FOLLOW sets for all nonterminal symbols.
(c) Construct the LL(1) parsing table for the grammar.
(d) Is the grammar LL(1)? Justify your answer in a few sentences.
(e) The string gx is NOT syntactically legal (since it is NOT in the language defined by the grammar). Explain concisely how this can be detected by an LL(1) table-driven parser for the language.
Note: In your answer, you can write E or e as an abbreviation for ǫ.
Accepted file to submit via give or Webcms3: *.txt.
Page 4 of 8
Programming Help
Question 4. Attribute Grammars [17 marks] Consider the following context-free grammar that generates regular expres-
6. | (R1)∗
(a) Define an attribute grammar that records the maximum number of nested Kleene star operators of a regular expression R in its attribute R.depth. For example, ab has depth 0, a∗ has depth 1 and a∗|(b∗|a)∗ has depth 2.
[14 marks]
(b) Is R.depth inherited or synthesized? Explain your answer.
Note: In your answer, you can write R1, R2 and ∗ as R1, R2 and ∗, respec- tively.
Accepted file via give: *.txt.
Page 5 of 8
Question 5. Code Generation [30 marks] Consider the following attribute grammar for generating “short-circuit” code,
• The semantic rules associated with a production are evaluated sequen- tially in a top-down manner, and
• “#” stands for the string concatenation operator.
S → whileB doS1
S.begin := getNewLabel();
B.true := getNewLabel();
B.false := S.next;
S1.next := S.begin;
S.code := emit(S.begin ′ :′) # B.code # emit(B.true ′ :′) # S1.code # emit(′goto′ S.begin)
S → ID = E
S.code := E.code # emit(ID.place ′ :=′ E.place)
E → E1 + E2
E.place := getNewTemp();
E.code := E1.code # E2.code # emit(E.place ′ :=′ E1.place ′ +′ E2.place)
E.place := ID.place; // ID.place is the lexeme of the ID E.code := ′ ′ // no code generated
B → B1 && B2
B1.true := getNewLabel();
B1.false := B.false;
B2.true := B.true;
B2.false := B.false;
B.code := B1.code # emit(B1.true ′ :′) # B2.code
B1.true := B.false;
B1.false := B.true;
B.code := B1.code B → ID1 > ID2
B.code := emit(′if′ ID1.place > ID2.place ′goto′B.true) # emit(′goto′B.false)
Note that this grammar is ambiguous but that does not affect the following questions.
Consider the following while loop:
while(! (a>b&&x>y))
r = p + q;
(a) Draw the AST (Abstract Syntax Tree) for the while loop.
Continued onto next page
Page 6 of 8
Question 5 continued from Page 6
(b) Suppose that S.next = L666, getNewLabel() will return labels L1, L2, … when called, and getNewTemp() will return temporary vari- ables t1, t2, . . . when called.
Give the B.true and B.false attributes for all the B nodes in the AST of (a).
(c) Give the S.code attribute for the root node S in the AST of (a). In other words, give the code generated for the while loop according to this attribute grammar.
(d) The production B → B1 && B2 given in the grammar serves to de- fine conditional AND expressions. Suppose we replace this production with B → B1 ∥ B2 so that conditional OR expressions are considered instead. Give the semantic rules for the new production to generate short-circuit code for conditional OR expressions.
(e) Give the semantic rules for the new production that defines do-while statements:
S → doS1 whileB
In a do-while statement, S1 will be executed at least once.
Note: In your answer, you can write S1, B1 and B2 as S1, B1 and B2, respectively.
Accepted file to submit via give or Webcms3: *.txt.
Page 7 of 8
Programming Help, Add QQ: 749389476
Appendix A. Jasmin assembly (i.e., JVM) instructions for Question 5.
public final class JVM {
// Arithmetic instructions
IADD = “iadd”,
ISUB = “isub”,
IMUL = “imul”,
IDIV = “idiv”,
// Loads (for loading a local variable into operand stack)
ILOAD = “iload”,
ILOAD_0 = “iload_0”,
ILOAD_1 = “iload_1”,
ILOAD_2 = “iload_2”,
ILOAD_3 = “iload_3”,
// Stores (for storing the top operand in operand stack into a local variable)
ISTORE = “istore”,
ISTORE_0 = “istore_0”,
ISTORE_1 = “istore_1”,
ISTORE_2 = “istore_2”,
ISTORE_3 = “istore_3”,
// Loads (for loading a constant into operand stack)
ICONST_M1 = “iconst_m1”,
ICONST_0 = “iconst_0”,
ICONST_1 = “iconst_1”,
ICONST_2 = “iconst_2”,
ICONST_3 = “iconst_3”,
ICONST_4 = “iconst_4”,
ICONST_5 = “iconst_5”,
// Control transfer instructions
GOTO = “goto”,
IFEQ = “ifeq”,
IFNE = “ifne”,
IFLE = “ifle”,
IFLT = “iflt”,
IFGE = “ifge”,
IFGT = “ifgt”,
IF_ICMPEQ = “if_icmpeq”,
IF_ICMPNE = “if_icmpne”,
IF_ICMPLE = “if_icmple”,
IF_ICMPLT = “if_icmplt”,
IF_ICMPGE = “if_icmpge”,
IF_ICMPGT = “if_icmpgt”,
// Operand stack management instructions
DUP_X2 = “dup_x2”,
DUP = “dup”,
POP = “pop”,
==================== END OF PAPER ==================== Page 8 of 8