如果你敲累了代码，想喝喝咖啡，顺便看点儿可以当佐料的文章那本文应该比较适合现在的你。(•̀ᴗ•́)و ̑̑

我们一天天都在和代码打交道，但是你了解代码的运行原理么？为什么你的一行代码就能被执行出五花八门的效果嘞？

其实代码这玩意儿就是一门语言。是的，你可以看成和中文、英文等语言平等的存在。是语言就得有语言的解析规则，不懂得规则自然无法理解语言的意思。就跟看没字幕的美剧一样，真是痛苦。╮(╯﹏╰)╭

中文有中文的语义、语法、句子、句法、文法，那么编程语言也有自己的语言系统。

我们知道，我们写的代码被编译器或者解释器所执行，那它们是按照什么文法来理解你的代码呢？这就是文法。

本文也不会深入去解析文法，不然可以直接转语言学了（笑~）。本文只是简单介绍文法的一些概念。如果您喝着咖啡，看完之后，能有些许收获，微微一笑，那本文的目的也就达到了。^_^

工欲善其事必先利其器。在谈文法之前，我们先介绍几个概念。

 

一.文法涉及的几个简单概念

 

假设Σ是一个有限的字母表集合，它的每一元素都是一个符号。Σ上的一个符号串就是指由Σ中的符号组成的一个有限序列。如果一个符号串不包含任何符号，就叫它空串，记为ε。现在再定义一个集合U和V的连接积的概念：

　　　　　　　　UV = {αβ | α∈U,β∈V}

比如A = {a,b}，B = {1,2}，则AB={a1,a2,b1,b2}。很简单的概念，是不是？

那么相信你也能知道V1，V2等的幂的概念了。

还有几个：



ok，定义结束，现在来谈谈咱们本次的主角——文法。一个比较拗口的定义，


文法是描述语言的语法结构的形式规则（即语法规则）。


这啥意思啊？可能你一脸黑人问号……



其实，就是指怎么由一堆符号组成一个有含义的句子的规则和协议。

所谓的上下文无关文法就是文法的一种，它所定义的语法单位是完全上下文无关的。比如我们在程序语言 中，碰到一个算数表达式时，我们完全可以对它“就事论事”，不用去考虑它上下有啥东西。当然，在自然语言（中文、英文等）中，一个语法单位（字、词、句子）肯定和上下文环境有关，不然当年我们中文考试的阅读理解题也就不会出现“根据上下文，解释xx句子的含意”了。(ˇˍˇ) 想～

所以说，上下文无关文法不能用来描述自然语言，但是对于当今的程序语言来说，上下文无关文法基本够用了。下文中的“文法”，如果没有特殊说明，都是之指“上下文无关文法”。



下面类比自然语言的具体例子，谈谈我们今天要说的文法。

一个英文句子：  


He gave me a book.


这个句子满足英语的语法规则，是一个语法正确的句子。如果我们用“→”表示“由...组成”或者“定义为”，按照我们中学的语法，可以分解一下这个句子：



这样，通过这样的一个个规则（又叫“产生式”），就把一个句子分解到了单词的层次。或者这么说，有了这些规则，我们可以这么干：



我们可以画一个更形象的图（语法分析树）来说明这种推导。



上面定义英文句子的规则就可以说是一个上下文无关文法。其中，<句子>被称为开始符号，<主语><谓语><代词>之类的被称为非终结符号，He、gave之类的被称为终结符号。

归纳起来，一个上下文无关文法G包括四个部分：终结符号，非终结符号，开始符号，产生式。

终结符号就是一门语言中最基本的符号。在程序语言中，基本字、标识符、常数、运算符号等都算终结符号。

非终结符号更像一个抽象的集合，比如“算数表达式”、“赋值句”都可以看做非终结符号。

产生式就是推导规则。

下面上精确定义：



 

二.递归定义的例子

 

有时候，只用一个产生式是不足以定义一个语法单位的，需要几个产生式的相互配合。有时候会需要递归的形式。举个栗子：



假设要定义一类含有+、*的算术表达式，这个定义可以这么说：

变量是一个算术表达式；
	
如果E1和E2是算术表达式，那么E1+E2、E1*E2、（E1）也是算术表达式。
我们用产生式的形式描述它：

E→i
	
E→E+E
	
E→E*E
	
E→(E)
其中 E 代表算术表达式， i 代表变量。这四个产生式的全体才定义了什么是“算术表达式”。后三个都是递归的形式。

