最近發現一款文法分析神器，看完官網（http://goldparser.org/）的介紹后感覺很犀利的樣子，于是就拿來測試了一番，寫了一個數學表達式分析的小程序，支持的數學運算符如下所示:
常規運算：+ - * / ^ sqrt sqrt2(a,b) pow2(a) pow(a,b)
三角函數：sin cos tan cot asin acos atan acot
指數對數：log2(a) log10(a) ln(a) logn(a,b) e^
最大最小：max(a,b,...) min(a,b,...)
一、 GOLD Parser簡介
GOLD Parser是一款強大的文法分析工具，支持c++, c, c#, java, Python, Pascal等多種語言，詳細信息請參見官網 http://goldparser.org/
使用該工具主要包括三個步驟：
二、 數學表達式語法定義
從官網上下載GOLD Parser Builder Tool，按照提示進行安裝，安裝完成后就可以編寫語法定義了。主界面如下，工具中附帶的測試工具十分強大，寫完語法定義后，可以直接對語法進行測試，生成語法樹狀圖。
在編寫語法描述之前，首先我們先熟悉一下GOLD Meta-Language的基本特性，該語言主要由以下幾部分組成：
1. 語法文件屬性描述
這部分是用來描述我們即將編寫的語法文件的相關信息的，如語法名稱、作者、版本號等等。格式如下：
"Name" = 'My PRogramming Language'
"Version" = '1.0 beta'
"Author" = 'John Q. Public'
"Start Symbol" = <Statement> //必不可少，表示定義的開始，上面的可以不寫
2. 字符集定義
這部分是用來描述我們語言中所要用到的字符集，GOLD Meta-Language中預先定義了很多字符集，如常用的數字集合{Number}、字母集合{Letter}、可打印字符集合{Printable}等等，也可以使用Unicode碼指定字符集范圍{&4F00..&99E0}，表示從4F00到99E0之間的所有字符。格式如下：
{String Char} = {Printable} – [”] //表示從可打印的字符中減去”字符
我們可以定義多個字符集供我們定義的語言使用
3. 終結符(Terminal)定義
終結符是指我們定義的語言中能被語法分析器識別的最小單元，舉例說明一下，比如下面一個數學表達式：3.3+sin(a+b1)，終結符為“3.3”“+”“sin”“(”“a”“b1”“)”，終結符通常是采用正則表達式定義的，如果我們對正則表達式不了解，那么強烈建議我們去補補正則表達式的相關知識了。在語法文件中，變量及數字的終結符采用如下方式定義
Variable = {Letter}{Number}* //表示一個字母后面跟0個或多個數字，如a,b,x1,y34
NumberValue = {Number}+ | ({Number}+'.'{Number}*) //表示整數或小數
4. Productions定義(這個不好翻譯o(╯□╰)o，就用英文表示吧)
我們所描述的語言的語法是由一系列Production定義的，而一個Production是由若干個終結符(Terminal)和非終結符(Nonterminal)組成，非終結符通常是由尖括號<>界定，并由若干個終結符及非終節符定義。下圖表示的是一個Production，表示語言中的if-then-end語句，其中<Stm>, <Exp>, <Stmts>是非終結符，if, then, end是終結符。
一系列相同類型的Production組成一個規則集(Role)，我們所描述的語言的語法就是由規則集定義，下面兩幅圖兩種表示是等價的，是同一個規則集。
在熟悉了GOLD Meta-Language的語法之后，就可以著手編寫數學表達式的語法定義了。本人定義的語法文件如下：
! Welcome to GOLD Parser Builder 5.2"Name" = 'Calculator'"Version" = 'v1.0'"Author" = 'xxchen'"Start Symbol" = <Exp> Variable = {Letter}{Number}*NumberValue = {Number}+ | ({Number}+'.'{Number}*) <Exp> ::= <Exp> '+' <Exp Mult> | <Exp> '-' <Exp Mult> | <Exp Mult> <Exp Mult> ::= <Exp Mult> '*' <Value> | <Exp Mult> Variable | <Exp Mult> '/' <Value> | <Value> <Exp Func> ::= <Exp Func1> | <Exp Func2> | <Exp Funcn> <Exp Func1> ::= 'sin' <Value> | 'cos' <Value> | 'tan' <Value> | 'cot' <Value> | 'asin' <Value> | 'acos' <Value> | 'atan' <Value> | 'acot' <Value> | 'sqrt' <Value> | 'log2(' <Value> ')' | 'log10(' <Value> ')' | 'pow2(' <Value> ')' | 'e^' <Value> | 'ln' <Value> <Exp Func2> ::= <ExpValue> '^' <Value> | 'pow(' <Exp> ',' <Exp> ')' | 'sqrt2(' <Exp> ',' <Exp> ')' | 'logn(' <Exp> ',' <Exp> ')' <Params> ::= <Params> ',' <Exp> | <Exp> <Exp Funcn> ::= 'max(' <Params> ')' | 'min(' <Params> ')' <Param> ::= NumberValue | Variable <ExpValue> ::= <Param> | '-' <Param> | '(' <Exp> ')' | '|' <Exp> '|' <Value> ::= <ExpValue> | <Exp Func>
寫完后，直接點軟件右下角的Next按鈕，在沒有提示錯誤后會生成一個.egt文法表文件，該文件在后面的程序編寫過程中需要用到。
三、 利用解析引擎編寫代碼
由于個人比較熟悉c#語言，故采用了c#語言版本的解析引擎，其它語言版本的引擎在官網上也有提供。在正式編寫代碼之前，還可以利用Builder Tool來生成對應引擎的解析框架，在Project-Create a Skeleton Program菜單下可以打開向導進行設置，選擇對應的語言及解析引擎，就可以生成相應的解析框架了。
自動生成出來的解析框架非常簡單，如下所示，主要有兩個函數需要注意，第一個是Parse函數，該函數接受一個TextReader類型的參數，用來讀取需要解析的內容，里面的解析邏輯都已自動生成；第二個是CreateNewObject函數，我們需要修改的就是這個函數，在引擎解析過程中，我們需要根據每個步驟的解析結果生成我們需要的對象，以實現我們需要的邏輯。在不影響整體框架的前提下，其它部分可以任意修改，在這里我添加了一個帶參數的構造函數，參數是文法表文件的路徑，然后在構造函數中初始化解析引擎。
為了實現計算邏輯，這里定義了一個簡單的表達式類，該類的構造函數可以接受一個常數，或者一個變量，或者接受若干個表達式。
/// <summary>/// 表達式類/// </summary>public class Expression{ /// <summary> /// Initializes a new instance of the <see cref="Expression"/> class. /// </summary> /// <param name="value">接受一個常數</param> public Expression(double value) { _value = t => value; } /// <summary> /// Initializes a new instance of the <see cref="Expression"/> class. /// </summary> /// <param name="variable">接受一個變量</param> public Expression(string variable) { _value = t => t[variable]; _varList = new List<string> { variable }; } /// <summary> /// Initializes a new instance of the <see cref="Expression"/> class. /// </summary> /// <param name="func">表達式計算函數</param> /// <param name="exps">接受若干個表達式</param> public Expression(Func<double[], double> func, params Expression[] exps) { _value = t => func(exps.Select(e => e._value(t)).ToArray()); foreach (var exp in exps) { if(exp._varList == null) continue; if(_varList == null) _varList = new List<string>(); _varList.AddRange(exp._varList); } if (_varList != null) _varList = _varList.Distinct().ToList(); } /// <summary> /// 存儲變量名稱的鏈表 /// </summary> private readonly List<string> _varList; /// <summary> /// 獲取表達式中的變量 /// </summary> /// <returns></returns> public IEnumerable<string> GetVariables() { if(_varList == null) yield break; foreach (var var in _varList) yield return var; } /// <summary> /// The _value /// </summary> private readonly Func<Dictionary<string, double>, double> _value; /// <summary> /// 獲取表達式的值,用于計算沒有變量的表達式 /// </summary> /// <returns>System.Double.</returns> public double GetValue() { return GetValue(null); } /// <summary> /// 獲取表達式的值,用于計算有變量的表達式 /// </summary> /// <param name="varTable">參數表</param> /// <returns>System.Double.</returns> public double GetValue(Dictionary<string, double> varTable) { try { return _value(varTable); } catch (Exception) { return double.NaN; } }}
再來看一下解析引擎中生成的CreateNewObject函數，下面只截取了部分代碼，里面的邏輯也很簡單，比如引擎在解析完數字后，可以根據注釋，這里是// <Param> ::= NumberValue ，表示r中數據的個數為1，其中r[0].Data對應的就是NumberValue的值，這時我們只需要返回一個常數表達式即可。在解析完變量后，注釋的代碼是// <Param> ::= Variable，返回一個變量表達式即可。在解析完+號時，對應的注釋代碼是// <Exp> ::= <Exp> '+' <Exp Mult> 表明r中數據的個數是3，r[0].Data及r[2].Data是我們之前的數據解析完時返回的表達式，對應于解析樹中的<Exp>及<Exp Mult>，r[1].Data是”+”號，故在這個節點我們需要生成一個新的加法表達式，然后返回該表達式即可。
Expression exp1, exp2;switch ((ProductionIndex)r.Parent.TableIndex()){ case ProductionIndex.Exp_Plus: // <Exp> ::= <Exp> '+' <Exp Mult> exp1 = r[0].Data as Expression; exp2 = r[2].Data as Expression; result = new Expression(t => t[0] + t[1], exp1, exp2); break; case ProductionIndex.Exp_Minus: // <Exp> ::= <Exp> '-' <Exp Mult> exp1 = r[0].Data as Expression; exp2 = r[2].Data as Expression; result = new Expression(t => t[0] - t[1], exp1, exp2); break; case ProductionIndex.Param_Numbervalue: // <Param> ::= NumberValue result = new Expression(double.Parse(r[0].Data.ToString())); break; case ProductionIndex.Param_Variable: // <Param> ::= Variable result = new Expression(r[0].Data.ToString()); break;……省略類似部分
至此，數學表達式的解析引擎已經構造完成，使用方法如下：
//根據文發表文件構造解析引擎var filePath = Path.Combine(Directory.GetCurrentDirectory(), "calculator.egt");var parser = new CalculatorParser(filePath);//解析讀入的字符串parser.Parse(new StringReader(line));//讀取解析結果，即一個表達式var exp = parser.Exp;//計算表達式的值result = exp.GetValue();
四、 實驗效果
程序可以計算用戶任意輸入的表達式，如果發現表達式有誤，則會提示用戶在哪個位置出現了錯誤。程序還可以識別變量，并且對數字后面緊接變量的表達方式理解為乘法運算，如3d表示3*d。圖中的cos-3-4.d會理解為cos(-3)-4.0xd，其中d為變量
五、 總結
總的來說GOLD Parser是一個非常強大的文法分析工具，可以解析任意有規律的文本文件，如xml, json, html, c, c++, java, c#等等，這些語言的語法描述文件在官網上也都能找得到（不用自己重頭再寫了）。如果要想解析一門新的語言或者數據描述文件，那么就得自己寫語法描述文件，對于語法不是很復雜的語言，在官網上找點資料，然后照著例子寫兩遍就能搞定了（從剛接觸GOLD Parser到完成這個小程序一共花了不到1天時間）。語法寫完后，借助現有的解析引擎，程序的編寫就非常簡單了。
源代碼下載地址：http://vdisk.weibo.com/s/yVSnUWjONKKp0
【原創】轉載請說明出處！
新聞熱點
疑難解答
