腳本解釋器(HOC)的實(shí)現(xiàn)與分析

Keamou 2009-11-18

展開全文

HOC(High Order Calculator) 是一個(gè)解釋型的程序語(yǔ)言，最初的版本由Brain Kernighan和Rob Pike在《The UNIX Programming Environment》[UNIX編程環(huán)境]一書中作為一個(gè)例子給出。本身由lex/yacc構(gòu)造，結(jié)構(gòu)十分清晰，作為一個(gè)教學(xué)語(yǔ)言，HOC支持函數(shù)，具有類C的語(yǔ)法，有簡(jiǎn)單的I/O，變量賦值，表達(dá)式計(jì)算，錯(cuò)誤恢復(fù)等機(jī)制。

后來(lái)，Bell實(shí)驗(yàn)室又陸續(xù)開發(fā)出了一些改進(jìn)的版本，使得HOC可以平坦的移植到各種Linux系統(tǒng)中，我在上學(xué)的時(shí)候閱讀過[UNIX編程環(huán)境] 這本書，并且對(duì)其中的HOC做了一些簡(jiǎn)單的改進(jìn)，后來(lái)又找到了Bell實(shí)驗(yàn)室的一個(gè)版本，深入的學(xué)了一遍，由于這個(gè)發(fā)布版本出自Research UNIX系統(tǒng)，我又對(duì)源碼做了一些修改，并將其移植到了Windows平臺(tái)。

在第一次學(xué)習(xí)HOC解釋器的時(shí)候，是在編譯原理課程結(jié)束后，當(dāng)時(shí)是想在linux下設(shè)計(jì)一個(gè)通用的數(shù)學(xué)計(jì)算引擎，然后將計(jì)算出的數(shù)據(jù)通過一個(gè)前端展示系統(tǒng)(最好平臺(tái)無(wú)關(guān))展示給最終用戶。開始，準(zhǔn)備用Delphi自己寫一個(gè)，但是一直沒有實(shí)現(xiàn)，這個(gè)項(xiàng)目就停止了。直到后來(lái)發(fā)現(xiàn)了一個(gè)優(yōu)秀的繪圖工具 gnuplot(關(guān)于gnuplot的更多細(xì)節(jié)，請(qǐng)參看我的另一篇文章), 用它來(lái)做前端似乎再合適不過了，于是，我決定將原來(lái)的改進(jìn)后的HOC移植到Windows下，然后進(jìn)行一個(gè)簡(jiǎn)單的整合。

下面是用HOC語(yǔ)言寫的一段代碼：

代碼很簡(jiǎn)單，先定義一個(gè)過程：plotSin(在HOC中有procedure,function之分，前者沒有返回值，而后者有)，這個(gè)過程定義了三個(gè)臨時(shí)變量begin,end,step,其中PI是一個(gè)常量，其值為3.1415926, 然后是一個(gè)for循環(huán)，begin不斷加step(0.1)，直到不小于end，退出循環(huán)，同時(shí)每次迭代時(shí)，先計(jì)算sin(begin)的值，并打印此時(shí)的begin和sin(begin)值。最后，調(diào)用這個(gè)過程，執(zhí)行計(jì)算并退出。

這個(gè)是程序生成的數(shù)據(jù)：

將數(shù)據(jù)交給gnuplot展示，gunplot可以輕易的從數(shù)據(jù)文件中讀出數(shù)據(jù)，并以第一列為橫坐標(biāo)，第二類為縱坐標(biāo)畫出圖形來(lái)，根據(jù)上邊這個(gè)數(shù)據(jù)文件，gnuplot畫出的圖形結(jié)果如下：

如果需要繪制3-D的圖形，事實(shí)上更為簡(jiǎn)單一些。如下面的代碼所示：

代碼很簡(jiǎn)單，就是兩層循環(huán)，計(jì)算出sin(x)*cos(y)的值，打印出來(lái)，一次x迭代結(jié)束后，打印一個(gè)空行，這樣gunplot可以識(shí)別次文件，并畫出3-D的圖形來(lái)。

使用gnuplot的3-D繪制命令，splot，可以得到下邊的圖形：

z = sin(x)*cos(y)

z = x * y

z = x^2 - y^2 (鞍面)

