先来一首网抑云防止抑郁。

预备

计算机基础知识纷繁复杂，我们在学习的时候一定要学会抽象这种思想，这里的抽象是指什么呢？就好比我们设计一个Golang包的时候，我们对外只提供关键的函数和结构体，使用者只关心这几个函数就能使用，而不用去理解具体的细节和实现方案，当别人基于这个包去开发其他包的时候，也是这样，对外提供关键函数，在在往上，别人的包也是基于这个包在开发了新的包，诸如此类层层抽象，最终完成一个庞大的软件。再来看看计算机的基础知识，从简单的晶体管抽象出各种逻辑门再到操作系统等等都是无穷无尽的层层抽象，如果我们学习编译原理遇到不懂的就去学习弄明白的话，那么你会在知识的海洋里迷失自我，就算给你几辈子的时间，你也不可能把所有细节全部弄清楚，我们应该习惯这种自然发展的规律，即选择好主线，对应其他细节的知识点我们可以大概只知道它是做什么的就行，明确好知识主线去学习。

上下文无关文法（context-free grammar, CFG）

上下文无关文法是描述程序语言语法的强有力的数学工具，可以理解为我们使用上下文无关文法来描述语法规则，在《编译原理粗浅学习笔记1预备知识》篇有简单介绍有关和无关文法，在上一篇也出现了正则文法，说实话，刚开始接触这些的时候一头雾水，只有不停的查资料，那么还有其他文法吗？？

• 3型文法：正则文法：词法结构
• 2型文法：上下文无关文法：语法结构
• 1型文法：上下文有关文法
• 0型文法：任意文法

上面四种文法也被称为乔姆斯基文法体系，他是一个数学家，为研究自然语言构建的一系列数学工具，感兴趣可以查阅相关文献。

为什么要用上下文无关文法来描述语法规则呢？

我们书写的程序其实就是一句一句的句子，由这些句子构成了一个程序（句子的集合），那么我们要如何去准确的描述这些集合的规则呢？比如程序里面的一个子句变量声明

int a = 2

该如何用规则来描述？？可以用正则文法吗？？ 其实正则文法属于3型文法，是无法做到准确描述各种规则的语法结构的，正则文法也只是上下文无关文法里面的一个子集， 也叫做线性文法（Linear Grammar），这里我们就要先来学习一下上下文无关文法之后 在来说说它和线性文法（正则文法）的区别。

先来看一个产生式

S –> AB
A –> aA | ε
B –> b | bB

ε 表示一个空句子，表示 A 可以用一个空句子来代替。 这个语法所能推导出的所有句子的集合为：

A : { ε, a, aa, aaa, ... }
B : { b, bb, bbb, ... }
S : { b, bb, bbb, ..., ab, abb, ..., aab, aabb, ... }

这里的文法可以用正则a*b+来描述, 现在来回忆下笔记1预备知识篇描述的上下文无关文法，文法中所有的产生式左边只有一个非终结符，S,A,B都是非终结符,右边是它的产生式,在语法解析的过程中，左边会被右边替代。如果替代之后还有非终结符，那么继续这个替代过程，直到最后全部都是终结符（Terminal），也就是 Token。只有终结符才可以成为 AST 的叶子节点。这个过程，也叫做推导（Derivation）过程。

推导也分为左推导和右推导

• 左推导---每一次选择最左边的终结符进行推导
• 右推导---每一次选择最右边的终结符进行推导

像上面我们在产生式S –> AB中，向下推导时先选择A就是左推导，先选择B就是右推导。

再来看看一个数学表达式

Expr -> Expr op Expr | (Expr) | number
op   -> + - * /

其中的 number 是词法分析得到的一个 token ，它在词法分析中用正则表达式 [0-9]+ 表示。

经过观察可知，此语法可以推导出所有的整数算术表达式：

Expr : { 123, 25 + 24, 78 - 34, 12 * ( 23 + 9 ), ... }

可以看出，上下文无关文法可以采用递归的形式推导，比正则表达式的表达能力要强大的多。

上下文无关文法 CFG是一个四元组(N,Σ,P,S) ，下面我们看一下CFG的组成：

• N 有限个非终结符的集合；
• Σ 有限个终结符的集合；
• P 有限个生产规则的集合；
• S 非终结符集合中唯一的开始符号

G = (N,Σ,P,S)

S –> AB
A –> aA | ε
B –> b | bB

N 可以理解为有限的非终结符，即上面的SAB

Σ 理解为有限的 Token 集合,即上面的abε

P 理解为语法规则，即一条条的产生式

S 唯一的开始符号

在学习 CFG 的时候，我们用小写字母表示终结符，大写字母表示非终结符。

---

对于这些概念大概有个印象，这块也有很多资料可以查询，可以翻阅下面资料

• https://www.zhihu.com/question/21833944
• https://pandolia.net/tinyc/ch9_context_free_grammar.html
• http://bakkot.github.io/cfgrammar-tool/

最后一个是一个在线的上下文无关文法演示，可以多练习，表达式 “|” 表示 或,如数学表达式

S->SOS|(S)|n
O->+|-|*|/

线性文法（Linear Grammar）（正则文法）

上面说正则文法就是线性文法，是上下文无关文法的一个子集，它的特点是产生式的右边部分最多只有一个非终结符，比如 X->aYb，其中 a 和 b 是终结符。

正则表达式 a[a-zA-Z0-9]*bc 也可以写成产生式的格式。

S0 -> aS1bc          
S1 -> [a-zA-Z0-9]S1  
S1 -> ε

EBNF(扩展巴科斯范式)

我们已经了解到上下文无关法，那么我们一般要怎样书写这些规则，这就要介绍 EBNF(BNF 的拓展)。这个就是表示上下文无关法的语言 BNF 规定书写文法规则如下

=            : 表示在其左右两边任选一项，相当于"OR"的意思。
 ,            :表示串接。
 (* ... *)    :表示注释
 :            : 是“被定义为”的意思
 "..."/'...'  : 终结符
 [...]        : 选项，最多出现一次
 {...}        : 重复项，任意次数，包括 0 次
 (...)        : 分组  注意分组是()  终结符()要写成'(' ')'
 ;            : 终止符号
 |            : 并列选项，只能选一个

那我们看下使用 EBNF 怎么来定义四则运算的语法， Expr -> Expr op Expr | (Expr) | number

expr  : expr sign expr | '(' expr ')' | number
sign  : '+'|'-'|'*'|'/'
number: digit {digit}
digit : 0|1|2|3|4|5|6|7|8|9

还有一点，编程语言其实是上下文相关的，比如使用变量必须先定义，但是语法分析阶段是不使用上下文相关文法的，我们一般不管上下文之间的依赖关系，这样能使得语法分析的任务更简单。而对于上下文相关的情况，则放到语义分析阶段再去处理。

这篇我们学习了语法分析中关键上下文无关无法，那么接下来就要开始结合实例学习递归下降算法。