介紹C# Parsing Library
C# Parsing Library 是一個LL解析器產生框架，可以在C#中模擬ENBF文法定義。設計思路來自于Boost.Spirit，一個C++解析器框架。
一）C# Parsing Library：Parser 基本概念
a) 文法定義舉例：P ::= a b C#用法：P = a + b 序列
b) 文法定義舉例：P ::= a | b C#用法：P = a | b 選擇
c) 文法定義舉例：P ::= a * C#用法：P = a.Star 0..n次匹配
d) 文法定義舉例：P ::= a + C#用法：P = a.Plus 1..n次匹配
e) 文法定義舉例：P ::= a ? C#用法：P = a.Opt 0..1次匹配
P為Parser類型，是解析器的抽象基類，它定義了一個抽象的Parse方法：
- bool Parse(Scanner scanner);
Scanner類主要存儲一個字符串輸入，及一個光標位置，光標隨著解析的進行向前移動。
例子：一個整數解析器, 定義為一個可選的符號后面跟若干數字：
- Parser signed = (Parser.Lit('+') | '-').Opt;
- Parser p = (signed + Parser.DigitChar.Plus).Lexeme;
- bool success = p.Parse(new Scanner("-123"));
其中，Lit表示常量，Lexeme表示為詞法分析，即不忽略空格。
二）C# Parsing Library：ParserRef
一個常用的四則運算表達式文法：
- group ::= '(' expression ')'
- factor ::= integer | group
- term ::= factor (('*' factor) | ('/' factor))*
- expression ::= term (('+' term) | ('-' term))*
用下面的方法是錯誤的：
- Parser group; // Parser 是抽象類，無法 new
- Parser factor;
- factor = Parser.Int | group; // 錯誤! group沒有初始化!
但是使用ParserRef 就可以了：
- ParserRef group = new ParserRef();
- ParserRef factor = new ParserRef();
- factor.Parser = Parser.Int | group;
完整的定義如下：
- ParserRef group = new ParserRef();
- ParserRef factor = new ParserRef();
- ParserRef term = new ParserRef();
- ParserRef expression = new ParserRef();
- group.Parser = '(' + expression + ')';
- factor.Parser = Parser.Int
- | group;
- term.Parser = factor +
- ( ('*' + factor)
- | ('/' + factor)
- ).Star;
- expression.Parser = term +
- ( ('+' + term)
- | ('-' + term)
- ).Star;
三）C# Parsing Library：Rule和語義支持
和 spirit一樣，通過對[]的重載，實現對語義的支持。一般的parser的Action類型為Action< string>, 即 void Action(string s)。s為該parser匹配的內容。如果要支持上下文， 就要使用Rule了. Rule帶有一個模板參數T，表示屬性類型。Action類型為Func< T,T,T> 即 T Action(T lhs, T rhs)。對于以下的簡單規則：
- LeftRule := RightRule [ Action(lhs, rhs) ]
其語義為：LeftRule.Attribute = Action(LeftRule.Attribute, RightRule.Attribute).
上面的四則運算示例可修改如下:
- Grammar< int> grammar = new Grammar< int>();
- Rule< int> group = new Rule< int>(grammar);
- Rule< int> factor = new Rule< int>(grammar);
- Rule< int> term = new Rule< int>(grammar);
- Rule< int> expression = new Rule< int>(grammar);
- Rule< int> start = new Rule< int>(grammar);
- grammar.Start = start;
- group.Parser = '(' + expression [ (lhs, rhs) => rhs ] + ')';
- factor.Parser = Parser.IntValue [ v => grammar.Ret(v) ] // (#1)
- | group [ (lhs, rhs) => rhs ];
- term.Parser = factor [ (lhs, rhs) => rhs ] +
- ( ('*' + factor [ (lhs, rhs) => lhs * rhs ])
- | ('/' + factor [ (lhs, rhs) => lhs / rhs ])
- ).Star;
- expression.Parser = term [ (lhs, rhs) => rhs ] +
- ( ('+' + term [ (lhs, rhs) => lhs + rhs ])
- | ('-' + term [ (lhs, rhs) => lhs - rhs ])
- ).Star;
- start.Parser = expression [ (lhs, rhs) => rhs ] + Parser.End;
- int result;
- bool success = grammar.Parse("10 + 20 + 30 * (40 + 50)", out result);
- if (success) Console.WriteLine(result);
說明：
對于一般的Parser，語義動作中并不能有返回值，因為它不知道屬性的確切類型，要支持屬性，必須使用 Grammar.Ret().
在我自己實現以前，大致搜了一下，在CodeProject上有一個類似的實現，也是模仿Boost.Spirit,不過它的語義處理采用C#的事件機制，用起來極不方便。這個項目我剛剛把它發布在google code 上面，項目主頁：http://code.google.com/p/csparsing/。當然它還遠遠不夠成熟。
【編輯推薦】
