随笔-341  评论-2670  文章-0  trackbacks-0

因为GacUI需要实现一个文本描述的窗口描述格式,再加上C++经常需要处理xml和json等常用数据结构,还有自己还要时不时开发一些语言来玩一玩之类的理由,每一次遇到自己的技术革新的时候,总是免不了要对可配置语法分析器做出修改。上一个版本的可配置语法分析器可以见之前的博客文章《Vczh Library++ 语法分析器开发指南》。

为什么要重写vlpp的这一部分呢?因为经过多次可配置语法分析器的开发,我感觉到了C++直接用来表达文法有很多弱点:

1、C++自身的类型系统导致表达出来的文法会有很多噪音。当然这并不是C++的错,而是通用的语言做这种事情总是会有点噪音的。无论是《Monadic Parser Combinators using C# 3.0》也好,我大微软研究院的基于Haskell的Parsec也好,还是boost的spirit也好,甚至是F#的Fsyacc也好,都在展示了parser combinator这个强大的概念的同时,也暴露出了parser combinator的弱点:在语法分析结果和语言的数据结构的结合方面特别的麻烦。这里的麻烦不仅在于会给文法造成很多噪音,而且复杂的parser还会使得你的结构特别的臃肿(参考Antlr的某些复杂的应用,这里就不一一列举了)。

2、难以维护。如果直接用C++描述一个强类型文法的话,势必是要借助parser combinator这个概念的。概念本身是很厉害的,而且实现的好的话开发效率会特别的高。但是对于C++这种非函数式语言来说,parser combinator这种特别函数式的描述放在C++里面就会多出很多麻烦,譬如闭包的语法不够漂亮啦、没有垃圾收集器的问题导致rule与rule的循环引用问题还要自行处理啦(在很早以前的一篇博客论证过了,只要是带完整闭包功能的语言,都一定不能是用引用计数来处理内存,而必须要一个垃圾收集器的)。尽管我一直以来都还是没做出过这方面的bug,但是由于(主要是用来处理何时应该delete对象部分的)逻辑复杂,导致数据结构必须为delete对象的部分让步,代码维护起来也相当的蛋疼。

3、有些优化无法做。举个简单的例子,parser combinator就根本没办法处理左递归。没有左递归,写起某些文法来也是特别的蛋疼。还有合并共同前缀等等的优化也不能做,这导致我们必须为了性能牺牲本来就已经充满了噪音的文法的表达,转而人工作文法的共同前缀合并,文法看起来就更乱了。

当然上面三个理由看起来好像不太直观,那我就举一个典型的例子。大家应该还记得我以前写过一个叫做NativeX的语言,还给它做了一个带智能提示的编辑器(还有这里这里)。NativeX是一个C++实现的C+template+concept mapping的语言,语法分析器当然是用上一个版本的可配置语法分析器来做的。文法规则很复杂,但是被C++这么以表达,就更加复杂了(.\Library\Scripting\Languages\NativeX\NativeXParser.cpp),已经到了不仔细看就无法维护的地步了。

综上所述,做一个新的可配置语法分析器出来理由充分,势在必得。但是形式上是什么样子的呢?上面说过我以前给NativeX写过一个带智能提示的编辑器。这个编辑器用的是WinForm,那当然也是用C#写的,因此那个对性能要求高到离谱的NativeX编辑器用的语法分析器当然也是用C#写的。流程大概如下:
1、用C#按照要求声明语法树结构
2、使用我的库用C#写一个文法
3、我的库会执行这个文法,生成一大段C#写的等价的递归下降语法分析器的代码
当时我把这个过程记录在了这篇博客文章里面。

因此现在就有一个计划,这个新的可配置语法分析器当然还是要完全用C++,但是这就跟正则表达式一样:
1、首先语法树结构和文法都声明在一个字符串里面
2、可配置语法分析器可以在内存中动态执行这段文法,并按照给定的语法树结构给出一个在内存中的动态的数据结构
3、可配置语法分析器当然还要附带一个命令行工具,用来读文法生成C++代码,包括自带Visitor模式的语法树结构,和C++写的递归下降语法分析器

所以现在就有一个草稿,就是那个“声明在字符串里面”的语法树结构和文法的说明。这是一个很有意思的过程。

首先,这个可配置语法分析器需要在内存中表达语法树结构,和一个可以执行然后产生动态数据结构的文法。因此我们在使用它的时候,可以选择直接在内存中堆出语法树结构和文法的描述,而不是非得用那个字符串的表达形式。当然,字符串的表达形式肯定是十分紧凑的,但这不是必须的,只是推荐的。

其次,parse这个“语法树结构和文法都声明”当然也需要一个语法分析器是不是?所以我们可以用上面的方法,通过直接在内存中堆出文法来用自己构造出一个自己的语法分析器。

再者,有了一个内存中的语法分析器之后,我就可以将上面第三步的命令行工具做出来,然后用它来描述自己的文法,产生出一段C++写的递归下降语法分析器,用来分析“语法树结构和文法都声明”,然后就有了一对C++代码文件。

最后,把产生出来的这对C++代码文件加进去,我们就有了一个C++直接写,而不是在内存中动态构造出来的“语法树结构和文法都声明”的分析器了。然后这个分析器就可以替换掉命令行工具里面那个原先动态构造出来的语法分析器。当然那个动态构造出来的语法分析器这个时候已经没用了,因为有了生成的C++语法分析器,我们就可以直接使用“语法树结构和文法都声明”来描述自己,得到这么一个描述的字符串,然后随时都可以用这个字符串来动态生成语法分析器了。

