对于计算机科学的专业来说，编译原理是一门必修课。尽管在大学时代，我也研读过编译原理，但当时只看得云里雾里，不知所以。工作多年后，重新审视编程语言时有诸多疑问，例如编程语言与我们日常生活所说的自然语言有什么区别，为什么设计编程语言时不能设计的像自然语言那样通俗易懂，如果你去设计一门编程语言应该考虑些什么问题。编译原理有编程界屠龙技之说法，如果有一天通过编译原理创造出一门流行的编程语言，那么你会成为万人敬仰的屠龙者。好了，回到现实
语言分类
不管是编程语言还是自然语言其实都是语言，是人们交流的工具，不要把编程语言想的特殊化了，如果可以的话，我们也可以通过编程语言来进行日常交流，只不过远没有自然语言那么方便罢了。首先这里先讲一讲泛用的语言的分类学，在我们平时说话，我们讲的是中文，当我们去国外留学或者旅游，我们都会需要讲英文。不知道大家有没有这种经历，在国外时因为英文不是很好的时候，我们会把关键词凑起来这么一说，然后语法也不对，但是老外也听懂了。比如说 “很久不见”，我们就会说 “long time no see”，然后老外还觉得挺好用的，所有他们也就加语言里面了。这类的语言有一个特点，就是它的语法没有一个严格的定义，所以我们叫它做 “ 非形式化语言 ”，典型的代表就是我们平时说的这些。而在计算机里面，大部分的语言都是 “ 形式语言 ” —— 形式语言它的特性是有一个形式化定义，它是非常的严谨严格。实际上世界上的语言，总体来说，可分为三类：
非形式化语言（也叫自然语言，比如英语和汉语）
定义：采用自然语言表达的规范风格
半形式化语言（数学语言，公式符号等，即自然语言加特定的符号）
定义：采用具有确定语义定义并有严格语法的语言表达的规范风格。
形式化语言（逻辑语言）
定义：在完备数学概念基础上，采用具有确定语义定义并有严格语法的语言表达的规范风格
自然语言不用多说了，我们无时无刻不在使用，语文课从小到大也一直在学，主要是其他两种语言。半形式化语言和形式化语言是只在一些特定领域在会使用的语言，因此生活中不常见
半形式化语言
任何一个数学分支的语言都是在自然语言的基础上附加一些特定的符号，它们与自然语言相比更具形式化。因此，称它为半形式化的语言。数学语言作为一种特定的符号语言，与自然语言相比，它与算法建立了联系。因此，它还具有“可操作性”。法国数学家违达提出：我们可以用字母（即符号）表示已知量和未知量，并对此进行纯形式的操作，也即我们可以摆脱问题的具体内容，而从一般角度总结出普遍的算法。正如人们所熟悉的，我们可以按照以下的算法去求得任何一个一元一次方程的解：①去分母；②去括号；③移项；④合并同类项；⑤同除以未知数的系数。
许多数学家都认为的符号系统促进了整个数学的发展。特别地，数学家克莱因对代数学的情况写道：代数学上的进步是引进了较好的符号体系，这对它本身和分析的发展比 16 世纪技术的进步远为重要。事实上，采取了这一步，才使代数有可能成为一门科学。” （《古今数学思想》，第一册，第 301 页）正是在这种意义上，数学家迪多内认为：“好的符号往往伴随着易于使用它们的算法：我们把这理解为计算或常规的推论，就是说一旦确定之后就是永远如此，对它们的应用几乎是自动化的，不需要从头做起，这样，极为明显地简化了数学语言，并且可以集中注意力于证明的基本要素。”与此相反，“常常是由于缺乏能够说清楚真正实质的符号，数学的某个领域就得不到发展”历史上，第一个有意识地、系统地在数学中使用字母的学者是十六世纪法国数学家韦达。他的这一工作不仅推动了代数学的发展，而且对十七世纪的数学家和逻辑学家莱布尼茨启发很大。因此，使数学本身有一套好看的、通用的符号，成为莱布尼茨在数学研究中的努力追求。因此，莱布尼茨的工作，导致了他在数学符号发展史上占据着重要的地位。如：莱布尼茨本人创立的微积分符号体系。在他的符号体系中， dx 表示 x 的微分， ddx 和 dddx 分别表示 x 的二阶和三阶微分。
然而，我国在辛亥革命之前，由于没有采用国际上通用的数学符号体系。直到 1906 年，京师大学堂使用的教科书上，仍然用天、地、人、元表示未知数，用符号“ ⊥ ”和“|”分别表示加和减，分数则自上而下读。这种表示方法显然是极不方便的，因此，也就必然遭到淘汰。
形式化语言
建立逻辑的语言，使逻辑学象数学那样也有一套好看的、通用的符号，其思想也可以追溯到莱布尼茨。他认为，我们可以建立一种普遍的、没有歧义的语言，通过这种语言，就可以把推理转变为演算。一旦发生争论，我们只要坐下来，拿出纸和笔算一算就行了。这里，他实际上提出了数理逻辑的两个基本思想：构造形式语言和建立演算。 莱布尼茨的想法，实际上就是要将逻辑形式化。不过莱布尼茨没有实现他的两个设想。1879年，逻辑学家弗雷格发表了名著的《概念文字：一种模仿算术语言构造的纯思维的形式语言》。在这本书中，弗雷格借鉴了两种语言，一种是传统逻辑使用的语言，另一种是算术的语言。从而成功地构造了一种逻辑的形式语言，即：一种表意的符号语言，并且用这种语言建立了一个一阶谓词演算系统，实现了莱布尼茨提出建立一种普遍语言的思想。在形式语言里面也是分类的，其中一种就是 “ 乔姆斯基谱系 ”。
形式化语言分类 （乔姆斯基谱系）
- 0-型：无限制文法 —— 只要定义清楚了语言是什么样的。其描述能力相当于图灵机，可使用任何的语法描述形式
- 1-型：上下文相关文法 —— 同样的一个词、句的组合，它的上文、下文和内容相关的。其描述能力相当于线性有界自动机，这种文法的产生式规则取如 xSy -> xAy。也就是说，S推导出A是和上下文x, y相关的，即S只有在上下文x, y的环境中才能推导出A
- 2-型：上下文无关文法 —— 同样一个表达，不管放到哪里都是一样的意思。其描述能力相当于下推自动机，这种文法的产生式规则取如 S -> A。S可以无条件的推导出A，和上下文无关，上下文无关文法因此得名。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
- 3-型：正则文法 —— 能够被正则表达式去描述的一种文法。其描述能力相当于有穷自动机，语法形式如下:S -> Aa。其中最后一个a必须为非终结符。
在乔姆斯基谱系里面 0123 是一种包含关系，就是说一个上下文相关文法，它一定也属于 0-型，但是反过来就不一定了。因此，一般的文法至少都是0型文法，也就是说0型文法限制最少。1 , 2 , 3型文法都是在0型文法基础上加以限制形成。若将0型文法比作基类的话，1 , 2 , 3就是不断继承并加以限制得到的子类。四种类型的文法的主要特点：
| 文法 | 语言 | 自动机 | 产生式 |
|---|---|---|---|
| 0-型 | 递归可枚举语言 | 图灵机 | α→β |
| 1-型 | 上下文相关语言 | 线性有界自动机 | xSy → xAy |
| 2-型 | 上下文无关语言 | 下推自动机 | S → A |
| 3-型 | 正规语言 | 有限状态自动机 | S → Aa |
约束形成
通俗地说，在0型文法基础上加以条件的约束，α—>β 后者长度要大于前者。于是1型文法即上下文有关文法诞生了。再在此基础上加上条件限制，让α只能为变量串，不允许有终极符就有了上下文无关文法；再添加限制条件，也就是产生式的右端必须得有终极符。这就是正则文法。
文法定义
刚用比较通俗的话解释了四种形式化语法的分类，下面用文法定义来重新描述四种类型文法，首先什么是文法，说了半天好像还没解释这个概念，文法就是语言中的每个句子可以用严格定义的规则来构造。通俗的讲就是：根据一些指定的规则，来确定编程语言的语法，从而实现编译器的功能。对于文法的定义首先设文法G的一组规则（VN ,VT , P , S）
- VN：非终结符集，通常用大写字母表示
- VT： 终结符集，通常用小写字母表示（例如Java中的分号
;，右大括号}就是终结符），其中VT和VN不存在交集 - P ：产生式集合（规则集合，即VN和VT组成的表达式）
- S ：开始符号（识别符号）
下面定义中的大写字母表示的是非终结符,而小写字母表示的是终结符。
- 0-型：设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)且至少含有一个非终结符，而β∈(VN∪VT)，则G是一个0型文法。0型文法是这几类文法中，限制最少的一个
- 1-型：它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
- 2-型：2型文法是在1型文法的基础上,再满足：每一个α→β都有α是一个非终结符。如A→Ba,符合2型文法要求。
- 3-型：它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）
文法推导
文法定义中常见的就是 → 运算符，它表示的是文法的推导，形式文法的推导比较好理解，即按文法G中的规则P推导。文法推导分为最右推导和最左推导。其实就是不同的推导规则
最左推导：每步推导中只改写最左边的那个非终结符最右推导：每步推导中只改写最右边的那个非终结符，又称规范推导
下面举个例子来理解文法的推导，给定文法G(S)的一组规则：
| 规则推导 | 解释 |
|---|---|
| NP → NN | NP Aux NP | NP改写为NN或者NP Aux NP |
| NN → 鲁迅 | 文章 | NN改写为”鲁迅“或者”文章“ |
| Aux → 的 | Aux改写为”的“ |
| P → 关于 | P改写为”关于“ |
推导 S→PNP（这里的S表示文法的初始符Start，而不是句子。）
根据这一组文法规则，”关于鲁迅的文章“的最左推导为：
S⇒P NP⇒关于 NP⇒关于NP Aux NP⇒关于NN Aux NP⇒关于鲁迅 Aux NP⇒关于鲁迅的 NP⇒关于鲁迅的 NN⇒关于鲁迅的文章
根据这一组文法规则，”关于鲁迅的文章“的最左推导为：
S⇒P NP⇒P NP Aux NP⇒P NP Aux NN⇒P NP Aux 文章⇒P NP 的文章⇒P NN的文章⇒P 鲁迅的文章⇒关于鲁迅的文章
现代编程语言
- C++ 中，
*可能表达乘号或者指针，具体是哪个，取决于星号前面的标识符是否被声明为类型； - VB 中，
<可能是小于号，也可能是 XML 直接量的开始，取决于当前位置是否可以接受XML直接量； - Python 中，行首的
tab符和空格会根据上一行的行首空白以一定规则被处理成虚拟终结符 indent 或者 dedent； - JavaScript 中，
/可能是除号，也可能是正则表达式开头，处理方式类似于 VB，字符串模版中也需要特殊处理}，还有自动插入分号规则；
形式语言—— 用途分类
- 数据描述语言 —— 有些时候我们需要去存储一个粹的数据，本身是没有办法进行编程的
- JSON, HTML, XAML, SQL, CSS
- 编程语言
- C, C++, Java, C#, Python, Ruby, Perl, PHP, Go, Perl, Lisp, T-SQL, Clojure, Haskell, JavaScript, CoffeeScriptx
形式语言 —— 表达方式
- 声明式语言
- JSON, HTML, XAML, SQL, CSS, Lisp, Clojure, Haskell
- 命令型语言
- C, C++, Java, C#, Python, Ruby, Perl, JavaScript
编程语言的图灵完备性
- 命令式 —— 图灵机
- goto
- if 和 while
- 声明式 —— lambda
- 递归
- 图灵完备性 ：在可计算性理论里，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟单带图灵机，那么它是图灵完全的。这个词源于引入图灵机概念的数学家艾伦·图灵。虽然图灵机会受到储存能力的物理限制，图灵完全性通常指“具有无限存储能力的通用物理机器或编程语言”。
- 图灵机（Turing machine） ：又称确定型图灵机，是英国数学家艾伦·图灵于 1936 年提出的一种将人的计算行为抽象掉的数学逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
令式编程语言的设计方式
般来说我们的命令式语言可能有一些细微的结构上的不一致，但是它总体上来讲会分成5个层级。
- 原子级（Atom）—— 一个语言的最小的组成单位
- 关键字（Identifier）
- 字符/数字的直接量（Literal）
- 变量名（Variables）
- 表达式（Expression）—— 原子级结构通过运算符相连接和辅助符号形成
- 原子单位（Atom）
- 操作符（Operator）—— 加减乘除，拼接符等等
- 语法符（Punctuator）
- 语句（Statement）—— 表达式加上特定的标识符、关键字、符号形成一定的结构
- 表达式（Expression）
- 关键字（Keyword）
- 语法符（Punctuator）
- 结构化（Structure）—— 帮助我们组织、分块、分成不同的复用结构
- 函数（Function）
- 类（Class）
- 过程（Process）—— PASCAL 语言就会有 Process 的概念
- 命名空间（Namespace）—— C++ / PHP 中就会有 Namespace 的概念
- 程序（Program）—— 管理语言模块和安装
- 程序（Program）—— 实际执行的代码
- 模块（Module）—— 准备好被复用的模块
- 包（Package）
- 库（Library）
