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

How many strings does the following grammar generate?

A→BB $A \rightarrow BB$

B→CC $B \rightarrow CC$

C→1∣2 $C \rightarrow 1 \mid 2$

Question 2

How many strings does the following grammar generate?

A→BB $A \rightarrow BB$

B→CC $B \rightarrow CC$

C→1∣2∣ϵ $C \rightarrow 1 \mid 2 \mid \epsilon$

Question 3

Which of the following grammar(s) produce regular languages?
[Choose all that apply]

Question 4

Considering the following grammar:

S→A $S \rightarrow A$

A→B∣C $A \rightarrow B \mid C$

B→(C) $B \rightarrow ( C )$

C→B+C∣D $C \rightarrow B + C \mid D$

D→1∣0 $D \rightarrow 1 \mid 0$
Adding which of the following will cause the grammar to be left-recursive?
[Choose all that apply]

Question 5

Which of the following grammars correctly removes left-recursion from:

S→Aα∣δ $S \rightarrow A \alpha \mid \delta$

A→Sβ $A \rightarrow S \beta$
[Choose all that apply]

S→δAα∣δ $S \rightarrow \delta A \alpha \mid \delta$

A→A′A∣ϵ $A \rightarrow A'A \mid \epsilon$

A′→αβ $A' \rightarrow \alpha \beta$

S→Aα∣δ $S \rightarrow A \alpha \mid \delta$

A→δβA′ $A \rightarrow \delta \beta A'$

A′→αβA′∣ϵ $A' \rightarrow \alpha \beta A' \mid \epsilon$

S→Aα∣δ $S \rightarrow A \alpha \mid \delta$

A→δβ∣Aαβ $A \rightarrow \delta \beta \mid A \alpha \beta$

S→δS′ $S \rightarrow \delta S'$

S′→AS′∣ϵ $S' \rightarrow AS' \mid \epsilon$

A→βα $A \rightarrow \beta \alpha$

Question 6

Consider the following grammar:

E→E∗E∣E+E∣(E)∣int $E \rightarrow E * E \mid E + E \mid ( E ) \mid int$
How many unique parse trees are there for the string

5∗3+(2∗7)+4 $5 * 3 + ( 2 * 7 ) + 4$ ?

Question 7

Using the grammar and string from the previous question (Question 6), which of the following rules are necessary to produce a unique parse tree for the string

5∗3+(2∗7)+4 $5 * 3 + ( 2 * 7 ) + 4$ ?
[Choose all that apply]

addition associates to the left

multiplication binds more tightly than addition

parentheses bind more tightly than multiplication

multiplication associates to the left

Question 8

[Choose all that apply]

The language "

0n2 $0^{n^2}$ , where n > 0 is an integer" is regular.

The language "

0n1n2n $0^n 1^n 2^n$ , where n > 0 is an integer" is context-free but not regular.

The language "

0n2 $0^{n^2}$ , where n > 0 is an integer" is neither context-free nor regular..

The language "strings with an even number of 0's" is both regular and context-free.

The language "

0n1n $0^n 1^n$ , where n > 0 is an integer" is context-free but not regular.

Question 9

Consider following 4 grammars:
G1.

S→aSb∣Sb∣b $S \rightarrow aSb \mid Sb \mid b$
G2.

S→Sa∣Sb∣c $S \rightarrow Sa \mid Sb \mid c$
G3.

S→SaS∣ϵ $S \rightarrow SaS \mid \epsilon$
G4.

S→bT $S \rightarrow bT$

T→aT∣ϵ $T \rightarrow aT \mid \epsilon$
Let n = the number of grammars where there exists a string that has at least two different left-most derivations;
m = the number of grammars where for any string, we only have one parse tree;
k = the number of grammars that can be used with a recursive descent parser
Choose the correct value for n,m and k.

Question 10

How many distinct strings and parse trees can be generated by the following grammar?

S→A1∣1B $S \rightarrow A 1 \mid 1 B$

A→10∣C∣ϵ $A \rightarrow 1 0 \mid C \mid \epsilon$

B→C1∣ϵ $B \rightarrow C 1 \mid \epsilon$

C→0∣1 $C \rightarrow 0 \mid 1$

5 strings, 7 parse trees

4 strings, 6 parse trees

6 strings, 7 parse trees

5 strings, 6 parse trees

Question 11

Which of the following grammar(s) are unambiguous and recognize the same grammar as:

E→E+E∣E−E∣E∗E∣E/E∣int $E \rightarrow E + E \mid E - E \mid E * E \mid E / E \mid int$
[Choose all that apply]

E→E+int∣E−int∣E∗int∣E/int∣int $E \rightarrow E + int \mid E - int \mid E * int \mid E / int \mid int$

E→int+E∣E−int∣int∗E∣E/int∣int $E \rightarrow int + E \mid E - int \mid int * E \mid E / int \mid int$

E→int+E∣int−E∣int∗E∣int/E∣int $E \rightarrow int + E \mid int - E \mid int * E \mid int / E \mid int$

E→E′+E∣E′−E∣E′ $E \rightarrow E' + E \mid E' - E \mid E'$

E′→int∗E′∣int/E′∣int $E' \rightarrow int * E' \mid int / E' \mid int$

E→int+E′∣int−E′∣int+E∣int−E $E \rightarrow int + E' \mid int - E' \mid int + E \mid int - E$

E′→int∗E′∣int/E′∣int $E' \rightarrow int * E' \mid int / E' \mid int$

Question 12

Let

Tn $T_n$ be the string

0n1 $0^n1$ , to be matched with a recursive descent parser using the following grammar:

S -> A | B | 0S
A -> 0A | 0
B -> 1

Is the number of token comparisons needed to (successfully) match

Tn $T_n$ :

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 #2 Help Center

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Question 12

Compilers

Compilersby Alex Aiken

Quiz #2 Help Center

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Question 12

Confirm Navigation

Compilers
by Alex Aiken