Terminal与Nonterminal：上下文无关语法中各个组分的含义

在上下文无关语法（Context-Free Grammar, CFG）中：

• Terminal（终结符）：是语法所描述语言中的“实际符号”，也就是最终生成的字符串里真正出现的字符或词。它不能再被展开或替换。

• Nonterminal（非终结符）：是语法中的“变量”或“语法类别”，用于表示某种结构或成分。它并不是最终字符串的一部分，而是推导过程中的中间符号，可以被产生式替换。

---

1. 终结符 Terminal

终结符是语言字母表中的基本符号。

例如，如果一种语言由单词组成，那么终结符可能就是具体的单词：

the, cat, dog, runs, sleeps

如果一种语言由字符组成，那么终结符就是具体字符：

a, b, c, 0, 1, +, -, ...

终结符的特点：

• 不能再被展开。

• 最终生成的句子中只包含终结符。

• 在语法规则中，通常用小写字母、数字、标点或带引号的形式表示。

例如：

Det → 'the'
N → 'cat'
V → 'runs'

这里的 'the'、'cat'、'runs' 都是终结符。

---

2. 非终结符 Nonterminal

非终结符是语法中的抽象符号，用来表示某种语法结构或成分，例如：

S, NP, VP, Det, N, V

它们通常代表：

• S：句子

• NP：名词短语

• VP：动词短语

• Det：限定词

• N：名词

• V：动词

非终结符的特点：

• 可以被产生式替换。

• 不会出现在最终生成的字符串中。

• 通常用大写字母、尖括号或特殊符号表示。

例如：

S → NP VP
NP → Det N
VP → V

这里的 S、NP、VP、Det、N、V 都是非终结符。

---

3. 形式化定义中的区别

一个上下文无关语法通常定义为一个四元组：

$G=(V,\mathrm{\Sigma },R,S)$

其中：

• $V$ ：非终结符的有限集合。

• $\mathrm{\Sigma }$ ：终结符的有限集合。

• $R$ ：产生式规则的有限集合。

• $S$ ：起始非终结符， $S\in V$ 。

并且要求：

$V\cap \mathrm{\Sigma }=\mathrm{\varnothing }$

也就是说，非终结符和终结符是两个不相交的集合，一个符号不能既是终结符又是非终结符。

产生式的一般形式是：

$A\to \alpha$

其中：

• $A$ 必须是非终结符，即 $A\in V$ 。

• $\alpha$ 是终结符和非终结符组成的字符串，即 $\alpha \in (V\cup \mathrm{\Sigma }{)}^{\ast }$ 。

---

4. 举例说明

假设有以下语法：

S → NP VP
NP → Det N
VP → V
Det → 'the'
N → 'cat'
V → 'runs'

其中：

• 非终结符：S, NP, VP, Det, N, V

• 终结符：'the', 'cat', 'runs'

• 起始符：S

推导过程：

S
→ NP VP
→ Det N VP
→ 'the' N VP
→ 'the' 'cat' VP
→ 'the' 'cat' V
→ 'the' 'cat' 'runs'

最终得到的字符串是：

the cat runs

这个最终字符串中只包含终结符，而非终结符在推导过程中全部被替换掉了。

---

5. 主要区别总结

方面	终结符 Terminal	非终结符 Nonterminal
是否出现在最终字符串中	是	否
能否被替换	不能	能
作用	表示实际的语言符号	表示语法结构或类别
表示习惯	小写、数字、标点、引号	大写字母、尖括号
在产生式中的位置	通常出现在右部	可以出现在左部和右部
举例	the, cat, runs	S, NP, VP, N, V

简单来说：非终结符是语法推导过程中的“中间变量”，而终结符是最终语言中真正出现的符号。