2025-2026学年上学期期末

华东师范大学期末试卷A卷 2025-2026 学年第 一 学期

一、选择题

1. 设正规式 (regular expression)

$$r = (a\mid b)(c\mid d\mid e)(x\mid y)$$

则 $L(r)$ 中元素个数（the number of elements in $L(r)$）为（）。

A. 6

B. 12

C. 18

D. 24 2. 文法 $G[S]$:

$$S \to aSb\,\mid\,ab$$

所识别的语言是（the language recognized by the grammar）是（）。

A. $\{a^nb^n\,\mid\,n \geq 0\}$

B. $\{a^nb^n\,\mid\,n \geq 1\}$

C. $\{a^nb^m\,\mid\,n,m \geq 1\}$

D. $\{(ab)^n\,\mid\,n \geq 1\}$

!!!warning 原题遗失，但原题是错题

4. 给定文法 $G$（$S$为开始符号）：

$$S \to aS\,\mid\,B \\ B \to bBc\,\mid\,ε$$

下列哪些符号串是 $L(G)$ 中的元素（which string is in $L(G)$）。

A. $a^2b^3c^3$

B. $a^2b^3c^2$

C. $ab$

D. $a^3c$

5. 一个 $LR(1)$ 文法（an LR(1) grammer）一定是（）。

A. 二义性文法

B. 无二义性文法

C. 左递归文法

D. LL(1) 文法

二、填空题

6. 已知文法 $G[E]$:

$$\begin{aligned} E &\to E-T\,\mid\,T \\ T &\to T/F\,\mid\,F \\ F &\to (E)\,\mid\,id \end{aligned}$$

则终结符集合(terminal set)为______，非终结符集合(non-terminal set)为）______。

7. 编译程序的工作过程一般可分为(the phases of a compile):______、______、______、______、______、______等基本阶段，同时还会伴有(also with)______和______。

8. 一个活动记录(activity record / stack frame)通常包括______、______、______、______、______等若干部分。

9. DFA和NFA主要区别在于(the key difference between DFA and NFA):______。

三、简答

1. 证明文法 $E \to E + E \mid E \,\,\texttt{\^{}}\, E \mid -E \mid id$ 具有二义性。
2. 为文法 $L = \{a^nb^mc^n\},n \geq 1,m \geq 0\}$ 设计CFG。
3. 对于属性文法

$S \to pAq$ {print 1};

$S \to p$ {print 2};

$A \to AS$ {print 3};

$A \to r$ {print 4};

输入串为 prpq，输出为什么

4. 对于文法：

$$\begin{aligned} S &\to Ad\\ A &\to aAb \mid c \end{aligned}$$

a. 给出 $aAbd$ 与 $acbd$ 的句柄

b. 分别给出 $aacbbd$ 的最左和最右推导

5. 消除下列文法的左递归

$$\begin{aligned} E &\to E - T \mid T\\ T &\to T / F \mid F\\ F &\to (E) \mid id \end{aligned}$$

四、计算

1. 对于正则表达式 $r = (a\mid b)^*(aba\mid bab)$

a. 使用直接构造法构造 DFA，给出状态表

b. 最小化上一问的 DFA ，给出状态表或说明合并结果

2. 对于文法

$$\begin{aligned} S &\to AB\\ A &\to aA\mid ε\\ B &\to bB\mid C\\ C &\to cC\mid d \end{aligned}$$

a. 构造 LR(0) 规范集组

b. 给出 follow 集

c. 构造 SLR(1) 状态表，说明是否为 SLR(1) 文法

d. 对于 $aabbccdd$$，给出文法分析过程

3. 给出下列代码的三地址码形式

while(m*2 < n+k OR m != k)
    while(n - m >= 3 AND k < 8>)
    {
        n = n - 1;
        k = k + m;
    }