整個(gè)思路很清晰，沒有什么難懂的地方，而這個(gè)HOC的原始版本就是在UNIX下用lex/yacc開發(fā)的，只要對(duì)正則表達(dá)式和BNF形式比較熟悉就可以很快的理解整個(gè)解釋器的實(shí)現(xiàn)(建議直接去看源碼)。如果不太熟悉，那么就接著往下看，我會(huì)詳細(xì)解釋這些工具的用法和一些形式語(yǔ)言的理論。

形式語(yǔ)言

在計(jì)算機(jī)科學(xué)中，形式語(yǔ)言 是用精確的數(shù)學(xué)定義或者機(jī)器可識(shí)別的公式定義的語(yǔ)言，形式語(yǔ)言跟自然語(yǔ)言很類似，包含兩部分：語(yǔ)法和語(yǔ)義 。形式語(yǔ)言的定義為：

寫道

形式語(yǔ)言是一個(gè)字母表上的某些有限長(zhǎng)的字符串的集合。數(shù)學(xué)定義如下：字母表 Σ 為任意有限集合，ε 表示空串，記 Σ0 為{ε}，全體長(zhǎng)度為 n 的字串為 Σn ， Σ* 為 Σ0∪Σ1∪…∪Σn∪…，語(yǔ)言 L 定義為 Σ* 的任意子集。

正則表達(dá)式和BNF

1940年代，Warren McCulloch與Walter Pitts將神經(jīng)系統(tǒng)中的神經(jīng)元描述成小而簡(jiǎn)單的自動(dòng)控制元。在1950年代，數(shù)學(xué)家斯蒂芬·科爾·克萊尼利用稱之為正則集合 的數(shù)學(xué)符號(hào)來(lái)描述此模型。正則表達(dá)式又稱為模式(pattern)，用來(lái)描述一系列符合某個(gè)句法規(guī)則的串，正則表達(dá)式的表達(dá)能力十分強(qiáng)大，特別在對(duì)串的描述上。通過一系列的數(shù)學(xué)符號(hào)的引入，使得一個(gè)很簡(jiǎn)潔的表達(dá)式可以匹配一個(gè)很復(fù)雜的串，這正是使用正則表達(dá)式的目的。正則表達(dá)式有很多的現(xiàn)，C,JAVA,JavaScript等語(yǔ)言都支持正則表達(dá)式,perl語(yǔ)言對(duì)正則表達(dá)式的支持更是到達(dá)了一個(gè)空前的高度。

在對(duì)一些有某些特征的串進(jìn)行描述的時(shí)候，通常會(huì)覺得特別難，在使用狀態(tài)機(jī)的理論后，可以得到一定的簡(jiǎn)化，在數(shù)學(xué)上可以證明，狀態(tài)機(jī)的表達(dá)能力跟正則表達(dá)式的表達(dá)能力是相等的，也就是說(shuō)，一切能用狀態(tài)機(jī)表示出來(lái)的語(yǔ)言用正則語(yǔ)言也是可以描述的。

下面說(shuō)兩個(gè)簡(jiǎn)單的例子，我們?cè)诒磉_(dá)“浮點(diǎn)數(shù)”這個(gè)概念時(shí)，用自然語(yǔ)言可以做如下描述：“由若干個(gè)數(shù)字開頭，然后是一個(gè)點(diǎn)號(hào)(.)，然后又是若干個(gè)數(shù)字”。將這種不確定的語(yǔ)言如何翻譯成機(jī)器能識(shí)別的語(yǔ)言呢？幸好，科學(xué)家發(fā)明了正則表達(dá)式，比如這個(gè)例子中，我們可以使用:[0-9]+\.[0-9]{1,} 來(lái)表示(當(dāng)然，這個(gè)版本可能有bug，暫時(shí)不考慮)。又比如，在很多計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言中，變量命的規(guī)則為“以下劃線或者字母開頭，由數(shù)字，下劃線，字母組成，長(zhǎng)度不超過某個(gè)限制(比如64個(gè)字符)”，用正則表達(dá)式可以做出下面的描述：[_a-zA-Z][_a-zA-Z0-9]{,63}.

