編譯原理上機實用教案

1、1一、上機實驗一、上機實驗(shyn)的的目的目的 通過做上機題加深對編譯器構(gòu)造原理和方法的理解，鞏固所學(xué)知識。通過做上機題加深對編譯器構(gòu)造原理和方法的理解，鞏固所學(xué)知識。 會用正規(guī)式和產(chǎn)生式設(shè)計簡單語言的語法；會用正規(guī)式和產(chǎn)生式設(shè)計簡單語言的語法； 會用遞歸下降子程序編寫會用遞歸下降子程序編寫(binxi)(binxi)編譯器或解釋器；編譯器或解釋器； 會寫上機報告。會寫上機報告。二、上機題目(tm)簡單函數(shù)繪圖語言的解釋器 2.1 題目(tm)簡述 實現(xiàn)簡單函數(shù)繪圖的語句實現(xiàn)簡單函數(shù)繪圖的語句循環(huán)繪圖（循環(huán)繪圖（FOR-DRAWFOR-DRAW）比例設(shè)置（比例設(shè)置（SCALESCALE）角

2、度旋轉(zhuǎn)（角度旋轉(zhuǎn)（ROTROT）坐標平移（坐標平移（ORIGINORIGIN）注釋注釋 （- - 或或 / /） 屏幕（窗口）的坐標系屏幕（窗口）的坐標系左上角為原點左上角為原點x x方向從左向右增長方向從左向右增長y y方向從上到下增長方向從上到下增長( (與一般的坐標與一般的坐標系方向相反系方向相反) )第1頁/共25頁第一頁，共26頁。2 函數(shù)繪圖函數(shù)繪圖(hu t)(hu t)源程序舉例源程序舉例 - - 函數(shù)函數(shù)f(t)=tf(t)=t的圖形的圖形origin is (100, 300);origin is (100, 300);- - 設(shè)置原點的偏移量設(shè)置原點的偏移量rot is

3、0;rot is 0;- - 設(shè)置旋轉(zhuǎn)角度設(shè)置旋轉(zhuǎn)角度(jiod)(jiod)(不旋轉(zhuǎn)不旋轉(zhuǎn)) )scale is (1, 1);scale is (1, 1);- - 設(shè)置橫坐標和縱坐標的比例設(shè)置橫坐標和縱坐標的比例for T from 0 for T from 0 toto 200 step 1 draw (t, 0); 200 step 1 draw (t, 0);- - 橫坐標的軌跡（縱坐標為橫坐標的軌跡（縱坐標為0 0）for T from 0 for T from 0 toto 150 step 1 draw (0, -t); 150 step 1 draw (0, -t);- -

4、 縱坐標的軌跡（橫坐標為縱坐標的軌跡（橫坐標為0 0）for T from 0 for T from 0 toto 120 step 1 draw (t, -t); 120 step 1 draw (t, -t);- - 函數(shù)函數(shù)f(t)=tf(t)=t的軌跡的軌跡 默認值：默認值：origin is (0, 0)origin is (0, 0)rot is 0;rot is 0;scale is (1, 1)scale is (1, 1)第2頁/共25頁第二頁，共26頁。32.2 2.2 語句語句(yj)(yj)的語法和語義（的語法和語義（syntax & syntax &

5、semanticssemantics） 語句滿足下述規(guī)定(原則)： 各類語句可以按任意次序書寫，且語句以分號結(jié)尾。源程序中的語句以它們出現(xiàn)的先后順序處理。 ORIGIN、ROT和SCALE 語句只影響其后的繪圖語句，且遵循最后出現(xiàn)的語句有效的原則。例如，若有下述ROT語句序列： ROT IS 0.7 ；ROT IS 1.57 ；則隨后的繪圖語句將按1.57而不是0.7弧度(hd)旋轉(zhuǎn)。 無論ORIGIN、ROT和SCALE語句的出現(xiàn)順序如何，圖形的變換順序總是：比例變換旋轉(zhuǎn)變換平移變換 語言對大小寫不敏感，例如for、For、FOR等，均被認為是同一個保留字。 語句中表達式的值均為雙精度類型，

