3A.2 文法
自然语言有明确的语法，用来约束如何构建一个合法的句子。程序语言也一样，这个控制程序结构的规则叫着文法。文法是用来定义形式语言结构的规则，其规范的定义如下：
概括地说，文法就是生成符号串的规则。
程序语言的文法通常使用一种叫着上下文无关文法的形式来表示。其对产生式做了如下限制：α -> β 中，α 只能是一个非终结符号。这也是“上下文无关”的意义：使用产生式将任意非终结符号 A 替换为其他符号串时，跟 A 所在的位置、以及 A 旁边的符号无关。
例如下面文法就是上下文无关文法，用来生成任意的合法括号对：
S -> (S) | SS | ()其中：
对编译器而言，任何源程序都是一个字符串，程序语言的文法确定了程序的合法结构。只是程序文法中的终结符号不是单个字母，而是词法分析的输出结果：Token
通过文法生成一个字符串的整个过程被称为一个推导。考虑上面生成括号对的文法：
S ->（S）-> （SS）->（（）S）->（（）（））就是一个推导。- 最左推导 每次都使用最左边的非终结符号进行推倒的过程，例如下面就是一个最左推导：
S -> SS ->（）S ->（）（S）->（）（（）） - 最右推导 每次都使用最右边的非终结符号进行推倒的过程，例如下面就是一个最右推导：
S -> SS -> S（S）-> S（（））->（）（（））
解析树是一个推导过程 的可视化，其叶子节点都是终结符号，中间节点都是非终结符号，叶子节点从左到右的排列就是被推导的终结符号串。如下例：
推导：
S -> SS -> S（S）-> S(())->()(())解析树：
Parse Tree
解析树只反映了整个字符串的推导方式，并没有体现其推导顺序。例如根据上面的解析树无法得知采用的是最左推导还是最右推导。