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