适合读者：软考中级备考同学
阅读时间：3分钟
内容：自上而下推导、最左推导与最右推导的定义、示例、区别、例题
1. 什么是自上而下推导？
语法分析分为两种策略：自上而下和自下而上。
自上而下推导是从文法的开始符号出发，反复用产生式的右部替换左部的非终结符，逐步展开，最终得到输入符号串。它直观地模拟了从语法树根节点向下构造叶节点的过程。
软考中常考查最左推导和最右推导两种方式，二者在最左/最右替换策略上不同，但最终得到的语法树相同。
2. 最左推导（Leftmost Derivation）
定义：在推导的每一步，都选择当前句型中的最左边的非终结符进行替换。
特点：
- 符合多数递归下降解析器的工作方式
- 易于手工推导
示例：
文法如下：
E → E + T | T T → T * F | F F → ( E ) | id输入串id + id * id，最左推导过程：
E ⇒ E + T (选择 E → E + T，替换最左非终结符 E) ⇒ T + T (替换最左的 E 为 T) ⇒ F + T (替换最左的 T 为 F) ⇒ id + T (替换最左的 F 为 id) ⇒ id + T * F (替换最左的 T 为 T * F) ⇒ id + F * F (替换最左的 T 为 F) ⇒ id + id * F (替换最左的 F 为 id) ⇒ id + id * id (替换最左的 F 为 id)每一步都是替换当前句型中最左边的非终结符。
3. 最右推导（Rightmost Derivation）
定义：在推导的每一步，都选择当前句型中的最右边的非终结符进行替换。
特点：
- 与自下而上归约（规范归约）是对应关系
- 在编译原理中，最右推导也称为规范推导
示例：同样文法，输入串id + id * id，最右推导过程：
E ⇒ E + T ⇒ E + T * F ⇒ E + T * id ⇒ E + F * id ⇒ E + id * id ⇒ T + id * id ⇒ F + id * id ⇒ id + id * id每一步都是替换当前句型中最右边的非终结符。
4. 最左推导 vs 最右推导
| 对比项 | 最左推导 | 最右推导 |
|---|---|---|
| 替换位置 | 最左边的非终结符 | 最右边的非终结符 |
| 对应分析方式 | 自上而下解析（递归下降） | 自下而上归约（LR分析） |
| 语法树 | 相同 | 相同 |
| 推导序列长度 | 相同 | 相同 |
| 是否为规范推导 | 否（但通常不称为规范） | 是（规范推导） |
注意：对于同一文法同一输入串，最左推导和最右推导产生的语法树（结构）是一样的，只是构造顺序不同。
5. 经典例题
题目1：给定文法：
S → aS | b用最左推导产生字符串aaab。
解：
S ⇒ aS (最左 S) ⇒ aaS ⇒ aaaS ⇒ aaab (S → b)答案：S ⇒ aS ⇒ aaS ⇒ aaaS ⇒ aaab
题目2：对于文法S → AB, A → a, B → b，写出最左推导和最右推导生成ab。
解：
- 最左推导：S ⇒ AB ⇒ aB ⇒ ab
- 最右推导：S ⇒ AB ⇒ Ab ⇒ ab
答案：略
题目3（判断）：最左推导和最右推导对于同一个输入串最终得到的语法树一定相同。（ ）
答案：正确（推导顺序不同，但树的结构相同）
6. 记忆口诀
自上而下开始符，反复展开成句子。
最左替换最左符，最右替换最右符。
语法树形都一样，分析顺序有差异。
7. 给备考同学的一句话
自上而下推导是语法分析的基础概念。软考中常以选择题或简答题形式考查：
- 区分最左推导和最右推导（看替换的是最左还是最右非终结符）
- 给定文法，手动进行最左或最右推导
- 理解推导与语法树的关系
记住：最左推导是“从左到右”展开，最右推导是“从右到左”展开。掌握基本示例，考试时按规则逐步替换即可。
🔔 **本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订
#软考中级 #软件设计师 #语法分析 #自上而下推导 #最左推导 #最右推导