BNF，說(shuō)起B(yǎng)NF就更牛了，BNF是一種上下文無(wú)關(guān)文法 (context-free)，基本上所有的計(jì)算機(jī)語(yǔ)言都是使用上下文無(wú)關(guān)文法描述的，在表達(dá)能力上，上下文無(wú)關(guān)文法要比有限自動(dòng)機(jī) 和正則文法 強(qiáng)大，先看看一個(gè)上下文無(wú)關(guān)文法的簡(jiǎn)單例子：

語(yǔ)言G1，有以下規(guī)則：

寫道

A -> 0A1
A -> B
B -> #

寫道

上下文無(wú)關(guān)文法由替換規(guī)則組成，這些替換規(guī)則被稱為產(chǎn)生式(production)。每一條規(guī)則占一行，由一個(gè)符號(hào)和一個(gè)串構(gòu)成，符號(hào)和串之間用->連接，符號(hào)成為變?cè)?，或稱非終結(jié)符，而右邊的串由變?cè)土硪环N被稱為終結(jié)符的符號(hào)組成。左邊的符號(hào)通常用大寫字母表示，而終結(jié)符通常用小寫字母，數(shù)字或特殊字符表示。一個(gè)上下文無(wú)關(guān)文法需要一個(gè)起始變?cè)鸵?guī)則。

語(yǔ)言L(G1)可以描述這樣一個(gè)語(yǔ)言：L(G1) = {0ⁿ # 1ⁿ | n >= 0}。
上下文無(wú)關(guān)文法的形式定義是這樣：

寫道

上下文無(wú)關(guān)文法是一個(gè)四元組(V, Σ, R, S) 且
1) V是一個(gè)有窮集合，稱為變?cè)?br>2) Σ是一個(gè)與V不相交的有窮集合，稱為終結(jié)符集
3) R是一個(gè)有窮規(guī)則集，每條規(guī)則由一個(gè)變?cè)?非終結(jié)符)和一個(gè)由變?cè)徒K結(jié)符組成的串組成
4) S ∈ V是起始變?cè)?/div>

如在文法G1中，V={A, B}, Σ = {0, 1, #}, S = A, R為:
A -> 0A1
A -> B
B -> #

這部分基本上是純理論，看懂了下邊的很好理解，看不懂的也沒有關(guān)系，在下邊的實(shí)踐中慢慢的理解，最終會(huì)理解的。

lex/yacc

這兩個(gè)工具太有名了，而且功能非常之強(qiáng)大，在UNIX下已經(jīng)牛了幾十年了，很多工具和語(yǔ)言的解釋器都是用它們來(lái)做的。一般來(lái)說(shuō)，lex生成關(guān)于記號(hào) 的規(guī)則，生成yacc需要用到的tokens，yacc定義文法以及語(yǔ)義，而語(yǔ)義的解釋一般由外部的C來(lái)完成，UNIX下，C是原生的，而且這些工具可以無(wú)縫連接，所以在*nix下做一個(gè)語(yǔ)言的解釋器是很容易的。當(dāng)然，如果你在windows平臺(tái)，照樣可以完成這些動(dòng)作，只是稍微有點(diǎn)麻煩。 lex/yacc已經(jīng)被已經(jīng)到了windows平臺(tái)，而且有很多個(gè)版本,GNU Bison已經(jīng)很好的工作在win32平臺(tái)了。還有一個(gè)集成開發(fā)環(huán)境，叫Parser Generator，不過這個(gè)是面向?qū)W生和教育工作者的，其他的人需要購(gòu)買一個(gè)License.

lex中，用正則表達(dá)式定義一些記號(hào)，如數(shù)字，字符串，關(guān)鍵字等的定義可以放在這個(gè)里，主要是做詞法分析。lex將輸入的文件按字符讀入，然后匹配定義好的規(guī)則，如果發(fā)現(xiàn)是數(shù)字則返回?cái)?shù)字，等等。返回的結(jié)果交給yacc(語(yǔ)法分析)做進(jìn)一步處理。

yacc，使用BNF描述一些語(yǔ)法規(guī)則，它將lex返回來(lái)的記號(hào)與自己的規(guī)則相匹配，發(fā)現(xiàn)匹配后，執(zhí)行一定的語(yǔ)義解釋，翻譯！

C語(yǔ)言的函數(shù)指針

