小r的博客 普通的博客

语法生成树

2017-05-29
XiaoR

使用c++和graphviz两个工具来分析绘制一颗语法生成树。


前置总结

首先需要掌握的基础是编译原理中的语法分析,以及更早的词法分析。

选择思路

绘制语法生成树,包括分析语法结构和绘制树两部分,c++是一门非常全能的语言,能够胜任前者,但是在绘图上占据劣势,因此再借助额外的专业绘图小工具Graphviz,先由c++生成后者可以理解的语法,再 使用这个结果进一步生成图像。

Graphviz介绍

graphviz是贝尔实验室开发的一个开源的工具包,它使用一个特定的DSL(领域特定语言): dot作为脚本语言,然后使用布局引擎来解析此脚本, 并完成自动布局。graphviz提供丰富的导出格式,如常用的图片格式,SVG,PDF格式等。

语法分析部分

这里使用递归向下的LL(1)分析法,首要步骤便是消除左递归,随后整个代码就变得十分清晰。

需要指出的是,递归下降肯定不止LL(1)这一种思路,但是使用其他思路,或许在局部能够便利的解决问题,但是问题一复杂反而不如LL(1)清晰,陷入无尽的判断条件之中。

这里给出一个简单的实例

/*
	A -> aB
	B -> b[A]
*/

extern vector<state> list;	//一个已经计算好状态的顺序列
int pointer = 0;

//一个match函数,用在确定下一个状态的情况下,一旦失败便会报错
bool match(State state){
	if(list[pointer] == state){
		pointer++;
		return true;
	}
	throw SyntaxError("can't match"+state);
	return false;
}

//偶尔需要的第二个match函数,用来判明接下来需要的状态
bool trymatch(State state){
	return (list[pointer] == state);
}

bool A(){
	match(a);
	B();
}

bool B(){
	match(b);
	if(trymatch(a))A();
}

这份代码仅作为简单示例而没有考虑建树的过程,关于建树,我支持的建议是“在对应的状态下建立这个状态节点”而不是在“父状态建立好所有的子节点”。这样可以规避很多问题。总之将其作为 一条规则并遵守的话可以避免自己的逻辑陷入混乱,加错节点。

使用多种match函数也可以精简代码,当然如果默认输入的程序是正确的,就不用考虑带throw的match了–如果要判明错误,这个带throw的match可比在主递归里写一堆判断条件好看多了。

使用C++的特性,例如Enum枚举状态以及异常类,都可以简明代码,要多加利用。

更多代码细节可以直接观看我[1][上传至github上的代码]。

生成dot

dot文件是描述图片结构的文件,在获得整个树结构后,按照dot这种方式将其输出并不困难。

一个示范的dot文件


digraph ast{
fontname = "Microsoft YaHei";
fontsize = 10;

node [shape = circle, fontname = "Microsoft YaHei", fontsize = 10];
edge [fontname = "Microsoft YaHei", fontsize = 10];
node [shape="plaintext"];

mul [label="mul(*)"];
add [label="add(+)"];

add -> 3
add -> 4;
mul -> add;
mul -> 5;
}

使用label以避免节点内容来做节点的key,同时使得节点名字非常容易编号,可以以“dotN”代表数据结构中的第N个元素。对于以数组存储树结构的我来说,直接用下标作为N再方便不过了。

生成图像

安装好graphviz后在命令行输入转化指令即可。

  • dot xxx.dot -Tpng -o xxx.png

完成图

完成


Similar Posts

下一篇 TShock学习

Comments