前面通过实例简单介绍了推导的大致过程，但并没有明确阐述推导的定义。本小节将从推导的定义出发，深入研究推导及其与编译器设计的联系。推导是用于描述文法定义语言的过程，其核心思想是把产生式的左部非终结符替换为右部的符号串。推导的方法是程序设计语言语法分析的核心方法之一。下面，给出推导的公理化定义：

如α→β是文法G=(V^t，Vⁿ，S，P)的规则（或说是P中的一条产生式），γ和δ是(VⁿUV^t)中的任意符号，若有符号串v，w满足：

v=γαδ，w=γβδ

则说v（应用规则α→β）直接产生w，或说w是v的直接推导(direct derivation)，记作V=>W。

如果α¹=>α²=>…=>αⁿ，则称其为α¹到αⁿ的推导(derivation)。通常，可以用“=>”表示“一步推导”，用“”表示“零步或多步推导”，用“”表示“一步或多步推导”。在不关心推导细节的情况下，可以将例3-3的推导过程简写为E。

对于文法开始符号为S的文法G，如果，则称α为G的句型（sentential form），其中α可能包含非终结符。不含非终结符的句型称为句子(sentence)。

关于推导的过程与实例，笔者认为没有必要再次阐述了，请读者参见例3-3。推导能运用文法验证用户输入的程序，那么，如何设计一个算法能让计算机自动完成推导验证程序的工作呢？这正是本书研究推导的目的。目前，手工推导验证程序完全是凭借个人经验完成的，这种随机性较大的工作流程是很难通过算法实现的。因此，有必要深入分析手工推导的过程，得到其工作模型，才能通过算法最终实现。读者仔细分析手工推导过程，不难发现每一步推导通常都存在两个选择：(www.daowen.com)

(1)选择哪个非终结符被替换。

(2)选择哪个候选式替换该非终结符。

以例j-j第二步推导为例，第二步推导过程是从符号串“E opl T”推导得到符号串“T opl T”。在符号串“E opl T”中存在三个非终结符，即E、opl、T。由于每一步推导只能替换一个非终结符，故必须只选择替换其中一个非终结符。实际上，无论选择替换哪个非终结符，其最终推导得到的句子都是一样的。笔者在此不作理论证明，只通过实例说明。读者可以参考例3-4的推导过程，例3-3的第二步选择对非终结符E进行推导，而例3-4在第二步推导中选择替换非终结符T。两个推导过程完全不同，但是其最终推导得到的句子是相同的。当然，读者也可以作其他尝试，可以发现最终结果是始终不变的。实践证明，选择哪个非终结符被替换并不影响最终的推导结果。那么，例j-j中选择对非终结符E进行推导，非终结符E的候选式有两个，即E opl T和T。此时，面临选择哪个候选式替换非终结符E的问题。注意，在推导过程中，通常某一步推导所能选择的候选式中往往只有一个可以正确推导得到给定句子，其余的都是错误的。当然，某些文法可能出现某一步推导所能选择的候选式中存在两个或以上的候选式能够正确推导得到给定句子的情况，必须通过变换文法的方法消除这类情况。如果某些文法经过变换后仍存在某一步推导能选择超过一个的正确候选式，则说明文法本身存在歧义，通常称为二义性。笔者将在3.1。3节中讨论文法的二义性问题，这里先不作深究。总之，读者必须明确一点，就是对于文法的任何一个合法句子而言，文法必须保证每一步推导过程中有且仅有一个候选式能够最终正确推导得到该句子。因此，选择哪个候选式替换非终结符最终得到的结果是不同的。要想正确推导得到句子，在每一步推导过程中，都必须选择那个唯一正确的候选式进行深入推导，否则，无法推导得到所需的句子。由于候选式的选择可能直接决定了是否能正确推导出给定句子，那么，如果选择了不合适的候选式可能会使推导过程回溯。例3-3中选择了E opl T候选式替换非终结符E，这是唯一正确的选择。读者可以尝试选择候选式T替换非终结符E，经过n步推导仍然无法推导出给定表达式。

推导过程可以判定给定句子是否符合文法。那么，模拟推导过程实现语法分析器的想法也就形成了。前面，已经分析了推导的过程，也发现了推导过程中的核心难点，即两个选择。构造基于推导的语法分析器就必须解决两个选择的问题，即非终结符的选择与候选式的选择。由于非终结符的选择并不会影响推导的结果，所以选择非终结符的问题就比较容易了。可以约定每一步推导都选择替换最左边或者最右边的非终结符，通常，这是最简单的选择方案。习惯上，将每次都选择替换最左边非终结符的推导过程称为最左推导(leftmost derivation)，例3-3的推导过程就是最左推导。而将每次都选择替换最右边非终结符的推导过程称为最右推导(rightmost derivation)。为了对句子进行确定性分析，编译技术只考虑最左推导、最右推导。至于候选式的选择就比较复杂了，笔者将在3.2节中详细讲述。

例3-4 最右推导实例。使用文法3-3验证表达式“3*5+(1-i)”是否合法？