詞法分析器1《編譯原理》上機作業（1）一、上機作業的目的2通過做上機題加深對編譯器構造原理和方法的理解，鞏固所學知識。<1>會用正規式和產生式設計簡單語言的語法；<2>會用遞歸下降子程序編寫編譯器或解釋器；<3>會寫上機報告。二、上機題目－簡單函數繪圖語言的解釋器2.1題目簡述<1>實現簡單函數繪圖的語句循環繪圖（FOR-DRAW）比例設置（SCALE）角度旋轉（ROT）

坐標平移（ORIGIN）注釋

（--

或//）<2>屏幕（窗口）的坐標系左上角為原點x方向從左向右增長y方向從上到下增長(與一般的坐標系方向相反)<3>函數繪圖源程序舉例3---------------函數f(t)=t的圖形origin

is

(100,

300);rot

is

0;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);--函數f(t)=t的軌跡默認值：origin

is

(0,

0)rot

is

0;scale

is

(1,

1)語句滿足下述規定(原se則m)：antics）4<1>各類語句可以按任意次序書寫，且語句以分號結尾。源程序中的語句以它們出現的先后順序處理。<2>ORIGIN、ROT和SCALE語句只影響其后的繪圖語句，且遵循最后出現的語句有效的原則。例如，若有下述ROT語句序列：ROT

IS

0.7

；ROT

IS

1.57

；則隨后的繪圖語句將按1.57而不是0.7弧度旋轉。<3>無論ORIGIN、ROT和SCALE語句的出現順序如何，圖形的變換順序總是：比例變換→旋轉變換→平移變換<4>語言對大小寫不敏感，例如for、For、FOR等，均被認為是同一個保留字。<5>語句中表達式的值均為雙精度類型，旋轉角度單位為弧度且為逆時針旋轉，平移單位為點。）語句5語法：FOR

T

FROM起點TO終點STEP步長DRAW(橫坐標,縱坐標語義)：;令T從起點到終點、每次改變一個步長，繪制出由(橫坐標，縱舉例坐：標)所規定的點的軌跡。說明F：OR

T

FROM

0

TO

2*PI

STEP

PI/50

DRAW

(cos(T),sin(T));語句的作用是令T從0到2*PI、步長PI/50，繪制出各個點的坐注意標：(cos(T)，sin(T))，即一個單位園。由于繪圖系統的默認值是ORIGIN

IS

(0,0);ROT

IS

0;SCALE

IS

(1,

1);所以實際繪制出的圖形是在屏幕左上角的一個點。2.2.2比例設置(SCALE)語句6語法：SCALE

IS(橫坐標比例因子，縱坐標比例因子);語義：設置橫坐標和縱坐標的比例，并分別按照比例因子進行縮放。舉例：SCALE

IS

(100,100);說明：將橫坐標和縱坐標的比例設置為1:1，且放大100倍。若：SCALE

IS

(100,100/3);則：橫坐標和縱坐標的比例為3:1。2.2.3坐標平移(ORIGIN)語句語法：ORIGIN

IS(橫坐標，縱坐標);語義：將坐標系的原點平移到橫坐標和縱坐標規定的點處。舉例：ORIGIN

IS

(360,240);說明：將原點從(0,0)平移到(360,240)處。2.2.4角度旋轉(ROT)語句7語法：ROT

IS角度；語義：逆時針旋轉角度所規定的弧度值。具體計算公式：旋轉后X=旋轉前X*COS(角度)+旋轉前Y*SIN(角度)旋轉后Y=旋轉前Y*COS(角度)-旋轉前X*SIN(角度舉例：)說明：ROT

IS

PI/2;逆時針旋轉PI/2，即逆時針旋轉90度。2.2.5注釋語句注釋的作用：便于理解；屏蔽暫時不需要的語句。語法： //

This

is

a

comment

line或--此行是注釋語義：

//

或--

之后，直到行尾，均是注釋語句功能的測試ORIGIN

