这篇短文的Idea来源于
一篇论文。这篇论文的题目是Higier-Order Functions for Parsing，Graham Hutton写的。论文中使用了一种叫Miranda的函数式语言来讲述如何使用高阶函数开发语法分析器。
高阶函数很多语言都支持，譬如JavaScript啊，C#的lambda expression啊，或者是我自己做的语言Vczh Free Script 2.0。不过Miranda是惰性计算的语言，我们常用的语言都不具有惰性计算的特性。因此我阅读了这篇文章之后，自己用Vczh Free Script 2.0写了一个等价的小规模的语法分析器。结构跟论文中所提到的那个有所区别，不过相同的经验可以直接应用在JavaScript里面或其它语言（例如Python等）的lambda expression里。C#我不知道行不行，没去考证。
这里首先要解决一个问题，就是如何引用没被定义的名字的问题。譬如如下文法：
Term=<number> | "(" Exp ")"
Factor=[ Factor ("*" | "/") ] Term
Exp=[Exp ("+" | "-") ] Factor
如果我们直接把这些东西写进代码的话，那就会遇到Exp没有定义的问题。因此每一个小parser我都定义为一个数组，这个数组只有一个元素。在运算的时候每次都把元素取出来执行，就可以模拟惰性计算在这里起到的作用了。
好了，现在我们开始制作。我对Parser的定义是这样的。一个Parser是一个只有一个函数的数组。这个函数接受一个输入，返回一个结果的数组。因为语法可能有歧义，所以返回多个结果是允许的。每一个结果由两部分组成，第一部分是分析的结果，第二部分是分析到这里为止还剩下的字符串。
首先，我们需要一个Fail，这个Fail无论输入什么都返回空：
1 Fail=[func(Input)
2 {
3 return [];
4 }];
5
然后，我们需要一个Ch来检查输入的前缀是否跟定义的一样：
1 Ch=func(c)
2 {
3 return [func(Input)
4 {
5 if(#Input>=#c)
6 if(Input[0:#c]==c)
7 return [[c,Input[#c:#Input-#c]]];
8 return Fail[0](Input);
9 }];
10 };
Ch的使用方法是这样的：Ch(字符串)。譬如Ch("vczh")就返回了一个parser，这个parser在输入"vczh123"的时候返回[ ["vczh" , "123"] ]。原因是这样的。因为Ch("vczh")是没有歧义的，所以返回包含一个结果的数组。这个结果又是一个数组，数组的两个元素分别是分析的结果（"vczh"）和剩余的字符串（"123"）。
为了方便，我们建立一个Regex来检查输入的前缀是否满足一个正则表达式：
1 Regex=func(Expression)
2 {
3 Expression=regexppure(Expression);
4 return [func(Input)
5 {
6 local Match=matchhead(Expression,Input);
7 if(Match!=null)
8 return [[text(Match),Input[#text(Match):#Input-#text(Match)]]];
9 else
10 return [];
11 }];
12 };
Regex与Ch是类似的。实际上Regex可以用其他的手段组合起来。因为我们现在制作的分析器是可以分析Type-2文法的，远远比正则表达式所能表达的Type-3文法强大很多。不过为了使用方便这么做也不是坏事。
接下来我们定义了一个Seq来表示多个parser串联：
1 Seq=func({
}Parsers)
2 {
3 return [func(Input)
4 {
5 local Result=[[[],Input]];
6 for(p in Parsers)
7 {
8 local NewResult=[];
9 for(r in Result)
10 {
11 for(pr in p[0](r[1]))
12 NewResult=NewResult++[[r[0]++[pr[0]],pr[1]]];
13 }
14 Result=NewResult;
15 }
16 return Result;
17 }];
18 };
串联的意思其实很简单。Seq(Ch("1") , Ch("2") , Ch("3"))就等于说输入必须由Ch("1")、Ch("2")和Ch("3")构成。为什么要这么做呢，因为Seq跟循环和分支配合起来的话会非常强大，详见下文。
好了，有了Seq我们就需要Alt：
1 Alt=func({}Parsers)
2 {
3 return [func(Input)
4 {
5 local Result=[];
6 for(p in Parsers)
7 Result=Result++p[0](Input);
8 return Result;
9 }];
10 };
Alt是分支的意思，譬如Alt(Ch("1") , Ch("2") , Ch("3")的意思是输入可以是Ch("1")或Ch("2")或Ch("3")。
然后我们就需要循环Any：
1 Any=func(Parser,Max)
2 {
3 return [func(Input)
4 {
5 local Result=[[[],Input]];
6 local Current=0;
7 do
8 {
9 Produce=0;
10 if(#Result[Current][0]!=Max)
11 for(r in Parser[0](Result[Current][1]))
12 {
13 Result=Result++[[Result[Current][0]++[r[0]],r[1]]];
14 }
15 Current=Current+1;
16 }
17 while(Current<#Result);
18 return Result;
19 }];
20 };
Any的第一个参数是Parser，第二个参数是最大循环次数，-1代表无限循环。这样的话，Any(Ch("1"),4)就可以接受""、"1"、"11"、"111"和"1111"了。如果4改为-1的话，那么多少个1都行了。如果要限制最少循环次数怎么办呢？嘿嘿，用Seq(X,X,X,Any(X,-1))吧，最少就3次了。如果你嫌麻烦的话可以再开发一个函数去简化这个过程。在这里我就不详细讨论了。
为了方便，我们让Rep(X)=Any(X,-1)，Opt(X)=Any(X,1)：
1 Opt=func(Parser)
2 {
3 return Any(Parser,1);
4 };
5
6 Rep=func(Parser)
7 {
8 return Any(Parser,-1);
9 };
最后我们需要一个Using：
1 Using=func(Parser,Handler)
2 {
3 return [func(Input)
4 {
5 local Result=Parser[0](Input);
6 for(r in Result)
7 r[0]=Handler(r[0]);
8 return Result;
9 }];
10 };
Using很好理解的，给他一个Parser和一个函数Handler，当Parser完成以后会把结果送给Handler进行转换（譬如进行四则运算的求值），然后把Handler函数的执行结果当成Parser的分析结果返回。
说到这里如果还不是很清楚的话，有两个办法。
1：自己使用JavaScript或者其他语言重写一次
2：阅读文章开头的论文（有链接）
好了，现在我们展示一下如何使用这些函数来对一个四则运算式子进行求值。
重新提一下四则运算的文法：
Term=<number> | "(" Exp ")"
Factor=[ Factor ("*" | "/") ] Term
Exp=[Exp ("+" | "-") ] Factor
我们这个语法分析器跟boost::spirit一样，不支持左递归哈。所以我们手动修改一下文法：
Term=<number> | "(" Exp ")"
Factor=Term ( ("*" | "/") Term )*
Exp=Factor ( ("+" | "-") Factor )*
好了，有了这个文法，我们用代码把它们表达出来：
1 CreateParser=func()
2 {
3 return [Fail];
4 };
5
6 SetParser=func(Object,Parser)
7 {
8 Object[0]=Parser[0];
9 };
10
11 Pass=func(Index)
12 {
13 return func(Params)
14 {
15 return Params[Index];
16 };
17 };
18
19 Calculator=func(Params)
20 {
21 local Result=Params[0];
22 for(pair in Params[1])
23 if(pair[0]=="+")
24 Result=Result+pair[1];
25 else if(pair[0]=="-")
26 Result=Result-pair[1];
27 else if(pair[0]=="*")
28 Result=Result*pair[1];
29 else if(pair[0]=="/")
30 Result=Result/pair[1];
31 else
32 throw("Unknown operator:"++pair[0]);
33 return Result;
34 };
35
36 Term=CreateParser();
37 Factor=CreateParser();
38 Exp=CreateParser();
39
40 SetParser(Term,Alt(Regex("\\d+(.\\d+)?"),Using(Seq(Ch("("),Exp,Ch(")")),Pass(1))));
41 SetParser(Factor,Using(Seq(Term,Rep(Seq(Alt(Ch("*"),Ch("/")),Term))),Calculator));
42 SetParser(Exp,Using(Seq(Factor,Rep(Seq(Alt(Ch("+"),Ch("-")),Factor))),Calculator));
43 Parser=Exp;
·Pass是的作用是分析道["(" , Exp , ")"]的时候把Exp返回，因为括号是不需要的。
·Calculator的作用是传入[1 [ ["+" , 2] , ["-" , 3] , ["+" , 4] ]]的时候吧表达式当成1+2+3+4进行计算。
·Term、Factor和Exp都是用了Using来处理返回的结果。这样的话就等于将语义绑定到语法上。
好了，让我们看一看运行结果吧。以下是主程序：
1 for(r in Parser[0](read("Input:")))
2 {
3 write("================================================================================");
4 writeln("RESULT :",r[0]);
5 writeln("REMAIN :",r[1]);
6 }
输入：(1+2)+(3+4)，屏幕上会出现：
1 Input:(1+2)*(3+4)
2 ================================================================================
3 RESULT :
4 REMAIN :(1+2)*(3+4)
5 ================================================================================
6 RESULT :3
7 REMAIN :*(3+4)
8 ================================================================================
9 RESULT :21
10 REMAIN :
11
万岁！
posted on 2008-05-21 00:57
陈梓瀚(vczh) 阅读(8141)
评论(5) 编辑 收藏 引用 所属分类:
脚本技术