STUDENT ID: SIGNATURE:
The University of New South Wales Final Examination
June 2021 COMP3131/COMP9102 Programming Languages and Compilers
Time allowed: 2 hours
Total number of questions: 5
Answer all questions
The questions are not of equal value Marks for this paper total 100
This paper may not be retained by the candidate No examination materials
Answers must be written in ink.
Question 1. Regular Expressions and Finite Automata [15 marks] Consider the following regular expression:
(a|b)∗ a(a|ǫ)
(a) Use Thompson’s construction to convert this regular expression into an NFA.
(b) Use the subset construction to convert the NFA of (a) into a DFA. (c) Convert the DFA of (b) into a minimal-state DFA.
[7 marks] [7 marks] [4 marks]
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.
********* ANSWER *********
12 789 14 ǫǫ ǫǫ
ǫǫǫǫ ǫǫa
2−5,7−10,12−14
start 1−3,5,8
2,3,5−8 b b
Renaming the states of the DFA yields:
The minimal-state DFA is:
Question 2. Context-Free Grammars
Assume that arithmetic expressions are built up from the following terminals:
• Binary infix operators: @, #, +, − • Unary prefix operator: ∼
• Variables: X, Y, Z
• Brackets: [, ]
[15 marks]
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.
********* ANSWER *********
|
|
|
| [
–> X | Y | Z
程序代写 CS代考 加QQ: 749389476
Question 3. Recursive Descent 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.
FIRST(S ) FIRST(A) FIRST(B) FIRST(C ) FIRST(D)
FOLLOW(S ) FOLLOW(A) FOLLOW(B) FOLLOW(C ) FOLLOW(D)
{x,g} {a, ǫ} {x,g} {c, ǫ} {x,g}
{a, f, $} {a,f,g,$} {a,c,f,g,$}
********* ANSWER ********* ********* ANSWER *********
acdxfg$ S P1P1 AP2 P3P3 B P4P4
C P6 P5 P6 P6 P6
D P7P8 (d) Yes. Each entry contains at most one production.
Stack Input Production Left Derivation
$ gx
$ gx
$AB gx
$ACD gx
$ACgCg advance
#ACgC x
S->BA S=>BA
B->DC S=>DCA
D->gCg S=>gCgCA
blank ===> error
Question 4. Attribute Grammars [15 marks] Consider the following context-free grammar that generates regular expressions:
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.
(b) Is R.depth inherited or synthesized? Explain your answer.
[14 marks]
Note: In your answer, you can write R1, R2 and ∗ as R1, R2 and ∗, respectively.
Accepted file via give: *.txt.
Programming Help, Add QQ: 749389476
This is straightforward except that adding an inherited attribute can be tricky.
R1|R2 (R1 )∗
{R.depth = 0; } {R.depth = 0; } {R.depth = 0; }
{ if R1.depth > R2.depth R.depth = R1.depth
R.depth = R2.depth }
{ if R1.depth > R2.depth R.depth = R1.depth
R.depth = R2.depth }
R.depth = R1.depth + 1 R.depth = R1.depth
********* ANSWER *********
(b) Synthesised as it is propagated to a node from its children
Question 5. Code Generation [30 marks] Consider the following attribute grammar for generating “short-circuit” code, where
• The semantic rules associated with a production are evaluated sequentially in a top- down manner, and
• “#” stands for the string concatenation operator.
S → whileBdoS1
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. [5 marks]
Continued onto next page
Question 5 continued from Page 6
(b) Suppose that S.next = L666, getNewLabel() will return labels L1, L2, … when called, and getN ewT emp() will return temporary variables 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 define 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.
(a) and (b)
B.true = L666 B B.false=L2
********* ANSWER *********
B.true = L2
B.false = L666 S
B.true = L3 B.false=L2 B
B B.true=L666E + E
B.false = L2
ID > ID ID > ID ID
if a > b goto L3
if x > y goto L666
B → B1 ∥ B2
B1.true := B.true;
B1.false := getNewLabel();
B2.true := B.true;
B2.false := B.false;
B.code := B1.code ⋊⋉ emit(B1.false ′ :′) ⋊⋉ B2.code
S → doS1 whileB
S.begin := getNewLabel();
B.true := S.begin();
B.false := S.next;
S1.next := S.begin;
emit(S.begin ′ :′) ⋊⋉ S1.code ⋊⋉ B.code
程序代写 CS代考 加微信: cstutorcs