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