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

本来说这一篇文章要把构造确定性状态机和look ahead讲完的,当我真正要写的时候发现东西太多,只好分成两篇了。上一篇文章说道一个基本的状态机是如何构造出来的,但是根据第一篇文章的说法,这一次设计的文法是为了直接构造出语法树服务的,所以必然在执行状态机的时候就要获得构造语法树的一切信息。如果自己开发过类似的东西就会知道,类似LALR这种东西,你可以很容易的把整个字符串分析完判断他是不是属于这个LALR状态机描述的这个集合,但是你却不能拿到语法分析所走的路径,也就是说你很难直接拿到那颗分析树。没有分析树肯定是做不出语法树的。因此我们得把一些信息插入到状态机里面,才能最终把分析树(并不一定真的要表达成树,像上一篇文章的“分析路径”(其实就是分析树的一种可能的表达形式)所确定的语法树构造出来。

就像《构造正则表达式引擎》一般给状态机添加信息的方法,就是把一些附加的数据加到状态与状态之间的跳转箭头里面去。为了形象的表达这个事情,我就拿第一篇文章的四则运算式子来举例。在这里我为了大家方便,重复一下这个文法的内容(除去了语树书声明):

token NAME = "[a-zA-Z_]/w*";
token NUMBER = "/d+(./d+)";
token ADD = "/+";
token SUB = "-";
token MUL = "/*";
token DIV = "//";
token LEFT = "/(";
token RIGHT = "/)";
token COMMA = ",";

rule NumberExpression Number
        = NUMBER : value;

rule FunctionExpression Call
        = NAME : functionName "(" [ Exp : arguments { "," Exp : arguments } ] ")";

rule Expression Factor
        = !Number | !Call;

rule Expression Term
        = !Factor;
        = Term : firstOperand "*" Factor : secondOperand as BinaryExpression with { binaryOperator = "Mul" };
        = Term : firstOperand "/" Factor : secondOperand as BinaryExpression with { binaryOperator = "Div" };

rule Expression Exp
        = !Term;
        = Exp : firstOperand "+" Term : secondOperand as BinaryExpression with { binaryOperator = "Add" };
        = Exp : firstOperand "-" Term : secondOperand as BinaryExpression with { binaryOperator = "Sub" };

那么我们把这个文发转成状态机之后,要给跳转加上什么呢?从直觉上来说,跳转的时候我们会有六种要干的事情:
1、Create:这个文法创建的语法树节点是某个类型的(区别于在这一刻给这个问法创建一个返回什么类型的语法树节点)
2、Set:给创建的语法树节点的某个成员变量设置一个指定的值
3、Assign:给创建的语法树节点的某个成员变量设置这一次跳转的符号产生的语法树节点(譬如说Exp = Exp: firstOperand “+” Term: secondOperand,走Term的时候,一个语法树节点就会被assign给那个叫做secondOperand的成员变量)
4、Using:使用这一次跳转的符号产生的语法树节点来做这次文法的返回值(譬如说Factor = !Number | !Caller这一条)
5、Shift:略
6、Reduce:略

在这里我们并没有标记整个文法从哪一个非终结符开始,因为在实际过程中,其实分析师可以从任何一个文法开始的。譬如说写IDE的时候,我们可能在某些情况下仅仅只需要分析一个表达式。所以考虑到每一个非终结符都有可能被用到,因此我们的“Token流开始”和“Token流结束”就会在每一个非终结符的状态机中都出现。因此在第一步创建Epsilon PDA(下推自动机)的时候,就可以先直接生成。在这里我们拿Exp做例子:

image

双虚线代表的是Token流和Token流结束,这并不是我们现在关心的事情。在剩下的转换中,实现是具有输入的转换,而虚线则是没有输入的转换(一般称为epsilon边)。

在这里我们要明确一个概念——分析路径。分析路径代表的是token在“流”过状态机的时候,状态是如何跳转的。因此对于实际的分析过程,分析路径其实就是分析树的一种表达形式。而在状态机里面,分析路径则代表一条从开始到结尾的可能的路径。譬如说在这里,分析路径可以有三条:
$e –> e1 –> e2 –> e$
$e –> e3 –> e8 –> e7 –> e6 –> e5 –> e4 –> e$
$e –> e9 –> e14 –> e13 –> e12 –> e11 –> e10 –> e$

因此我们可以清楚,一条路径上是不能出现多个create的,否则你就不知道应该创建的是什么了。当然create和using都不能同时出现,using也不能有多个。而且由于create和set都是在描述这个非终结符(在这里是Exp)所创建的语法树节点的类型和属性,跟执行他们的时机无关,所以其实在同一条分析路径里面,create和set放在哪里都没关系。就譬如说在上面的第二条分析路径里面,create是在e6->e5里面标记出来的。就算他移动到了e3->e8,做的事情也一样。反正只要一条路径上标记了create,那么他在这条路径被确定之后,就一定会create所指定的具体类型的语法树节点。这是相当重要的,因为在后面的分析中,我们很可能需要移动create和set的具体位置。

跟上一篇文章说的一样,接下来的一步就是去除epsilon边了。结果如下:

image

面对这种状态机,去除epsilon边就不能跟处理正则表达式一样简单的去除了。首先,所有的终结状态——也就是所有经过或者不经过epsilon边之后,通过“Token流结束”符号连接到最后一个状态的状态,在这里分别是e2、e6和e12——都是不能删掉的。而且所有的“Token流开始”和“Token流结束”——也就是图里面的$转换——是不能带有信息的。所以我们就会看到e6后面的信息全部被移动到了e7->e6这条边上面。由于create和set的流动性,我们这么做对于状态机的定义完全没有影响。

到了这里还没完,因为这个状态机还是有很多冗余的状态的。譬如说e8和e14、e7和e13、e2和e6和e12实际上是可以合并的。合并的策略其实十分简单:

1、如果我们有跳转e0->e1和e0->e2,并且两个跳转所携带的token输入和信息完全一致的话,那么e1和e2就可以合并。
2、如果我们有跳转e1->e0和e2->e0,并且两个跳转所携带的token输入和信息完全一致的话,那么e1和e2就可以合并。

所以对于e8和e14我们是完全可以合并的。那么e7和e13怎么办呢?根据create和set的流动性,我们只要把这两个东西挪到他的前面一个或者若干个跳转去,那这两个状态就可以合并了。为了让算法更加的简单,我们遇到两个跳转类似的时候,总是先挪动create和set,然后再看看是不是真的可以合并。所以这一步处理完之后就会变成下面这个样子:

image

我们在不改变状态机语义的情况下,把Exp的三个状态机最终压缩成了这个样子。看过上一篇文章的同学们都知道,下一步就是要把所有的状态机统统都连接起来了。关于在连接的时候如何具体操作转换附带的信息、以及做出一个确定性的下推状态机的所有事情将在下一篇文章详细解释。大家敬请期待。

posted @ 2012-12-22 08:28 陈梓瀚(vczh) 阅读(4895) | 评论 (1)编辑 收藏

刚刚发了上一篇文章之后就发现状态机画错了。虽然LiveWriter有打开博客并修改文章的功能,不过为了让我留下一个教训,我还是决定发一篇勘误。这个教训就是,作分析的时候不要随便“跳步”,该一步一步来就一步一步来。其实人呢,就是很容易忘掉以前的教训的了。第一个告诉我不能这么干的人其实是小学三年级的数学老师。当时我因为懒得写字,所以计算应用题的时候省了几步,被批评了。

故事就从状态机开始。文法我就不重复了,见上一篇文章。现在我们从状态机开始。第一个状态机是直接从文法变过来的:

image

然后我们把所有的非终结符跳转都通过Shift和Reduce连接到该非终结符所代表的状态机的状态上面,就会变成下面的图。具体的做法是,对于每一条非终结符的跳转,譬如说S0 –> Symbol –> S1。首先抹掉这条跳转。然后增加两条边,分别是S0到Symbol的起始节点,操作是Shift<S0>。还有从Symbol的终结节点到S0,操作是Pop<S0> Reduce。Shift<S>等于把状态S给push到堆栈里,然后Pop<S>等于在状态里面弹出内容是S的栈顶元素。如果失败了怎么办呢?那就不能用这条跳转。跟上图一样,所有输入$跳转到Finish的边,操作都是要Pop<Null>的。在刚开始分析的时候,堆栈有一个Null值,用来代表“语法分析从这里开始”。

image

这个图的粗虚边代表所有跟左递归有关的跳转。这些边是成对的,分别是左递归跳转的Shift和Reduce。如果不是为了实现高性能的语法分析的话,其实这个状态机已经足够了。这个图跟语法分析的“状态跳转轨迹”有很大的关系。虽然IDList0你不知道第一步要跳转到IDList0还是ID0,不过没关系,现在我们先假设我们可以通过某种神秘的方法来预测到。那么,当输入是A,B,C$的时候,状态跳转轨迹就会是如下的样子:

image

为什么要这么做呢?我们把这幅图想象成为
1:想做的箭头表示push一个状态
2:向下的箭头表示修改当前状态
3:向右的状态表示pop一个状态并修改当前状态

因此当输入到B的时候,到达ID1,并跳转到IDList1。这个时候IDList1【左边】的所有【还留在堆栈里】的状态时Null和IDList0,当前状态IDList1,输入剩下,C$。这个图特别的有用。当我们分析完并且把构造语法树的指令附着在这些箭头上面之后,按顺序执行这些指令就可以构造出一颗完整的语法树了。

但是在实际操作里面,我们并没有办法预测“这里要左递归两次”,也没办法在多次reduce的时候选择究竟要从哪里跳到哪里。所以实际上我们要学习从EpsilonNFA到DFA的那个计算过程,把Shift和Reduce当成Epsilon,把吃掉一个token当成非Epsilon边,然后执行我之前写的《构造可配置词法分析器》一文中的那个去Epsilon边算法(如何从Nondeterministic到Deterministic,以及相关的Look Ahead,是下一篇文章的内容),然后就可以把状态机变成这样:

image

上面粗体的Pop<IDList0>表示,这一个Pop是对应于那个左递归Shifting操作的。实际上这是做了一个怎样的变化呢?从“物理解释”上来讲,其实是把“状态跳转轨迹”里面那些除了左递归shifting之外的所有不吃掉token的边都去掉了:

image

在这里我们可以看到,为什么当堆栈是IDList0, IDList0和IDList0, IDList3的时候,从ID0都可以通过吃掉一个”,”从而跳转到IDList3。在上面这张“状态跳转轨迹”里面,这两个事情都发生了,分别是第一条向左的箭头和第二条向左的方向。而且这两条边刚好对应于上图带有蓝色粗体文字的跳转,属于左递归Reducing操作。

所以,其实在这个时候,我们同时解决了“应该在什么时候进行左递归Shifting”的问题。只要当左递归Reducing已发生,我们立刻在轨迹上面补上一条左递归Shifting就好了。因此,我们在一开始做parsing的时候,根本不需要预先做左递归Shifting。所以当刚刚输入A的时候,“状态跳转轨迹”是这样子的:

image

然后遇到一个”,”,发现之前“做漏”了一个左递归Shifting,因此就变成下面这个样子:

image

这也就是上一篇文章那个Fake-Shift所做的事情了。

posted @ 2012-12-07 02:49 陈梓瀚(vczh) 阅读(4924) | 评论 (2)编辑 收藏

上一篇博客讲到了构造符号表的事情。构造完符号表之后,就要进入语义分析的后一个阶段了:构造状态机。跟我以前写的如何实现正则表达式引擎的两篇文章讲的一样,自动机先从Epsilon Nondeterministic Automaton开始,然后一步一步构造成Deterministic Automaton。但是语法分析和正则表达式有很大不同,那么这个自动机是什么样子的呢?

(对学术感兴趣的人可以去wiki一下“下推自动机”)

下推自动机和有限自动机的区别是,下推自动机扩展成普通的自动机的时候,他的状态的数目是无限的(废话)。但是无限的东西是没办法用编程来表达的,那怎么办呢?那就加入一个不定长度的“状态描述”。下面我举一个简单的文法:

ID = NAME
IDList = ID | IDList “,” ID

这样就构成了一个简单的文法,用来分析带逗号分割的名字列表的。那么写成状态机就是如下的形式:

ID0 = ● NAME
ID1 = NAME ●
IDList0 = ● (ID | IDList “," ID)
IDList1 = (ID | IDList “,” ID) ●
IDList2 = (ID | IDList ● “,” ID)
IDList3 = (ID | IDList “,” ● ID)

ID0 –> NAME –> ID1
IDList0 –> ID –> IDList1
IDList0 –> IDList –> IDList2
IDList2 –> “,” –> IDList3
IDList3 –> ID –> IDList1

可以很容易的看出,ID0和IDList0是文法的起始状态,而ID1和IDList1是文法的终结状态,画成图如下:

image

(PowerPoint画图复制到LiveWriter里面是一幅图面简直太方便了)

但是这样还没完。IDList0跳到IDList2的时候的输入“IDList”其实还不够,因为用作输入的token其实只有NAME和","两种。下一步即将演示如何从这个状态机编程名副其实的下推状态机。

在这里我先介绍几个概念。第一个是移进,第二个是规约。为什么要用这两个名字呢?因为大部分人看的傻逼清华大学出版社的低能编译原理课本都是这么讲的,黑化分别叫Shift和Reduce。好了,什么是Shift呢?IDList0跳到IDList2的时候,要移进IDList。IDList3跳到IDList1,要移进到ID。IDList0跳到IDList1也要移进到ID。这也就是说,状态转移经过一条非终结符的边的时候会移进到另一条文法的状态机里。ID1和IDList1作为ID和IDList的终结节点,要根据“从那里移进来的”分别规约然后跳转到“IDList2或者IDList1”。这也就是说,一旦你到达了一条闻法的状态机的终结状态,就要开始规约然后跳转到上一级的状态了

有人要问,那我怎么知道规约结束的时候要跳转去哪里呢?这个问题问得非常好。让我们回想一下我以前写的如何手写语法分析器这一篇文章。里面怎么说的?当你手写递归下降的语法分析器的时候,每一条文法其实都是一个函数。那调用函数的时候程序怎么就知道函数结束的时候下一条指令是什么呢?那当然是因为编译器帮我们把“调用函数的时候的下一条指令的地址”给push进了调用堆栈。但是我们现在不手写语法分析器了,而用下推状态机来做,道理也是一样的。在“移进”的时候,先把当前的状态push进堆栈,规约的时候,就可以看一下“栈顶那几个状态都是什么”,配合一次向前查看(这就是Look Ahead。LALR的那个LA,LALR(1)就是在LA的时候偷看一个token),来决定规约到哪里去。至于LA在这里的深刻内涵我将下一篇文章再说。因为现在我还没有做到Nondeterministic到Deterministic的一步,里面有很多黑科技,我想集中讨论。

那现在让我们把上面那幅图的两个状态机连起来,产生一个下推自动机。但是在这里我先做第一步。因为IDList0到IDList1的跳转是一个左递归的过程,先暂时不管。

image

橙色的边都是一个输入非终结符的跳转,所以实际上在下推状态机里面是不存在的。在这张图里面我们处理了两条ID的边。IDList0会shift(就是在堆栈里面push)自己然后跳转到ID0,因此ID1在查看到栈顶是IDList0的时候,他就知道走的是IDList0 –> ID –> IDList1这条路,因此就reduce并跳转到了IDList1。IDList3同理。

但是Shift的时候并没有产生输入,所以实际上应该改成下面这个样子。

image

这样Shift边也就有输入了。而且ID0到ID1也废掉了。实际上ID0自己也应该废掉。现在还有一个问题没解决,就是左递归和Reduce不产生输入的问题。这两个问题实际上是一起的。我们先来考虑一下为什么这里没办法用相同的办法来把Reduce处理成产生输入的。实际上是因为,你在这一个阶段还不知道究竟Reduce要输入什么才能跳转,特别是token已经结束并且parse出了一个完整的IDList的时候。以前你们是不是在看《Parsing Techniques》和《龙书》都对为什么一个字符串结尾要产生一个$字符感到很困惑呢?实际上他是特别有用的。现在我们来给他加上大家就明白了。在这里,这个文法的目标是产生一个IDList结构,所以$当然也要加在IDList的终结状态——IDList1上:

image

然后就轮到Reduce。ID1应该是Reduce到哪里了?第一步自然是Reduce到IDList1。那么IDList1又要Reduce到哪里呢?我们可以看到,在IDList结束的时候,要么就是跳到IDList2,要么就是跳到FINISH。但是IDList2是通过左递归产生的,我们先不管他。跳到FINISH需要什么条件呢?第一个是输入$,第二个是Pop完状态之后堆栈会为空。所以这个时候我们可以先修改一下ID1到IDList1的Reduce边:

image

最后就是左递归了。左递归的处理有点像hack,因为实际上你不能预先判断你要不要左递归(也就是看一下token stream有多少个逗号),然后先shift几个IDList0进去,再慢慢来。所以我们只有在满足跳转关系的时候临时插入一些IDList0。那么这个关系是什么呢?左递归的IDList结束——也就是从IDList0跳到IDList2——之后只有一种可能,就是输入","。而且所有指向IDList1的边都是输入ID,所以这条左递归的线应该从ID1(ID的终结状态)连到IDList2,并且在链接的时候补充“假shift IDList0”:

image

橙色的两个状态分别是整个parsing过程的起始状态和终结状态。这个时候我们把所有没用的边和状态都干掉,就变成了:

image

是不是觉得特别亲切呢,这不就是正则表达式NAME ( “,” NAME)*的状态机吗?这也是因为这个文法刚好可以表达为一个正则文法才有这样的结果,如果我们给他加点儿括号改变点优先级什么的,那就会变成一个复杂得多的状态机了。好了。现在我们来模拟一下下推状态机的状态转换和堆栈操作过程,来分析一下A,B,C$这个输入吧。

在下面的标示图里面,我们用s|abc|def来分别表达当前状态s、当前堆栈里的状态abc(栈顶在右边)和正在等待的输入def。那么初始状态肯定就是
IDList0 | null | A,B,C$

然后就开始了!(用文字表达实在是太难看了,所以贴成图)

image

如果成功到达FINISH并且堆栈和输入都全部没有了的话,那就证明,parsing过程完美结束,没有任何错误发生。

如何从文法生成下推自动机并完成parsing工作的大概过程就写到这里了。目前开发进度是到“生成非确定性下推自动机”这里。当我完成了生成“确定性下推自动机”——也就是上面的最后一个状态机图的时候——就会开始写下一篇文章,讲面对复杂的文法的时候,下推自动机将要如何调整。同时将重点描述Look Ahead部分,以及为什么LALR(1)要设计成那个样子。

posted @ 2012-12-07 00:43 陈梓瀚(vczh) 阅读(4545) | 评论 (2)编辑 收藏

群号:31724825

在最近这几年里,一起讨论编译器的人也不多,一般都是ooseven、@装配脑袋、@空明流转(<--高手,要跪)、@belleveinvis等这几个人。而且也零星有一些我也不记得叫什么名字的在我的评论里面提出过一些很好的建议,让我得到了充分的学习。因此我想,如果有兴趣的人可以加进来一起讨论的话,应该不仅对我,对大家也是有好处的。而且我本人喜欢的领域也比较分散,譬如图形界面、软件渲染、编译原理、游戏开发等等。这几个领域都有互相促进的作用,而且需要的背景知识交集又少,不同领域的人的思想和类型也不一样。如果群里的人北京分布比较广泛的话,也许还会有意想不到的idea出现。

所以只要满足以下要求的人都热烈欢迎。
1、热爱编程
2、不是来求代码的
3、不要问各种傻逼问题(譬如说为什么cout<<1+2<<endl;会有错误啊)和求写大作业(我可没时间管这些不见棺材不流泪的学生们)
4、可以交换知识就最好了

本穷丑矮不是VIP,故群人数有上限(不过我想应该是达不到的),先到先得。

引用http://www.cppblog.com/vczh/archive/2012/11/29/195779.html的三楼

老大,你的博客很好,代码很好,但是我们有时候消化不了这么快,有时候想找人交流交流,却找不到,我建议你建立一个群,把群号放在博客首页,这样研究你源码的人会聚集在一起,大家也可以讨论,你也不需要参与讨论,甚至你不在群里都可以,毕竟你时间有限,你还要去微博灌水,二次元啥的。

这样你也没啥损失。但对祖国的编译器苦手们就大有帮助。
(后略)
posted @ 2012-11-29 02:53 陈梓瀚(vczh) 阅读(18524) | 评论 (13)编辑 收藏

上一篇博客讲到了构造语法树的问题。有朋友在留言问我,为什么一定要让语法分析器产生语法树,而不是让用户自己决定要怎么办呢?在这里我先解答这个问题。

1、大部分情况下都是真的需要有语法树
2、如果要直接返回计算结果之类的事情的话,只需要写一个visitor运行一下语法树就好了,除去自动生成的代码以外(反正这不用人写,不计入代价),代码量基本上没什么区别
3、加入语法树可以让文法本身描述起来更简单,如果要让程序员把文法单独放在一边,然后自己写完整的语义函数来让他生成语法树的话,会让大部分情况(需要语法树)变得特别复杂,而少数情况(不需要语法树)又没有获得什么好处。

尽管类似yacc这样的东西的确是不包含语法树的内容而要你自己写的,但是用起来难道不是很难受吗?

现在转入正题。这一篇文章讲的主要是构造符号表的问题。想要把符号表构造的好是一件很麻烦的问题。我曾经尝试过很多种方法,包括强类型的符号表,弱类型的符号表,基于map的符号表等等,最后还是挑选了跟Visual Studio自带的用来读pdb文件的DIA类其中的IDIASymbol(http://msdn.microsoft.com/en-us/library/w0edf0x4.aspx)基本上一样的结构:所有的符号都只有这么一个symbol类,然后包罗万象,什么都有。为什么最后选择这么做呢?因为在做语义分析的时候,其实做的最多的事情不是构造符号表,而是查询符号表。如果符号表是强类型的画,譬如说类型要一个类,变量要一个类,函数要一个类之类的,总是需要到处cast来cast去,也找不到什么好方法来在完成相同事情的情况下,保留强类型而不在代码里面出现cast。为什么语法树就要用visitor来解决这个问题,而符号表就不行呢?因为通常我们在处理语法树的时候都是递归的形式,而符号表并不是。在一个上下文里面,实际上我们是知道那个symbol对象究竟是什么东西的(譬如说我们查询了一个变量的type,那这返回值肯定只能是type了)。这个时候我们要cast才能用,本身也只是浪费表情而已。这个时候,visitor模式就不是和面对这种情况了。如果硬要用visitor模式来写,会导致语义分析的代码分散得过于离谱导致可读性几乎就丧失了。这是一个辩证的问题,大家可以好好体会体会。

说了这么一大段,实际上就是怎么样呢?让我们来看“文法规则”本身的符号表吧。既然这个新的可配置语法分析器也是通过parse一个文本形式的文法规则来生成parser,那实际上就跟编译器一样要经历那么多阶段,其中肯定有符号表:

class ParsingSymbol : public Object
{
public:
    enum SymbolType
    {
        Global,
        EnumType,
        ClassType,        // descriptor == base type
        ArrayType,        // descriptor == element type
        TokenType,
        EnumItem,        // descriptor == parent
        ClassField,        // descriptor == field type
        TokenDef,        // descriptor == token type
        RuleDef,        // descriptor == rule type
    };
public:
    ~ParsingSymbol();

    ParsingSymbolManager*            GetManager();
    SymbolType                        GetType();
    const WString&                    GetName();
    vint                            GetSubSymbolCount();
    ParsingSymbol*                    GetSubSymbol(vint index);
    ParsingSymbol*                    GetSubSymbolByName(const WString& name);
    ParsingSymbol*                    GetDescriptorSymbol();
    ParsingSymbol*                    GetParentSymbol();
    bool                            IsType();
    ParsingSymbol*                    SearchClassSubSymbol(const WString& name);
    ParsingSymbol*                    SearchCommonBaseClass(ParsingSymbol* classType);
};

因为文法规则本身的东西也不多,所以这里的symbol只能是上面记载的9种对象。这些对象其实特别的相似,所以我们可以看出唯一的区别就是当GetType返回值不一样的时候,GetDescriptorSymbol返回的对象的意思也不一样。而这个区别记载在了enum SymbolType的注释里面。实际上这种做法在面对超级复杂的符号表(考虑一下C++编译器)的时候并不太好。那好的做法究竟是什么呢?看上面IDIASymbol的链接,那就是答案。

不可否认,微软设计出来的API大部分还是很有道理的,除了Win32的原生GUI部分。

我们还可以看到,这个ParsingSymbol类的几乎所有成员函数都是用来查询这个Symbol的内容的。这里还有两个特殊的函数,就是SearchClassSubSymbol和SearchCommonBaseClass——当且仅当symbol是ClassType的时候才起作用。为什么有了GetSubSymbolByName,还要这两个api呢?因为我们在搜索一个类的成员的时候,是要搜索他的父类的。而一个类的父类的sub symbol并不是类自己的sub symbol,所以就有了这两个api。所谓的sub symbol的意思现在也很明了了。enum类型里面的值就是enum的sub symbol,成员变量是类的sub symbol,总之只要是声明在一个符号内部的符号都是这个符号的sub symbol。这就是所有符号都有的共性。

当然,有了ParsingSymbol,还要有他的manager才可以完成整个符号表的操作:

class ParsingSymbolManager : public Object
{
public:
    ParsingSymbolManager();
    ~ParsingSymbolManager();

    ParsingSymbol*                    GetGlobal();
    ParsingSymbol*                    GetTokenType();
    ParsingSymbol*                    GetArrayType(ParsingSymbol* elementType);

    ParsingSymbol*                    AddClass(const WString& name, ParsingSymbol* baseType, ParsingSymbol* parentType=0);
    ParsingSymbol*                    AddField(const WString& name, ParsingSymbol* classType, ParsingSymbol* fieldType);
    ParsingSymbol*                    AddEnum(const WString& name, ParsingSymbol* parentType=0);
    ParsingSymbol*                    AddEnumItem(const WString& name, ParsingSymbol* enumType);
    ParsingSymbol*                    AddTokenDefinition(const WString& name);
    ParsingSymbol*                    AddRuleDefinition(const WString& name, ParsingSymbol* ruleType);

    ParsingSymbol*                    CacheGetType(definitions::ParsingDefinitionType* type, ParsingSymbol* scope);
    bool                            CacheSetType(definitions::ParsingDefinitionType* type, ParsingSymbol* scope, ParsingSymbol* symbol);
    ParsingSymbol*                    CacheGetSymbol(definitions::ParsingDefinitionGrammar* grammar);
    bool                            CacheSetSymbol(definitions::ParsingDefinitionGrammar* grammar, ParsingSymbol* symbol);
    ParsingSymbol*                    CacheGetType(definitions::ParsingDefinitionGrammar* grammar);
    bool                            CacheSetType(definitions::ParsingDefinitionGrammar* grammar, ParsingSymbol* type);
};

这个ParsingSymbolManager有着符号表管理器的以下两个典型作用

1、创建符号。
2、讲符号与语法树的对象绑定起来。譬如说我们在一个context下面推导了一个expression的类型,那下次对于同样的context同样的expression就不需要再推导一次了(语义分析有很多个pass,对同一个expression求类型的操作经常会重复很多次),把它cache下来就可以了。
3、搜索符号。具体到这个符号表,这个功能被做进了ParsingSymbol里面。
4、保存根节点。GetGlobal函数就是干这个作用的。所有的根符号都属于global符号的sub symbol。

因此我们可以怎么使用他呢?首先看上面的Add函数。这些函数不仅会帮你在一个符号表里面添加一个sub symbol,还会替你做一些检查,譬如说阻止你添加相同名字的sub symbol之类的。语法树很复杂的时候,很多时候我们有很多不同的方法来给一个符号添加子符号,譬如说C#的成员变量和成员函数。成员变量不能同名,成员函数可以,但是成员函数和成员变量却不能同名。这个时候我们就需要把这些添加操作封装起来,这样才可以在处理语法树(声明一个函数的方法可以有很多,所以添加函数符号的地方也可以有很多)的时候不需要重复写验证逻辑。

其次就是Cache函数。其实Cache函数这么写,不是用来直接调用的。举个例子,在分析一个文法的时候,我们需要把一个“类型”语法树转成一个“类型”符号(譬如说要决定一个文法要create什么类型的语法树节点的时候)。因此就有了下面的函数:

ParsingSymbol* FindType(Ptr<definitions::ParsingDefinitionType> type, ParsingSymbolManager* manager, ParsingSymbol* scope, collections::List<Ptr<ParsingError>>& errors)
{
    ParsingSymbol* result=manager->CacheGetType(type.Obj(), scope);
    if(!result)
    {
        FindTypeVisitor visitor(manager, (scope?scope:manager->GetGlobal()), errors);
        type->Accept(&visitor);
        result=visitor.result;
        manager->CacheSetType(type.Obj(), scope, result);
    }
    return result;
}

很明显,这个函数做的事情就是,查询一个ParsingDefinitionType节点有没有被查询过,如果有直接用cache,没有的话再从头计算他然后cache起来。因此这些Cache函数就是给类似FindType的函数用的,而语义分析的代码则直接使用FindType,而不是Cache函数,来获取一个类型的符号。聪明的朋友们可以看出来,这种写法蕴含着一个条件,就是语法树创建完就不会改了(废话,当然不会改!)。

这一篇的内容就讲到这里了。现在的进度是正在写文法生成状态机的算法。下一篇文章应该讲的就是状态机究竟是怎么运作的了。文法所需要的状态机叫做下推状态机(push down automaton),跟regex用的NFA和DFA不太一样,理解起来略有难度。所以我想需要用单独的一篇文章来通俗的讲一讲。

posted @ 2012-11-28 08:50 陈梓瀚(vczh) 阅读(6744) | 评论 (6)编辑 收藏

就像之前的博客文章所说的,(主要还是)因为GacUI的原因,我决定开发一个更好的可配置轻量级语法分析器来代替之前的落后的版本。在说这个文章之前,我还是想在此向大家推荐一本《编程语言实现模式》,这的确是一本好书,让我相见恨晚。

其实说到开发语法分析器,我从2007年就已经开始在思考类似的问题了。当时C++还处于用的不太熟练的时候,难免会做出一些傻逼的事情,不过总的来说当年的idea还是能用的。从那时候开始,我为了锻炼自己,一直在实现各种不同的语言。所以给自己开发一个可配置语法分析器也是在所难免的事情了。于是就有:
第一版:http://hi.baidu.com/geniusvczh/archive/tag/syngram%E6%97%A5%E5%BF%97
第二版:http://www.cppblog.com/vczh/archive/2009/04/06/79122.html
第三版:http://www.cppblog.com/vczh/archive/2009/12/13/103101.html
还有第三版的教程:http://www.cppblog.com/vczh/archive/2010/04/28/113836.html

上面的所有分析器都致力于在C++里面可以通过直接描述文法和一些语义行为来让系统可以迅速构造出一个针对特定目的的用起来方便的语法分析器,而“第三版”就是到目前为止还在用的一个版本。至于为什么我要做一个新的——也就是第四版——之前的文章已经说了。

而今天,第四版的开发已经开始了有好几天。如果大家关心进度的话,可以去GacUI的Codeplex页面下载代码,然后阅读Common\Source\Parsing下面的源文件。对应的单元测试可以在Common\UnitTest\UnitTest\TestParsing.cpp里找到。

于是今天就说说关于构造语法树的事情。

用C++写过parser的人都知道,构造语法树以及语义分析用的符号表是一件极其繁琐,而且一不小心就容易写出翔的事情。但是根据我写过无穷多棵语法树以及构造过无穷多个符号表以及附带的副作用,翔,啊不,经验,做这个事情还是有一些方法的。

在介绍这个方法之前,首先要说一句,人肉做完下面的所有事情是肯定要疯掉的,所以这一次的可配置语法分析器我已经决定了一定要TMD写出一个生成语法树的C++代码的工具。

一颗语法树,其实就是一大堆互相继承的类。一切成熟的语法树结构所具有的共同特征,不是他的成员怎么安排,而是他一定会附带一个visitor模式的机制。至于什么是visitor模式,大家请自行参考设计模式,我就不多说废话了。这一次的可配置语法分析器是带有一个描述性语法的。也就是说,跟Antlr或者Yacc一样,首先在一个文本文件里面准备好语法树结构和文法规则,然后我的工具会帮你生成一个内存中的语法分析器,以及用C++描述的语法树的声明和实现文件。这个描述性语法就类似下面的这个大家熟悉到不能再熟悉的带函数的四则运算表达式结构:

class Expression
{
}

class NumberExpression : Expression
{
    token value;
}

class BinaryExpression : Expression
{
    enum BinaryOperator
    {
        Add,
        Sub,
        Mul,
        Div,
    }

    Expression firstOperand;
    Expression secondOperand;
    BinaryOperator binaryOperator;
}

class FunctionExpression : Expression
{
    token functionName;
    Expression[] arguments;
}

token NAME = "[a-zA-Z_]/w*";
token NUMBER = "/d+(./d+)";
token ADD = "/+";
token SUB = "-";
token MUL = "/*";
token DIV = "//";
token LEFT = "/(";
token RIGHT = "/)";
token COMMA = ",";

rule NumberExpression Number
        = NUMBER : value;

rule FunctionExpression Call
        = NAME : functionName "(" [ Exp : arguments { "," Exp : arguments } ] ")";

rule Expression Factor
        = !Number | !Call;

rule Expression Term
        = !Factor;
        = Term : firstOperand "*" Factory : secondOperand as BinaryExpression with { binaryOperator = "Mul" };
        = Term : firstOperand "/" Factory : secondOperand as BinaryExpression with { binaryOperator = "Div" };

rule Expression Exp
        = !Term;
        = Exp : firstOperand "+" Term : secondOperand as BinaryExpression with { binaryOperator = "Add" };
        = Exp : firstOperand "-" Term : secondOperand as BinaryExpression with { binaryOperator = "Sub" };

上面的语法树声明借用的C#语法,描述起来特别简单。但是要在C++里面达到可以使用的程度,肯定要有一个自带的visitor模式。所以出来之后的代码大概就类似于下面这个样子:

class Expression;
class NumberExpression;
class BinaryExpression;
class FunctionExpression;

class Expression : public ParsingTreeCustomBase
{
public:
    class IVisitor : public Interface
    {
    public:
        virtual void Visit(NumberExpression* node)=0;
        virtual void Visit(BinaryExpression* node)=0;
        virtual void Visit(FunctionExpression* node)=0;
    };

    virtual void Accept(IVisitor* visitor)=0;
};

class NumberExpression : public Expression
{
public:
    TokenValue value;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class BinaryExpression : public Expression
{
public:
    enum BinaryOperator
    {
        Add, Sub, Mul, Div,
    };
    Ptr<Expression> firstOperator;
    Ptr<Expression> secondOperator;
    BinaryOperator binaryOperator;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class FunctionExpression : public Expression
{
public:
    TokenValue functionName;
    List<Ptr<Expression>> arguments;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

为什么要这样做呢?学习过面向对象开发方法的都知道,把一个明显是继承结构的东西写成一堆union/struct和一个enum来判断他们,是不对的。第一个不好的地方就是,如果其中的成员需要构造函数和析构函数,那union就用不了了,struct就一定会造成大量的内存浪费。因为一颗语法树是可以很大的。其次,当语法树的结构(主要是添加删除了新的语法树类型)之后,我们根本不可能保证我们所有的swtich(node->enumType)语句都接受到了正确的更新。

那要如何解决这两个问题呢?答案之一就是使用visitor模式。尽管刚开始写起来的时候可能会有点别扭,但是我们只要把原本是swtich结构的代码做一下Continuation Passing Style变换,就可以写出使用visitor的版本了。在这里我做一个小小的演示,如何把一个“把上面的语法树还原成四则运算式子的函数”给用Expression::IVisitor的框架下实现出来:

class FunctionExpression : public Expression
{
public:
    TokenValue functionName;
    List<Ptr<Expression>> arguments;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class ExpressionPrinter : public Expression::IVisitor
{
public:
    WString result;

    void Visit(NumberExpression* node)
    {
        result+=node->value.stringValue;
    }

    void Visit(BinaryExpression* node)
    {
        result+=L"(";
        node->firstOperand->Accept(this);
        switch(binaryOperator)
        {
        case Add: result+=L" + "; break;
        case Sub: result+=L" - "; break;
        case Mul: result+=L" * "; break;
        case Div: result+=L" / "; break;
        }
        node->secondOperand->Accept(this);
        result+=L")";
    }

    void Visit(FunctionExpression* node)
    {
        result+=node->functionName.stringValue+L"(";
        for(int i=0;i<arguments.Count();i++)
        {
            if(i>0) result+=L", ";
            arguments[i]->Accept(this);
        }
        result+=L")";
    }
};

WString PrintExpression(Ptr<Expression> expression)
{
    ExpressionPrinter printer;
    expression->Accept(&printer);
    return printer.result;
}

其实大家可以看到,使用了visitor模式,代码量其实也没有多大变化,本来是递归的地方还是递归,本来该计算什么还计算什么,唯一不同的就是原本这个“函数”的参数和返回值都跑到了一个visitor类的成员变量里面去了。当然,为了便于使用,一般来说我们会把原本的函数的原型写出来,并且在里面调用visitor模式,就像上面的PrintExpression函数一样。如果我们高兴的话,完全可以在ExpressionPrinter这个visitor类里面使用PrintExpression,无非就是在里面构造新的ExpressionPrinter然后获取结构罢了。一般来说,visitor类都是非常的轻量级的,在现今的CPU性能下面,构造多几个完全不会带来多大影响。

可配置语法分析器既然拥有一个描述性语法,那么我肯定也针对这个描述性语法写了一颗语法树的。这颗语法树的代码在Common\Source\Parsing\ParsingDefinition.h里面,而ParsingLogging.cpp则是跟上面说的一样,用visitor的方法写了一个庞大的把语法树转回描述性语法的函数。这个函数非常有用,不仅可以用来打log,还可以用来保存程序生成的一个语法规则(反正可以parse回来,所以保存成文本是一件特别方便的事情),甚至是生成错误消息的片段等等。

今天就先讲到这里了。现在的可配置语法分析器的开发进度是正在写语义分析的部分。等到语义分析写完了,我会再写一篇纪事来说明开发语义分析程序和构造符号表的一般做法。

posted @ 2012-11-21 06:42 陈梓瀚(vczh) 阅读(11531) | 评论 (6)编辑 收藏
     摘要: Uniscribe是Windows 2000以来就存在于WinAPI中的一个库。这个库能够提供给我们关于字符串渲染的很多信息,譬如说哪里可以换行啦,渲染的时候字符的顺序应该是什么样子啦,还有每一个字符的大小什么的。关于Uniscribe的资料可以在http://msdn.microsoft.com/en-us/library/windows/desktop/dd374091(v=vs.85).as...  阅读全文
posted @ 2012-11-06 06:34 陈梓瀚(vczh) 阅读(5031) | 评论 (5)编辑 收藏

由于接下去要用uniscribe(这是一个可以告诉我们在渲染一个超长unicode字符串的时候,什么地方可以换行,什么地方要换顺序,什么字符要用一种神奇的方法来渲染之类的库)做可以插入图片和其它乱七八糟东西的rich text box,为了更方便做实验,而且也考虑到很多软件也需要直接绘图的功能,所以我写了这么两个Demo:

1、Rendering.RawAPI.GDI(http://www.gaclib.net/Demos/Rendering.RawAPI.GDI/Demo.html
2、Rendering.RawAPI.Direct2D(
http://www.gaclib.net/Demos/Rendering.RawAPI.Direct2D/Demo.html

由于这两个Demo很像,而且Direct2D的比较复杂,所以我在这里介绍一下这个Direct2D的demo。

在Demo里面可以看到,我们可以使用GuiGDIElement或者GuiDirect2DElement来进行手工的绘图操作。这两个Element的使用有限制。当GacUI使用GDI绘图(SetupWindowsGDIRenderer)的时候才可以使用GuiGDIElement,对于Direct2D也是一样的。在使用它们进行绘图的时候,坐标用的是窗口的坐标。但是GacUI会在绘制的时候先加入一个clip,这样我们在绘制的时候就算绘制出了边界,也不会有任何不好的影响。而且这个clip的矩形范围会在渲染事件触发的时候给出。在这里我们先来看一下Direct2D的demo。

首先,整个程序的框架是这样子的:

#include "..\..\Public\Source\GacUI.h"
#include <math.h>
#include <Windows.h>

int CALLBACK WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int CmdShow)
{
    // SetupWindowsDirect2DRenderer() is required for GuiDirect2DElement
    return SetupWindowsDirect2DRenderer();
}

class Direct2DWindow : public GuiWindow
{
protected:

    // arguments.rt is ID2D1RenderTarget.
    void element_Rendering(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
    {
    }

    // The render target is going to be destroyed, any binded resources should be released.
    void element_BeforeRenderTargetChanged(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
    {
    }

    // The new render target is prepared, any binded resources are allowed to recreate now.
    void element_AfterRenderTargetChanged(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
    {
    }
public:
    Direct2DWindow()
        :GuiWindow(GetCurrentTheme()->CreateWindowStyle())
    {
        SetText(L"Rendering.RawAPI.Direct2D");
        SetClientSize(Size(640, 480));
        GetBoundsComposition()->SetPreferredMinSize(Size(640, 480));
        MoveToScreenCenter();
        {
            GuiDirect2DElement* element=GuiDirect2DElement::Create();
           
element->Rendering.AttachMethod(this, &Direct2DWindow::element_Rendering);
           
element->BeforeRenderTargetChanged.AttachMethod(this, &Direct2DWindow::element_BeforeRenderTargetChanged);
            element->AfterRenderTargetChanged.AttachMethod(this, &Direct2DWindow::element_AfterRenderTargetChanged);

            GuiBoundsComposition* composition=new GuiBoundsComposition;
            composition->SetAlignmentToParent(Margin(0, 0, 0, 0));
            composition->SetOwnedElement(element);
            GetContainerComposition()->AddChild(composition);
        }
    }
};

void GuiMain()
{
    Direct2DWindow window;
    GetApplication()->Run(&window);
}

在构造函数里面,我们创建了一个GuiDirect2DElement,然后把它放进一个会自动充满整个窗口的composition里面。然后我们需要监听三个事件(GDI只有一个,就是Rendering):
1、Rendering。这个事件在窗口被绘制的时候调用。GacUI才用了一个低功耗的方法让程序不断的绘制自己,所以我们并不需要担心“如何刷新窗口”的这个问题。
2、BeforeRenderTargetChanged。在这个时候我们要清理掉我们创建出来的资源,譬如说画刷等等。
3、AfterRenderTargetChanged。在这个时候我们要建立一些绘图资源,譬如说画刷等等。

为什么下面两个函数那么蛋疼呢?因为Direct2D的类似画刷这样的东西,是必须跟一个ID2D1RenderTarget绑定在一起的,不同的render target之间的画刷不能共享。而且那个可怜的render target还有可能会失效,这个时候GacUI就要重新创建他们。所以无论如何,都必须监听这三个对象,除非我们只用GuiDirect2DElement来渲染文字(因为文字相关的资源是IDWriteFactory控制的,跟render target无关)。

在这个Demo里面,我们要画的是一个会动的钟。在这个钟里面我们要绘制4种线形:边框、时针、分针、秒针。因此我们需要4个不同的ID2D1SolidColorBrush。由于操作COM对象的时候总要去记得操作那个引用计数,特别的麻烦,而且还容易忘掉。所以我特地为大家提供了一个叫做ComPtr的东西。所以我们就可以这么声明、创建和释放他们:

ComPtr<ID2D1SolidColorBrush>            borderBrush;
ComPtr<ID2D1SolidColorBrush>            secondBrush;
ComPtr<ID2D1SolidColorBrush>            minuteBrush;
ComPtr<ID2D1SolidColorBrush>            hourBrush;

// The render target is going to be destroyed, any binded resources should be released.
void element_BeforeRenderTargetChanged(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
{
    borderBrush=0;
    secondBrush=0;
    minuteBrush=0;
    hourBrush=0;
}

// The new render target is prepared, any binded resources are allowed to recreate now.
void element_AfterRenderTargetChanged(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
{
    ID2D1SolidColorBrush* brush;
    {
        brush=0;
        arguments.rt->CreateSolidColorBrush(D2D1::ColorF(0.0f, 0.0f, 0.0f), D2D1::BrushProperties(), &brush);
        borderBrush=brush;
    }
    {
        brush=0;
        arguments.rt->CreateSolidColorBrush(D2D1::ColorF(0.0f, 0.0f, 1.0f), D2D1::BrushProperties(), &brush);
        secondBrush=brush;
    }
    {
        brush=0;
        arguments.rt->CreateSolidColorBrush(D2D1::ColorF(0.0f, 1.0f, 0.0f), D2D1::BrushProperties(), &brush);
        minuteBrush=brush;
    }
    {
        brush=0;
        arguments.rt->CreateSolidColorBrush(D2D1::ColorF(1.0f, 0.0f, 0.0f), D2D1::BrushProperties(), &brush);
        hourBrush=brush;
    }
}

想必大家都应该看清楚了。Before和After事件里面,GacUI都会提供用来绘图的ID2D1RenderTarget,这个时候必须正确的创建和释放资源。只要这些资源都建立了起来,那么剩下的就只有把一个时钟画出来了。画一个时钟还是很容易的,只需要那么几行代码就行了:

static const int                        Radius=200;
static const int                        LongScale=10;
static const int                        ShortScale=5;
static const int                        SecondLength=180;
static const int                        MinuteLength=150;
static const int                        HourLength=120;

float GetAngle(float second)
{
    return (second-15.0f)*3.1416f/30.0f;
}

void DrawLine(ID2D1RenderTarget* rt, ComPtr<ID2D1SolidColorBrush> brush, float angle, int width, int startLength, int endLength, int x, int y)
{
    float s=sin(angle);
    float c=cos(angle);
    float x1=(c*startLength)+(float)(x+Radius);
    float y1=(s*startLength)+(float)(y+Radius);
    float x2=(c*endLength)+(float)(x+Radius);
    float y2=(s*endLength)+(float)(y+Radius);
    rt->DrawLine(D2D1::Point2F(x1, y1), D2D1::Point2F(x2, y2), brush.Obj(), (float)width);
}

// arguments.rt is ID2D1RenderTarget.
void element_Rendering(GuiGraphicsComposition* sender, GuiDirect2DElementEventArgs& arguments)
{
    int w=arguments.bounds.Width();
    int h=arguments.bounds.Height();
    int x=arguments.bounds.Left()+(w-Radius*2)/2;
    int y=arguments.bounds.Left()+(h-Radius*2)/2;

    arguments.rt->DrawEllipse(D2D1::Ellipse(D2D1::Point2F((float)(x+Radius), (float)(y+Radius)), (float)Radius, (float)Radius), borderBrush.Obj());
    for(int i=0;i<60;i++)
    {
        int scale=i%5==0?LongScale:ShortScale;
        float angle=GetAngle((float)i);
        DrawLine(arguments.rt, borderBrush, angle, 1, Radius-scale, Radius, x, y);
    }

    DateTime dt=DateTime::LocalTime();
    {
        float angle=GetAngle(dt.hour*5+dt.minute/12.0f+dt.second/720.0f);
        DrawLine(arguments.rt, hourBrush, angle, 5, 0, HourLength, x, y);
    }
    {
        float angle=GetAngle(dt.minute+dt.second/60.0f);
        DrawLine(arguments.rt, minuteBrush, angle, 3, 0, MinuteLength, x, y);
    }
    {
        float angle=GetAngle((float)dt.second);
        DrawLine(arguments.rt, secondBrush, angle, 1, 0, SecondLength, x, y);
    }
}

然后我们就获得了下图:(LiveWrite真是太好了,cppblog的傻逼编辑器每次插入图片都会插入到一个诡异的位置中去)

DXGUI_58

这样我们就完成了一个时钟的制作了,而且也学会了如何在GacUI里面直接使用GDI和Direct2D绘图了。

posted @ 2012-11-05 07:14 陈梓瀚(vczh) 阅读(4458) | 评论 (2)编辑 收藏

因为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 @ 2012-10-29 08:23 陈梓瀚(vczh) 阅读(3936) | 评论 (6)编辑 收藏

在S1死程群@kula的鼓励下,我开始使用kula提供的api来操作那个傻逼的“鸟窝”网站(https://www.niaowo.me)。不过由于我自己在业余时间写的程序都喜欢用C++和Windows API,因此我琢磨了几天,真的让我用C++给写了出来。

我写了一个HttpUtility库来实现C++操作http/https服务的功能,这份代码可以在这里获得:

HttpUtility.h:http://gac.codeplex.com/SourceControl/changeset/view/95641#2295555
HttpUtility.cpp:http://gac.codeplex.com/SourceControl/changeset/view/95641#2295554

使用的时候很简单,只需要HttpRequest里面填满了参数,然后就可以用HttpQuery参数获得一个HttpResponse类型,这个类型里面写满了http服务器的返回值、返回内容和cookie等的数据。譬如说用来post来登陆鸟窝,然后拿到cookie之后查询首页的所有帖子,大概就可以这么写:

WString NestleGetSession(const WString& username, const WString& password, const WString& apiKey, const WString& apiSecret)
{
    WString body=L"api_key="+apiKey+L"&api_secret="+apiSecret+L"&username="+username+L"&password="+password;

    HttpRequest request;
    HttpResponse response;

    request.SetHost(L"https://www.niaowo.me/account/token/");
    request.method=L"POST";
    request.contentType=L"application/x-www-form-urlencoded";
    request.SetBodyUtf8(body);
    HttpQuery(request, response);

    if(response.statusCode==200)
    {
        return response.cookie;
    }
    else
    {
        return L"";
    }
}

WString NestleGetXml(const WString& path, const WString& cookie)
{
    HttpRequest request;
    HttpResponse response;

    request.SetHost(L"https://www.niaowo.me"+path+L".xml");
    request.method=L"GET";
    request.cookie=cookie;
    request.acceptTypes.Add(L"application/xml");
    HttpQuery(request, response);
   

    if(response.statusCode==200)
    {
        return response.GetBodyUtf8();
    }
    else
    {
        return L"";
    }
}

于是我们终于获得了一个保存在vl::WString的xml字符串了,那怎么办呢?这个时候需要出动IXMLDOMDocument2来解析我们的xml。只要装了IE的计算机上都是有IXMLDOMDocument2的,而不装IE的Windows PC是不存在的,因此我们总是可以大胆的使用。当然,用IXMLDOMDocument直接来遍历什么东西特别的慢,所以我们需要的是xpath。xpath对于xml就跟regex对于字符串一样,可以直接查询出我们要的东西。首先看一下如何操作IXMLDOMDocument2接口:

IXMLDOMNodeList* XmlQuery(IXMLDOMNode* pDom, const WString& xpath)
{
    IXMLDOMNodeList* nodes=0;
    BSTR xmlQuery=SysAllocString(xpath.Buffer());
    if(xmlQuery)
    {
        HRESULT hr=pDom->selectNodes(xmlQuery, &nodes);
        if(FAILED(hr))
        {
            nodes=0;
        }
        SysFreeString(xmlQuery);
    }
    return nodes;
}

WString XmlReadString(IXMLDOMNode* node)
{
    WString result;
    BSTR text=0;
    HRESULT hr=node->get_text(&text);
    if(SUCCEEDED(hr))
    {
        const wchar_t* candidateItem=text;
        result=candidateItem;
        SysFreeString(text);
    }
    return result;
}

void XmlReadMultipleStrings(IXMLDOMNodeList* textNodes, List<WString>& candidates, int max)
{
    candidates.Clear();
    while((int)candidates.Count()<max)
    {
        IXMLDOMNode* textNode=0;
        HRESULT hr=textNodes->nextNode(&textNode);
        if(hr==S_OK)
        {
            candidates.Add(XmlReadString(textNode));
            textNode->Release();
        }
        else
        {
            break;
        }
    }
}

IXMLDOMDocument2* XmlLoad(const WString& content)
{
    IXMLDOMDocument2* pDom=0;
    HRESULT hr=CoCreateInstance(__uuidof(DOMDocument60), NULL, CLSCTX_INPROC_SERVER, IID_PPV_ARGS(&pDom));
    if(SUCCEEDED(hr))
    {
        pDom->put_async(VARIANT_FALSE);
        pDom->put_validateOnParse(VARIANT_FALSE);
        pDom->put_resolveExternals(VARIANT_FALSE);

        BSTR xmlContent=SysAllocString(content.Buffer());
        if(xmlContent)
        {
            VARIANT_BOOL isSuccessful=0;
            hr=pDom->loadXML(xmlContent, &isSuccessful);
            if(!(SUCCEEDED(hr) && isSuccessful==VARIANT_TRUE))
            {
                pDom->Release();
                pDom=0;
            }
            SysFreeString(xmlContent);
        }
    }
    return pDom;
}

有了这几个函数之后,我们就可以干下面的事情,譬如说从鸟窝首页下载第一页的所有topic的标题:

WString xml=NestleGetXml(L”/topics”, cookie);
IXMLDOMDocument2* pDom=XmlLoad(xml);
List<WString> titles;
IXMLNodeList* nodes=XmlQuery(pDom, L”/hash/topics/topic/title/text()”);
XmlReadMultipleStrings(nodes, titles, 100);

为什么上面的xpath是hash/topics/topic/title/text()呢?因为这个xml的内容大概类似于:
<hash>
    <topics>
        <topic>
            <title>TITLE</title>

剩下的大家就去看代码吧。这个故事告诉我们,只要有一个合适的封装,C++写起这些本来应该让C#来写的东西也不是那么的烦人的,啊哈哈哈哈。

posted @ 2012-10-26 23:19 陈梓瀚(vczh) 阅读(3854) | 评论 (1)编辑 收藏
仅列出标题
共35页: 1 2 3 4 5 6 7 8 9 Last