woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

用Flex/Bison分析c代码的经历

这些日子花了不少时间在一个c语言的语法分析程序上,这个程序要能识别变量、函数的定义、声明和引用,简而言之就是找出sourceinsight所能提供的信息(比si还要精确)。

分析代码和编译代码一样,都要做语法分析。但是因为分析代码不做预处理,所以就会遇到一些麻烦,比如处理一些定义的稀奇古怪的宏,无法判断一个identifier是变量还是类型。这么一来,严格的用C语言语法来分析代码就没法通过。

考虑到这个问题,一开始决定用lex作词法分析,生写语法分析。进行到中间,代码复杂度越来越高,感觉力不从心。又决定通过修改标准的C语言语法规则,用bisonyaccGNU实现)来完成语法分析

所谓“工欲善其事,必先利其器”,bison在做语法分析上,果然很方便。但是很快就遇到上面所说的问题:不做预处理,无法得到一个token的类型。标准的yacc支持的是LALR语法,LALR语法只预读一个token,无法解决这个问题。

好在GNUYacc实现bison支持GLR语法GLR没有只预读一个token的限制,它用状态分裂来解决无法判断token类型的问题。采用GLR,写语法规则就基本上没有什么限制了。

但是GLR有个问题,它用状态分裂解决问题,如果所有分裂的状态只有一个能分析成功,那自然OK;如果不能,就叫产生了ambiguity(不确定),分析就失败了。

解决ambiguity,可以用%dprec来指定规则的优先级。当两个状态发生ambiguity时,根据它们对应的reduce规则的优先级,选择优先级高的那个状态。

但还有一类ambiguity的情况,用%dprec也没发解决。那就是两个产生ambiguity的状态它们对应的reduce规则是同一条。这类问题很棘手,我只好采用重写规则来避免。但这就导致规则的可读性很差,而且往往是解决一个ambiguity又引入另外一个。

无奈,往bisonmail list里发了一封信求救,第二天收到一哥们回信,信中说:

“用merge啊。我也遇到过类似的问题。”

merge是啥呢?merge就正好是处理上面这类问题的,相当于把多个状态合并。因为是比较新的特性,在bison的文档里并没有很明显的提及。

这样,用bison分析c代码就基本没有问题了;)

 

备注

Flex:词法分析器

Bison:语法分析器

GNU bison是一个自由软件,用于自动生成语法分析器程序,实际上可用于所有常见的操作系统。Bison把LALR形式的上下文无关文法描述转换为可做语法分析的CC++程序。在新近版本中,Bison增加了对GLR语法分析算法的支持。

GNU bison基本兼容Yacc,并做了一些改进。它一般与flex一起使用。

posted on 2008-11-22 00:02 肥仔 阅读(7519) 评论(1)  编辑 收藏 引用 所属分类: LEX & YACC

评论

# re: 用Flex/Bison分析c代码的经历[未登录]  回复  更多评论   

果然想到一起了,最近也在做提取C变量、函数的定义之类的程序想用lex和yacc,也郁闷在预处理上了,不知项目能否开源参考一下?
2012-11-19 15:45 | 逗你玩

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理