还可以简化为：E→i | E+E | E*E | (E)。其中的“|”代表“或”，是一种元语言符号。

 

三.文法与语言的推导

 

假设G是一个文法，S是开始符号，如果S经过零步或者若干步推出α，那么称α是一个句型。只包含终结符号的句型是一个句子。文法G产生的所有句子构成一门语言，记为L（G）。

那么怎么从文法推导出它代表的语言嘞？

为了方便，我们引入一些符号。



方法：把产生式看成替换规则，把当前符号串中的非终结符号用其产生式右边的符号来替换。



 再看有文法G2->语言L（G2）例子。



推导过程如下：



语言L（G2）-> G2 的例子。



由上面的两个例子我们可以知道，一个文法可以唯一确定一个语言，但是一个语言不一定唯一对应一个文法。

 

四.语法分析树与二义性

 

我们发现从一个句型到另一个句型的推导过程不是唯一的。例如从E+E->i+i，存在两个推导过程：

E+E->E+i->i+i  最右推导，每个推导过程都是从最右边的非终结符号的替换开始
	
E+E->i+E->i+i  最左推导，每个推导过程都是从最左边的非终结符号的替换开始
当然为了对句子的结构进行一个确定性的分析，我们一般只考虑最左推导或者最右推导。

前面我们提到过用一种树形的图示来表示这个句型的推导过程，这棵树就被称为”语法分析树“，简称”语法树“。

比如从E->(i+i) 的过程：



对于一个文法，如果它的某些句子对应两棵不同的语法树，这个文法就属于“二义性文法”。



注意，文法的二义性和我们通常所说的语言的二义性不同，我们可能有两个不同的文法G1，G2，一个是二义性，一个是非二义性，但是可能L（G1） = L（G2）。对于程序语言来说，我们常常希望它的文法是非二义性的，但是，只要我们能够控制和驾驭文法的二义性，文法二义性的存在也不一定是坏事。

现在已经证明了，文法二义性是不可判定的。也就是说不存在一个算法，在有限步骤内算出一个文法是不是二义性的。我们能做的事儿，就是找一组充分条件来说明非二义性。比如，规定运算符号的优先级和结合性。

对于我们上面使用的那个文法：E->E+E | (E) | E*E | i   

如果限定*的优先级高于+，并且都是左结合的，那么上述文法就变成了非二义性文法。读者大大可以试试推导E->(i*i+i)。

什么是文法？我们从一个自然语言的例子讲起：

                                    

这是一个简化版本的英文文法。比如一个句子是由名词短语和动词短语构成的。名词短语由形容词和名词短语构成。从这个例子中我们能够看出语法的基本构成。用尖括号括起来的部分是语法成分，而没有被尖括号括起来的部分是语言的基本符号。英文的基本符号就是单词了。

那么编译语言的文法形式化定义是什么呢？

                                                                 

文法G = （Vt, Vn, P, S）是由四元组Vt,Vn，P,S所构成的。

其中：

Vt是终结符集合，是文法定义语言的基本符号，就像是英文中的单词一样。

Vn是非终结符。用来表示语法成分的符号，类似上面的<名词短语>，也就是语法变量。

P是产生式。描述了终结符和非终结符组合成串的方法。表示形式是：α -> β， α至少要包含一个非终结符。

S是开始符号。是一个非终结符，是一个文法的最大的语法成分。就如同上面的<句子>

例如：

                                                                 

上面这张图中描述的是加法乘法表达式的文法。其中我们能够看出，终结符Vt = {id, + * (,)}这些都是最终的一个一个语法不能被替换的元素；非终结符是E，他表示表达式，它可以被替换成各种数字等等。产生式P包含四种，可以被替换成加法，乘法，括号以及单独的数字。S开始符号是E,因为只有这一个非终结符，自然就是最大的了。

一般来说，第一个产生式的左部那个非终结符就是开始符号。

根据上课内容顺序写的博客，并不是按照书的目录来的

使用龙书以及编译程序设计原理（第二版）金成植、金英编著

老师的PPT是英文的，我自己随便翻的，不一定对




文章目录
语法分析parsing
语法分析过程
语法分析基础知识
语法分析方法分类
上下文无关文法
什么是文法
乔姆斯基文法分类
上下文无关文法
例子
语法分析书和抽象语法树
语法树
二义性
简单语言的语法







语法分析parsing

知识图谱








语法分析过程




语法分析基础知识



