這篇短文的Idea來源于
一篇論文。這篇論文的題目是Higier-Order Functions for Parsing，Graham Hutton寫的。論文中使用了一種叫Miranda的函數(shù)式語言來講述如何使用高階函數(shù)開發(fā)語法分析器。
高階函數(shù)很多語言都支持，譬如JavaScript啊，C#的lambda expression啊，或者是我自己做的語言Vczh Free Script 2.0。不過Miranda是惰性計算的語言，我們常用的語言都不具有惰性計算的特性。因此我閱讀了這篇文章之后，自己用Vczh Free Script 2.0寫了一個等價的小規(guī)模的語法分析器。結(jié)構(gòu)跟論文中所提到的那個有所區(qū)別，不過相同的經(jīng)驗(yàn)可以直接應(yīng)用在JavaScript里面或其它語言（例如Python等）的lambda expression里。C#我不知道行不行，沒去考證。
這里首先要解決一個問題，就是如何引用沒被定義的名字的問題。譬如如下文法：
Term=<number> | "(" Exp ")"
Factor=[ Factor ("*" | "/") ] Term
Exp=[Exp ("+" | "-") ] Factor
如果我們直接把這些東西寫進(jìn)代碼的話，那就會遇到Exp沒有定義的問題。因此每一個小parser我都定義為一個數(shù)組，這個數(shù)組只有一個元素。在運(yùn)算的時候每次都把元素取出來執(zhí)行，就可以模擬惰性計算在這里起到的作用了。
好了，現(xiàn)在我們開始制作。我對Parser的定義是這樣的。一個Parser是一個只有一個函數(shù)的數(shù)組。這個函數(shù)接受一個輸入，返回一個結(jié)果的數(shù)組。因?yàn)檎Z法可能有歧義，所以返回多個結(jié)果是允許的。每一個結(jié)果由兩部分組成，第一部分是分析的結(jié)果，第二部分是分析到這里為止還剩下的字符串。
首先，我們需要一個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"] ]。原因是這樣的。因?yàn)镃h("vczh")是沒有歧義的，所以返回包含一個結(jié)果的數(shù)組。這個結(jié)果又是一個數(shù)組，數(shù)組的兩個元素分別是分析的結(jié)果（"vczh"）和剩余的字符串（"123"）。
為了方便，我們建立一個Regex來檢查輸入的前綴是否滿足一個正則表達(dá)式：
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是類似的。實(shí)際上Regex可以用其他的手段組合起來。因?yàn)槲覀儸F(xiàn)在制作的分析器是可以分析Type-2文法的，遠(yuǎn)遠(yuǎn)比正則表達(dá)式所能表達(dá)的Type-3文法強(qiáng)大很多。不過為了使用方便這么做也不是壞事。
接下來我們定義了一個Seq來表示多個parser串聯(lián)：
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 };
串聯(lián)的意思其實(shí)很簡單。Seq(Ch("1") , Ch("2") , Ch("3"))就等于說輸入必須由Ch("1")、Ch("2")和Ch("3")構(gòu)成。為什么要這么做呢，因?yàn)镾eq跟循環(huán)和分支配合起來的話會非常強(qiáng)大，詳見下文。
好了，有了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")。
然后我們就需要循環(huán)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的第一個參數(shù)是Parser，第二個參數(shù)是最大循環(huán)次數(shù)，-1代表無限循環(huán)。這樣的話，Any(Ch("1"),4)就可以接受""、"1"、"11"、"111"和"1111"了。如果4改為-1的話，那么多少個1都行了。如果要限制最少循環(huán)次數(shù)怎么辦呢？嘿嘿，用Seq(X,X,X,Any(X,-1))吧，最少就3次了。如果你嫌麻煩的話可以再開發(fā)一個函數(shù)去簡化這個過程。在這里我就不詳細(xì)討論了。
為了方便，我們讓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和一個函數(shù)Handler，當(dāng)Parser完成以后會把結(jié)果送給Handler進(jìn)行轉(zhuǎn)換（譬如進(jìn)行四則運(yùn)算的求值），然后把Handler函數(shù)的執(zhí)行結(jié)果當(dāng)成Parser的分析結(jié)果返回。
說到這里如果還不是很清楚的話，有兩個辦法。
1：自己使用JavaScript或者其他語言重寫一次
2：閱讀文章開頭的論文（有鏈接）
好了，現(xiàn)在我們展示一下如何使用這些函數(shù)來對一個四則運(yùn)算式子進(jìn)行求值。
重新提一下四則運(yùn)算的文法：
Term=<number> | "(" Exp ")"
Factor=[ Factor ("*" | "/") ] Term
Exp=[Exp ("+" | "-") ] Factor
我們這個語法分析器跟boost::spirit一樣，不支持左遞歸哈。所以我們手動修改一下文法：
Term=<number> | "(" Exp ")"
Factor=Term ( ("*" | "/") Term )*
Exp=Factor ( ("+" | "-") Factor )*
好了，有了這個文法，我們用代碼把它們表達(dá)出來：
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返回，因?yàn)槔ㄌ柺遣恍枰摹?br> ·Calculator的作用是傳入[1 [ ["+" , 2] , ["-" , 3] , ["+" , 4] ]]的時候吧表達(dá)式當(dāng)成1+2+3+4進(jìn)行計算。
·Term、Factor和Exp都是用了Using來處理返回的結(jié)果。這樣的話就等于將語義綁定到語法上。
好了，讓我們看一看運(yùn)行結(jié)果吧。以下是主程序：
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)，屏幕上會出現(xiàn)：
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) 閱讀(8192)
評論(5) 編輯 收藏 引用 所屬分類:
腳本技術(shù)