C語(yǔ)言中，函數(shù)是可以作為一個(gè)指針，這個(gè)指針指向函數(shù)的內(nèi)存空間，如果這些指針放在一個(gè)數(shù)組中，你甚至可以通過指針的移動(dòng)如*pc++來(lái)調(diào)用下一個(gè)函數(shù)(當(dāng)然，這種方式本身是不推薦的)。

定義一個(gè)函數(shù)指針 ：

double (*func)(double);

表示，當(dāng)以了一個(gè)函數(shù)指針*func,這個(gè)函數(shù)接受一個(gè)double類型的參數(shù)，并返回一個(gè)double型的數(shù)。比如，在HOC中，有一個(gè)函數(shù)名與具體函數(shù)之間的映射表，代碼如下

init.c line42

C代碼 
static struct {        /* Built-ins */  
    char *name;  
    double    (*func)(double);  
} builtins[] = {  
    "sin",    sin,  
    "cos",    cos,  
    "tan",    tan,  
    "atan",    atan,  
    "asin",    Asin,    /* checks range */  
    "acos", Acos,    /* checks range */  
    "sinh",    Sinh,    /* checks range */  
    "cosh",    Cosh,    /* checks range */  
    "tanh",    tanh,  
    "log",    Log,    /* checks range */  
    "log10", Log10,    /* checks range */  
    "exp",    Exp,    /* checks range */  
    "sqrt",    Sqrt,    /* checks range */  
    "gamma", Gamma,    /* checks range */  
    "int",    integer,  
    "abs",    fabs,  
    "erf",    erf,  
    "erfc",    erfc,  
    0,    0  
};  

再比如，HOC的符號(hào)表 (編譯器內(nèi)部的一個(gè)常用的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)編譯過程中的二元組)Symbol結(jié)構(gòu)：

hoc.h line4

C代碼 
typedef struct Symbol { /* symbol table entry */  
    char *name;  
    long type;  
    union {  
        double val; /* VAR */  
        double (*ptr)(double); /* BLTIN */  
        Inst *defn; /* FUNCTION, PROCEDURE */  
        char *str; /* STRING */  
    } u;  
    struct Symbol *next; /* to link to another */  
} Symbol;  

其中內(nèi)部的匿名union中，有一個(gè)字段double (*ptr)(double)就是一個(gè)函數(shù)指針，名字為ptr,用于表示內(nèi)建的函數(shù)表，也就是剛才提到的builtins數(shù)組。

好了，理論就先說(shuō)到這里，下面開始從頭開始構(gòu)造HOC語(yǔ)言，我會(huì)先設(shè)計(jì)一個(gè)簡(jiǎn)單的框架，我們逐步擴(kuò)展這個(gè)框架，并在最后實(shí)現(xiàn)這個(gè)語(yǔ)言解釋器。好了，可以開始了……

一個(gè)簡(jiǎn)單的計(jì)算器

hoc.l

C代碼 
%{  
#include "y.tab.h"  
extern YYSTYPE yylval;  
extern int lineno;  
%}  
%%  
[ \t]+        {;}//空白字符，如空格，table等  
[0-9]+|[0-9]*\.[0-9]+     
            {//浮點(diǎn)數(shù)  
                sscanf(yytext,"%lf",&yylval.val);  
                return NUMBER;  
            }  
\n          {//換行  
                lineno++;  
                return '\n';  
            }  
.           {//其他任意字符  
                return yytext[0];  
            }  
%%  

hoc.l很簡(jiǎn)單，讀到空白字符，如空格，table等鍵則忽略不計(jì)，接著讀下一個(gè)字符，讀到換行，就將lineno變量加一，讀到浮點(diǎn)數(shù)，則將內(nèi)容讀入yylval，并返回NUMBER標(biāo)記。

hoc.y

C代碼 
%{  
#include <stdio.h>  
#include <stdlib.h>  
char *progname;//記錄程序名，為了顯示錯(cuò)誤  
int    lineno = 1;//行號(hào)，用于顯示錯(cuò)誤  
%}  
%union{  
    double val;  
}  
%token <val> NUMBER  
%type <val> expr  
%left '+' '-'  
%left '*' '/'  
%left UNARYMINUS//left 意思為這些操作符的結(jié)合方式是從左到右，而有些操作符如平方，與此相反  
%%  
list    :     
        |    list '\n'  
        |    list expr '\n'    {printf("\t%.8g\n",$2);}//打印結(jié)果  
        ;  