6、旋轉(zhuǎn)角度單位為弧度(hd)且為逆時針旋轉(zhuǎn)，平移單位為點。 第3頁/共25頁第三頁，共26頁。42.2.1 2.2.1 循環(huán)循環(huán)(xnhun)(xnhun)繪圖（繪圖（FOR-DRAW FOR-DRAW ）語句語句 語法(yf)：語義：舉例：說明：注意：FOR T FROM FOR T FROM 起點起點 TOTO 終點終點 STEP STEP 步長步長 DRAW( DRAW(橫坐標橫坐標, , 縱坐標縱坐標););令令T T從起點到終點、每次改變一個步長，繪制出由從起點到終點、每次改變一個步長，繪制出由( (橫坐標，縱坐標橫坐標，縱坐標) )所規(guī)定的點的軌跡。所規(guī)定的點的軌跡。FOR T FR

7、OM 0 FOR T FROM 0 TOTO 2 2* *PI STEP PI/50 DRAW (cos(T), sin(T);PI STEP PI/50 DRAW (cos(T), sin(T);該語句該語句(yj)(yj)的作用是令的作用是令T T從從0 0到到2 2* *PIPI、步長、步長 PI/50 PI/50，繪制出各個點的坐標，繪制出各個點的坐標(cos(T)(cos(T)，sin(T)sin(T)，即一個單位園。，即一個單位園。由于繪圖系統(tǒng)的默認值是ORIGIN IS (0,0);ORIGIN IS (0,0);ROT IS 0;ROT IS 0;SCALE IS (1, 1)

8、;SCALE IS (1, 1);所以實際繪制出的圖形是在屏幕左上角的一個點。第4頁/共25頁第四頁，共26頁。52.2.2 2.2.2 比例設(shè)置比例設(shè)置(shzh)(SCALE)(shzh)(SCALE)語句語句語法(yf)：語義：舉例：說明：SCALE IS (SCALE IS (橫坐標比例因子，縱坐標比例因子橫坐標比例因子，縱坐標比例因子););設(shè)置設(shè)置(shzh)(shzh)橫坐標和縱坐標的比例，并分別按照比例因子進行縮放。橫坐標和縱坐標的比例，并分別按照比例因子進行縮放。SCALE IS (100, 100);SCALE IS (100, 100);將橫坐標和縱坐標的比例設(shè)置將橫坐標

9、和縱坐標的比例設(shè)置(shzh)(shzh)為為1:11:1，且放大，且放大100100倍。倍。語法：語義：舉例：說明：ORIGIN ISORIGIN IS (橫坐標，縱坐標); 將坐標系的原點平移到橫坐標和縱坐標規(guī)定的點處。ORIGIN IS (360, 240);ORIGIN IS (360, 240); 將原點從(0, 0)(0, 0)平移到(360, 240)(360, 240) 處。若： SCALE IS (100, 100/3);SCALE IS (100, 100/3); 則：橫坐標和縱坐標的比例為3:13:1。第5頁/共25頁第五頁，共26頁。62.2.4 2.2.4 角度角度(

10、jiod)(jiod)旋轉(zhuǎn)旋轉(zhuǎn)(ROT)(ROT)語句語句語法(yf)：語義：舉例：說明：ROT IS ROT IS 角度；角度； 逆時針旋轉(zhuǎn)角度所規(guī)定的弧度逆時針旋轉(zhuǎn)角度所規(guī)定的弧度(hd)(hd)值。具體計算公式：值。具體計算公式：旋轉(zhuǎn)后旋轉(zhuǎn)后X=X=旋轉(zhuǎn)前旋轉(zhuǎn)前X X* *COS(COS(角度角度)+)+旋轉(zhuǎn)前旋轉(zhuǎn)前Y Y* *SIN(SIN(角度角度) ) 旋轉(zhuǎn)后旋轉(zhuǎn)后Y=Y=旋轉(zhuǎn)前旋轉(zhuǎn)前Y Y* *COS(COS(角度角度)-)-旋轉(zhuǎn)前旋轉(zhuǎn)前X X* *SIN(SIN(角度角度) )公式的推導(dǎo)可參閱輔助教材。公式的推導(dǎo)可參閱輔助教材。ROT IS PI/2; ROT IS PI/2;

11、 逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)PI/2PI/2，即逆時針旋轉(zhuǎn)，即逆時針旋轉(zhuǎn)9090度。度。2.2.5 注釋語句 注釋的作用：語法：語義：便于理解；屏蔽暫時不需要的語句。/ This is a comment line/ This is a comment line 或 - 此行是注釋 / 或 - 之后，直到行尾，均是注釋第6頁/共25頁第六頁，共26頁。7語句功能語句功能(gngnng)(gngnng)的測試的測試ORIGIN IS (360, 240);ORIGIN IS (360, 240);/ (1) / (1) 原點移至原點移至(360, 240)(360, 240)SCALE IS (100

12、, 100);SCALE IS (100, 100);/ (2) / (2) 圖形圖形(txng)(txng)放大放大100100SCALE IS (100, 100/3);SCALE IS (100, 100/3);/ (3) / (3) 縱坐標縮小為三分之一縱坐標縮小為三分之一ROT IS PI/2;ROT IS PI/2;/ (4) / (4) 逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)9090度度- - 繪制園的軌跡繪制園的軌跡FOR T FROM 0 FOR T FROM 0 TOTO 2 2* *PI STEP PI/50 DRAW (cos(T), sin(T);PI STEP PI/50 DRAW

13、(cos(T), sin(T);僅僅(1)(1)和和(2)(2)加入加入(3)(3)加入加入(4)(4)第7頁/共25頁第七頁，共26頁。8其他函數(shù)其他函數(shù)(hnsh)(hnsh)圖形：圖形：看實例看實例(shl)第8頁/共25頁第八頁，共26頁。92.3 2.3 記號記號(j ho)(j ho)的語法和語義的語法和語義 記號的種類(zhngli)：常數(shù)、參數(shù)、函數(shù)、保留字、運算符、分隔符 常數(shù) 常數(shù)字面量和標識符形式的常量名均稱為常數(shù)。字面量的形式為普通的數(shù)值，如果沒有小數(shù)部分，可以(ky)省略小數(shù)點。例如2、2.、2.0都是合法的常數(shù)。 標識符PI、E也是常數(shù)，它們分別代表圓周率和自然對數(shù)

14、的底。常數(shù)不能有符號位，如-1和+2不是常數(shù)而是（一元運算的）表達式。 參數(shù) 本作圖語言中唯一的、已經(jīng)被定義好的變量名T T被稱為參數(shù)，它也是一個表達式。由于作圖語言中只有這唯一的變量，因此作圖語言中無需變量或參數(shù)的聲明和定義語句。 第9頁/共25頁第九頁，共26頁。102.3 2.3 記號記號(j ho)(j ho)的語法和語義（續(xù)）的語法和語義（續(xù)） 保留字：語句(yj)中具有固定含義的標識符，包括：ORIGIN, SCALE, ROT, IS, TO, STEP, DRAW, FOR, FROM 運算符PLUS, MINUS, MUL, DIV, POWER即:+ - * /* 分隔符S

15、EMICO, L_BRACKET, R_BRACKET, COMMA即:; ( ) , 函數(shù)（調(diào)用） 為簡單起見，當(dāng)前函數(shù)調(diào)用僅支持Sin、Cos、Tan、Sqrt以及Exp和Ln。有興趣的同學(xué)可以(ky)再加入其他函數(shù)。第10頁/共25頁第十頁，共26頁。11三、三、 題目題目(tm)(tm)與與要求要求1.用某種程序設(shè)計語言（如C/C+、Pascal、Java等）和遞歸下降子程序方法編寫完整的解釋器，由于環(huán)境限制，本書統(tǒng)一采用C/C+程序設(shè)計語言；2.利用編譯器編寫工具(gngj)LEX/YACC提供的方式規(guī)定繪圖語言的詞法和語法，用C/C+語言編寫解釋器的語義。3.1 解釋器的實現(xiàn)(sh

16、xin)方法題目：為函數(shù)繪圖語言編寫一個解釋器 解釋器接受用繪圖語言編寫的源程序，經(jīng)語法和語義分析之后，將源程序所規(guī)定的圖形顯示在顯示屏（或窗口）中。目的：通過自己動手編寫解釋器，掌握語言翻譯特別是語言識別的基本方法。第11頁/共25頁第十一頁，共26頁。123.1 3.1 解釋器的實現(xiàn)解釋器的實現(xiàn)(shxin)(shxin)方法方法 兩種方法的語義部分(b fen)基本相同，主要區(qū)別在于詞法和語法分析器的構(gòu)造是手工完成還是借助于工具完成。 第12頁/共25頁第十二頁，共26頁。133.3 3.3 任務(wù)劃分任務(wù)劃分(hu fn)(hu fn)與上機報告與上機報告 任務(wù)劃分：（三個階段）詞法分析

17、器、語法分析器、語義分析器機時比例（大概）：1:1:1要求：驗收經(jīng)過測試的程序提交上機報告(bogo)。其中上機報告(bogo)可以包括以下內(nèi)容： 任務(wù)與目的 軟件設(shè)計a. 軟件的總體結(jié)構(gòu)與模塊劃分b. 關(guān)鍵算法與重要數(shù)據(jù)結(jié)構(gòu) 測試例程設(shè)計與測試結(jié)果分析 總結(jié)、體會、改進建議等 工作方法建議：每個階段均進行設(shè)計與測試，并且寫出報告；采用(ciyng)增量式設(shè)計；工作全部完成后將三個階段的工作進行總結(jié)即可。第13頁/共25頁第十三頁，共26頁。14四、遞歸子程序方法的參考四、遞歸子程序方法的參考(cnko)(cnko)解決方案解決方案4.1 4.1 詞法分析器的構(gòu)造詞法分析器的構(gòu)造 步驟：正規(guī)(

18、zhnggu)式NFADFA最小DFA編寫程序測試 4.1.1 記號的設(shè)計 詞法分析器的三個任務(wù)：1濾掉源程序中的無用成分；2輸出記號供語法分析器使用(shyng)；3識別非法輸入，并將其標記為“出錯記號”。 記號的組成：記號的類別和屬性。 記號的數(shù)據(jù)結(jié)構(gòu)： struct struct TokenToken/ 記號的數(shù)據(jù)結(jié)構(gòu) Token_TypeToken_Type type; type;/ 類別char char * * lexeme; lexeme;/ 屬性，原始輸入的字符串double value;double value;/ 屬性，若記號是常數(shù)則是常數(shù)的值double (double

19、(* * FuncPtr)(double); FuncPtr)(double);/ 屬性，若記號是函數(shù)則是函數(shù)指針; ; 例例2.22.2第14頁/共25頁第十四頁，共26頁。154.14.1詞法詞法(cf)(cf)分析器的構(gòu)造（續(xù)分析器的構(gòu)造（續(xù)1 1） 函數(shù)繪圖語言中記號(j ho)的分類與表示enum Token_Typeenum Token_Type / / 記號記號(j ho)(j ho)的類別，共的類別，共2222個個 ORIGIN, SCALE, ROT, IS,ORIGIN, SCALE, ROT, IS, / / 保留字（一字一碼）保留字（一字一碼）TOTO, STEP, D

20、RAW,FOR, FROM, / , STEP, DRAW,FOR, FROM, / 保留字保留字; ; T,T, / 參數(shù)SEMICO, L_BRACKET, R_BRACKET, COMMA,SEMICO, L_BRACKET, R_BRACKET, COMMA,/ 分隔符PLUS, MINUS, MUL, DIV, POWER,PLUS, MINUS, MUL, DIV, POWER,/ 運算符FUNC,FUNC, / 函數(shù)（調(diào)用）CONST_ID,CONST_ID, / 常數(shù)NONTOKEN,NONTOKEN, / 空記號（源程序結(jié)束）ERRTOKENERRTOKEN / 出錯記號（非

21、法輸入）下一頁下一頁關(guān)系關(guān)系第15頁/共25頁第十五頁，共26頁。164.1.2 4.1.2 模式模式(msh)(msh)的正規(guī)式表示的正規(guī)式表示 letterletter= a-zA-Z= a-zA-Zdigitdigit= 0-9 = 0-9 COMMENT COMMENT = /|-= /|-WHITE_SPACE WHITE_SPACE = ( |t|n)+= ( |t|n)+SEMICO SEMICO = ;= ;L_BRACKET L_BRACKET = (= (R_BRACKET R_BRACKET = )= )COMMA COMMA = ,= ,PLUS PLUS = += +

22、MINUS MINUS = -= -MUL MUL = = * * DIV DIV = /= /POWER POWER = = * * * CONST_ID CONST_ID = digit+(. digit= digit+(. digit* *)?)?ID ID = letter+ = letter+ （去除注釋（去除注釋(zhsh)(zhsh)與白空有與白空有1111個正規(guī)式）個正規(guī)式） 由于是手工構(gòu)造詞法分析器，而正規(guī)式個數(shù)越少越便于程序的編寫，因此設(shè)計上采用相同模式的記號共用一個正規(guī)式的方法。 常數(shù)的字面量部分設(shè)計為CONST_ID，而常量(chngling)名則合并到ID中。 這就帶

23、來一個問題，函數(shù)繪圖語言中的保留字、常量(chngling)名、參數(shù)名、以及函數(shù)名均被描述為ID，當(dāng)識別出ID時，如何再細分它們？ 上一頁上一頁關(guān)系關(guān)系第16頁/共25頁第十六頁，共26頁。174.1.3 4.1.3 區(qū)分區(qū)分(qfn)(qfn)記號的符號表記號的符號表 static Token TokenTab =static Token TokenTab = CONST_ID,CONST_ID,PI,PI,3.1415926,3.1415926,NULL,NULL,CONST_ID,CONST_ID,E,E,2.71828,2.71828,NULL,NULL, 預(yù)先(yxin)定義且內(nèi)容不

24、變的符號表更多被習(xí)慣地稱為字典。 T,T,T,T,0.0,0.0,NULL,NULL,FUNC,FUNC,SIN,SIN,0.0,0.0,sin,sin,FUNC,FUNC,COS,COS,0.0,0.0,cos,cos,FUNC,FUNC,TAN,TAN,0.0,0.0,tan,tan,FUNC,FUNC,LN,LN,0.0,0.0,log,log,FUNC,FUNC,EXP,EXP,0.0,0.0,exp,exp,FUNC,FUNC,SQRT,SQRT,0.0,0.0,sqrt,sqrt,ORIGIN,ORIGIN,ORIGIN,ORIGIN,0.0,0.0,NULL,NULL,SCALE

25、,SCALE,SCALE,SCALE,0.0,0.0,NULL,NULL,ROT,ROT,ROT,ROT,0.0,0.0,NULL,NULL,IS,IS,IS,IS,0.0,0.0,NULL,NULL,FOR,FOR,FOR,FOR,0.0,0.0,NULL,NULL,FROM,FROM,FROM,FROM,0.0,0.0,NULL,NULL,TO,TO,TO,TO,0.0,0.0,NULL,NULL,STEP,STEP,STEP,STEP,0.0,0.0,NULL,NULL,DRAW,DRAW,DRAW,DRAW,0.0,0.0,NULLNULL;關(guān)系關(guān)系(gun x)(gun x)第17頁

26、/共25頁第十七頁，共26頁。18三者之間的關(guān)系三者之間的關(guān)系(gun x)(gun x)1.記號類別（enum Token_Type）：作用是規(guī)定所有記號的類別；2.正規(guī)式：作用是描述和識別所有類別的記號；3.字典：作用是區(qū)分(qfn)同一模式下的不同記號； 當(dāng)輸入被匹配為ID時，首先去查字典，從字典中得到此ID所代表的記號，然后返回記號信息給語法分析器。 內(nèi)部識別的模式與外部返回的記號之間不是一一對應(yīng)的，可以根據(jù)實際(shj)情況設(shè)計，原則是能夠正確識別和返回所有記號，且便于程序?qū)崿F(xiàn)。ROT IS PI/6ROT IS PI/6第18頁/共25頁第十八頁，共26頁。19例例2.2 2.2

27、語句語句(yj) ROT IS PI/6 (yj) ROT IS PI/6 的記號流的記號流ROTNULLISNULLCONST_IDNULLDIVNULLCONST_IDNULL 存放存放(cnfng)(cnfng)記號的數(shù)據(jù)結(jié)構(gòu)記號的數(shù)據(jù)結(jié)構(gòu)第19頁/共25頁第十九頁，共26頁。204.1.4 4.1.4 正規(guī)正規(guī)(zhnggu)(zhnggu)式的式的DFA DFA letterletter= a-zA-Z= a-zA-Zdigitdigit= 0-9 = 0-9 ID = letter+ID = letter+CONST_ID = digit+(. digitCONST_ID = di

28、git+(. digit* *)?)?POWER = POWER = * * * COMMENT = /|-COMMENT = /|-SEMICO = ;SEMICO = ;L_BRACKET = (L_BRACKET = (R_BRACKET = )R_BRACKET = )COMMA = ,COMMA = ,PLUS = +PLUS = +MINUS = -MINUS = -MUL = MUL = * * DIV = /DIV = /“WHITE_SPACE = ( |t|n)WHITE_SPACE = ( |t|n)+ +注意：WHITE_SPACE（白空）沒有(mi yu)在DFA中。

29、如何處理白空？第20頁/共25頁第二十頁，共26頁。214.1.5 4.1.5 詞法詞法(cf)(cf)分析器的程序框架分析器的程序框架struct Token token=ERRTOKEN, “ ”, 0.0, NULL; / struct Token token=ERRTOKEN, “ ”, 0.0, NULL; / 用于返回記號用于返回記號token.lexeme = TokenBuffer;token.lexeme = TokenBuffer;/ / 記號的字符記號的字符(z f)(z f)指針指向字符指針指向字符(z f)(z f)緩沖區(qū)緩沖區(qū)（其中的輔助(fzh)函數(shù)和變量看教材）

30、 char =GetChar();char =GetChar();/ 從源文件中讀取一個字符/ 空格、TABTAB、回車等字符的過濾AddInTokenString (char);AddInTokenString (char);/ 將讀入的字符放進緩沖區(qū)TokenBufferTokenBuffer中if (isalpha(char) if (isalpha(char) / / 識別IDID else if (isdigit(char) else if (isdigit(char) / 識別數(shù)字常量 else else switch(char) switch(char) case case ;

31、;: token.type = SEMICO; : token.type = SEMICO; return token; return token; 第21頁/共25頁第二十一頁，共26頁。224.1.6 4.1.6 與語法分析器的接口與語法分析器的接口(ji ku) (ji ku) 詞法(cf)分析器的測試#include scanner.h#include scanner.hvoid main(int argc, char void main(int argc, char * *argv)argv) Token token; Token token; if (argc2) printf(p

32、lease input Source File !n ); return;if (argc2) printf(please input Source File !n ); return;if (!InitScanner(argv1) / if (!InitScanner(argv1) / 初始化詞法初始化詞法(cf)(cf)分析器分析器 printf(Open Source File Error ! n); return; printf(Open Source File Error ! n); return; printf(printf(記號類別 字符串 常數(shù)值 函數(shù)指針n);n);printf(_n);printf(_n);while(1) while(1) token = token = GetToken GetToken()(); ;/ 通過詞法分析器獲得一個記號 if(token.type != NONTOKEN)if(token.type != NONTOKEN)/ 打印記號的內(nèi)容printf(%4d,%12s,%12f,%12xn,printf(%4d,%12s,%12f,%12xn,token.type,