
116
;;Functionintmain()(main)@1@2@3@4
function-declfunction-nodefunction-typecompound-stmt
name:@2Cstrg:mainsize:@5prms:@7line:6
body:@8
next:@9
type:@3externIngt:4algn:64
retn:@6
计算机应用2004年
词法分析器识别FUNCTION、NUMBER、IDENT、
srcp:stu.c:2body:@4
TAGLABEL和TAGVALUE五种记号,词法分析器通过使用bison变量yylval将这五种记号对应的文本传递给语法分析
器。语法分析器的语法规则包含五种非终结符,分别为asg、
node、tags、doublet和tag-value。语法规则的第一个非终结符
为asg,它代表一个抽象语法树分析的开始;node代表一个抽象语法树节点;tags代表节点标记的列表;doublet代表标记标签由单个单词组成,标记值非空的标记;tag-value代表节点标记值。语义动作中各函数使用的伪变量是词法分析器所识别记号的文本。
语义动作使用了四个函数:
1)new-asg($1)为抽象语法树新建名为$1的空哈希表,
3 抽象语法树解析方法
抽象语法树结构比较简单,其对应的词法规则和语法规则[2,3]易于构造,使用flex和bison工具生成的解析器能够有效地对抽象语法树进行解析。解析器由三部分组成,分别是
flex生成的词法分析器、bison生成的语法分析器和手工编写
的驱动程序。词法分析器识别抽象语法树文件的记号流,提供给语法分析器;语法分析器利用嵌入其中的语义动作识别语法树节点,完成解析任务;驱动程序负责为词法分析器和语法分析器提供一个调用接口,并提供解析所需的数据结构和函数的实现。
为使解析后的抽象语法树便于遍历,使用哈希表
[4]
作为抽象语法树的存储结构;
2)add-node($1,$2)在哈希表中增加一个关键字为$1,标识符值为$2的节点;
3)add-tag($1,$2),;
$1,2存储的字符串组合,
作为
,得到如图1所示的解析结果

。
抽象语法树的存储结构,树节点,,造哈希函数。、储,。解析过程主要使用链表、,因此Linux下实现该解析器,可以使用glib库提供的链表、哈希表及其操作函数作为解析器所需的数据结构和函数。
词法分析器使用的词法规则如下(&b&代表空格):
FUNCTION=";;Function".3$NUMBER="@"[0-9]+IDENT=[a2zA2Z-]+
TAGLABEL=[a2zA2Z]+(":"|"&b&:"|"&b&&b&:")
TAGVALUE=[a2zA2Z029<>.:-2]+|\"(.)3\"
图1 部分抽象语法树解析结果
从图1可以看到,抽象语法树从函数声明节点逐渐展开,生成完整的树结构。抽象语法树的结点代表了语言不同的语法结构,从树的根结点开始对抽象语法树进行遍历的过程中,可以访问到所关心语法结构对应的树节点。遍历过程中加入特定的语义动作对树节点进行处理,就可以实现源程序浏览器、程序分析器等工具。
对于其他记号,词法分析器不做任何动作。
语法分析器使用的语法规则及嵌入的语义动作如下:
asg:asgnode
|;
node:NUMBERIDENTtags{add-node($1,$2);}
|FUNCTION{new-asg($1);};
tags:doublettags
|IDENTtags{add-tag($1,NULL);}
|IDENTTAGVALUENUMBERtags{add-tag(create-tag($1,$2),$3);}|;
doublet:TAGLABELtag-value{add-tag($1,$2);}
;
tag-value:NUMBER{$$=$1;}
|TAGVALUE{$$=$1;}|IDENT{$$=$1;}|{$$=NULL;};
4 结束语
利用flex和bison工具生成的解析器能够快速有效地解析GCC产生的抽象语法树文件,使用哈希表作为存储抽象语法树的存储载体可以快速遍历抽象语法树,便于对解析后的抽象语法树进行处理。我们在Linux环境下实现的解析器,能够成功解析出GCC生成的抽象语法树。
参考文献
[1] StallmanRM.UsingandPortingtheGNUCompilerCollection
[EB/OL].doc.guandang.net.
[2] AhoAV,SothiR,UllmanJD.Compilers2Principles,Techniques,
andTools[M].Addison2WesleyPublishingCompany,1986.[3] WattDA.ProgrammingLanguageSyntaxandSemantics[M].
PrenticeHallInc,1991.
[4] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.
一种基于GCC抽象语法树的程序特征提取方法_化学_自然科学_专业资料。 程序设计... 推理型题分析与总结+申请认证 文档贡献者 维普网 中国最大最早的专业内容网站...
基于GCC的抽象语法树对C++源程序结构的分析_专业资料。源程序静态信息的提取是实现对源程序静态分析的基础,提取的静态信息的完整性、信息的规范性是静态分析的关犍...
基于GCC的抽象语法树对C_源程序结构的分析 (1)_自然科学_专业资料。基于 ...第一种方式, 这类静态分析器使用语法制导分析源代码, 特点是语法识别准确, ...
一个重建GCC抽象语法树的方法_IT/计算机_专业资料。一个重建 !"" 抽象语法...文档重建 345 将’(( 345 转换成 DEF 文档后, 使用 DEF 文档解析器, C$!...
1 算法达到的目标 为了达到引入 GCC 改善评分系统 [ 1 ] 性能的目的 ,算法达 到目标是 : 消除抽象语法树文本中所有与分析数据流 、 控制流 ( 不能丢失有用...
一种解析GCC抽象语法树的方... 2页 2财富值喜欢此文档的还喜欢 第三章 ...表示组织成4 级层次结构,包括:文件级,过程级,高级结构控制级和指令表达式树级...
图一 源代码语法树 和抽象语法树相对的是具体语法树(concrete syntax tree) ,通常称作分析树 (parse tree) 。一般的,在源代码的翻译和编译过程中,语法分析器...
基于Java语言的抽象语法树的创建与遍历_廖兴_计算机软件及应用_IT/计算机_专业...相匹配的语法分析树.在JavaParser类中, 每个节点类都对应一个调用方法,用于创建...
而③ 显然抽象语法树中的一个结点可以由包含若干个成员的记录或结构体来实现 。 13抽 象语 法树 的构 造 . 抽象语法树是在语法分析的过程中建立起来的,立 ...
基于GCC的抽象语法树对C++源程序结构的分析王相懂张毅坤 (西安理工大学计算机科学与工程学院,西安710048)E-mail:wangxiangdong@sina.COrn 摘 要 源程序静态信息的...
热门文档