# Sample Problems – Final Examination Solutions Selected Solutions: Problem 1

Yüklə 59.02 Kb.
 tarix 28.02.2016 ölçüsü 59.02 Kb.

Sample Problems – Final Examination - Solutions

Selected Solutions:
Problem 1: As the initial step in the design of an SLR parser, construct the DFA that corresponds to the LR(0) item sets for the grammar. Make sure that you clearly identify the items in each set.

S  A B y

A  S y | x

B  y S

## I0 = closure([S’.S]) = { S’.S, S .A B, A .S y, A .x}

Now we need to compute GOTO on I0 on symbols S, A, and x.

GOTO(I0,S) = closure([S’S. , A S.y]} = { S’S. , A S.y}= I1

GOTO(I0,A) = closure([S  A.B]) = { S  A.B, B  .y S} = I2

GOTO(I0,x) = closure([A x.]) = { A x.} = I3
Now we’re done with I0, so we move on to I1. We need to compute GOTO on I1 for symbol y, the only symbol to the right of the “.” in I1.
GOTO(I1,y) = closure([A S y.]) = { A S y.} = I4
This finishes I1, and we move on to I2. We need GOTO for symbols B and y.
GOTO(I2,B)=closure([S  A B. ])={ S  A B. } = I5

GOTO(I2,y)=closure([B  y. S])={B y. S, S.A B, A.Sy, A.x}=I6

Now we’re done with I2. Neither I3 nor I4 has anything to offer, since neither has any symbols to the right of the dot. So we move on to I5, and compute GOTO for symbol y.
Next we compute GOTO on I6 for S, A, and x.
GOTO(I6,S)=closure([B y S., A S.y]) = { B y S., A S.y} = I7

GOTO(I6,A)=closure([S  A.B ])={ S  A.B , B  .y S} = I2

(notice this gives us an item set we’ve already seen before)
GOTO(I6,x)=closure([A x.])={ A x.} = I3
I7 has nothing to contribute, so we move on to I8 on symbol y.
GOTO(I8,y) = closure([A S y.])={ A S y.} = I4

From these we can depict the DFA, as follows:

I0

A

S

I2

x

I1

B

x

y

y

y

A

S

I5

I3

I4

I6

I7

Is the grammar SLR? Why or why not? Reason out your answer without constructing the entire parse table!

The grammar is not SLR, since there is a shift / reduce conflict from state 8 on symbol y. This comes from the two items AS.y and ByS. Together with the fact that
FOLLOW(S) = {\$,y} FOLLOW(A) = {y} FOLLOW(B) = {\$,y}
SLR (0) Item Sets:

I0: S’® .S

S ® .AB

A ® .Sy

A ® .x
I1: S’® S.

A ® S.y
I2: S ® A.B

B ® .yS
I3: A ® x.
I4: A ® Sy.
I5: A ® AB.
I6: B ® y.S

S ® .AB

A ® .Sy

A ® .x
I7: B ® yS.

A ® S.y
LR(1) ITEM SETS
I0: S’® .S, \$

S ® .AB, \$/y

A ® .Sy, y

A ® .x, y
I1: S’® S., \$

A ® S.y, y
I2: S ® A.B, \$/y

B ® .yS, \$/y
I3: A ® x., y
I4: A ® Sy., y
I5: A ® AB., \$/y
I6: B ® y.S, \$/y

S ® .AB, \$/y

A ® .Sy, y

A ® .x, y
I7: B ® yS., \$/y

A ® S.y, y

Problem 5: As the initial step in the design of an LR(1) parser, construct the DFA that corresponds to the LR(1) item sets for the grammar. Make sure that you clearly identify the items in each set. Hint: Your final DFA should have a total of 14 item sets.
S' ---> S

S ---> d D d

S ---> e D e

S ---> d E e

S ---> e E d

D ---> f

E ---> f

## I0 = closure([S’.S,\$]) = {[S’.S,\$],[S.dDd,\$],[S.eDe,\$],[S.dEe,\$],[S.eEd,\$]}

Now we need to compute GOTO on I0 on symbols S, d, and e.

