這篇短文的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) 閱讀(8192)
評論(5) 編輯 收藏 引用 所屬分類:
腳本技術