语法分析器的功能
输入：词法单元/词法单元序列

输出：语法结构的内在表达式

过程：

  读取词法单元

  生成语法结构——语法树，根据语法定义（上下文无关文法）

  检查语法错误


语法结构
用来描述一个明确定义的程序的结构

程序
声明

   常数声明

  类型声明

  变量声明

  程序/函数声明
主体
声明（赋值，条件语句，循环，函数调用）
表达式（算数，逻辑，布尔）

 

语法错误
不同类型的语法错误：

后继单词错误
标识符或者常量错
关键字错
开始单词错
括号配对错



处理语法错误：

立即退出，不实际
错误恢复
错误修补
错误改正
没有完美的办法





语法分析方法分类



通用于任何语法的语法分析方法（低效）

  Cocke-Younger-Kasami算法

  Earley’s 算法

自顶向下语法分析方法（有限制，可预测的）

  递归下降法  recursive descendent parsing

  LL(K)  – K=1

自底向上语法分析方法（有限制，归约）

  SLR(k)

  LR(k)

  LALR(k)

  简单优先关系法






上下文无关文法




什么是文法

文法是表示无穷字符串集的强有力的一种有限方式
文法G  (VT, VN, S, P)

  VT 是一个有限的终极符集合

  VN是一个有限的非终极符集合

  S是文法的开始符

  P是产生式的集合

每个生成规则都有以下形式






乔姆斯基文法分类



文法的分类

O型文法: 也称为短语文法，其产生式具有形式:

α→β，其中α,β∈(VT∪VN)*，并且α至少含一个非终极符;


1型文法: 也称为上下文有关文法。其产生式形式为：

αAβ→αuβ，A∈VN，u为非空串，它是0型文法的特例，即要求|α| ≤ |β|；


2型文法: 也称为上下文无关文法。

它是1型文法的特例，即要求产生式左部是一个非终极符: A→β


3型文法: 也称为正则文法。

它是2型文法的特例，即其产生式的右部至多有两个符号，而且具有下面形式之一:
A →a ，A →a B, 其中A,B∈VN ，a∈VT





上下文无关文法与正则表达式
正则表达式(a|b)*abb

文法：A0 → aA0|bA0|aA1

      A1 → bA2

      A2 →bA3

      A3→ ε


文法的分类
描述能力

  0型文法 > 1型文法 > 2型文法 > 3型文法

对应自动机

  0型文法：图灵机

  1型文法：线性有界自动机

  2型文法：下推自动机

  3型文法：有限自动机




上下文无关文法

上下文无关文法

Context Free Grammar(CFG)
定义为四元组(VT,VN,S,P)

  VT是有限的终极符集合

  VN是有限的非终极符集合

  S是开始符，S∈ VN

  P是产生式的集合，且具有下面的形式：

    A→X1X2…Xn

  其中A∈VN，Xi∈ (VT∪VN) ，右部可空。


一些通常的符号变量
通常情况下

{A,B,…,Z}用来表示非终极符
{a,b,…,z}用来表示终极符
{α,β,…}用来表示字符串
ε用来表示空字符串



推导
如果有一个产生式A→β，我们得到αAγ=>αβγ        =>代表用A→β一步推导

我们可以说αβγ 是αAγ推导的
=>的含义是，使用一条规则，代替=>左边的某个符号，产生=>右端的符号串




扩展巴克斯范式



文法转换的一些算法
文法等价变化：L(G1)=L(G2)

增补文法（增光文法）：开始符不能出现在产生式的右侧

 Z→S

消除公共前缀

公共前缀    A→αβ1| … | αβn | γ1 | … | γm

提取公因子     A→αA’ |  γ1 | … | γm     A’ → β1 | … |  βn






例子



例子1
VT={i, n, +, , (, )}

VN={E, T, F}

S=E

P:{ E→T  E→E+T  T→F  T→TF  F→(E)  F→i  F→n }
  

      


例子2
算术表达式

VT={id, num, (, ), +, -, *, /}

VN={Exp}

S=Exp

P:{ Exp→Exp+Exp  Exp→Exp-Exp  Exp→Exp * Exp  Exp→Exp/Exp  Exp→(Exp)  Exp→id  Exp→num }


例子3
程序

VT={VarDec, TypeDec, ConstDec, MainFun, FunDec}

VN={Program, Dec, Decs}

S=Program

