[编译原理]如何判断某文法的二义性以及找到文法对应的语言
2023-04-18 15:27:25 时间
随便说说
这学期开编译原理课了,觉得还挺有意思的,写点博客记录记录。
如何根据文法找到其对应生成的语言
如图所示,假设我们现在有文法如下:
[G(Z):Z->aZb|ab
]
根据文法产生语言的定义,语言是文法产生的句子的全体,用集合表示如下:
[L(G)=left { α|Sstackrel+Rightarrow α &α∈V_T^*
ight }
]
而句子的定义则是由文法的开始符S出发,经过1步或有限步推导出来的符号串并且该符号串全部由终结符组成。
在上述白板题目中,由文法可知,开始符为G,有两个产生式,分别是Z->aZb和Z->ab
采用递归的方式,任意组合两种产生式,进行一步或有限步的推导,使得声称式的右侧不含有非终结符。
终结符就是语言中不可再分的基本符号,例如一个语言的字母表
而非终结符也叫语法变量,代表语法实体或语法范畴,是一个一定的语法概念,可以是一个类、一个集合。
过程也就很简单了,如上图中白板所示即可,但最终需要归纳,因为有一种推导的右侧时刻会存在非终结符Z,所以可以无限添加a和b的数量。
如何判断某文法的二义性
判断二义性的前提是需要知道最左推导和最右推导。
最左推导的定义是,在我们每次使用产生式推导的过程中,肯定会遇到右侧存在非终结符的情况,非终结符会存在任意位置,其中如果我们每次推导都替换掉从右往左的第一个非终结符,那么本次推导就是一次最右推导,反之则为最左推导。
而判断文法的二义性则是在此基础上进行推导:
如果文法G[S]的一个句子能够找到两种不同的最左推导或最右推导,也就是说存在两棵不同的语法树,那么这个句子就是二义性的,而文法若存在一个有二义性的句子,那么这个文法也是二义性的。
假设有文法如下:
[Gleft [ S
ight ] :S->ifspace bspace S
]
[S->ifspace bspace S space else space S
]
[S->a
]
根据白板上书写的两种最右推导,可以知道句子if b if b a else a是个二义性的句子,因为有两种最右推导都可以最终得到这个句子,那么对应的这个文法也就是二义性的了。
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击