上下文无关文法

第一次学编译原理的时候就听到了这个名词，然后就稀里糊涂的开始学词法分析、语法分析、first集、follow集，然后就是各种算法，但是最近回过头来重新学编译原理，发现自己连上下文无关文法是什么都不是很清楚。

所以这篇博客主要是简单的说明上下文无关文法是什么，他的分类准则是什么，除了这个什么别的文法，他们分别有什么特点。这边不会形式化的证明，但是会指出他们的特点，限制，以及应用场景。

历史以及分类标准

历史早期，主要是语言学的发展，语言学家发现语言中存在一些基本的组织规则，但缺乏形式化的描述方法。

上世纪50年代，诺姆·乔姆斯基(Noam Chomsky)在研究自然语言时定义了文法的层级，分别是:

1. 0型文法，一种无限制文法

   1. 定义形式：α → β 其中 α 和 β 可以是任意的终结符和非终结符的组合字符串
   2. 一般只用在学术研究中

2. 1型文法，上下文有关文法。

   1. 定义形式：αAβ → αγβ ​其中 A 是非终结符，α、β 是上下文，γ 是非空字符串
   2. 简单来说就是产生式需要依赖上下文，比如对于英语中的系动词，am is are 他们的选择的跟上下文有关，这个文法可以用来辅助检测蛋白质结构。但是对于程序员来说不太需要关心这个事情。

3. 2型文法，上下文无关文法

   1. 定义形式：A → γ​，其中 A 是非终结符，γ 是终结符和非终结符的任意组合
   2. 上下文无关的意思是，我们不需要关心上下文，我们可以在任何地方应用我们的产生式，将他进行转换。 我们编程语言中的语法分析就是上下文无法文法，可以判断我们写的代码是否符合语法规范。

4. 3型文法，正则文法

   1. 定义形式：

      1. 右线性：A → aB 或 A → a
      2. 左线性：A → Ba 或 A → a
      3. 其中 A、B 是非终结符，a 是终结符

   2. 我们平时使用的正则表达式就是正则文法，但是他有很多限制，正如他的文法显示的，他必须在最左或者最右推导出一个终结符，这就导致他没有办法处理嵌套的场景。因为我们无法使用非终结符来保存嵌套状态

以上就是基本的分类，主要简单介绍什么是上下文无关文法。

‍