[编译原理]如何判断某文法的二义性以及找到文法对应的语言

随便说说

这学期开编译原理课了，觉得还挺有意思的，写点博客记录记录。

如何根据文法找到其对应生成的语言

如图所示，假设我们现在有文法如下：

\[G(Z)：Z->aZb|ab \]

根据文法产生语言的定义，语言是文法产生的句子的全体，用集合表示如下：

\[L(G)=\left \{ α|S\stackrel+\Rightarrow α \&α∈V_T^*\right \} \]

而句子的定义则是由文法的开始符S出发，经过1步或有限步推导出来的符号串并且该符号串全部由终结符组成。
在上述白板题目中，由文法可知，开始符为G，有两个产生式，分别是Z->aZb和Z->ab
采用递归的方式，任意组合两种产生式，进行一步或有限步的推导，使得声称式的右侧不含有非终结符。
终结符就是语言中不可再分的基本符号，例如一个语言的字母表
而非终结符也叫语法变量，代表语法实体或语法范畴，是一个一定的语法概念，可以是一个类、一个集合。
过程也就很简单了，如上图中白板所示即可，但最终需要归纳，因为有一种推导的右侧时刻会存在非终结符Z，所以可以无限添加a和b的数量。

如何判断某文法的二义性

判断二义性的前提是需要知道最左推导和最右推导。
最左推导的定义是，在我们每次使用产生式推导的过程中，肯定会遇到右侧存在非终结符的情况，非终结符会存在任意位置，其中如果我们每次推导都替换掉从右往左的第一个非终结符，那么本次推导就是一次最右推导，反之则为最左推导。
而判断文法的二义性则是在此基础上进行推导：
如果文法G[S]的一个句子能够找到两种不同的最左推导或最右推导，也就是说存在两棵不同的语法树，那么这个句子就是二义性的，而文法若存在一个有二义性的句子，那么这个文法也是二义性的。
假设有文法如下：

\[G\left [ S \right ] :S->if\space b\space S \]

\[S->if\space b\space S \space else \space S \]

\[S->a \]

根据白板上书写的两种最右推导，可以知道句子if b if b a else a是个二义性的句子，因为有两种最右推导都可以最终得到这个句子，那么对应的这个文法也就是二义性的了。