上一节中通过词法扫描器将标示符,数字,操作运算符等token扫描出来,这节将这些扫描出来的token放入抽象语法树节点中保存起来,以后将会利用这 些节点构建完整的抽象语法树结构,有关抽象语法树的概念可以...

  上一节中通过词法扫描器将标示符,数字,操作运算符等token扫描出来,这节将这些扫描出来的token放入抽象语法树节点中保存起来,以后将会利用这 些节点构建完整的抽象语法树结构,有关抽象语法树的概念可以在《龙书》中找到,这里只做简单说明:比如表达式 c = a + b ,这么一个表达式经过词法扫描器扫描后,将会得到 ‘c’ ,‘ =’ ,‘a’ , ‘+’ , ‘b’ 这五个token,将这5个token放入AST(抽象语法树)结构的nodes(节点列表)中,再根据赋值运算符和加法运算符的优先级关系,以及具体的 程式算法,就可以构建这5个token的相互之间的父子关系。从上到下的父子关系图就像一棵树一样,如图:

 

  在这个树形结构中,越在下面的运算优先级越高,那么在以后要生成汇编代码的时候,就可以先根据加法运算符先生成a+b的汇编码,最后生成赋值运算的汇编码,这样就可以完成一个简单的编译(这些具体内容以后再说)。

  现在知道语法树的意义和重要性了,那么这一节的程式主要是为构建这样的抽象语法树结构做准备,即将token以节点的形式加入到语法树的节点列表。

  本节代码还是放在sourceforge上面,下载链接:http://sourceforge.net/projects/zengl/files/zengl_lang_v0.0.2_forXP.rar/download  (此链接为zengl v0.0.2版本的xp版本,解压后将得到vs2008的项目解决方案,请使用火狐浏览器点开此链接并下载,IE浏览器请右键目标另存为...)。 http://sourceforge.net/projects/zengl/files/zengl_language_v0.0.2_forLinux.tar.gz/download (此链接为zengl v0.0.2的Linux版本,这次用的是tar.gz压缩包,解压后有usage.txt使用说明文档),http://sourceforge.net/projects/zengl/files/v0.0.2-v0.0.1-diffs.txt/download (此为v0.0.2与v0.0.1版本的代码变化),本想发布到爱问等网盘上面去,不过这些网盘要 审核,所以先放到sourceforge上。

  百度盘共享链接地址: http://pan.baidu.com/share/link?shareid=85544&uk=940392313

  现在以XP版本为例进行说明,在该版本里有三个代码文件,main.c ,parser.c ,global.h

  在v0.0.1版本里的main.c开头的一些声明,比如include ,#define  FALSE  0等的定义都放到了global.h 全局头文件里。这样不同的C文件里就可以共用一些结构体和宏定义了。在main.c的main()入口函数里,while循环getToken部分,前一 个版本是直接调用printToken(token)将token信息打印出来,在这个版本里,是先调用AddNode(token) 将扫描到的元素加入到语法树的Node节点中,最后在循环结束后,调用printASTnodes函数将所有节点信息打印出来。

  该版本的主要部分是在parser.c源文件里,该文件的代码将作为处理抽象语法树的主程式。该文件里的initTreeNode函数用于初始化抽象语法 树的动态节点数组AST_nodes结构,该结构定义在文件的开头:TreeNode_Type AST_nodes;  其中TreeNode_Type在global.h的定义如下:

typedef struct{
    int size;
    int count;
    Node_Type *nodes;
}TreeNode_Type;

  其中size成员表示动态数组中一共可以存放多少元素,在初始化zl_malloc函数分配动态内存空间时,会根据size和Node_Type类型的大 小决定要分配的内存大小,count成员表示当前动态数组中存放了多少个节点元素,nodes指针成员指向zl_malloc分配的内存空间的指针。

  在以后还会遇到很多这样的动态数组结构,组成结构都差不多。当动态数组的count等于size时,表示动态数组当前分配的空间已用完,需要加入更多的元 素的话,就需要增加size的值,再根据新的size,调用zl_realloc函数调整动态数组的内存大小,同时更新nodes指针成员,使其指向新的 空间大小,zl_realloc函数内部会调用realloc系统库函数来调整内存大小,再调整时会将原来的数据也拷贝到新空间里,所以该函数可以在不丢 失原有数据的情况下进行扩容。这样就实现了一个动态数组。在AddNode函数添加新节点时就用到了这点:

    if(AST_nodes.count == AST_nodes.size)
    {
        AST_nodes.size += TREENODE_SIZE//TREENODE_SIZE为数组的初始大小,也是每次扩容时要增加的大小,定义在global.h中,默认为40
        AST_nodes.nodes = zl_realloc(AST_nodes.nodes,
                                        AST_nodes.size * sizeof(Node_Type));
        memset(AST_nodes.nodes+(AST_nodes.size - TREENODE_SIZE),0,
                TREENODE_SIZE * sizeof(Node_Type));  //将扩容后的新内存空间用0填充。
    }

  AST_nodes里的nodes指向节点的内存空间,每个节点的类型都是Node_Type,该类型在global.h中的定义如下:

  typedef struct{
    bool isvalid; //节点是否有效,有效表示该节点存放了一个token信息,已被占用,不能再存信息。无效则表示该节点还没存放token信息,可以用来存放信息。
    enum TOKENTYPE toktype//表示该节点存放了什么类型的token,如ID表示标示符,NUM表示数字等。
    char * tokstr//该token的字符串信息,如标示符 abc的节点,则在toktype里会存放ID表示这是一个标示符,在tokstr里则存放的是"abc"的字符串。
}Node_Type;

  在该版本里每个节点的tokstr成员都会由zl_malloc分配一个字符串的内存空间用来存放标示符的字符串信息,如果节点数很多的情况 下,zl_points的内存池就需要分配很多的内存指针来存放这些字符串信息,效率和性能上都会出问题,这个问题在后面的版本中会用一个特殊方法进行处 理。

  在parser.c的最后定义了printASTnodes函数,通过循环调用printNode函数来打印所有的节点信息,而printNode则根据指定节点的toktype类型,将该节点的tokstr字符串信息打印出来。

  由于代码最初是在linux上进行开发的,采用的是git做的版本控制,但是在开发时因时间关系,没有给代码做注释,所以导致git里所有的历史版本都没 有注释,如果现在要给代码加上注释的话,那么所有的历史版本都要加一遍注释,重复的工作量太大,所以就暂时不在代码里加注释,先通过这里发布的网页说明文 档和程序调试的方法来理解代码吧,在最后一个版本中将会加入注释信息。

  为了方便查看上个版本和当前版本的不同,所以从git提取了信息存放在v0.0.2-v0.0.1-diffs.txt文件里,从该文件里可以看出两个版本的代码变化情况。

 v0.0.2-v0.0.1-diffs.txt文件的下载地址:http://sourceforge.net/projects/zengl/files/v0.0.2-v0.0.1-diffs.txt/download

  最后linux下的用户在解压Linux版代码后,根据usage.txt的说明,先make clean 清理原来生成的二进制文件,再make生成当前环境下的可执行文件,最后./zengl test.zl 来测试,当然前提是安装了gcc编译器

  本例的抽象语法树等很多高级的原理都可以在《龙书》中找到。

  网上可以搜索(龙书 编译原理) 来下载pdf电子档。

  最后的最后,如果转载请注明来源 http://www.zengl.com   , OK , 先到这里,休息,休息一下 O(∩_∩)O~

上下篇

下一篇: zengl编程语言v0.0.3构建抽象语法树

上一篇: 开发自己的编程语言-zengl编程语言v0.0.1词法扫描器的实现

相关文章

zengl编程语言v0.0.8第二代语法解析函数

zengl v1.4.0 调试接口 zengl_SDL项目

zenglServer v0.1.1 url解码,新增builtin模块实现数组成员的迭代操作

zengl编程语言v0.0.3构建抽象语法树

zengl v1.8.3 修复ReUse接口缺陷及段错误,完善语法检测,使用Android Studio开发android项目

zengl v1.5.0 移植到zenglOX系统