总而言之就是
1、实现可配置语法分析器,可以直接用数据结构做出一个产生动态数据结构的parser combinator,记为PC。
2、用PC做一个“语法树结构和文法都声明”的语法分析器。这个“语法树结构和文法都声明”记为PC Grammar。
3、PC Grammar当然可以用来表达PC Grammar自己,这样我们就得到了一个专门用来说明什么是合法的“语法树结构和文法都声明”的描述的字符串的这么个文法,记为PC Grammar Syntax Definition。
4、通过这份满足PC Grammar要求的PC Grammar Syntax Definition,我们就可以用PC来解释PC Grammar Syntax Definition,动态产生一个解释PC Grammar的语法分析器
5、有了PC Grammar的语法分析器PC Grammar Parser (in memory version),之后我们就可以把“文法->C++代码”的代码生成器做出来,称之为PC Grammar C++ Codegen。
6、有了PC Grammar C++ Codegen,我们就可以用他读入PC Grammar Syntax Definition,产生一个直接用C++写的PC Grammar的语法分析器,叫做PC Grammar Parser (C++ version)。

到此为止,我们获得的东西有
1、PC (Parser Combinator)
2、PC Grammar
3、PC Grammar Syntax Definition
4、PC Grammar Parser (in memory version)
5、PC Grammar Parser (C++ version)
6、PC Grammar C++ Codegen

其中,1、3、4、5、6都是可以执行的,2是一个“标准”。到了这一步,我们就可以用PC Grammar Parser (C++ version)来替换掉PC Grammar C++ Codegen里面的PC Grammar Parser (in memory version)了。这就跟gcc要编译一个小编译器来编译自己得到一个完整的gcc一样。这个过程还可以用来测试PC Grammar C++ Codegen是否写的足够好。

那么“语法树结构和文法都声明”到地是什么样子的呢?我这里给出一个简单的文法,就是用来parse诸如int、vl::collections::List<WString>、int*、int&、int[]、void(int, WString, double*)的这些类型的字符串了。下面首先展示如何用这个描述来解决上面的“类型”的语法书声明:

class Type{}

class DecoratedType : Type
{
    enum Decoration
    {
        Pointer,
        Reference,
        Array,
    }
    Decoration        decoration;
    Type            elementType;
}

class PrimitiveType : Type
{
    token            name;
}

class GenericType : Type
{
    Type            type;
    Type[]            arguments;
}

class SubType : Type
{
    Type            type;
    token            name;
}

class FunctionType : Type
{
    Type            returnType;
    Type[]            arguments;
}

然后就是声明语法分析器所需要的词法元素,用正则表达式来描述:

token SYMBOL        = <|>|\[|\]|\(|\)|,|::|\*|&
token NAME            = [a-zA-Z_]\w*

这里只需要两种token就可以了。接下来就是两种等价的对于这个文法的描述,用来展示全部的功能。

========================================================

Type SubableType    = NAME[name] as PrimitiveType
                    = SubableType[type] '<' Type[arguments] { ',' Type[arguments] } '>' as GenericType
                    = SubableType[type] '::' NAME[name] as SubType

Type Type            = @SubableType
                    = Type[elementType](
                            ( '*' {decoration = DecoratedType::Pointer}
                            | '&' {decoration = DecoratedType::Reference}
                            | '[' ']' {decoration = ecoratedType::Array}
                            )
                        ) as DecoratedType
                    = Type[returnType] '(' Type[arguments] { ',' Type[arguments] } ')' as FunctionType

========================================================

rule PrimitiveType    PrimitiveType    = NAME[name]
rule GenericType    GenericType        = SubableType[type] '<' Type[arguments] { ',' Type[arguments] } '>'
rule SubType        SubType            = SubableType[type] :: NAME[name]
rule Type            SubableType        = @PrimitiveType | @GenericType | @SubType

rule DecoratedType    DecoratedType    = Type[elementType] '*' {decoration = DecoratedType::Pointer}
                                    = Type[elementType] '&' {decoration = DecoratedType::Reference}
                                    = Type[elementType] '[' ']' {decoration = DecoratedType::Array}
rule FunctionType    FunctionType    = Type[returnType] '(' Type[arguments] { ',' Type[arguments] } ')'
rule Type            Type            = @SubableType | @DecoratedType | @FunctionType

========================================================

如果整套系统开发出来的话,那么我就会提供一个叫做ParserGen.exe的命令行工具,把上面的字符串转换为一个可读的、等价与这段文法的、使用递归下降方法来描述的、C++写出来的语法分析器和语法树声明了。

posted on 2012-10-29 08:23 陈梓瀚(vczh) 阅读(3861) 评论(6)  编辑 收藏 引用 所属分类: C++

评论:
# re: 又到了一年一度重构通用可配置语法分析器的时候了 2012-10-29 16:18 | 空明流转
先跪再看!  回复  更多评论
  
# re: 又到了一年一度重构通用可配置语法分析器的时候了 2012-10-29 18:15 | DiryBoy
恭喜  回复  更多评论
  
# re: 又到了一年一度重构通用可配置语法分析器的时候了[未登录] 2012-10-29 18:20 | avlee
支持各种原创精神,基于boost spirit编写的晦涩的代码一直让人印象深刻啊  回复  更多评论
  
# re: 又到了一年一度重构通用可配置语法分析器的时候了 2012-10-29 21:20 | 空明流转
@avlee

Spirit比手工的好读多了。。。
VC你应该感谢我!
  回复  更多评论
  
# re: 又到了一年一度重构通用可配置语法分析器的时候了 2012-10-29 21:26 | lwch
好长的描述符.....  回复  更多评论
  
# re: 又到了一年一度重构通用可配置语法分析器的时候了[未登录] 2012-10-30 20:47 | 陈梓瀚(vczh)
@空明流转
感谢!  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理