这学期开编译原理课了,觉得还挺有意思的,写点博客记录记录。
如图所示,假设我们现在有文法如下:
根据文法产生语言的定义,语言是文法产生的句子的全体,用集合表示如下:
而句子的定义则是由文法的开始符S出发,经过1步或有限步推导出来的符号串并且该符号串全部由终结符组成。
在上述白板题目中,由文法可知,开始符为G,有两个产生式,分别是Z->aZb和Z->ab
采用递归的方式,任意组合两种产生式,进行一步或有限步的推导,使得声称式的右侧不含有非终结符。
终结符就是语言中不可再分的基本符号,例如一个语言的字母表
而非终结符也叫语法变量,代表语法实体或语法范畴,是一个一定的语法概念,可以是一个类、一个集合。
过程也就很简单了,如上图中白板所示即可,但最终需要归纳,因为有一种推导的右侧时刻会存在非终结符Z,所以可以无限添加a和b的数量。
判断二义性的前提是需要知道最左推导和最右推导。
最左推导的定义是,在我们每次使用产生式推导的过程中,肯定会遇到右侧存在非终结符的情况,非终结符会存在任意位置,其中如果我们每次推导都替换掉从右往左的第一个非终结符,那么本次推导就是一次最右推导,反之则为最左推导。
而判断文法的二义性则是在此基础上进行推导:
如果文法G[S]的一个句子能够找到两种不同的最左推导或最右推导,也就是说存在两棵不同的语法树,那么这个句子就是二义性的,而文法若存在一个有二义性的句子,那么这个文法也是二义性的。
假设有文法如下:
根据白板上书写的两种最右推导,可以知道句子if b if b a else a是个二义性的句子,因为有两种最右推导都可以最终得到这个句子,那么对应的这个文法也就是二义性的了。