P:{ Program→Dec MainFun Decs  Dec→ε  Dec→VarDec  Dec→ConstDec  Dec→FunDec  Dec→TypeDec  Decs→Dec   Decs→Decs;Dec}






语法分析书和抽象语法树



问题：推导是从开始符构造一个句子的方法

 许多推导来自同一个句子

 不能唯一地代表句子的结构

语法书：表示一个句子的结构的方法
依旧是上面的例子



语法树



一颗使用上下文无关文法的有标号树

根必须是开始符的标号

每一个节点都是一个与之相关联的符号

每个叶子必须是一个终极符的标签

对于每一个与非终极符A相关的节点，都有n个儿子，从左到右他们一起与符号B1,B2,…,Bn相关，必须有个产生式A→B1B2…Bn






二义性


二义性文法

对于一个文法G，如果存在一个句子有不止一颗语法树，G被称为二义性文法

二义性文法是不可判定的

解决方案1：重写文法

解决方案2：制定一个语法分析树作为推荐的






简单语言的语法


C0程序的结构

编译原理START—龙书虎书鲸书

什么是龙书虎书鲸书



龙书

英文名：《Compilers: Principles, Techniques, and Tools 》 

中文名：《编译原理技术和工具》 

作者 ：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman  

下载地址：https://download.csdn.net/download/diehuang3426/10283590 

简介：此书全面、深入地探讨了编译器设计方面的重要主题，包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术，并在相关章节中给出大量的实例。与上一版相比，本书进行了全面的修订，涵盖了编译器开发方面的最新进展。每章中都提供了大量的系统及参考文献。因书封面初始为恐龙和骑士，故亦叫做龙书。 

目录：https://book.douban.com/subject/3296317/ 

第一版 


第二版 


中文版 




虎书

英文名：Modern Compiler Implementation in C  

作者：Andrew W.Appel,with Jens Palsberg  

中文名：现代编译原理-C语言描述  

简介：《现代编译原理:C语言描述》全面讲述了现代编译器的结构、编译算法和实现方法，是Andrew w．Apple的“虎书”——Modern Compiler Implementation——“红、蓝、绿”三序列之一。这三本书的内容基本相同。但是使用不同的语言来实现书中给出的一个编译器。本书使用的是更适合广大读者的c语言，而另外两本书分别采用ML语言和Java语言。本书的另一个特点是增加了一些其他编译原理教科书没有涉及的内容。前端增加了面向对象的程序设计语言、函数式程序设计语言等现代语言的编译实现方法，后端增加了针对现代计算机体系结构特征的一些比较成熟的优化方法。这部分内容展现了现代商业编译器需解决的一些关键问题，开拓了学生的视野，为学生未来进行更深入的研究奠定了基础。 

《现代编译原理:C语言描述》全面讲述了现代编译器的各个组成部分，包括词法分析、语法分析、抽象语法、语义检查、中间代码表示、指令选择、数据流分析、寄存器分配以及运行时系统等。全书分成两部分，第一部分是编译的基础知识，适用于第一门编译原理课程(一个学期)；第二部分是高级主题，包括面向对象语言和函数语言、垃圾收集、循环优化、ssA(静态单赋值)形式、循环调度、存储结构优化等，适合于后续课程或研究生教学。书中专门为学生提供了一个用C语言编写的实习项目，包括前端和后端设计，学生可以在一学期内创建一个功能完整的编译器 

目录：https://book.douban.com/subject/1806974/ 

下载地址：https://download.csdn.net/download/diehuang3426/10283582 


中文版 




鲸书

原名：Advanced Compiler Design  andImplementation 

作者：Steven S.Muchnick 

中文名：高级编译器设计与实现 

简介：此书是经典的编译器著作，与“龙书”齐名。书中针对现代语言和体系结构全面介绍了编译器设计与实现的高级论题，从编译器的基础领域中的高级问题开始，然后深入讨论了各种重要的代码优化。本书专为编译器专业人士和计算机专业本科生，研究生编写，在设计和实现高度优化的编译器以及确定优化的重要性和实现优化的最有效的方法等方面，为读者提供了非常有价值的指导。 

目录：https://book.douban.com/subject/1128349/ 

下载地址：https://download.csdn.net/download/diehuang3426/10283594 


中文版 




总结

龙书全，偏理论。 

鲸书比龙书偏后端，也偏理论。 

虎书也全，是龙书和鲸书结合之后的简化版，重实践。 

粗略之写，现在在看编译原理，其他等以后读过了，有一定理解来补。