您所在位置：主题：[原创]基于.net的好用的语法分析辅助工具：GOLD Parser（１）
dyna
[专家分：0] 发布于 2006-11-15 17:37:00
基于.net的好用的语法分析辅助工具：GOLD Parser（１）
[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的优点（由于还没有深入，可能观点有误）：
１．GP的帮助是我见过的最好的文档之一，每章的内容简短易懂（这也是因为GP的使用简单），且排列顺序基本上代表了阅读顺序。
２．使用LALR算法进行分析，且支持上下文相关文法。
３．语法文件格式简单明了。（因为GP将Builder和Engine分开实现）
４．预定义的集合、属性很多，使用方便。
５．支持导入yacc语法文件，并支持导出为XML、网页及其它格式。
６．方便的GUI界面（可能因为windows用多了，什么时候能成为linux下的命令行高手呢？不过GP也提供了cmdline界面），完善的信息显示（包括语法错误、表信息、DFA信息等）。
７．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])
[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的优点（由于还没有深入，可能观点有误）：
１．GP的帮助是我见过的最好的文档之一，每章的内容简短易懂（这也是因为GP的使用简单），且排列顺序基本上代表了阅读顺序。
２．使用LALR算法进行分析，且支持上下文相关文法。
３．语法文件格式简单明了。（因为GP将Builder和Engine分开实现）
４．预定义的集合、属性很多，使用方便。
５．支持导入yacc语法文件，并支持导出为XML、网页及其它格式。
６．方便的GUI界面（可能因为windows用多了，什么时候能成为linux下的命令行高手呢？不过GP也提供了cmdline界面），完善的信息显示（包括语法错误、表信息、DFA信息等）。
７．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])