GOTO(I0,S) = closure([S’S.,\$]} = {[S’S.,\$]}= I1
GOTO(I0,d) = closure([Sd.Dd,\$],[Sd.Ee,\$]). First work on [Sd.Dd,\$] and note that FIRST(d\$)={d}. With this in mind we add [D.f,d] to the closure. Similarly, using [Sd.Ee,\$] and noting that FIRST(e\$)={e}, we include [E.f,e]. Thus overall we have I2={[Sd.Dd,\$],[Sd.Ee,\$],[D.f,d],[E.f,e]}
GOTO(I0,e) = closure([Se.De,\$],[Se.Ed,\$]). Proceeding as above, with the fact that FIRST(e\$)={e}, we add [D.f,e], and since FIRST(d\$)={d}, we add [E.f,d]. Finally, since each item is itself in the closure, I3={[Se.De,\$],[Se.Ed,\$],[D.f,e],[E.f,d]}
Now we’re done with I0, so we move on to I1. But I1 has nothing to offer (no symbols to the right of the “.” in I1). Thus we move on to I2 and compute GOTO for symbols D, E, f.
GOTO(I2,D) = closure(Sd.Dd,\$) = {[Sd.Dd,\$]= I4
GOTO(I2,E) = closure(SdE.e,\$) = {[SdE.e,\$]= I5
GOTO(I2,f) = closure([Df.,d],[Ef.,e])={[Df.,d],[Ef.,e]}=I6
This finishes the GOTO on I2 and we move on to GOTO on I3 for D,E,f.
GOTO(I3,D) = closure([SeD.e,\$]) = {[SeD.e,\$]} = I7
GOTO(I3,E) = closure([SeE.d,\$]) = {[SeE.d,\$]} = I8
GOTO(I3,f) = closure([Df.,e],[Ef.,d])={[Df.,e],[Ef.,d]}=I9
This finishes GOTO on I3. Using I4 we only have one, for symbol d.

GOTO(I4,d) = closure([SdDd.,\$]) = {[SdDd.,\$]} = I10

Similarly, on I5 we have
GOTO(I5,d) = closure([SdEe.,\$]) = {[SdEe.,\$]} = I11
For I6 there is nothing to do. For I7 we calculate GOTO(I7,e).
GOTO(I7,e) = closure([SeDe.,\$]) = {[SeDe.,\$]} = I12
A similar calculation for I8 yields
GOTO(I8,e) = closure([SeEd.,\$]) = {[SeEd.,\$]} = I13

This finishes all the LR(1)item sets since no other Ij contributes. The DFA looks like this:

Is the grammar LR(1)? Why or why not? Reason out your answer without constructing the entire parse table!

The grammar is LR(1), since there are no shift / reduce conflicts or reduce / reduce

conflicts. I6 and I9 would be the candidates for R/R conflicts, but they act on different input symbols.

SLR (0) Item Sets: LR(1) Item Sets

`

I0: S’® .S

S ® .d D d

S ® .e D e

S ® .d E e

S ® .e E d
I1: S’® S.
I2: S ® d.D d

S ® d.E e

D ® .f

E ® .f
I3: S ® e.D e

S ® e.E d

D ® .f

E ® .f
I4: S ® d D.d
I5: S ® d E.e
I6: D ® f.

E ® f.
I7: S ® e D.e
I8: S ® e E.d
I9: S ® d D d.
I10: S ® d E e.
I11: S ® e D e.
I12: S ® e E d.
I0: S’® .S, \$

S ® .d D d, \$

S ® .e D e, \$

S ® .d E e, \$

S ® .e E d, \$
I1: S’® S. , \$
I2: S ® d.D d , \$

S ® d.E e, \$

D ® .f, d

E ® .f, e
I3: S ® e.D e , \$

S ® e.E d, \$

D ® .f, e

E ® .f, d
I4: S ® d D.d, \$
I5: S ® d E.e, \$
I6: D ® f., d

E ® f., e
I7: S ® e D.e, \$
I8: S ® e E.d, \$
I9: D ® f., e

E ® f., d
I10: S ® d D d. , \$
I11: S ® d E e. , \$
I12: S ® e D e. , \$
I13: S ® e E d. , \$

Is the Grammar LR(1)? Why or Why Not?

Which LR(1) sets are Merged for LALR(1)?
Is the Grammar LALR(1)?

Why or Why Not?

Problems 8a and 8b: A "Combined" Solution for Attribute Grammar Problems 2a and 2b
Attributes: trans - synthesized, used for both translations

itrans - synthesized, used for infix translation

ptrans - synthesized, used for postfix translation
E --> ( = id L)
E.itrans = concat(id, "=", L.itrans);

E.ptrans = concat(L.ptrans, id, "=");

L --> ( A L1.1 L1.2)
L.itrans = concat("(", L1.1.itrans, A.trans, L1.2.itrans, ")");

L.ptrans = concat(L1.1.ptrans, L1.2.ptrans, A.trans);

L --> ( M L1.1 L1.2)
L.itrans = concat("(", L1.1.itrans, M.trans, L1.2.itrans, ")");

L.ptrans = concat(L1.2.ptrans, L1.1.ptrans, M.trans);

L1 --> L

L1.itrans = L.itrans;

L1.ptrans = L.ptrans;
L1 --> int

L1.itrans = str(int.lexval);

L1.ptrans = str(int.lexval);
L1 --> id

L1.itrans = id.lexval;

L1.ptrans = id.lexval;
A --> + M --> *

A.trans = "+" M.trans = "*"

A --> - M --> /

A.trans = "-" M.trans = "/"

Problem 9:
B2, B4, B6, B7, B8, and B10 are unchanged. Other basic blocks as below:
+------------+

B1 | i := n; |

| t8:= i*4 ; |

+------------+
+------------+

B3 | jmax := 1; |

| j := 2; |

| t1 := j-2 |

| t2 :=t1*4; |

+------------+
+------------+

B5 | t2 :=t2+4; |

| t3:=x[t2]; |

| Rest of B5 |

| from t4 |

| down is |

| Unchanged |

+------------+
+--------------+

B9 | t8 :=t8-4; |

| temp:=x[t8]; |

| Rest of B9 |

| from t10 |

| down is |

| Unchanged |

+--------------+

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət
The text passage contains multiple problems and solutions related to constructing DFAs for SLR and LR(1) parsers, as well as questions about the properties of the grammars. It also includes a problem on attribute grammars and a problem on basic blocks in compiler optimization.
multiple_questions_with_answers
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Sample Problems – Final Examination Solutions Selected Solutions: Problem 1

Yüklə 59.02 Kb.
 tarix 28.02.2016 ölçüsü 59.02 Kb.

Sample Problems – Final Examination - Solutions

Selected Solutions:
Problem 1: As the initial step in the design of an SLR parser, construct the DFA that corresponds to the LR(0) item sets for the grammar. Make sure that you clearly identify the items in each set.

S  A B y

A  S y | x

B  y S

## I0 = closure([S’.S]) = { S’.S, S .A B, A .S y, A .x}

Now we need to compute GOTO on I0 on symbols S, A, and x.

GOTO(I0,S) = closure([S’S. , A S.y]} = { S’S. , A S.y}= I1

GOTO(I0,A) = closure([S  A.B]) = { S  A.B, B  .y S} = I2

GOTO(I0,x) = closure([A x.]) = { A x.} = I3
Now we’re done with I0, so we move on to I1. We need to compute GOTO on I1 for symbol y, the only symbol to the right of the “.” in I1.
GOTO(I1,y) = closure([A S y.]) = { A S y.} = I4
This finishes I1, and we move on to I2. We need GOTO for symbols B and y.
GOTO(I2,B)=closure([S  A B. ])={ S  A B. } = I5

GOTO(I2,y)=closure([B  y. S])={B y. S, S.A B, A.Sy, A.x}=I6

Now we’re done with I2. Neither I3 nor I4 has anything to offer, since neither has any symbols to the right of the dot. So we move on to I5, and compute GOTO for symbol y.
Next we compute GOTO on I6 for S, A, and x.
GOTO(I6,S)=closure([B y S., A S.y]) = { B y S., A S.y} = I7

GOTO(I6,A)=closure([S  A.B ])={ S  A.B , B  .y S} = I2

(notice this gives us an item set we’ve already seen before)
GOTO(I6,x)=closure([A x.])={ A x.} = I3
I7 has nothing to contribute, so we move on to I8 on symbol y.
GOTO(I8,y) = closure([A S y.])={ A S y.} = I4

From these we can depict the DFA, as follows:

I0

A

S

I2

x

I1

B

x

y

y

y

A

S

I5

I3

I4

I6

I7

Is the grammar SLR? Why or why not? Reason out your answer without constructing the entire parse table!

The grammar is not SLR, since there is a shift / reduce conflict from state 8 on symbol y. This comes from the two items AS.y and ByS. Together with the fact that
FOLLOW(S) = {\$,y} FOLLOW(A) = {y} FOLLOW(B) = {\$,y}
SLR (0) Item Sets:

I0: S’® .S

S ® .AB

A ® .Sy

A ® .x
I1: S’® S.

A ® S.y
I2: S ® A.B

B ® .yS
I3: A ® x.
I4: A ® Sy.
I5: A ® AB.
I6: B ® y.S

S ® .AB

A ® .Sy

A ® .x
I7: B ® yS.

A ® S.y
LR(1) ITEM SETS
I0: S’® .S, \$

S ® .AB, \$/y

A ® .Sy, y

A ® .x, y
I1: S’® S., \$

A ® S.y, y
I2: S ® A.B, \$/y

B ® .yS, \$/y
I3: A ® x., y
I4: A ® Sy., y
I5: A ® AB., \$/y
I6: B ® y.S, \$/y

S ® .AB, \$/y

A ® .Sy, y

A ® .x, y
I7: B ® yS., \$/y

A ® S.y, y

Problem 5: As the initial step in the design of an LR(1) parser, construct the DFA that corresponds to the LR(1) item sets for the grammar. Make sure that you clearly identify the items in each set. Hint: Your final DFA should have a total of 14 item sets.
S' ---> S

S ---> d D d

S ---> e D e

S ---> d E e

S ---> e E d

D ---> f

E ---> f

## I0 = closure([S’.S,\$]) = {[S’.S,\$],[S.dDd,\$],[S.eDe,\$],[S.dEe,\$],[S.eEd,\$]}

Now we need to compute GOTO on I0 on symbols S, d, and e.

GOTO(I0,S) = closure([S’S.,\$]} = {[S’S.,\$]}= I1
GOTO(I0,d) = closure([Sd.Dd,\$],[Sd.Ee,\$]). First work on [Sd.Dd,\$] and note that FIRST(d\$)={d}. With this in mind we add [D.f,d] to the closure. Similarly, using [Sd.Ee,\$] and noting that FIRST(e\$)={e}, we include [E.f,e]. Thus overall we have I2={[Sd.Dd,\$],[Sd.Ee,\$],[D.f,d],[E.f,e]}
GOTO(I0,e) = closure([Se.De,\$],[Se.Ed,\$]). Proceeding as above, with the fact that FIRST(e\$)={e}, we add [D.f,e], and since FIRST(d\$)={d}, we add [E.f,d]. Finally, since each item is itself in the closure, I3={[Se.De,\$],[Se.Ed,\$],[D.f,e],[E.f,d]}
Now we’re done with I0, so we move on to I1. But I1 has nothing to offer (no symbols to the right of the “.” in I1). Thus we move on to I2 and compute GOTO for symbols D, E, f.
GOTO(I2,D) = closure(Sd.Dd,\$) = {[Sd.Dd,\$]= I4
GOTO(I2,E) = closure(SdE.e,\$) = {[SdE.e,\$]= I5
GOTO(I2,f) = closure([Df.,d],[Ef.,e])={[Df.,d],[Ef.,e]}=I6
This finishes the GOTO on I2 and we move on to GOTO on I3 for D,E,f.
GOTO(I3,D) = closure([SeD.e,\$]) = {[SeD.e,\$]} = I7
GOTO(I3,E) = closure([SeE.d,\$]) = {[SeE.d,\$]} = I8
GOTO(I3,f) = closure([Df.,e],[Ef.,d])={[Df.,e],[Ef.,d]}=I9
This finishes GOTO on I3. Using I4 we only have one, for symbol d.

GOTO(I4,d) = closure([SdDd.,\$]) = {[SdDd.,\$]} = I10

Similarly, on I5 we have
GOTO(I5,d) = closure([SdEe.,\$]) = {[SdEe.,\$]} = I11
For I6 there is nothing to do. For I7 we calculate GOTO(I7,e).
GOTO(I7,e) = closure([SeDe.,\$]) = {[SeDe.,\$]} = I12
A similar calculation for I8 yields
GOTO(I8,e) = closure([SeEd.,\$]) = {[SeEd.,\$]} = I13

This finishes all the LR(1)item sets since no other Ij contributes. The DFA looks like this:

Is the grammar LR(1)? Why or why not? Reason out your answer without constructing the entire parse table!

The grammar is LR(1), since there are no shift / reduce conflicts or reduce / reduce

conflicts. I6 and I9 would be the candidates for R/R conflicts, but they act on different input symbols.

SLR (0) Item Sets: LR(1) Item Sets

`

I0: S’® .S

S ® .d D d

S ® .e D e

S ® .d E e

S ® .e E d
I1: S’® S.
I2: S ® d.D d

S ® d.E e

D ® .f

E ® .f
I3: S ® e.D e

S ® e.E d

D ® .f

E ® .f
I4: S ® d D.d
I5: S ® d E.e
I6: D ® f.

E ® f.
I7: S ® e D.e
I8: S ® e E.d
I9: S ® d D d.
I10: S ® d E e.
I11: S ® e D e.
I12: S ® e E d.
I0: S’® .S, \$

S ® .d D d, \$

S ® .e D e, \$

S ® .d E e, \$

S ® .e E d, \$
I1: S’® S. , \$
I2: S ® d.D d , \$

S ® d.E e, \$

D ® .f, d

E ® .f, e
I3: S ® e.D e , \$

S ® e.E d, \$

D ® .f, e

E ® .f, d
I4: S ® d D.d, \$
I5: S ® d E.e, \$
I6: D ® f., d

E ® f., e
I7: S ® e D.e, \$
I8: S ® e E.d, \$
I9: D ® f., e

E ® f., d
I10: S ® d D d. , \$
I11: S ® d E e. , \$
I12: S ® e D e. , \$
I13: S ® e E d. , \$

Is the Grammar LR(1)? Why or Why Not?

Which LR(1) sets are Merged for LALR(1)?
Is the Grammar LALR(1)?

Why or Why Not?

Problems 8a and 8b: A "Combined" Solution for Attribute Grammar Problems 2a and 2b
Attributes: trans - synthesized, used for both translations

itrans - synthesized, used for infix translation

ptrans - synthesized, used for postfix translation
E --> ( = id L)
E.itrans = concat(id, "=", L.itrans);

E.ptrans = concat(L.ptrans, id, "=");

L --> ( A L1.1 L1.2)
L.itrans = concat("(", L1.1.itrans, A.trans, L1.2.itrans, ")");

L.ptrans = concat(L1.1.ptrans, L1.2.ptrans, A.trans);

L --> ( M L1.1 L1.2)
L.itrans = concat("(", L1.1.itrans, M.trans, L1.2.itrans, ")");

L.ptrans = concat(L1.2.ptrans, L1.1.ptrans, M.trans);

L1 --> L

L1.itrans = L.itrans;

L1.ptrans = L.ptrans;
L1 --> int

L1.itrans = str(int.lexval);

L1.ptrans = str(int.lexval);
L1 --> id

L1.itrans = id.lexval;

L1.ptrans = id.lexval;
A --> + M --> *

A.trans = "+" M.trans = "*"

A --> - M --> /

A.trans = "-" M.trans = "/"

Problem 9:
B2, B4, B6, B7, B8, and B10 are unchanged. Other basic blocks as below:
+------------+

B1 | i := n; |

| t8:= i*4 ; |

+------------+
+------------+

B3 | jmax := 1; |

| j := 2; |

| t1 := j-2 |

| t2 :=t1*4; |

+------------+
+------------+

B5 | t2 :=t2+4; |

| t3:=x[t2]; |

| Rest of B5 |

| from t4 |

| down is |

| Unchanged |

+------------+
+--------------+

B9 | t8 :=t8-4; |

| temp:=x[t8]; |

| Rest of B9 |

| from t10 |

| down is |

| Unchanged |

+--------------+

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət
user
The text passage contains multiple problems and solutions related to constructing DFAs for SLR and LR(1) parsers, as well as questions about the properties of the grammars. It also includes a problem on attribute grammars and a problem on basic blocks in compiler optimization.

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS