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

本文主要是介绍[编译原理]如何判断某文法的二义性以及找到文法对应的语言，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

随便说说

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

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

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

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

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

如何判断某文法的二义性

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

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

这篇关于[编译原理]如何判断某文法的二义性以及找到文法对应的语言的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！