Stanford Compiler Quiz 2

课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

这次回顾Quiz 2。

Question 1

How many strings does the following grammar generate?

$\begin{array}{l} A \rightarrow B B \\ B \rightarrow C C \\ C \rightarrow 1 \mid 2 \end{array}$

因为

$A\to CCCC$

所以答案为

$2^4=16$

Question 2

How many strings does the following grammar generate?

$\begin{array}{l} A \rightarrow B B \\ B \rightarrow C C \\ C \rightarrow 1|2| \epsilon \end{array}$

因为

$A\to CCCC$

所以答案为（按照长度累加）

$\sum_{i=0}^4 2^i=2^5-1=31$

Question 3

Which of the following grammar(s) produce regular languages?

[Choose all that apply]

$A \rightarrow (A) \mid \epsilon$
$A \rightarrow (A(\; \mid \epsilon$
$\begin{array}{l}
A \rightarrow(B) \mid(B B) \\
B \rightarrow(C C) \mid(C C C) \\
C \rightarrow(D D D) \\
D \rightarrow()
\end{array}$
$A \rightarrow aA \mid b$
$A \rightarrow Aa \mid b$
$A \rightarrow aaAb \mid \epsilon$
$A \rightarrow AAaab \mid \epsilon$
$A \rightarrow AAaab \mid aab$

列出选择的选项及其对应表达式：

$A \rightarrow (A(\; \mid \epsilon:((()^{\star}$
$\begin{array}{l}
A \rightarrow(B) \mid(B B) \\
B \rightarrow(C C) \mid(C C C) \\
C \rightarrow(D D D) \\
D \rightarrow()
\end{array}$：确定性的语言，结果有限
$A \rightarrow aA \mid b:a^{\star}b$
$A \rightarrow Aa \mid b:ba^{\star}$
$A \rightarrow AAaab \mid \epsilon:(aab)^{\star}$
$A \rightarrow AAaab \mid aab:(aabaab)^{\star}$

Question 4

Considering the following grammar:

$\begin{array}{l} S \rightarrow A \\ A \rightarrow B \mid C \\ B \rightarrow(C) \\ C \rightarrow B+C \mid D \\ D \rightarrow 1 \mid 0 \end{array}$

Adding which of the following will cause the grammar to be left-recursive?

[Choose all that apply]

$B\to C$
$D\to B$
$A\to D$
$D\to A$
$C\to 1C$
$C\to C+B$

左递归即出现无穷递归的情形

$B\to C:B\to C, C\to B+C$
$D\to A:A\to C,C\to D$
$C\to C+B$

Question 5

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

$\begin{array}{l} S \rightarrow A \alpha \mid \delta \\ A \rightarrow S \beta \end{array}$

[Choose all that apply]

$\begin{array}{l}
S \rightarrow A \alpha \mid \delta \\
A \rightarrow \delta \beta A^{\prime} \\
A^{\prime} \rightarrow \alpha \beta A^{\prime} \mid \epsilon
\end{array}$
$\begin{array}{l}
S \rightarrow \delta S^{\prime} \\
S^{\prime} \rightarrow A S^{\prime} \mid \epsilon \\
A \rightarrow \beta \alpha
\end{array}$
$\begin{array}{l}
S \rightarrow A \alpha \mid \delta \\
A \rightarrow \delta \beta \mid A \alpha \beta
\end{array}$
$\begin{array}{l}
S \rightarrow \delta A \alpha \mid \delta \\
A \rightarrow A^{\prime} A \mid \epsilon \\
A^{\prime} \rightarrow \alpha \beta
\end{array}$

第三项依然是左递归。

第四项和原语法不等价，因为$\delta \alpha$无法生成。

选择第一第二项。

Question 6

Consider the following grammar:

$E \rightarrow E \star E \mid E + E \mid ( E ) \mid int$

How many unique parse trees are there for the string $5 \star 3 + ( 2 \star 7 ) + 4$

解析过程

注意这里并没有指定运算优先级，所以有5种解析：

$[ [5 \star 3] + (2 \star7) ] + 4$
$[5 \star 3] + [(2 \star 7) + 4]$
$5 \star [ 3 + [(2 \star 7) + 4]]$
$[5 \star [3 + (2 \star 7)]] + 4$
$5 \star [[3 + (2 \star 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$?
[Choose all that apply]

addition associates to the left
multiplication associates to the left
multiplication binds more tightly than addition
parentheses bind more tightly than multiplication

提供符号优先级即可，选择第一第三项。

Question 8

[Choose all that apply]

The language “strings with an even number of $0$’s” is both regular and context-free.
The language “$0^n1^n$, where $n > 0$ is an integer” is context-free but not regular.
The language “$0^n1^n2^n$, where $n > 0$ is an integer” is context-free but not regular.
The language “$0^{n^2}$, where $n > 0$ is an integer” is regular.
The language “$0^{n^2}$, where $n > 0$ is an integer” is neither context-free nor regular.

选择1,2,5，第二项可以由如下CFG得到：

$\begin{aligned} s &\rightarrow 0s1\\ s &\rightarrow \epsilon \end{aligned}$

Question 9

Consider following 4 grammars:

G1. $S→aSb∣Sb∣b$

G2. $S→Sa∣Sb∣c$

G3. $S→SaS∣ϵ$

G4. $S→bT,T→aT∣ϵ$

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.

n =1; m = 2; k = 1
n =1; m = 1; k = 0
n = 2; m = 2; k = 1
n = 2; m = 2; k = 2
n = 1; m = 1; k = 1

注意有如下事实：

G1,G2满足条件1
G2,G4满足条件2
G4满足条件3

所以选第3项。

Question 10

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

$\begin{array}{l} S \rightarrow A 1 \mid 1 B \\ A \rightarrow 10|C| \epsilon \\ B \rightarrow C 1 \mid \epsilon \\ C \rightarrow 0 \mid 1 \end{array}$

5 strings, 7 parse trees
5 strings, 6 parse trees
6 strings, 7 parse trees
4 strings, 6 parse trees

首先求字符串：

$S\to 101| C1| 1 | 1C1|1$
$S\to 101|01|11|1|101|111 |1$

每个字符串对应一个解析树，所以一共有7个解析树。

不同字符串为

$101,01,11,1,111$

所以一共有5种不同的字符串。

Question 11

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

$E \rightarrow E + E \mid E - E \mid E * E \mid E / E \mid int$

[Choose all that apply]

$E \rightarrow int + E \mid int - E \mid int * E \mid int / E \mid int$
$E \rightarrow E+i n t|E-i n t| E * \operatorname{int}|E / i n t| \text { int } t$
$E \rightarrow \operatorname{int}+E|E-\operatorname{int}| \operatorname{int} * E \mid E / \text {int} \mid \text { int } t$
$E \rightarrow int + E’ \mid int - E’ \mid int + E \mid int - E$
$E \rightarrow E’ + E \mid E’ - E \mid E’$

第三项无法产生int - int * int。

第四项无法产生int * int。

其他选项均正确。

Question 12

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

$\begin{aligned} & S\to A | B | 0S\\ & A \to 0A | 0\\ & B \to 1 \end{aligned}$

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

$O(1)$
$O(n)$
$O(n^2)$
$O(n^3)$
$O(2^n)$

对每个$0$，解析器只有遇到最后一个$1$才会回溯，所以每个$0$的比较次数为$O(n)$，因此比较次数为$O(n^2)$。