Klausur 2016, Fragen PDF

Preview

Summary

1 Exam 2016...

Description

2

Compiler Construction SS 2016 Chair for Software Modeling and Verification Rheinisch-Westf¨alische Technische Hochschule Aachen

apl. Prof. Dr. Thomas Noll C. Matheja, M. Volk

Compiler Construction SS 2016 — 1st Exam — First Name: Second Name: Matriculation Number: Degree Programme (please mark): ◦ ◦ ◦ ◦ ◦

CS Bachelor CS Master CS Lehramt SSE Master Other:

General Information: • Mark every sheet with your matriculation number. • Check that your copy of the exam consists of 13 sheets (25 pages). • Duration of exam: 120 minutes. • This is a closed exam, i.e. no helping materials (e.g. books, notes, slides) are permitted. • Give your solution on the respective sheet. Also use the backside if necessary. If you need more paper, ask the assistants. • Write with blue or black ink; do not use a pencil or red ink. • Make sure all electronic devices are switched off and are nowhere near you. • Any attempt at deception leads to failure for this exam, even if detected only later.

Task Task Task Task Task Task Σ

1 2 3 4 5 6

Σ Points Points obtained 20 18 17 25 20 20 120

Matriculation Number:

(10 · 2 Points)

Task 1 (Questions)

For each question mark the correct answers below. Note that more than one answer might be correct. For each question points are awarded if and only if exactly the correct answers are marked. (a) The complexity of the simple matching problem using the DFA method during the construction phase is in  space linear in the length of the regular expression  space exponential in the length of the regular expression  space linear in the size of the input word (b) Given a word w ∈ Ω+ and regular expressions α1 , . . . , αn over Ω,  there exists at most one rightmost analysis of w  there exists at least one LM-decomposition of w  there exists an LM-decomposition of w if there exists an FLM analysis of w (c) A context-free grammar G is unambiguous  iff its language L(G) is not inherently ambiguous  iff G is an LR(k) grammar for some k ≥ 0  iff there is at most one rightmost and one leftmost derivation for every word w ∈ L(G) (d) Mark the correct relationships.  Every language generated by an unambiguous CFG can be accepted by a deterministic pushdown automaton  Every SLR(1) grammar is also an LALR(1) grammar  Every language generated by an LL(0) grammar is finite (e) Consider the item set I given by [A → a · b], [A → bA·], [A → b · a].  I contains a reduce/reduce conflict  I contains a shift/reduce conflict  I contains no conflicts (f ) Consider the following grammar: A → B∗ and B → ∗ with attributes Syn(A) = {a}, Inh(A) = ∅, Syn(B) = {b}, Inh(B) = {c}. Mark all valid attribute grammars. 

A → B∗ : a.0 = 4, c.1 = 3 B→∗ : b.0 = 1



A → B∗ : a.0 = c.1 ∗ b.1, c.1 = b.1 B→∗ : b.0 = 34



A → B∗ : a.0 = b.1, c.1 = b.1 B→∗ : b.0 = c.0 2

Matriculation Number:

(g) Let G be an attribute grammar and t be a syntax tree of G with set of nodes K . Mark the correct statements below.  For each α.k ∈ V art the attribute equation system Et contains at least one equation with left-hand side α.k  For each α.k ∈ V art the attribute equation system Et contains at most one equation with left-hand side α.k  There might exist synthesized attribute variables α at the root of t such that the attribute equation system Et contains two equations with left-hand side α.k.  There might exist inherited attribute variables α at the root of t such that the attribute equation system Et contains two equations with left-hand side α.k . (h) Consider the values for sl, dl and ra in the same frame of a process stack. Then  sl = dl holds always.  sl = dl might hold.  sl > dl holds always.  sl > dl might hold.  sl < dl holds always.  sl < dl might hold.  dl = ra holds always.  dl > ra holds always.  dl < ra holds always. (i) Which statements concerning the compiler implementation While2JasminCompiler are true?  The SLR1Parser only needs the computation of the f ollow sets but not the computation of the f irst sets.  When changing the grammar, the LR0Parser does not need to be changed.  The BacktrackingDFA starts by computing the product automaton of all DFAs. (j) Consider the following expression: e := ((a + c)/3) ∗ (4 − (3 ∗ x)) What is the number of required registers r(e)? 1

