有的时候,灵感的出现真不一定让人感觉很舒服

刘地 发布于 2012/11/30 00:40
阅读 460
收藏 0

最近一直在研究语法分析,因为bnf我一直弄不明白,更喜欢自底向上的“堆建”方法,这个方法可以很轻松的处理表达式和语句,也尝试着做了个实现,但是这个方法的缺点,标识符的声明之类的有顺序要求的“操作时状态”,不好处理,让我很发愁。

直到我突然觉悟,bnf文法不就是一种特殊的类正则表达式的东西吗?只不过这个包括了多个规则,而这一点,我们可以使用映射表来实现,如是,就可以将bnf转化为一个非常简单的附带字典的类正则结构。

我曾经自己做出过正则表达式的c++实现,采用的是“串联-并联”思想,结合递归实现正则表达式,而匹配时,并联取第一个匹配,串联则采用回溯算法,这个实现很简单,但是还算能用,正则表达式的大部分功能都实现了,没有实现的是:匹配但不消耗字符串、不匹配才匹配、分组实现了但不能个别提取和命名(默认全部按数字编号了)。(那个时候我就不知道那些高级用法)

这个bnf完全可以按这个思路来嘛,而且bnf是很规则的东西,因此甚至不需要回溯,这就更加简单了。而且python的表处理相当不错,按这个想法弄出来一个实现,总共也不过200行代码左右,花了2个多小时,还主要是浪费在输出列表的去嵌套上了。

好吧,一个灵感直接让我花了2-3天做的从底向上的版本(未实现),心情真奇怪。

然后,半小时前,睡前,我思考正则表达式时(因为bnf联想过去的,打算完善一下),对正则表达式默认贪婪原则很奇怪,因为回溯法显然更适合非贪婪模式,事实上我的实现就是默认的非贪婪模式的,贪婪模式相当困难,想来想去,突然意识到,正统的正则表达式莫非是右递归的?

妹!二叉树!如果采用二叉树这种数据结构的话,正则表达式的实现就极为简单了!而且二叉树是我非常熟悉非常擅长的数据结构!那么我这些时间、这些功夫都是干啥了啊!

虽然灵感很棒,可是心情真难过!为什么来的这么晚!

加载中
0
刘地
刘地
我是野路子,编程储备偏科很严重,不知道你们有没有这种情况,是不是野路子这种情况更多一些?
0
水牛叔叔
水牛叔叔
你的东西能写个详细的博客来分享么?一来你可以备忘,二来我很想看。以前看编译原理没人交流,资料又不好找,所以不太懂,但是还是很想把它看懂。
0
uian2000
uian2000
野路子就是干啥储备啥。挤时间看书吧,共勉
0
明月照大江
明月照大江
总要走那么几条弯路才叫折腾~!
0
leo108
leo108
楼主这野路子感觉比大多数科班出身的人牛逼多了,他们会考试,楼主会写代码。
0
曾建凯
曾建凯

结论有时候很简单,简单到好像之前拍拍脑门就该想得到。但其实重要的是你经历了一次思考——摸索——升华的过程,现实中大多的问题,没有具体的指引,或者是所谓“指引”其实只适合部分、有限的环境,并不适用你所碰到的情况,这就需要这种模式去找出解决问题的办法。

野路子,呃……

历史上,英语之于法语,就是野路子,法国人是不屑说英语的。英语当时其实是英格兰民间的老百姓使用的语言,就连英国国王使用的也是法语,如很著名的狮心王。但是最终,英语成为一个世界性语言。

又或者,中国历史上历来的南北对抗时期,多数是少数民族和汉人政权之间的对抗,如南北朝时期,北宋vs契丹、西夏,南宋vs金、蒙古(元朝),明末vs后金(就是后来的清朝了)。少数民族的政权,多数被当时的汉人政权视为野路子,不过多数情况下是,在南北激烈对抗1-2个世纪以后,最终出现民族融合的景象。真正能透过武力驱逐的,都是我们数得出来的中国历史的鼎盛时期,周-春秋-战国时期,汉驱匈奴,唐逐突厥,明初的蒙古。

0
宏哥
宏哥

语言的语法犹如 语言的语法

软件就犹如文章

要写出好文章, 和语法本身关系并不大. 往往和生活经历关系更大.

莎士比亚甚至有自己的语法

正则确实是一个神奇的东西

0
mental
mental
赞一个,能沉住气研究算法,让我想起大学时会为一个算法在自习室,一个人,一支笔,一个本子,乱画一个晚上. 出来工作就没那耐心了,唉
0
hanxh
hanxh

bnf应该算是上下文无关文法吧,比正则文法高。正则文法永远无法解决括号匹配问题。

而bnf能,bnf应该等价于栈。  买本形式语言与自动机就行,或者离散数学一般也有。

具体的还有什么确定下推自动机。 具体到编译上就是LL,LR。

不过这些用不到就不学也罢。



返回顶部
顶部