expr    :    NUMBER            {$$ = $1;}  
        |    '-' expr %prec UNARYMINUS {$$ = -$2;}//負(fù)數(shù)  
        |    expr '+' expr    {$$ = $1 + $3;}  
        |    expr '-' expr    {$$ = $1 - $3;}  
        |    expr '*' expr    {$$ = $1 * $3;}  
        |    expr '/' expr    {$$ = $1 / $3;}  
        |    '(' expr ')'     {$$ = $2;}  
        ;  
%%  
//上邊的$$表示根規(guī)則(變?cè)?的值，$1,$2,$i 等表示，第i個(gè)子表達(dá)式(終結(jié)符或者變?cè)?  
int main(int argc,char **argv)  
{  
    progname = argv[0];//記錄程序的名字  
    yyparse();  
}  
yywrap()  
{  
    return 1;  
}  
yyerror(char *s)  
{  
    warning(s,(char *)0);  
}  
warning(char *s,char *t)  
{  
    fprintf(stderr,"%s : %s",progname,s);  
    if(t)  
        fprintf(stderr," %s",t);  
    fprintf(stderr," near line %d\n",lineno);  
}  

hoc.y中間的%%與%%之間的一段就是計(jì)算器的BNF的描述，這樣一個(gè)簡(jiǎn)潔的描述和一些簡(jiǎn)單的語(yǔ)義規(guī)則($$ = $1 + $3等)即可完成一個(gè)桌面計(jì)算器的形式描述。其他的幾個(gè)函數(shù)，是yacc要求實(shí)現(xiàn)的，做一些錯(cuò)誤處理等操作。

如果你工作在*nix系統(tǒng)，可以使用下面的makefile來(lái)自動(dòng)編譯整個(gè)程序，需要注意的是，你需要一個(gè)lex和一個(gè)yacc,當(dāng)然，C的編譯器和目標(biāo)文件的連接器也是必須的。

makefile

C代碼 
hoc:    y.tab.o lex.yy.o  
    gcc y.tab.o lex.yy.o -o hoc  
y.tab.o:y.tab.c  
    gcc -c y.tab.c  
y.tab.c:hoc.y  
    yacc -d hoc.y  
lex.yy.o:lex.yy.c  
    gcc -c lex.yy.c  
lex.yy.c:hoc.l  
    lex hoc.l  
  
clean:  
    rm -f y.tab.[cho]  
    rm -f lex.yy.[cho]  

編譯通過后，你即可使用在shell中測(cè)試一些簡(jiǎn)單的表達(dá)式求值：
$./hoc
這個(gè)版本的hoc可以處理一些比較簡(jiǎn)單的表達(dá)式，如(1+3)*(5-2),(-12)*6/2等，可以計(jì)算出結(jié)果，并打印出來(lái)。如果有不認(rèn)識(shí)的文法如a++,3^2 = ?或者除0錯(cuò)誤4/0等，你會(huì)得到一個(gè)錯(cuò)誤信息，并且hoc會(huì)退出(這正是YACC默認(rèn)的行為)。

支持變量

