【程序语言与编译】语法分析：自上而下推导（最左/最右）

适合读者：软考中级备考同学
阅读时间：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 最右推导

注意：对于同一文法同一输入串，最左推导和最右推导产生的语法树（结构）是一样的，只是构造顺序不同。

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篇，点击头像 → 专栏《软考中级高频考点》订

#软考中级 #软件设计师 #语法分析 #自上而下推导 #最左推导 #最右推导