IS

(360,

240);SCALE

IS

(100,

100);SCALE

IS

(100,

100/3);//(1)原點移至(360,240)//(2)圖形放大100//(3)縱坐標縮小為三分之一ROT

IS

PI/2;

//(4)逆時針旋轉90度--繪制園的軌跡FOR

T

FROM

0

TO

2*PI

STEP

PI/50

DRAW

(cos(T),

sin(T));僅(1)和(2)加入(3)加入(4)8其他函數圖形：看實例92.3記號的語法和語義10記號的種類：常數、參數、函數、保留字、運算符、分隔符<1>常數常數字面量和標識符形式的常量名均稱為常數。字面量的形式為普通的數值，如果沒有小數部分，可以省略小數點。例如2、2.、2.0都是合法的常數。標識符PI、E也是常數，它們分別代表圓周率和自然對數的底。常數不能有符號位，如-<12和>參+2數不是常數而是（一元運算的）表達式。本作圖語言中唯一的、已經被定義好的變量名T被稱為參數，它也是一個表達式。由于作圖語言中只有這唯一的變量，因此作圖語言中無需變量或參數的聲明和定義語句。<3>函數（調用）為簡單起見，當前的函數僅支持正弦函數Sin，余弦函數Cos，正切函數Tan，算術平方根函數Sqrt以及指數函數Exp和對數函數Ln。有興趣的同學可以再加入其他函數。2.3記號的語法和語義（續）11<4>保留字語句中具有固定含義的標識符，包括：ORIGIN,

SCALE,

ROT,

IS,

TO,STEP,

DRAW,

FOR,

FROM<5>運算符PLUS,

MINUS,

MUL,即:

+

-

*<6>分隔符DIV,

POWER/

**R_BRACKET,SEMICO,

L_BRACKET,COMMA即:

;

(

),三、題目與要求12題目：為函數繪圖語言編寫一個解釋器解釋器接受用繪圖語言編寫的源程序，經語法和語義分析之后，將源程序所規定的圖形顯示在顯示屏（或窗口）中。目的：通過自己動手編寫解釋器，掌握語言翻譯特別是語言識別的基本方法。3.1解釋器的實現方法用某種程序設計語言（如C/C++、Pascal、Java等）和遞歸下降子程序方法編寫完整的解釋器，由于環境限制，本書統一采用C/C++程序設計語言；利用編譯器編寫工具LEX/YACC提供的方式規定繪圖語言的詞法和語法，用C/C++語言編寫解釋器的語義。3.1解釋器的實現方法兩種方法的語義部分基本相同，主要區別在于詞法和語法分析器的構造是手工完成還是借助于工具完成。133.3任務劃分與上機報告14任務劃分：（三個階段）詞法分析器、語法分析器、語義分析器機時比例（大概）：2:3:3要求：驗收經過測試的程序提交上機報告。其中上機報告可以包括以下內容：<1>任務與目的<2>軟件設計軟件的總體結構與模塊劃分關鍵算法與重要數據結構<3>測試例程設計與測試結果分析<4>總結、體會、改進建議等工作方法建議：每個階段均進行設計與測試，并且寫出報告；采用增量式設計；工作全部完成后將三個階段的工作進行總結即可。決方案步驟4：.正1規詞式－法NFA分－DF析A－最器小的DFA－構編寫造程序－測試記號的設計<1>詞法分析器的三個任務：濾掉源程序中的無用成分；輸出記號供語法分析器使用；識別非法輸入，并將其標記為“出錯記號”。<2>記號的組成：記號的類別和屬性。<3>記號的數據結構：struct

Token

//記號的數據結構{

Token_Type

type;

//類別char

*

lexeme;//屬性，原始輸入的字符串double

value;

//屬性，若記號是常數則是常數的值double

(*

FuncPtr)(double);//屬性，若記號是函數則15

是函數指4.1詞法分析器的構造（續1）16<4>函數繪圖語言中記號的分類與表示enum

