学堂在线测试 —— 编译原理#

高级程序设计语言的语法描述 习题#

---

一、 单项选择题（本题共 10 小题，每小题 1 分，共 10 分）#

1. 文法 $G：S \to xS \mid y$ 所识别的语言是 ( )。

• A. $xyx$
• B. $(xyx)^*$
• C. $x^*y$
• D. $xy$

2. 从编译程序的语法分析角度看，源程序是句子的集合，______ 可以较好地反映句子的结构。

• A. 线性表
• B. 树
• C. 强连通图
• D. 堆栈

3. 由文法的开始符号经 0 步或多步推导产生的文法符号序列是 ( )

• A. 短语
• B. 句柄
• C. 句型
• D. 句子

4. 由文法的开始符号经 0 步或多步推导产生的不含非终结符号的文法符号序列是 ( )

• A. 短语
• B. 句柄
• C. 句型
• D. 句子

5. 若文法 $G$ 是无二义的，则它的任何句子：( )

• A. 最左推导和最右推导对应的语法树必定相同
• B. 最左推导和最右推导对应的语法树可能不同
• C. 最左推导和最右推导必定相同
• D. 可能存在两个不同的最左推导，但它们对应的语法树相同

6. 给定文法 $A \to bA \mid cc$，下面的符号串中为该文法句子的是 ( ) ① $cc$ ② $bcbc$ ③ $bcbcc$ ④ $bccbcc$ ⑤ $bbbcc$

• A. ①⑤
• B. ①③④⑤
• C. ①④
• D. ①④⑤

7. 下列哪种文法是上下文无关文法的子集 ( )

• A. 0 型文法
• B. 1 型文法
• C. 2 型文法
• D. 3 型文法

8. 文法 $G$ 产生的 ( ) 的全体称为该文法的语言。

• A. 句型
• B. 句子
• C. 非终结符
• D. 终结符

9. 若文法 $G$ 为：$S \to aS \mid b$，则该文法生成的语言是 ( )。

• A. 所有以 b 结尾的 a、b 字符串
• B. 所有含一个 b 和任意个 a 的字符串
• C. 所有以 a 开头、以 b 结尾的字符串
• D. 所有 a 的个数大于 b 的个数的字符串

10. 下列关于二义性文法的说法，错误的是 ( )。

• A. 二义性文法存在至少一个句子对应多棵语法树
• B. 二义性文法不能用于语法分析
• C. 可以通过增加约束规则（如运算符优先级）消除二义性
• D. 多数程序设计语言的文法本质上是二义性的，需通过附加规则处理

---

二、 填空题（本题共 1 小题，每小题 1 分，共 1 分）#

1. 二义文法是指该文法存在一个句子 ______。

---

三、 主观题（本题共 6 小题，每小题 10 分，共 60 分）#

1. 设字母表 $\Sigma = \{a, b\}$，$U = \{ab, b\}$，$V = \{aa, bb\}$，求 $UV$, $\Sigma^*$, $\Sigma^+$。

2. 已知文法 $G[S]$：

$$\begin{aligned} S &\to a \mid \varepsilon \mid (T) \\ T &\to T, S \mid S \end{aligned}$$

分别给出下列句子的最左和最右推导过程： (1) $(a, (a, a))$ (2) $(a, (a, \varepsilon))$

3. 考虑文法 $G[S]$：

$$\begin{aligned} S &\to bA \\ A &\to aA \mid a \end{aligned}$$

该文法定义了一个什么样的语言？

4. 构造一个文法 $G$，使 $L(G) = \{a^n b^n \mid n \ge 1\}$。

5. 给定文法 $G[E]$：

$$\begin{aligned} E &\to E i T \mid T \\ T &\to T + F \mid i F \mid F \\ F &\to E * \mid ( \end{aligned}$$

请回答该文法是否为二义文法，说明理由。

6. 令文法 $G_6$ 为：

$$\begin{aligned} N &\to D \mid ND \\ D &\to 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9 \end{aligned}$$

(1) $G_6$ 的语言 $L(G_6)$ 是什么？ (2) 给出句子 0127、34 和 568 的最左推导和最右推导。