2

3

4

5

3

 more than 5

Matriculation Number:

Task 2 (Lexical Analysis)

(6+6+1+5 Points)

Consider the following regular expressions over Ω = {a, b}:

α1 = b α 2 = b+ a α3 = a with corresponding tokens T1 , T2 , and T3 . (a) Construct the product DFA corresponding to the regular expressions α1 , α2 , α3 and the tokens T1 , T2 , T3 . Moreover, provide the partitioning of final states and the set of productive states. (b) Provide a run of the backtracking DFA on the word w = abbab with respect to α1 , α2 , and α3 . (c) Assume we want to bound the lookahead of the backtracking automaton. For the resulting d–bounded backtracking automaton the length of the lookahead is not allowed to exceed a constant d; otherwise it backtracks. Complete the following formal definition of the transition function of the d–bounded backtracking automaton:  ′  if  (Ti , q w, W ) ′ (T, vqaw, W ) ⊢ (T, vaq w, W ) if   (N, q vaw, W T ) if 0

(d) What is the worst-case runtime of an d–bounded backtracking automaton? Justify your answer.

4

Matriculation Number:

Task 3 (Top-Down Parsing)

(6+4+7 Points)

(a) Transform the following context-free grammar G into an equivalent LL(1) grammar: S → a | Saab | Saa Prove that your obtained grammar is in LL(1). (b) Let G′ be the context-free grammar given by S → a | b | baSab | abSba. Prove or disprove: G′ ∈ LL(3).

5

Matriculation Number:

(c) Let G′′ be the context-free grammar given by S → [p]S | a = b

(1, 2)

where S is the single nonterminal symbol and [, ], a, b, p, = are terminal symbols. Complete the following skeleton of a recursive descent parser for this grammar. Hint: As in the lecture, you may assume the existence of a procedure next() that provides the next token (or reports an error if no next token exists). Moreover, you may assume procedures print(int) and print(error) to print your analysis and report errors, respectively. proc main(): token := next(); S()

proc S(): // implement parser here

6

Matriculation Number:

Task 4 (Bottom-up Parsing)

(12+1+6+6 Points)

Consider the following grammar G: S′ S A B

→ → → →

S Ac | AB aS | a bS

(0) (1, 2) (3, 4) (5)

(a) Compute the LR(0) sets of G. (Hint: apart from the sink state there should be 9 LR(0) sets.) (b) Check the LR(0) sets for conflicts and give the type of conflict for each of them. (c) Give the SLR(1) parsing table of G. (d) Parse the input aacbac.

7

Matriculation Number:

8

Matriculation Number:

Task 5 (Semantic Analysis)

(7+13 Points)

(a) Consider the following context-free grammar G: S → Ac | AB | ABA | BA A → aS | c B → bS | a Extend G to an attribute grammar that contains a synthesized Boolean attribute flag such that flag.0 is true at the root of a derivation tree of G if and only if the corresponding word contains an equal number of a’s and b’s. Apart from the attribute flag you may use at most one additional attribute. (b) Consider the following attribute grammar G′ : S S A A B B

→ → → → → →

AB BA aS c bS a

s.0 = s.1, i.1 = s.2, i.2 = s.1 s.0 = s.1 + s.2, i.1 = s.1, i.2 = s.2 s.0 = i.0, i.2 = i.0 + 1 s.0 = s.1, i.1 = 0 s.0 = 1, i.2 = i.0 s.0 = i.0

Apply the circularity test to G′ . To this end: (a) Give the dependency graph for each production rule of G′ . (b) Calculate the set IS(X) for all X ∈ N . (c) Is G circular? Justify your answer.

