4西安電子科技大學《編譯原理》

《4西安電子科技大學《編譯原理》》由會員分享，可在線閱讀，更多相關(guān)《4西安電子科技大學《編譯原理》（22頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,上機作業(yè),一、上機作業(yè)的目的,通過做上機題加深對編譯器構(gòu)造原理和方法的理解，鞏固所學知識。,會用正規(guī)式和產(chǎn)生式設計簡單語言的語法；,會用遞歸下降子程序編寫編譯器或解釋器；,會寫上機報告。,二、上機題目簡單的函數(shù)繪圖語言,2.1 題目簡述,實現(xiàn)簡單函數(shù)繪圖的語句,循環(huán)繪圖（,FOR-DRAW,）,比例設置（,SCALE,）,角度旋轉(zhuǎn)（,ROT,）,坐標平移（,ORIGIN,）,注釋 （-或/）,屏幕（窗口）的坐標系,左上角為原點,x,方向從左向右增長,y,方向從上到下增長（與一般的坐標系方向相反）,1,函數(shù)繪

2、圖源程序舉例,-函數(shù),f(t)=t,的圖形,origin is(100,300);-,設置原點的偏移量,rot is 0;-,設置旋轉(zhuǎn)角度(不旋轉(zhuǎn)),scale is(1,1);-,設置橫坐標和縱坐標的比例,for T from 0 to 200 step 1 draw(t,0);,-,橫坐標的軌跡（縱坐標為0）,for T from 0 to 150 step 1 draw(0,-t);,-,縱坐標的軌跡（橫坐標為0）,for T from 0 to 120 step 1 draw(t,-t);,-,函數(shù),f(t)=t,的軌跡,默認值：,origin is(0,0),rot is 0;,sc

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

