基于.net的好用的语法分析辅助工具:GOLD Parser(1)


[IMG]http://bbs.pediy.com/upload/2006/4/image/1.jpg_743.jpg[/IMG] 

在看完虎书(现代编译原理——C语言实现英文版)的前两章之后,要求用Lex与Yacc写一个关于Tiger语言的词法和语法分析。之前看龙书的时候(可惜没看完,呵呵)了解过Parser Generator,它完全兼容lex与yacc的语法,不过我想寻找一个.net下使用方便的生成器。正好,在Code Project上看到了《Introduction to GOLD Parser》,其中有段文字非常好,介绍了现在流行的词法与语法分析生成器:


The first time you learn about a parser or lexer, you are immediately linked to the classic Lex and YACC tools developed many years ago. You may also be referred to the open-source, Bison tool provided with the GNU distribution or ANTLR, a commercial parsing tool or Spirit, an open-source parsing system based on C++ templates. What's common to all these tools is that the code generated for parsing is always C or C++.

[color=FF0000]For those using .NET, there are really only two choices; Grammatica, which was recently ported from its original Java implementation to C# and GOLD Parser.[/color]
 

于是决定先试用GOLD Parser(后面就称GP,版本v3.2.3)。简单总结下GP的优点(由于还没有深入,可能观点有误):

1.GP的帮助是我见过的最好的文档之一,每章的内容简短易懂(这也是因为GP的使用简单),且排列顺序基本上代表了阅读顺序。

2.使用LALR算法进行分析,且支持上下文相关文法。

3.语法文件格式简单明了。(因为GP将Builder和Engine分开实现)

4.预定义的集合、属性很多,使用方便。

5.支持导入yacc语法文件,并支持导出为XML、网页及其它格式。

6.方便的GUI界面(可能因为windows用多了,什么时候能成为linux下的命令行高手呢?不过GP也提供了cmdline界面),完善的信息显示(包括语法错误、表信息、DFA信息等)。

7.Engine很多,这样可以生成不同语言的代码。(比如C#、C++、C、ASM等等)

 

GP的主界面如下:

[IMG]http://bbs.pediy.com/upload/2006/4/image/10.jpg[/IMG]

这么多的优点,还有什么理由不使用它呢?下面就用GP来生成虎书前两章要求的Tiger语言词法和语法分析器。编写语法(GP中称为GOLD Meta-Language)可以直接在GP中进行,也可以在其网站提供的GrammarEdit中进行,后者主要功能是语法高亮。由于GP的语法十分简单,帮助文档二十分钟就可以读完,因此直接给出源代码。

 

第一步:编写语法文件

tiger0.grm主要用于实现虎书中Appendix A里的第一个示例queens.tig,由于是边学边写,所以tiger0.grm中还没有实现while语句、break和其它一些功能,但能正确对queens.tig进行分析。(详细代码见附件中的tiger0.grm)

语法文件编写的过程中参照了GP网站提供的ANSI-C的语法文件,毕竟是第一次写,有个参考可以学到很多东西。其中部分内容没有完全按照Tiger的规范来,比如增加了行注释//,又比如原书中将所有的代码(不管是语句还是表达式)归为Exp,而我个人更倾向于将Statement(语句)和Expression(表达式)分开写。
 

第二步:进行编译

GP中的语法文件编译十分简单,直接点击“Continue”,并且会给出每一步的信息。第一步Check the grammar完成后,显示信息如下:

[IMG]http://bbs.pediy.com/upload/2006/4/image/2.jpg_782.jpg[/IMG] 
 

这表示语法正确。再次Continue,生成LALR表。这一步是关键,因为两种冲突(Shift-Reduce Conflict和Reduce-Reduce Conflict)均在这一步被检测出来。其中前者可以自动修复(丢弃Reduce,采用Shift),而后者则要由编者自己完成。第二步中显示我们的源代码出错:

[IMG]http://bbs.pediy.com/upload/2006/4/image/3.jpg_831.jpg[/IMG] 

 

双击带!号的行,显示详细信息如下:

[IMG]http://bbs.pediy.com/upload/2006/4/image/4.jpg_885.jpg[/IMG]


Log显示在state 200处产生了Shift-Reduce冲突。虽然GP会自动fix,但我们还是看看什么原因造成这个冲突。点击Configurations,显示详细信息:

[IMG]http://bbs.pediy.com/upload/2006/4/image/5.jpg_948.jpg[/IMG] 

看来是经典的if语句,分析器读入else时,不知道是应该shift还是reduce。这说明我们的源码有误。看一下源码:

<Then Stm> ::= [b]'if' <Exp> 'then' <Then Stm>[/b]

            |'if' <Exp> 'then' <Then Stm> 'else' <Then Stm>

            |'for' Identifier ':=' <Exp> 'to' <Exp> do <Then Stm>

            | <Normal Stm>

其中黑体部分就是冲突的原因,因为<Normal Stm>中后来又调用了<Stm>,修改很简单,将黑体部分删除:

<Then Stm> ::= 'if' <Exp> 'then' <Then Stm> 'else' <Then Stm>

              |'for' Identifier ':=' <Exp> 'to' <Exp> do <Then Stm>

              | <Normal Stm>

这样一路前进,语法正确,LALR正确,DFA正确,最后显示可以创建语法表了。(当然,中间经过了数次出错并修改。)


[IMG]http://bbs.pediy.com/upload/2006/4/image/6.jpg_982.jpg[/IMG] 


[IMG]http://bbs.pediy.com/upload/2006/4/image/9.jpg[/IMG] 

第三步:测试代码

下面怎么测试生成的代码是否正确呢?其中没有必要编译一个实体程序出来,GP提供了非常方便的test功能。

点击test按钮后会出现测试窗口,我们在Source栏输入源代码:


[IMG]http://bbs.pediy.com/upload/2006/4/image/7.jpg_023.jpg[/IMG] 

 

随后点击“Test”。如果出错的话,Parse Actions栏中最后一行会出现是哪一步出错,根据这个信息可以修改源代码,如果正确会直接跳到Parse Tree栏显示分析树。


[IMG]http://bbs.pediy.com/upload/2006/4/image/8.jpg_094.jpg[/IMG] 
 

这个树结构实在是了解整个分析过程的好东西。同时,GP提供的导出功能也非常有用,可以将整个LALR表和DFA导出为xml、txt和html文件,查阅起来非常方便。

附件中提供的tiger1.grm是修改过的GP语法文件,初学,代码中的错误在所难免,请大家指正(http://vxer.cn/blog)。本文学习了GP的基本使用,下一次会学习怎么利用GP的Engine将代码集成到我们的程序中。

(由于不能传附件,大家去我的BLOG上下载源码吧!另外,希望这个编译原理的论坛一直办下去,越办越好,我也会常来学习![em4])