随便说说

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

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

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

：：�(�)：�−>���|��

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

�(�)={�|�⇒+�&�∈��∗}

而句子的定义则是由文法的开始符S出发，经过1步或有限步推导出来的符号串并且该符号串全部由终结符组成。

在上述白板题目中，由文法可知，开始符为G，有两个产生式，分别是Z->aZb和Z->ab

采用递归的方式，任意组合两种产生式，进行一步或有限步的推导，使得声称式的右侧不含有非终结符。

终结符就是语言中不可再分的基本符号，例如一个语言的字母表

而非终结符也叫语法变量，代表语法实体或语法范畴，是一个一定的语法概念，可以是一个类、一个集合。

过程也就很简单了，如上图中白板所示即可，但最终需要归纳，因为有一种推导的右侧时刻会存在非终结符Z，所以可以无限添加a和b的数量。

如何判断某文法的二义性

判断二义性的前提是需要知道最左推导和最右推导。

最左推导的定义是，在我们每次使用产生式推导的过程中，肯定会遇到右侧存在非终结符的情况，非终结符会存在任意位置，其中如果我们每次推导都替换掉从右往左的第一个非终结符，那么本次推导就是一次最右推导，反之则为最左推导。

而判断文法的二义性则是在此基础上进行推导：

如果文法G[S]的一个句子能够找到两种不同的最左推导或最右推导，也就是说存在两棵不同的语法树，那么这个句子就是二义性的，而文法若存在一个有二义性的句子，那么这个文法也是二义性的。

假设有文法如下：

�[�]:�−>�� � �

�−>�� � � ���� �

�−>�

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