Token_Type{

ORIGIN,

SCALE,

ROT,

IS,//記號的類別//保留字（一字一碼）};TO,STEP,DRAW,FOR,FROM,//保留字T,

//參數SEMICO,

L_BRACKET,

R_BRACKET,

COMMA,//

分隔符PLUS,

MINUS,

MUL,

DIV,

POWER,

//

運算符FUNC,CONST_ID,NONTOKEN,ERRTOKEN//函數//常數//空記號（源程序結束）//出錯記號（非法輸入）4.1.2模式的正規式表示17letterdigit=

[a-zA-Z]=

[0-9]COMMENT =

"http://"|"--"WHITE_SPACE=

";"=

"("=

")"=

","=

"+"=

"-"=

"*"=

"/"=

"**"SEMICOL_BRACKETR_BRACKETCOMMAPLUSMINUS

MULDIVPOWERCONST_IDID=

digit+("."

digit*)?=

letter+由于是手工構造詞法分析器，而正規式個數越少越便于程序的編寫，因此設計上采用相同模式的記號共用一個正規式的方法。=(""|\t|\n)+常數的字面量部分設計為CONST_ID，而常量名則合并到ID中。這就帶來一個問題，函數繪圖語言中的保留字、常量名、參數名、以及函數名均被描述為ID，當識別出ID時，如何再細分它們？static

Token

TokenTab[]

=3.1415926,NULL}{

{CONST_ID,

"PI",,NULL},4.1.3區分記號的預先符定義號且內表容不變的符號表更多被習慣地稱為字典。{T,

"T",0.0,NULL},"SIN",

2.718280,.0,sin"COS",0.0,{CFOUNSCT,_ID,

"E",},{FUNC,cos},{FUNC,"TAN",{ORIGINt,an},

"ORIGIN",0.0,"SLCNA"L,E",00..00,,0.0,NULL},NlUogLL},"ROT","EXP",0.0,eNxULL},{SFCUANLCE,,},{RFOUTN,C,p},{IFSU,NC,"IS","SQRT",{FOR,

sqrt},"FOR",0.0,0.0,0.0,NULL},NULL},{FROM,

"FROM",0.0,

18例2.2語句ROT

IS

PI/6的記號流19<ROT"ROT"0.0NULL><IS"IS"0.0NULL><CONST_ID"PI"3.141593NULL><DIV"/"0.0NULL><CONST_ID"6"6.0NULL>4.1.4正規式的DFAletterdigit=

[a-zA-Z]=

[0-9]ID =

letter+CONST_IDPOWERCOMMENTSEMICO=

digit+("."

digit*)?=

"**"=

"http://"|"--"=

";"L_BRACKETR_BRACKET=

"("=

")"COMMAPLUSMINUS=

","=

"+"=

"-"MUL =

"*"D注IV意：W=HI"T/E“_SPACE（白空）沒有在DFA中。

WHITE_S如PA何CE處=理("白"|空\t？|\n)+204.1.5詞法分析器的程序框架struct

Token

token={ERRTOKEN,“”,0.0,NULL};//用于返回記號cthoakren=.GletxCehmaer(=)T;okenBuffer;//從記源號文的件字中符讀指取針一指個向字符緩沖區……

//空格、TAB、回車等字符的過濾AddInTokenString

(char);

//將讀入的字符放進緩沖區TokenBuffer中if

(isalpha(char)){……}

//識別IDelse

if

(isdigit(char)){……}//識別數字常量else{

switch(char){ case

‘;’:

token.type

=

SEMICO;return

token;……}}21<1>詞法分析的器的接測口試#include

"scanner.h"void

main(int

argc,

char

*argv[]){

Token

token;if

(argc<2)

{

printf("please

input

Source

File

!\n"

);

returnif

(!InitScanner(argv[1]))

//初始化詞法分析器{

printf("Open

Source

File

Error

!

\n");

return;

}printf("記號類別