STUDENT ID: SIGNATURE:
The University of New South Wales Final Examination
June 2022 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) Use Thompson’s construction to convert this regular expression into an NFA.
********* ANSWER *********
(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.
[6 marks] [6 marks] [3 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.
011ǫ2 7ǫ8 ǫǫ
start 0 1 1,2,3,5,8
The minimal-state DFA is:
start 0 1 1−8
Question 2. Context-Free Grammars [20 marks] Consider the following context-free grammar for describing arithmetic expressions:
expr → term + expr | term
term → factor * term | term / factor | factor factor → INTLITERAL
where the the non-terminals are given in italics and the terminals in boldface (including ‘+’, ‘*’, ‘/’, and INTLITERAL (representing integer constants)).
(a) Write a leftmost derivation for the sentence 5 + 4 ∗ 3 / 2.
(b) Draw a parse tree for this sentence.
(c) Iftheoperators+,*and/representtheoperationsofintegeraddition,integermultipli-
cation and integer (truncated) division, respectively, what would be the value implied by your parse tree found in (b)?
(d) Is this grammar ambiguous? Justify your answer.
(e) Answer the following true or false questions about this grammar:
1. + is always right-associative.
2. * is always left-associative.
3. / is always right-associative.
4. + must always have higher precedence than * and /. 5. * may have higher precedence than /.
[4 marks] [4 marks]
6. / may have higher precedence than *.
[6 marks with 1 mark for each true/false question]
********* ANSWER ********* (a) Two different leftmost derivations:
⇒lm factor + expr
⇒lm 5+expr
⇒lm 5+term
⇒lm 5 + term / factor
⇒lm 5+factor∗term/term ⇒lm 5+4∗term/term ⇒lm 5+4∗factor/term ⇒lm 5+4∗3/factor
⇒lm 5+4∗3/2
⇒lm term + expr
⇒lm factor + expr
⇒lm 5+expr
⇒lm 5+term
⇒lm 5 + factor ∗ term ⇒lm 5+4∗term
⇒lm 5+4∗term/factor ⇒lm 5+4∗factor/factor ⇒lm 5+4∗3/factor ⇒lm 5+4∗3/2
(b) Two corresponding parse trees:
+ expr term
term factor 5
term + expr
term / factor
(c) The values for the two parse trees are: 11 and 9.
(d) YES due to the existence of two different leftmost derivations or parse trees. (e) 1. TRUE 2. FALSE 3. FALSE 4. FALSE 5. TRUE 6. TRUE
Programming Help, Add QQ: 749389476
Question 3. Recursive Descent Parsing Consider the following context-free grammar:
1. S → SS∗ 2. S → SS+ 3. S → INT 4. S → ID
[25 marks]
where S is the non-terminal, and ‘*’, ‘+’, INT (representing integer constants) and ID (rep- resenting identifiers) are the four terminals.
(a) Eliminate the left recursion in the grammar.
(b) Do left-factorisation of the grammar produced in (a).
[5 marks] [5 marks]
(c) Compute the FIRST and FOLLOW sets for every non-terminal in the grammar pro-
duced in (b).
(d) ConstructanLL(1)parsingtableforthegrammarproducedin(b),basedontheFIRST
and FOLLOW sets computed in (c).
(e) The sentence 4 x + ∗ is NOT syntactically legal (since it is NOT in the language defined by the grammar). Explain concisely how 4 x + ∗ can be detected by an LL(1) table-driven parser for the language, by showing the moves of the parser on this sentence based on the LL(1) parsing table produced in (d), as shown in Week 9’s Wednesday Lecture:
Stack Input Production
$ INT ID + *
********* ANSWER *********
S –> INT S’ S –> ID S’ S’ –> S*S’ S’ –> S+S’ S’ –> ǫ
1. S –> INT S’ 2.S –>IDS’ 3. S’ –> S A 4. S’ –> ǫ
5.A –>*S’ 6. A –> +S’
————————————————
S {INT, ID}
S’ {INT, ID, ǫ}
A {*, +} —————————————
INT ID * + $ —————————————– S12
S’ 3 3 4 4 4 A56 —————————————–
{+, *, $} {+, *, $}
Input INT ID INT ID ID+* ID+* ID+* + *
+ * + * * *
Production
S -> INT S’ pop & scanner S’–>SA S–>IDS’ pop & scanner S’ –> epsilon A–>+S’ pop & scanner S’ –> epsilon error
Left Derivation
Code Help, Add WeChat: cstutorcs
Question 4. Attribute Grammars [25 marks] Consider the following context-free grammar:
program → stmt-list → stmt-list → stmt → stmt →
func stmt-list
stmt stmt-list
for ID = INTLITERAL upto INTLITERAL begin stmt-list end assignment
where the non-terminals are given in italics and the terminals in boldface.
This grammar describes a simple language, which allows iterating through a sequence of statements, ultimately assignments. A for-loop is specified by the range of its loop variable (identified by ID), given by integer constants (identified by INTLITERAL), representing its lower and upper bounds. In other words, a for-loop, with its lower and upper bounds being L and U, respectively, will execute its loop body, i.e., stmt-list exactly U − L + 1 times. No production for assignments is given (as it is irrelevant here). Therefore, assignments, represented by assignment, are treated here as terminals.
A sample program is given below (with its loop executed exactly 20 times):
2 assignment
3 for i = 1 upto 20
5 assignment
6 assignment
7 assignment
9 assignment
(a) Write an attribute grammar that determines for each assignment how many times the assignment will be executed when running the program. You can assume that for each loop, its lower bound is no larger than its upper bound (so that you do not have to check this in your solution).
(b) Describe whether each attribute used is synthesised or inherited.
[20 marks] [5 marks]
This question can be a bit involved, as students need to figure out to use an inherited attribute to solve this problem.
********* ANSWER *********
program -> func stmt-list {
program.t = 1
prog.t = 1
stmt-list.t = 1
stmt-list1 -> stmt stmt-list2
stmt.t = stmt-list1.t
stmt-list2.t = stmt-list1.t
stmt-list -> stmt
stmt.t = stmt-list.t
stmt -> for ID = INTLITERAL1 upto INTLITERAL2 begin stmt-list end {
stmt-list.t = stmt.t x (INTLITERAL2.val – INTLITERAL1.val + 1)
stmt -> assignment
(b) Inherited
assignment.t = stmt.t
Question 5. Code Generation [15 marks] Suppose we introduce a do-while (loop) statement into our VC language:
do stmt while “(” expr “)”
where expr and stmt are defined exactly as in our VC grammar. Note that how these two
nonterminals are defined is irrelevant to this question.
The do-while statement has exactly the same semantics as that in C/C++/Java. It executes
stmt repeatedly until the value of expr is false.
Suppose we use the following AST class to represent a do-while statement in the AST rep-
resentation of a VC program:
package VC.ASTs;
import VC.Scanner.SourcePosition;
public class DoWhiletmt extends Stmt {
public Expr E;
public Stmt S;
public DoWhileStmt (Expr eAST, Stmt sAST, SourcePosition Position)
super (Position);
E.parent = S.parent = this;
public Object visit(Visitor v, Object o)
return v.visitDoWhileStmt(this, o);
Write Emitter.visitDoWhileStmt in Java for generating Jasmin code for the do-while state- ment by using the visitor design pattern as you did in Assignment 5 (for translating the for and while loops in VC).
You do not need to include code for computing the operand stack size required. However, you are required to include code to generate appropriate labels that can be used for translating any break or continue statement that may be contained in a do-while loop, similarly as you did in Assignment 5.
public Object Frame
visitDoWhileStmt(DoWhileStmt ast, Object o) { frame = (Frame)o;
firstLabel = frame . getNewLabel (); secondLabel = frame . getNewLabel ( ) ;
conStack . push ( f i r s t L a b e l ) ; brkStack . push ( secondLabel ) ;
********* ANSWER *********
String String
frame . frame .
emit(firstLabel + ”:”);
ast.S.visit(this, o);
ast.E.visit(this, o);
emit (JVM. IFEQ , secondLabel ) ; emit (JVM.GOTO, firstLabel ); emit(secondLabel + ”:”);
frame . conStack . pop ( ) ; frame . brkStack . pop ( ) ;
return null ;
程序代写 CS代考 加微信: cstutorcs