适合读者：软考中级备考同学
阅读时间：3分钟
内容：文法的基本概念、终结符与非终结符、产生式、推导与归约、例题
1. 什么是文法？
文法是形式语言理论的核心概念，用于精确描述程序设计语言的语法规则。一个文法定义了一门语言中哪些符号串是合法的句子。编译程序在语法分析阶段会根据文法判断源程序是否合乎语法规则。
软考中常考查文法的基本组成（终结符、非终结符、产生式）以及文法的分类。
2. 文法的形式定义
文法GGG是一个四元组：
G=(VT,VN,P,S)G = (V_T, V_N, P, S)G=(VT,VN,P,S)
其中：
- VTV_TVT：终结符集合（Terminal Symbols）
- VNV_NVN：非终结符集合（Non-terminal Symbols）
- PPP：产生式集合（Production Rules）
- SSS：开始符号（Start Symbol），S∈VNS \in V_NS∈VN
3. 终结符（Terminal）
定义：文法中不能再被替换的基本符号，是语言中实际出现的字符或单词。
特点：
- 终结符是语言的字母表中的元素
- 它们出现在最终生成的句子中
- 没有产生式可以进一步展开终结符
示例：
- 在算术表达式文法中，
+,-,*,/,(,), 数字0~9是终结符 - 在程序语言文法中，关键字
if,else,while，运算符=,==，标识符等是终结符
通常表示：用小写字母、数字或特定符号表示（如a,b,+,id）。
4. 非终结符（Non-terminal）
定义：可以被进一步展开的语法变量，用于表示语法结构。
特点：
- 非终结符不出现在最终生成的句子中（在推导过程中会被终结符序列替代）
- 每个非终结符对应一个语法成分（如：表达式、语句、程序块）
示例：
<表达式>、<赋值语句>、<循环>等是非终结符- 通常用尖括号或大写字母表示（如
E,T,F,<stmt>）
开始符号SSS是一个特殊的非终结符，代表整个语法成分的起点。
5. 产生式（Production Rule）
定义：描述非终结符如何展开的规则，形式为：
α→β\alpha \rightarrow \betaα→β
其中α\alphaα（左部）是至少包含一个非终结符的符号串，β\betaβ（右部）是由终结符和非终结符组成的符号串（可以为空串ε\varepsilonε）。
含义：左部的符号可以被右部的符号串替换。
示例：
E → E + T E → T T → T * F T → F F → ( E ) F → id这里的箭头→表示“定义为”或“可替换为”。
6. 推导与归约
- 推导：从开始符号出发，反复使用产生式替换非终结符，最终得到一个全部由终结符组成的串，称为该文法的一个句子。
- 最左推导：每次都替换最左边的非终结符。
- 最右推导（规范推导）：每次都替换最右边的非终结符。
- 归约：推导的逆过程，将终结符串逐步替换为非终结符，最终得到开始符号。
7. 完整示例
文法（简单算术表达式）：
S → E E → E + T | T T → T * F | F F → ( E ) | id- VT={+,∗,(,),id}V_T = \{+, *, (, ), id\}VT={+,∗,(,),id}（
id代表标识符，如变量名） - VN={S,E,T,F}V_N = \{S, E, T, F\}VN={S,E,T,F}
- PPP为上述产生式
- SSS为开始符号
推导示例：推导句子id + id * id的最左推导过程：
S ⇒ E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + T * F ⇒ id + F * F ⇒ id + id * F ⇒ id + id * id8. 文法的分类（乔姆斯基体系）
| 类型 | 名称 | 产生式形式 | 对应自动机 |
|---|---|---|---|
| 0型 | 短语结构文法 | α→β\alpha \rightarrow \betaα→β（无限制） | 图灵机 |
| 1型 | 上下文有关文法 | αAβ→αγβ\alpha A \beta \rightarrow \alpha \gamma \betaαAβ→αγβ，γ≠ε\gamma \neq \varepsilonγ=ε | 线性有界自动机 |
| 2型 | 上下文无关文法 | A→γA \rightarrow \gammaA→γ（AAA为单个非终结符） | 下推自动机 |
| 3型 | 正则文法 | A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a | 有限自动机 |
软考主要考查2型（上下文无关文法），因为它足够描述多数程序设计语言的语法结构。
9. 经典例题
题目1：给定文法GGG的产生式如下：
S → aB | bA A → aS | bAA | a B → bS | aBB | b下列符号串中，属于该文法语言的是（ ）。
A. aaabb
B. ab
C. abab
D. ba
解析：需要尝试推导。该文法表示一个关于aaa和bbb个数相等的语言。选项 Dba可通过S → bA → ba推导得到（A→aA \rightarrow aA→a）。其他选项无法推导。
答案：D
题目2：在文法中，不能出现在最终句子中的符号是（ ）。
A. 终结符
B. 非终结符
C. 运算符
D. 标识符
答案：B
题目3（判断）：一个文法的开始符号必须是终结符。（ ）
答案：错误（开始符号是非终结符）
10. 记忆口诀
终结符出现最终句，非终结符可继续换。
产生式左边变右边，推导归约来检验。
11. 给备考同学的一句话
文法定义是编译原理的基础，软考中常以选择题形式考查：
- 区分终结符和非终结符（看是否能被展开）
- 产生式的形式（左部至少一个非终结符）
- 最左推导/最右推导的过程理解
记住：终结符是“不能再拆”的单词，非终结符是“语法变量”。掌握这个核心区别，相关题目即可得分。
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅
#软考中级 #软件设计师 #文法 #终结符 #非终结符 #产生式 #编译原理