下一個(gè)版本，我們給hoc加入變量聲明的機(jī)制，變量可以是a-z中的任意個(gè)字母，如可以定義：a = 2,b = -4等形式的量，變量可以跟數(shù)字一樣做+/-/*/等操作。我們可以簡(jiǎn)單的加入一個(gè)數(shù)組來(lái)維護(hù)這些變量，對(duì)于第一個(gè)版本來(lái)說(shuō)，改動(dòng)并不大：

hoc.l

C代碼 
[a-z]{  
         yylval.index = yytext[0] - 'a';  
         return VAR;  
     }  

對(duì)hoc.l來(lái)說(shuō)，我們可以添加這樣一個(gè)簡(jiǎn)單的規(guī)則，將讀到的變量的ASCII值放入一個(gè)全局變量(在lex和yacc中共享)中，并返回記號(hào)VAR，yac會(huì)對(duì)這個(gè)記號(hào)做處理。

hoc.y

C代碼 
double mem[26];  
... ...  
%union{  
    double val;  
    int    index;  
}  
expr:  
... ...  
|    VAR             {$$ = mem[$1];}  
|    VAR '=' expr    {$$ = mem[$1] = $3;}  
... ...  

對(duì)于hoc.y改動(dòng)也不是很大，增加了一個(gè)用于存儲(chǔ)變量的值的數(shù)組mem,這個(gè)數(shù)組的大小跟英文中的字母數(shù)目一樣，從規(guī)則expr的改動(dòng)可以看出，當(dāng)你在給一個(gè)變量賦值后，可以通過變量名來(lái)引用這個(gè)變量的值，比如，你先設(shè)置一個(gè)變量x = 5,在接下來(lái)的某個(gè)地方使用x，你會(huì)得到一個(gè)輸出5，當(dāng)然，這兩個(gè)語(yǔ)句之間要確保x沒有被修改過。

錯(cuò)誤恢復(fù)

當(dāng)你的程序在執(zhí)行過程中，你可能不太希望一出錯(cuò)馬上就退出，可能想要讓系統(tǒng)從錯(cuò)誤中恢復(fù)過來(lái)，繼續(xù)下邊的語(yǔ)句，這雖然不一定是必須的，但是，在這里可能是有用的。

C代碼 
#include <setjmp.h>  
jmp_buf begin;  
int main(int argc,char **argv)  
{  
    int fpecatch();  
    progname = argv[0];  
    setjmp(begin);  
    signal(SIGFPE,fpecatch);//注冊(cè)回調(diào)函數(shù)，當(dāng)發(fā)生FPE時(shí)，調(diào)用fpecatch()  
    yyparse();//調(diào)用分析程序  
}  
fpecatch()//Floating point exception  
{  
    warning("floating point exception",(char *)0);  
}  
yyerror(char *s)  
{  
    warning(s,(char *)0);  
    longjmp(begin,0);//跳轉(zhuǎn)回begin初始化的地方  
}  

現(xiàn)在main中初始化一個(gè)jmp_buf型的變量begin，然后設(shè)置信號(hào)setjmp(begin)，然后調(diào)用yyparse()，當(dāng)錯(cuò)誤發(fā)生時(shí)，如除零錯(cuò)誤，yacc會(huì)調(diào)用yyerror()來(lái)處理，這時(shí)，在yyerror內(nèi)部，可以調(diào)用一個(gè)系統(tǒng)調(diào)用longjmp(begin, 0)，即可恢復(fù)到begin被初始化的地方，即main函數(shù)中，yyparse()之前的位置。

關(guān)于C語(yǔ)言中，這個(gè)jmp_buf, setjmp(jmp_buf b)和longjmp(jmp_buf buf, int code)的具體使用，可以參考別的C語(yǔ)言手冊(cè)。

與C整合，調(diào)用外部的C函數(shù)

lex/yacc真正強(qiáng)大之處在于他們和C語(yǔ)言的結(jié)合能力上。它們可以自由的使用外部的C語(yǔ)言定義好的函數(shù)。事實(shí)上，由于lex/yacc只是一種中間結(jié)果，它們最終還是要生成C代碼的，所以使用外部的C語(yǔ)言是沒有任何問題的。我們現(xiàn)在可以給hoc添加冪函數(shù)的處理，對(duì)冪函數(shù)的實(shí)現(xiàn)我們可以使用外部的C語(yǔ)言的math庫(kù)。

hoc.y

C代碼 
... ...  
extern double POW(double ,double);  
... ...  
%right '^'//冪函數(shù)的操作符是自右到左結(jié)合的  
... ...  
expr :  
... ...  
|    expr '^' expr     {$$ = POW($1,$3);}//調(diào)用外部的POW函數(shù)  
... ...  

math.c

C代碼 
#include <stdio.h>  
#include <math.h>  
  
double POW(double x,double y)//當(dāng)然，也可以在內(nèi)部調(diào)用math.pow，但是這里要說(shuō)明的是使用外部的C代碼  
{  
    return pow(x,y);  
}  

我們可以進(jìn)行一些簡(jiǎn)單的測(cè)試，現(xiàn)在我們可以把第二個(gè)版本的hoc的完整代碼給出來(lái)：

lex.l

C代碼 
%{  
#include "y.tab.h"  
extern YYSTYPE yylval;  
extern int lineno;  
%}  
%%  
[ \t]+          {;}  
[0-9]+|[0-9]*\.[0-9]+    
             {  
               sscanf(yytext,"%lf",&yylval.val);  
               return NUMBER;  
             }  
[a-z]        {  
               yylval.index = yytext[0] - 'a';  
               return VAR;  
             }  
\n           {lineno++;return '\n';}  
.            {return yytext[0];}  
%%  

lex.y

C代碼 
%{  
#include <stdio.h>  
#include <stdlib.h>  
char *progname;  
int    lineno = 1;  
double mem[26];  
extern double POW(double ,double);  
%}  
%union{  
    double val;  
    int    index;  
}  
%token <val> NUMBER  
%token <index> VAR  
%type <val> expr  
%right '='  
%left '+' '-'  
%left '*' '/'  
%left UNARYMINUS  
%right '^'  
%%  
list    :     
        |    list '\n'  
        |    list expr '\n'    {printf("\t%.8g\n",$2);}  
        |    list error '\n'   {yyerrok;}  
        ;  
expr    :    NUMBER  
        |    VAR              {$$ = mem[$1];}  
        |    VAR '=' expr     {$$ = mem[$1] = $3;}  
        |    '-' expr %prec UNARYMINUS {$$ = -$2;}  
        |    expr '+' expr    {$$ = $1 + $3;}  
        |    expr '-' expr    {$$ = $1 - $3;}  
        |    expr '*' expr    {$$ = $1 * $3;}  
        |    expr '/' expr    {if($3 == 0.0)  
                                yyerror("devide zero error\n");  
                                $$ = $1 / $3;}  
        |    expr '^' expr    {$$ = POW($1,$3);}  
        |    '(' expr ')'     {$$ = $2;}  
        ;  
%%  
#include <signal.h>  
#include <setjmp.h>  
jmp_buf begin;  
int main(int argc,char **argv)  
{  
    int fpecatch();  
    progname = argv[0];  
    setjmp(begin);  
    signal(SIGFPE,fpecatch);  
    yyparse();  
}  
fpecatch()//Floating point exception  
{  
    warning("floating point exception",(char *)0);  
}  
yyerror(char *s)  
{  
    warning(s,(char *)0);  
    longjmp(begin,0);  
}  
yywrap()  
{  
    return 1;  
}  
warning(char *s,char *t)  
{  
    fprintf(stderr,"%s : %s",progname,s);  
    if(t)  
        fprintf(stderr," %s",t);  
    fprintf(stderr," near line %d\n",lineno);  
}  

math.c

C代碼 
#include <stdio.h>  
#include <math.h>  
  
double POW(double x,double y)  
{  
    return pow(x,y);  
}  

makefile

C代碼 
hoc:    y.tab.o lex.yy.o maths.o  
    gcc y.tab.o lex.yy.o maths.o -o hoc -lm  
y.tab.o:y.tab.c  
    gcc -c y.tab.c  
y.tab.c:hoc.y  
    yacc -d hoc.y  
lex.yy.o:lex.yy.c  
    gcc -c lex.yy.c  
lex.yy.c:hoc.l  
    lex hoc.l  
maths.o:maths.c  
    gcc -c maths.c  
clean:  
    rm -f y.tab.[cho]  
    rm -f lex.yy.[cho]  
    rm -f maths.o  

make成功以后，就可以測(cè)試一下，對(duì)變量的支持，和錯(cuò)誤的恢復(fù)，以及對(duì)冪函數(shù)的支持?，F(xiàn)在離我們的目標(biāo)還有多遠(yuǎn)呢？我覺得已經(jīng)比較接近了，但是，我們現(xiàn)在還需要支持更多的外部函數(shù)，如計(jì)算正弦余弦函數(shù)，計(jì)算對(duì)數(shù)函數(shù)，開方，冪函數(shù)等等。還有，像很多個(gè)數(shù)學(xué)引擎一樣，我們應(yīng)該考慮內(nèi)建一些常量，如 PI，E等。當(dāng)然，除了我們第二個(gè)版本的半成品，再?zèng)]有一個(gè)語(yǔ)言的變量會(huì)規(guī)定為一個(gè)字母，因此，我們需要對(duì)這些方面進(jìn)行一些改造。

這一次就先寫這些，我對(duì)高版本的HOC再做一些注釋，然后再寫一些解釋很分析出來(lái)。

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自： Keamou > 《Computer Science》

舉報(bào)/認(rèn)領(lǐng)