那么大语法树

麦大劳全新小食“那么大语法树”,好敲不累,越看越醉。

咳咳,言归正传。应Professor Wan的要求,在这里分享一下种语法树的过程以及心得。

看完本文,相信你就会觉得种语法树其实并不难!

友情提示:种语法树是一个需要专注的过程,切不可分而种之。idea出现之时,就要一边涂霸王一边熬夜写代码之时。

作者利用清明节的时间种出了这颗树,有风有雨,适合种树。

第一部分:理论准备(赚钱)

如果你没有好好听Professor Wan讲课,那么你可以点击右上角的红叉(Professor Wan讲课那么有趣还不听?)

种出一颗语法树其实并没有那么难,你所要准备的只有:

(1)认真阅读语法树实验报告,理解语法规则

(2)建议在纸上或者其他设备上根据上述语法规则画出“语法规则树”

图为作者画的“语法规则树”(手残党)

(3)选择一种递归方式(什么?你不知道什么是递归?):

例如 “自顶向下”,“自底向上”,LR等

第二部分:代码准备(挑选种子)

(1)选择编程语言

思路:无论什么语言去写语法树,所用的数据结构都基本一致,那么如何展示数据成为了选择编程语言最优先要考虑的因素。

JS,优点,插件库多,交互性强。(Jquery文件树插件、d3.js、Fabric.js等等)

JAVA,优点,简易,健壮性强。(JTree文件树、Java2D绘树等等)

C++,优点,大多数人比较熟悉,高效。(也有相应图形库)

(2)确定绘树、展示方法(推荐使用工具,见上)

(3)已完成的Lexer(请确保输出的是二元式表,除了整数以及标识符最好输出具体的值)

如图:

第三部分:编写代码(种树中)

(1)编写树的数据结构类(多叉树)

包含属性:layer 当前树的深度

data 存放的字符串信息

childs 子树列表

(2)编写Token类(单词结构)

包含属性:type 二元式第一个参数

pos  二元式第二个参数

方法:isToken(pos,type)判断是否为指定单词

isToken(type) 判断是否为整数和标识符时使用的重载方法

(3)开始写Parser类(语法分析器)

属性:tokenList 存储Token的列表

syntaxTree 树根(树类型)

i 记录当前分析的位置,用于回溯(整型)

 思路:如:自顶向下递归,先调用isProgram方法判断是否为程序,在isProgram中调用isSubProgram(),如果isSubProgram返回true,则isProgram将isSubProgram返回的树作为子树填下到syntaxTree中。(同理,在isSubProgram方法中需要判断构成subProgram的所有子条件)根据整型变量i——游标,结合每个方法中定义的临时变量,记录当前分析的位置,如果判断方法isXXX返回了false,则i应恢复至调用该判断方法前的值。

e.g.(个人方法)

第一步:读取词法分析器生成的二元式表文件,将每个二元式存入Token类,作为一个单词

第二步:根据语法树编写所有判断方法,思路见上,所有方法均为无参,返回值为树类型,每个方法中new一个树,如果不符合条件,将new的树置为null,返回即可。可根据方法返回的树是否为null来判断是否符合对应的语法规则。

第三步:调用isProgram作为入口,即可将syntaxTree种出。但是,现在仅仅是生成了一颗有数据的树,想要将它展示出来,还是需要各位去花时间搜寻适当的插件或库。

第四部分:测试

测试时先对单条语法逐条测试,再整体测试。这里给出作者的测试用例:

//aaaaa
procedure first
/*666666666
6764747674*/
begin
    a=1+2*3*4+5+2*3*4+6;
    if( a==2)
        c=2
    else
        b=3;
    def a,b,c;
    def d,e;
end
//next sub-program
procedure second
begin
    while((2+3)>=g and 1 or 2)
        call first;
        if(1>2 and 2>=3 and 2 or 3 or 4<=5)
            begin
                if(2<=3)
                    g=1
                else
                    g=(5*3/2+4)
            end
        else
            g=e
end

第五部分:美化树

好不容易种出来树了,那就当成一个作品吧,编写一个GUI界面是个不错的选择。

第六部分:生成exe

exe可执行文件还是很重要的,或者如果是用js做的语法树,将前端文件部署到服务器上展示一下何乐而不为呢?

分享一个java生成exe的文章https://blog.csdn.net/qq_29496057/article/details/53333419

个人心得

写语法树的过程其实也是培养耐心的过程,只要认真去做,一定可以完成的,然后Professor Wan会给你编译原理实验课满分,爽死了。

要看鱼皮Java文档的同学私戳QQ592789970,希望大家都能早日过掉语法树!

发表评论

电子邮件地址不会被公开。