上下文无关语言

推导树与二义性

推导树

所谓推导树，就是用图的方式表示一个句型的推导，可以直观的看出推导过程
从作业来看，画最左推导/最右推导基本是必考题型
推导树也很可能考

形式定义

设D是上下文无关语法 的推导树，满足：
- 根节点是S
- 枝节点标记是非终结符
- 叶节点标记是终结符或
- 标记为A的节点，有直接子孙 ，那么 是P的一个生成式
容易发现，推导树可以给出一个句子的推导过程，而叶节点就是这个句子。
因此，我们将从左到右的顺序，将叶子连成一个串，称为边缘

如图所示，即为句子的推导树
我们容易知道，在这个树中，边缘和句子是等价的，因此我们很容易推出以下的定理：
定理1 对于上下文无关语言 如果存在 当且仅当文法G中有一颗边缘为的树。

二义性

由上面的例子我们可以看出，对于一个句子来说，推导树可以有多个形式，这意味着可以通过不同的推导方式来得到这个句子。这种二义性是我们不想要的，因为它破坏了严谨性，因此我们规定一种默认的推导方式，确保无二义性。

最左推导和最右推导

即，在推导过程中，每次都对最左(右)的非终结符进行推导的过程，称为最左(右)推导。

文法和语言的二义性

应当指出，文法的二义性和语言的二义性是不同的，完全有可能有两个不同的文法G1，G2，其中一个有二义性，一个无二义性，却能产生相同的语言。一般来说，我们希望文法无二义性，这样在推导的过程是唯一的。

上下文无关文法的变换

删除无用符号

算法1 找出有用非终结符(可以推出终结符的非终结符)

大致过程可以这样描述：
1、首先N定义为空集
2、我们找到能推出终结符（这里是，推出的式子中只有有且仅有终结符，类似aB这样的是不行的）的非终结符，加入N
3、我们找能推出N中的非终结符的非终结符，加入N
4、直到加无可加，算法终止

算法2 找出有用符号(可以被推出的非终结符)

大致过程可以这样描述：
1、N’定义为
2、把能被N推出的非终结符加入N’中
3、重复2，直到加无可加为止
4、得到的N1为N和N‘的交集

删除无用符号的过程可以理解为，从结束的地方出发，找找有用的，再从出发的地方出发，找找有用的。把俩一交，就完事了。

删除生成式

大致过程可这样描述：
1、首先利用算法1找出可以推出的非终结符
2、对于每个非终结符，只要是能够推出的，都要对所有的生成式进行排列组合添加把该非终结符去掉的生成式
3、如果S是可以推出的非终结符，那么需要一个新的非终结符，，然后把S1加入N中
4、得到结果

消除单生成式

大致过程可描述如下：
1、对每个非终结符X，构造集合，其中包含所有X可以通过单生成式推出的非终结符
2、对于，如果存在不是单生成式，那么把加入P1中
3、最终得到P1
理解起来，其实就是一个代入的过程而已，但是这个算法可以程序化实现。

消除递归

首先给出递归的简单定义，即左侧和右侧有同样的非终结符。
如果形如，则称为左递归，若形如，则称为右递归，如果存在，则称G是循环的文法

消除左递归

消除直接递归的讲解可以参考链接~https://www.bilibili.com/video/BV1vMV2z6EeD

总体来说，就是把有左递归的部分，把递归的地方转移到了另一个非终结符上，形成右递归而已。
大致流程如下：
1、首先按照顺序排列非终结符，类似
2、接下来，我们从A1开始，先消去A1中的直接递归
3、消去之后，我们进入到下一个非终结符
4、然后，如果该非终结符的生成式中，最左侧有下标比他小的非终结符，那么进行带入
5、循环直到An为止

注意，文法的化简有一定的顺序

Chomsky范式和Greibatch范式

CNF

形式定义

上下文无关语法，生成式形式都为和，其中,，则G为CNF

CNF的转化问题

想把一个文法转化为CNF，有两个要点
1、生成式里如果有终结符和非终结符混合的，那么可以把终结符替换为非终结符
2、生成式中有超过三个非终结符的，可以替换为两个非终结符

GNF

形式定义

上下文无关语法，生成式形式都为且不包含生成式，其中,，则G为GNF

GNF的转化问题

1、先把文法转化为CNF
2、指定一个顺序，将N中所有的集合按照这个顺序排序
3、保留生成式中，由小下标生成式推得大下标生成式的
4、对于大下标推小下标的式子，就把推得的小下标的所有生成式带入小下标中，消去小下标即可
5、如此，对于某一个，当它被修正好之后，我们就用作为新的非终结符，替代掉，代表其已经被修正
6、在修正过之后，下标最大的A中，一定已经满足了GNF的形式定义的要求，把它代入到前面的地方就可以了

泵引理

泵引理是判断上下文无关语言的必要条件，因此只能用来证明某语言不是上下文无关语言

形式定义

如果语言是上下文无关语言，那么存在正整数，对，只要，就可以将z分成五部分，，满足：
1)
2)
3)

可以利用这个图来更好的理解一下上下文无关文法的泵引理的原因。
我们假设是CNF，一共具有m个非终结符，假设，那么此时的情况，一定是一颗二叉树。
对于二叉树而言，接收N的话，深度一定为，也就是说，其中一定有某一个非终结符重复了。我们假设在处重复，为重复的非终结符，那么我们假设处A推出的结果是，处推出的结果是，那么我们有：
显然，结果中包含
证毕