9

Matriculation Number:

Task 6 (Code Generation)

(5+10+5 Points)

(a) Consider the following program: i n / out x , y ; c o n s t p i := 3 ; p roc P ; va r z ; z := 1 0 ; [ . . . 1 0 :R ( ) . . . ] p roc R ; va r t ; p roc Q; va r a , b ; a := 2 ; [ . . . 2 8 :R ( ) . . . ] [ . . . 2 3 :Q( ) . . . ] [ ...20:P ( ) . . . ] Here [...20: P ()...] states that in the corresponding intermediate code procedure P () is called at program address 20. Construct the procedure stack after the call of R() in line 28. If not further specified, variables have value 0. Hint: The Main method is called from program address 2.

10

Matriculation Number:

(b) Translate the following EPL program into abstract machine (AM) code: i n / out x ; p roc P ; va r y ; w h i l e x > 1 do x := x − 1 y := x P( ) ; x := 0 Hint: You can find the translation rules as a reference on the last pages of the exam.

11

Matriculation Number:

(c) Consider the following intermediate code: 11: 12: 13:

.. . CALL(20, 1, 1); LOAD(2, 1); CALL(20, 1, 1); .. .

20: 21: 22:

LIT(2); STORE(2,1); RET;

Give the next four states of the AM starting in: (ca, d, p) := (21, 2, 6 : 2 : 12 : 3 : 2 : 23 : 4 : 3 : 2 : 1 : 0 : 0 : 0 : 1)

12

Matriculation Number:

Reference trans(in/out I1 , . . . ,In ;K .) := 1 : CALL(a,0,size(K )); 2 : JMP(0); kt(K, stI /O , a, 1) kt(D C, st , a, l) := dt(D, update(D, st, l), l) ct(C, update(D, st, l), a, l) a′ : RET; dt(DC DV DP , st, l) := dt(DP , st, l) dt(ε, st, l) := ε dt(proc I1 ;K1 ; . . . ;proc In ;Kn ;, st, l) := kt(K1 , st, a1 , l + 1) .. . kt(Kn , st, an , l + 1) where st(Ij ) = (proc, aj , . . . , . . .) for every j ∈ [n] ct(I := A, st, a, l) := at(A, st, a, l) a′ : STORE(l − lev ,off ); if st(I) = (var, lev , off ) ct(I (), st, a, l) := a : CALL(ca ,l − lev ,loc ); if st(I) = (proc, ca , lev , loc ) ct(C1 ;C2 , st, a, l) := ct(C1 , st, a, l) ct(C2 , st, a′ , l) ct(if B then C1 else C2 , st, a, l) := bt(B, st, a, l) a′ : JFALSE(a′′); ct(C1 , st, a′ + 1, l) a′′ − 1 : JMP(a′′′); ct(C2 , st, a′′, l) a′′′ : ct(while B do C, st, a, l) := bt(B, st, a, l) a′ : JFALSE(a′′ + 1); ct(C, st, a′ + 1, l) a′′ : JMP(a);

13

Matriculation Number:

bt(A1 < A2 , st, a, l) := at(A1 , st, a, l) at(A2 , st, a′ , l) a′′ : LT; bt(not B, st, a, l) := bt(B, st, a, l) a′ : NOT; bt(B1 and B2 , st, a, l) := bt(B1 , st, a, l) bt(B2 , st, a′ , l) a′′ : AND;

Of course, you may also use OR, GT, LEQ, GEQ, EQ and NEQ which are defined analogously. at(z, st, a, l) := a : LIT(z ); ( a : LIT(z); if st(I) = (const, z ) at(I, st, a, l) := a : LOAD(l − lev ,off ); if st(I) = (var, lev , off ) at(A1 + A2 , st, a, l) := at(A1 , st, a, l) at(A2 , st, a′ , l) a′′ : ADD; Of course, you may also use SUB, MUL and DIV which are defined analogously.

14...