2025-2026学年上学期期末

2025-2026学年上学期期末试卷（A）

说明

• 原卷标题：华东师范大学期末试卷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\}$

提示

原题遗失，但原题是错题

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;
       }