OpenCASCADE Expression Interpreter by Flex & Bison
eryar@163.com
Abstract. OpenCASCADE provide data structure of any expression, relation or function used in mathematics. Flex and Bison are tools for building programs that handle structured input. They were originally tools for building compilers, but they have proven to be useful in many other areas. The Expression Interpreter in OpenCASCADE is made by Flex and Bison. So let’s know something about Flex and Bison.
Key Words. OpenCASCADE, Expression Interpreter, Flex, Bison
1.Introduction
OpenCASCADE的TKMath中提供了數(shù)學(xué)表達式求解的包Expr和ExprIntrp，用來對數(shù)學(xué)表達式或函數(shù)進行解析計算。所謂的數(shù)學(xué)表達式如：sin(10)+20*6-6/3等。以前在《數(shù)據(jù)結(jié)構(gòu)》的書上看到用棧的方式來對簡單表達式求值，感覺已經(jīng)很不錯了。但是如果表達式中包含三角函數(shù)、對數(shù)、指數(shù)等，程序就要復(fù)雜了。如何簡單、優(yōu)雅地去解決這個問題，當(dāng)時也是很茫然。
工作中遇到前輩自己寫了一個用于定義幾何的語言，還可以計算表達式。雖然沒有看到源碼，對其已是崇拜不已。后來接觸了腳本語言，像Tcl/Tk，Python之類，發(fā)現(xiàn)原來利用這些開源庫，也是可以實現(xiàn)一個簡單、穩(wěn)定的自定義開發(fā)語言。因為這類腳本不僅可以計算表達式，還可以計算帶參數(shù)的表達式，如：
set x 3
set y 4
set z [expr sqrt($x*$x+$y*$y)]
只要你在Unix環(huán)境中寫過程序，你必定會邂逅神秘的Lex&YACC，就如GUN/Linux用戶所熟知的Flex&Bison，這里的Flex就是由Vern Paxon實現(xiàn)的一個Lex，Bison則是GNU版本的YACC。學(xué)習(xí)過《編譯原理》的同學(xué)們對這兩個神器應(yīng)該不會陌生。使用這兩個工具，不僅可以實現(xiàn)一個表達式解析計算器，還可以用來解析SQL語法，如PostgreSQL中就是使用他們實現(xiàn)SQL語法解析。甚至還可以實現(xiàn)一個編譯器。
因為是Unix上的工具，在Windows上需要使用winflexbison，可以從sourceforge上下載：https://sourceforge.net/projects/winflexbison/
本文介紹如何使用Flex來理解OpenCASCADE中ExprInterp的實現(xiàn)，開闊視野。OpenCASCADE中ExprInterp的用法見：Evaluate Math Expression
http://www.shnenglu.com/eryar/archive/2013/10/09/203625.html
2.Flex Example
FLEX是一個自動化工具，可以按照定義好的規(guī)則自動生成一個C函數(shù)yylex()，也成為掃描器（Scanner）。這個C函數(shù)把文本串作為輸入，按照定義好的規(guī)則分析文本串中的字符，找到符合規(guī)則的一些字符序列后，就執(zhí)行在規(guī)則中定義好的動作（Action）。例如在規(guī)則中可以這樣定義：如果遇到一個換行字符\n，那么就把行計數(shù)器的值加一。
Flex文件就是一個文本文件，內(nèi)容包括定義好的一系列詞法規(guī)則。文件的命名習(xí)慣上以小寫字母l(L)來作為文件后綴。如果為了清晰，也可以用.flx或者.flex作為文件的后綴名。Flex文件完成后，就執(zhí)行下列命令：
$ flex example.flex
這個命令執(zhí)行后將生成一個C文件，默認(rèn)文件名為lex.yy.c。這個C文件主要內(nèi)容就是函數(shù)yylex()的定義。
如果要直接將這個文件編譯成為一個可執(zhí)行程序，還有一些要注意的地方。如果在Flex文件中沒有提供main()函數(shù)的定義，那么這個C文件中不會有main()函數(shù)。此時單獨編譯這個C文件的時候，一定要加上-lfl的連接庫參數(shù)；若提供了main()函數(shù)，就不必要提供這個連接庫參數(shù)了。連接庫libfl提供了一個缺省的main函數(shù)。缺省的main()函數(shù)中只是簡單地調(diào)用yyflex()函數(shù)，而自己提供的main()函數(shù)則可以根據(jù)需要加入許多其他的處理代碼。
詞法規(guī)范定義文件給出了單詞構(gòu)成規(guī)則。詞法文件在習(xí)慣上用字母l(即L的小寫)來作為后綴。Flex文件由三個部分組成。或者說三個段。三個段之間用兩個%%分隔。
定義段(definitions)
%%
規(guī)則段(rules)
%%
用戶代碼段(user code)
下面給出一個簡單的Flex程序，代碼如下所示：
/* hello world for Flex. */
%option noyywrap
%{
int char_count = 0;
int line_count = 0;
%}
%%
\n { ++char_count; ++line_count; }
. { ++char_count; }
%%
int main(int argc, char* argv[])
{
yylex();
printf("# of lines = %d, # of chars = %d\n", line_count, char_count);
return 0;
}
將上述文件保存為hello.lex，然后運行如下圖所示命令：
會生成一個lex.yy.c的源程序，將這個C源文件編譯，鏈接即可生成一個可執(zhí)行程序。運行程序如下圖所示：
3.Flex and Bison in occ
在OpenCASCADE的文件夾中也有相關(guān)的語法規(guī)則定義，如下圖所示：
由上圖可知，OpenCASCADE的表達式解析功能的實現(xiàn)也是利用了Flex和Bison。
4.Conclusion
借助于Flex和Bison這兩個強大的工具，你可以實現(xiàn)一個高級的計算器，即任意數(shù)學(xué)表達式計算器。
OpenCASCADE的ExprInterp使用了Flex和Bison實現(xiàn)了數(shù)學(xué)表達式的解析計算。當(dāng)理解了工具的用途，有興趣的讀者不妨結(jié)合《編譯原理》等理論知識，對工具的原理進行一番探究。
5.References
1. 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版). 清華大學(xué)出版社. 1997
2. 趙建華, 鄭滔, 戴新宇 譯. 編譯原理. 機械工業(yè)出版社. 2011
3. John Levine, flex & bison. O’REILLY. 2009