4、中表達式的值均為雙精度類型，旋轉(zhuǎn)角度單位為弧度且為逆時針旋轉(zhuǎn)，平移單位為點。,3,2.2.1 循環(huán)繪圖（,FOR-DRAW,）,語句,語法：,語義：,舉例：,說明：,注意：,FOR T FROM,起點,TO,終點,STEP,步長,DRAW,(,橫坐標,縱坐標,);,令,T,從,起點,到,終點,、,每次改變一個,步長,，,繪制出由(,橫坐標,，,縱坐標,)所規(guī)定的點的軌跡。,FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(,cos,(T),sin(T);,該語句的作用是令,T,從0到2*,PI、,步長,PI/50，,繪制出各個點的坐標(,cos,(T)，sin(T)，,

5、即一個單位園。,由于繪圖系統(tǒng)的默認值是,ORIGIN IS(0,0);,ROT IS 0;,SCALE IS(1,1);,所以實際繪制出的圖形是在屏幕左上角的一個點。,4,2.2.2 比例設置(,SCALE,),語句,語法：,語義：,舉例：,說明：,SCALE IS(,橫坐標比例因子，縱坐標比例因子,);,設置橫坐標和縱坐標的比例，并分別按照比例因子進行縮放。,SCALE IS(100,100);,將橫坐標和縱坐標的比例設置為1:1，且放大100倍。,語法：,語義：,舉例：,說明：,2.2.3 坐標平移(,ORIGIN,),語句,ORIGIN IS,(,橫坐標，縱坐標);,將坐標系的原點平移到

6、橫坐標和縱坐標規(guī)定的點處。,ORIGIN IS(360,240);,將原點從,(0,0),平移到,(360,240),處。,若：,SCALE IS(100,100/3);,則：,橫坐標和縱坐標的比例為,3:1,。,5,2.2.4 角度旋轉(zhuǎn)(,ROT,),語句,語法：,語義：,舉例：,說明：,ROT IS,角度；,逆時針旋轉(zhuǎn)角度所規(guī)定的弧度值。具體計算公式：,旋轉(zhuǎn)后,X,=,旋轉(zhuǎn)前,X*COS,(,角度)+旋轉(zhuǎn)前,Y*SIN,(,角度),旋轉(zhuǎn)后,Y,=,旋轉(zhuǎn)前,Y*COS,(,角度)-旋轉(zhuǎn)前,X*SIN,(,角度),公式的推導可參閱輔助教材58頁。,ROT IS PI/2;,逆時針旋轉(zhuǎn),PI/2

7、,，,即,逆時針旋轉(zhuǎn)90度。,2.2.5 注釋語句,注釋的作用：,語法：,語義：,便于理解；,屏蔽暫時不需要的語句。,/,This is a comment line,或 -此行是注釋,/或-之后，直到行尾，均是注釋,6,語句功能的測試,ORIGIN IS(360,240);,/(1),原點移至(360,240),SCALE IS(100,100);,/(2),圖形放大100,SCALE IS(100,100/3);,/(3),縱坐標縮小為三分之一,ROT IS PI/2;,/(4),逆時針旋轉(zhuǎn)90度,-繪制園的軌跡,FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(,

8、cos,(T),sin(T);,僅(1)和(2),加入(3),加入(4),7,其他函數(shù)圖形：,8,2.3 記號的語法和語義,記號的種類：,常數(shù),參數(shù),函數(shù)（調(diào)用）,常數(shù)、參數(shù)、函數(shù)、保留字、運算符、分隔符,常數(shù)字面量,和標識符形式的,常量名,均稱為常數(shù)。字面量的形式為普通的數(shù)值，如果沒有小數(shù)部分，可以省略小數(shù)點。例如,2、2.、2.0,都是合法的常數(shù)。標識符,PI、E,也是常數(shù)，它們分別代表圓周率和自然對數(shù)的底。常數(shù)不能有符號位，如,-1,和,+2,不是常數(shù)而是（一元運算的）表達式。,本作圖語言中唯一的、已經(jīng)被定義好的,變量名,T,被稱為參數(shù),，它也是一個表達式。由于作圖語言中只有這唯一的變量

9、，因此作圖語言中無需變量或參數(shù)的聲明和定義語句。,為簡單起見，當前的函數(shù)僅支持正弦函數(shù),Sin,，,余弦函數(shù),Cos,，,正切函數(shù),Tan,，,算術(shù)平方根函數(shù),Sqrt,以及指數(shù)函數(shù),Exp,和對數(shù)函數(shù),Ln,。,有興趣的同學可以再加入其他函數(shù)。,9,2.3 記號的語法和語義（續(xù)）,保留字,運算符,分隔符,語句中具有固定含義的標識符，包括：,ORIGIN,SCALE,ROT,IS,TO,STEP,DRAW,FOR,FROM,PLUS,MINUS,MUL,DIV,POWER,即:,+-*/*,SEMICO,L_BRACKET,R_BRACKET,COMMA,即:,;(),10,三、題目與要求,用

10、某種程序設計語言（如,C/C+、Pascal、Java,等）和遞歸下降子程序方法編寫完整的解釋器，由于環(huán)境限制，本書統(tǒng)一采用,C/C+,程序設計語言；,利用編譯器編寫工具,LEX/YACC,提供的方式規(guī)定繪圖語言的詞法和語法，用,C/C+,語言編寫解釋器的語義。,兩種方法的語義部分基本相同，主要區(qū)別在于詞法和語法分析器的構(gòu)造是手工完成還是借助于工具完成。,3.1 解釋器的實現(xiàn)方法,題目：,為函數(shù)繪圖語言編寫一個解釋器,解釋器接受用繪圖語言編寫的源程序，經(jīng)過語法和語義分析之后，將源程序所規(guī)定的圖形顯示在顯示屏（或顯示窗口）上,目的：,通過自己動手編寫解釋器，掌握語言翻譯特別是語言識別的基本方法,

11、11,3.1 解釋器的實現(xiàn)方法,兩種方法的語義部分基本相同，主要區(qū)別在于詞法和語法分析器的構(gòu)造是手工完成還是借助于工具完成。,12,3.3 任務劃分與上機報告,任務劃分：（三個階段）,詞法分析器,語法分析器,語義分析器,機時比例（大概）：,2:2:2,要求：,驗收,經(jīng)過測試的程序,提交上機報告。其中上機報告可以包括以下內(nèi)容：,任務與目的,軟件設計,a.,軟件的總體結(jié)構(gòu)與模塊劃分,b.,關(guān)鍵算法與重要數(shù)據(jù)結(jié)構(gòu),測試例程設計與測試結(jié)果分析,總結(jié)、體會、改進建議等,工作方法建議：,每個階段均進行設計與測試，并且寫出報告；采用增量式設計；工作全部完成后將三個階段的工作進行總結(jié)即可。,13,四、遞歸子程

12、序方法的參考解決方案,4.1詞法分析器的構(gòu)造,詞法分析器的構(gòu)造步驟：,正規(guī)式,NFADFA,最小,DFA,編寫程序測試,4.1.1 記號的設計,詞法分析器的三個任務：,1,濾掉源程序中的無用成分；,2輸出記號供語法分析器使用；,3識別非法輸入，并將其標記為“出錯記號”。,記號的組成：記號的,類別,和,屬性,。,記號的數(shù)據(jù)結(jié)構(gòu)：,struct,Token,/,記號的數(shù)據(jù)結(jié)構(gòu),Token_Type,type;/,類別,char*lexeme;/,屬性，原始輸入的字符串,double value;/,屬性，若記號是常數(shù)則是常數(shù)的值,double(*,FuncPtr,)(double);,/,屬性，若

13、記號是函數(shù)則是函數(shù)的指針,;,14,4.1詞法分析器的構(gòu)造（續(xù)1）,函數(shù)繪圖語言中記號的分類與表示,enum,Token_Type,/,記號的類別,ORIGIN,SCALE,ROT,IS,/,保留字（一字一碼）,TO,STEP,DRAW,FOR,FROM,/,保留字,T,/,參數(shù),SEMICO,L_BRACKET,R_BRACKET,COMMA,/,分隔符,PLUS,MINUS,MUL,DIV,POWER,/,運算符,FUNC,/,函數(shù),CONST_ID,/,常數(shù),NONTOKEN,/,空記號（源程序結(jié)束）,ERRTOKEN,/,出錯記號（非法輸入）,;,15,4.1.2 模式的正規(guī)式表示,l

14、etter=a-,zA,-Z,digit=0-9,COMMENT =/|-,WHITE_SPACE=(|t|n),+,SEMICO =;,L_BRACKET=(,R_BRACKET=),COMMA =,PLUS =+,MINUS =-,MUL =*,DIV =/,POWER =*,CONST_ID =digit,+,(.digit,*,)?,ID =letter,+,(letter|digit),*,由于是手工構(gòu)造詞法分析器，而正規(guī)式個數(shù)越少越便于程序的編寫，因此設計上采用相同模式的記號共用一個正規(guī)式的方法。,常數(shù)的字面量部分設計為,CONST_ID,，,而常量名則合并到,ID,中。,這就帶來

15、一個問題，函數(shù)繪圖語言中的保留字、常量名、參數(shù)名、以及函數(shù)名均被描述為,ID,，,當識別出,ID,時，如何再細分它們？,16,4.1.3 區(qū)分記號的符號表,static Token,TokenTab,=,CONST_ID,PI,3.1415926,NULL,CONST_ID,E,2.71828,NULL,T,T,0.0,NULL,FUNC,SIN,0.0,sin,FUNC,COS,0.0,cos,FUNC,TAN,0.0,tan,FUNC,LN,0.0,log,FUNC,EXP,0.0,exp,FUNC,SQRT,0.0,sqrt,ORIGIN,ORIGIN,0.0,NULL,SCALE,SC

16、ALE,0.0,NULL,ROT,ROT,0.0,NULL,IS,IS,0.0,NULL,FOR,FOR,0.0,NULL,FROM,FROM,0.0,NULL,TO,TO,0.0,NULL,STEP,STEP,0.0,NULL,DRAW,DRAW,0.0,NULL,;,預先定義且內(nèi)容不變的符號表更多被習慣地稱為,字典,。,17,例2.2,語句,ROT IS PI/6,的記號流,18,4.1.4 正規(guī)式的,DFA,letter=a-,zA,-Z,digit=0-9,COMMENT =/|-,WHITE_SPACE=(|t|n),+,SEMICO =;,L_BRACKET =(,R_BRACKET =),COMMA =,PLUS =+,MINUS =-,MUL =*,DIV =/,POWER =*,CONST_ID =digit+(.digit*)?,ID =letter+(letter|digit),*,注意：,WHITE_SPACE,（,白空）沒有在,DFA,中。,如何處理白空？,19,4.1.5 詞法分析器的程序框架,struct,Token token=ERRTOKEN,“,”,