Coursera

Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.

In accordance with the Coursera Honor Code, I (Anonymous Student) certify that the answers here are my own work.

Question 1

Consider the following grammar:

S

→ $\rightarrow$ A ( S ) B

∣ $\mid$

ϵ $\epsilon$
A

→ $\rightarrow$ S

∣ $\mid$ S B

∣ $\mid$ x

∣ $\mid$

ϵ $\epsilon$
B

→ $\rightarrow$ S B

∣ $\mid$ y

What are the first and follow sets of S?

First: {x, y, '(',

ϵ $\epsilon$ }, Follow: {$, '(', y}

First: {x, y, '(',

ϵ $\epsilon$ }, Follow: {$, y, x, '(', ')'}

First: {x,

ϵ $\epsilon$ }, Follow: {$, y, x, '(', ')'}

First: {x, y, '(',

ϵ $\epsilon$ }, Follow: {y, x, '(', ')'}

First: {x, y, '('}, Follow: {$, y, x, '(', ')'}

First: {x, '('}, Follow: {$, y, x}

Question 2

What are the items in the initial state of the SLR(1) parsing automaton for the grammar in last question(Question 1)?
Do not add an extra symbol to the grammar; just use the grammar as is.
[Choose all that apply]

Question 3

Which of the following are true of the initial state of the SLR(1) parsing automaton from the last question (Question 2)?
[Choose all that apply]

The state has a reduce-reduce conflict on end-of-input.

This state has a shift-reduce conflict on input '('.

This state has a shift-reduce conflict on end-of-input.

This state has a shift-reduce conflict on input x.

This state has a shift-reduce conflict on transition S.

The state has a reduce-reduce conflict on input x.

The state has a reduce-reduce conflict on transition S.

The state has a reduce-reduce conflict on input '('.

Question 4

Consider grammars G1, G2, and G3.

G1: E

→ $\rightarrow$ idT

∣ $\mid$ (E)T
T

→ $\rightarrow$ + id

∣ $\mid$ * id
G2: S

→ $\rightarrow$ bSb

∣ $\mid$ A

∣ $\mid$

ϵ $\epsilon$
A

→ $\rightarrow$ aA

∣ $\mid$

ϵ $\epsilon$
G3: R

→ $\rightarrow$ aR'

∣ $\mid$ (R)R'
R'

→ $\rightarrow$

ϵ $\epsilon$

∣ $\mid$ XR'
X

→ $\rightarrow$ . R

∣ $\mid$ + R

∣ $\mid$ *

The number of symbols in the first sets for the *non-terminals* are:

G1: E = 4; T = 2
G2: S = 2; A = 2
G3: R = 2; R' = 4; X = 3

G1: E = 2; T = 2
G2: S = 3; A = 1
G3: R = 2; R' = 3; X = 3

G1: E = 4; T = 2
G2: S = 2; A = 2
G3: R = 2; R' = 3; X = 3

G1: E = 2; T = 2
G2: S = 3; A = 2
G3: R = 2; R' = 4; X = 3

G1: E = 2; T = 2
G2: S = 3; A = 2
G3: R = 2; R' = 3; X = 3

Question 5

Given the following grammar,

stmt

→ $\rightarrow$ var | if_stmt
if_stmt

→ $\rightarrow$ if var then stmt | if var then stmt else stmt
var

→ $\rightarrow$ a | b | win | loss

Which of the following series is a valid bottom-up parsing for the string:
if a then if b then win else loss
[Choose all that apply]

if a then if b then win else loss
if var then if b then win else loss
if var then if var then win else loss
if var then if var then var else loss
if var then if var then stmt else loss
if var then if_stmt else loss
if var then stmt else loss
if var then stmt else var
if var then stmt else stmt
if_stmt
stmt

if a then if b then win else loss
if var then if b then win else loss
if var then if var then win else loss
if var then if var then var else loss
if var then if var then stmt else loss
if var then if var then stmt else var
if var then if var then stmt else stmt
if var then if_stmt
if var then stmt
if_stmt
stmt

if a then if b then win else loss
if var then if b then win else loss
if var then if b then win else loss
if var then if b then var else loss
if var then if b then stmt else var
if var then if var then stmt else var
if var then if var then stmt else stmt
if var then if_stmt
if var then stmt
if_stmt
stmt

if a then if b then win else loss
if var then if b then win else loss
if var then if var then win else loss
if var then if var then var else loss
if var then if var then var else var
if var then if var then stmt else var
if var then if var then stmt else stmt
if var then if_stmt
if var then stmt
if_stmt
stmt

if a then if b then win else loss
if var then if b then win else loss
if var then if var then win else loss
if var then if var then var else loss
if var then if var then stmt else var
if var then if var then stmt else stmt
if var then if_stmt
if var then stmt
if_stmt
stmt

Question 6

For the grammar in last question (Question 5), when applying shift-reduce parsing to the same string:
if a then if b then win else loss
What kind of conflicts will we have?

Shift-reduce conflict

Reduce-reduce conflict

Both conflicts

No conflict

Question 7

Consider the following grammar:

E

→ $\rightarrow$ T * E

∣ $\mid$ T
T

→ $\rightarrow$ int + T

∣ $\mid$ int

$\mid$ (E)

Using shift-reduce parsing, how many shift and how many reduce moves does it take to accept the input string:
((int + int)*int)

Question 8

Consider the following grammar:

S

$\rightarrow$ Sb

$\mid$ a

This grammar is:

not SLR(1)

SLR(1) but not LL(1)

LL(1)

Question 9

Consider the following grammar:

S

$\rightarrow$ SbS

$\mid$ a

This grammar is:

SLR(1) but not LL(1)

not SLR(1)

LL(1)

Question 10

Consider the following grammar:

S

$\rightarrow$ bS

$\mid$ a

This grammar is:

LL(1)

SLR(1) but not LL(1)

not SLR(1)

Question 11

Which of the following statements are true about this grammar:

S

$\rightarrow$ aTUb

$\mid$

$\epsilon$
T

$\rightarrow$ cUc

$\mid$ bUb

$\mid$ aUa
U

$\rightarrow$ Sb

$\mid$ cc

The first set of S is {

$\epsilon$ , a, b}

The first set of U is {a, b, c}

The follow set of T is {a, b, c}

The follow set of S is {$, b}

In accordance with the Coursera Honor Code, I (Anonymous Student) certify that the answers here are my own work.

You cannot submit your work until you agree to the Honor Code. Thanks!

Compilers

Top Navigation Bar

Compilers
by Alex Aiken

Side Navigation Bar

Quiz #3 Help Center

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Compilers

Compilersby Alex Aiken

Quiz #3 Help Center

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Confirm Navigation

Compilers
by Alex Aiken