随笔-91  评论-137  文章-0  trackbacks-0
《面向组合子的一些测试》 进一步完善代码,制作出词法分析器.

我们首先需要一个Fail基类,他有一个纯虚函数Parser.
1 class Fail
2 {
3 public:
4     virtual NWString Parser(NWString& input)=0;
5 };
Parser的输入为要分析的字符串,输出为分析完成后剩余的字符串.

然后我们需要一个Ch和一个Str分别用来分析单个字符和一个字符串.
 1 class Ch : public Fail
 2 {
 3 public:
 4     Ch(WCHAR _value) : value(_value){}
 5 
 6     NWString Parser(NWString& input);
 7 
 8     WCHAR Value();
 9 protected:
10     WCHAR value; // 待匹配串
11 };
12 
13 class Str : public Fail
14 {
15 public:
16     Str(NWString _value) : value(_value){}
17 
18     NWString Parser(NWString& input);
19 protected:
20     NWString value; // 待匹配串
21 };

然后是Seq,Alt和Any,分别表示组合,选择和循环.
 1 class Seq : public Fail
 2 {
 3 public:
 4     Seq(const NAutoPtr<Fail>& _left,const NAutoPtr<Fail>& _right) : left(_left),right(_right){}
 5 
 6     NWString Parser(NWString& input);
 7 protected:
 8     NAutoPtr<Fail> left;
 9     NAutoPtr<Fail> right;
10 };
11 
12 class Alt : public Fail
13 {
14 public:
15     Alt(const NAutoPtr<Fail>& _left,const NAutoPtr<Fail>& _right) : left(_left),right(_right){}
16 
17     NWString Parser(NWString& input);
18 protected:
19     NAutoPtr<Fail> left;
20     NAutoPtr<Fail> right;
21 };
22 
23 class Any : public Fail
24 {
25 public:
26     Any(const NAutoPtr<Fail>& _left,const int _count) : left(_left),count(_count){}
27 
28     NWString Parser(NWString& input);
29 protected:
30     NAutoPtr<Fail> left;
31     int count;
32 };

最后我们需要一个Node类型来存放以上这几类对象.
 1 class Node
 2 {
 3 public:
 4     Node(){}
 5     Node(const NAutoPtr<Fail>& _left) : left(_left){}
 6 
 7     friend NAutoPtr<Node> operator+(const NAutoPtr<Node>& left,const NAutoPtr<Node>& right);
 8     friend NAutoPtr<Node> operator|(const NAutoPtr<Node>& left,const NAutoPtr<Node>& right);
 9     friend NAutoPtr<Node> operator-(const NAutoPtr<Node>& left,const NAutoPtr<Node>& right);
10 
11     static NAutoPtr<Node> OnceMore(NAutoPtr<Node> node);
12     static NAutoPtr<Node> More(NAutoPtr<Node> node);
13     static NAutoPtr<Node> NewCh(WCHAR input);
14     static NAutoPtr<Node> NewStr(NWString input);
15 
16     NWString Parser(NWString& input);
17 
18     NAutoPtr<Fail>& Value();
19 protected:
20     NAutoPtr<Fail> left;
21 };
下面来分析一下Node里的函数:
+:对应于Seq,用于将两个Node连接起来.
|:对应与Alt,用于选择两个Node.
-:只有left和right的Value()都是NAutoPtr<Ch>时才可使用,内部有类型转换,表示从哪个字符到哪个字符.
OnceMore:重复1次及以上.
More:重复0次以上.
NewCh:生成一个NAutoPtr<Ch>的Node对象.
NewStr:生成一个NAutoPtr<Str>的Node对象.

下面我们需要4个宏.
1 #define ONCEMORE(N)                    Node::OnceMore(N)
2 #define MORE(N)                        Node::More(N)
3 #define NEWCH(N)                    Node::NewCh(N)
4 #define NEWSTR(N)                    Node::NewStr(N)
这4个宏仅为了输入方便

