适合读者软考中级备考同学阅读时间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篇点击头像 → 专栏《软考中级高频考点》订#软考中级 #软件设计师 #语法分析 #自上而下推导 #最左推导 #最右推导