然后我们来测试一下:
1     NAutoPtr<Node> Symbol = ONCEMORE(NEWCH('_'| NEWCH('a'- NEWCH('z')) | (NEWCH('A'- NEWCH('Z'))
2         + MORE(NEWCH('_'| (NEWCH('0'- NEWCH('9')) | (NEWCH('a'- NEWCH('z')) | (NEWCH('A'- NEWCH('Z')));
3     NAutoPtr<Node> Number = ONCEMORE(NEWCH('0'- NEWCH('9'));
4     NAutoPtr<Node> Real = Number + NEWCH('.'+ Number;
相信对正则表达式有一定认识的同学已经知道这3条语句分别对应于什么正则表达式.
Symbol->[_a-zA-Z]+[_0-9a-zA-Z]*
Number->[0-9]+
Real->[0-9]+.[0-9]+

定义一个待分析的字符串.
1     NWString str = L"abcce_fg123.459agetr";

对其分析.
1     wprintf(L"%s\n",str);
2     wprintf(L"%s\n",Symbol->Parser(str));
3     wprintf(L"%s\n",Real->Parser(str));
4     wprintf(L"%s\n",Symbol->Parser(str));

分析结果.
1 abcce_fg123.459agetr
2 123.459agetr
3 agetr
4 

因为没有考虑分析效率问题,所以使用NWString作为输入和输出,在实际使用中可用LPTSTR来代替NWString,同时修改响应代码.
最后给出源代码
posted on 2011-01-26 22:11 lwch 阅读(2278) 评论(9)  编辑 收藏 引用 所属分类: NScript

评论:
# re: 使用面向组合子算法写词法分析器 2011-01-27 10:46 | 陈梓瀚(vczh)
嗯,就快达到四则运算分析器的目标了。你知道你这么做的话在让Node递归的时候可能还有些问题你没考虑到,譬如说

A = a | B
B = b | A

你如何在B还没有被=的时候就能用它呢,恩恩。

话说回来,你TM的基类竟然是Fail……  回复  更多评论
  
# re: 使用面向组合子算法写词法分析器 2011-01-27 14:44 | lwch
@陈梓瀚(vczh)
这个问题还真没考虑过..惰性计算的确不是一件容易的事情..
但这个作为词法分析器已经足够  回复  更多评论
  
# re: 使用面向组合子算法写词法分析器 2011-01-27 16:29 | 陈梓瀚(vczh)
@lwch
词法分析器用DFA才是最快的,用这个慢死了。而且那玩意儿也不是惰性计算……  回复  更多评论
  
# re: 使用面向组合子算法写词法分析器 2011-01-28 12:36 | ooseven
速度慢还不是最大的问题,最大的问题是用这个算法你需要自己开发算法进行状态数的优化,难度很高的。如果不优化的话,稍微复杂一点的正则文法,可能需要好几万个Node,比如你用这个作为basic语言的后台词法分析引擎试试?
  回复  更多评论
  
# re: 使用面向组合子算法写词法分析器 2011-01-28 14:11 | 陈梓瀚(vczh)
@ooseven
压缩状态的算法已经很成熟的啦,不用怕  回复  更多评论
  
# re: 使用面向组合子算法写词法分析器 2011-01-28 14:27 | lwch
@陈梓瀚(vczh)
Node是在运行时生成的,要压缩的话还得遍历一遍..  回复  更多评论
  
# re: 使用面向组合子算法写词法分析器 2011-01-28 16:46 | 陈梓瀚(vczh)
@lwch
那你实现的好一点就好了。一个词法分析器出来也就那么几百个状态吧,便利一次非常快。  回复  更多评论
  
# re: 使用面向组合子算法写词法分析器 2011-01-29 00:31 | ooseven
@陈梓瀚(vczh)
太乐观了,一个没有经过压缩的basic语言的词法分析状态估计有好几万个,单单生成就得好一会儿
  回复  更多评论
  
# re: 使用面向组合子算法写词法分析器 2011-01-29 04:01 | 陈梓瀚(vczh)
@ooseven
不可能,你有很多投机取巧用来压缩状态的算法没做。我出来的一直都只有几百个。不过其实我介绍这个算法的文章也在我的置顶里面,你可以去看看。我在做编译器的时候这些状态也是运行时产生的。我那个nativex跟basic可以比吧,也有那么多复杂的token。基本上构造状态机的时候瞬间就搞定了,根本无法感受他的时间,更不存在你所说的“好一会儿”。显然还是实现的问题。  回复  更多评论
  

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