實(shí)驗(yàn)一詞法分析器課件

詞法分析器1《編譯原理》上機(jī)作業(yè)（1）一、上機(jī)作業(yè)的目的2通過(guò)做上機(jī)題加深對(duì)編譯器構(gòu)造原理和方法的理解，鞏固所學(xué)知識(shí)。<1>會(huì)用正規(guī)式和產(chǎn)生式設(shè)計(jì)簡(jiǎn)單語(yǔ)言的語(yǔ)法；<2>會(huì)用遞歸下降子程序編寫(xiě)編譯器或解釋器；<3>會(huì)寫(xiě)上機(jī)報(bào)告。二、上機(jī)題目－簡(jiǎn)單函數(shù)繪圖語(yǔ)言的解釋器2.1題目簡(jiǎn)述<1>實(shí)現(xiàn)簡(jiǎn)單函數(shù)繪圖的語(yǔ)句循環(huán)繪圖（FOR-DRAW）比例設(shè)置（SCALE）角度旋轉(zhuǎn)（ROT）

坐標(biāo)平移（ORIGIN）注釋

（--

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

is

(100,

300);rot

is

0;scale

is

(1,

1);--設(shè)置原點(diǎn)的偏移量--設(shè)置旋轉(zhuǎn)角度(不旋轉(zhuǎn))--設(shè)置橫坐標(biāo)和縱坐標(biāo)的比例for

T

from

0

to

200

step

1

draw

(t,

0);--橫坐標(biāo)的軌跡（縱坐標(biāo)為0）for

T

from

0

to

150

step

1

draw

(0,-t);--縱坐標(biāo)的軌跡（橫坐標(biāo)為0）for

T

from

0

to

120

step

1

draw

(t,-t);--函數(shù)f(t)=t的軌跡默認(rèn)值：origin

is

(0,

0)rot

is

0;scale

is

(1,

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

IS

0.7

；ROT

IS

1.57

；則隨后的繪圖語(yǔ)句將按1.57而不是0.7弧度旋轉(zhuǎn)。<3>無(wú)論ORIGIN、ROT和SCALE語(yǔ)句的出現(xiàn)順序如何，圖形的變換順序總是：比例變換→旋轉(zhuǎn)變換→平移變換<4>語(yǔ)言對(duì)大小寫(xiě)不敏感，例如for、For、FOR等，均被認(rèn)為是同一個(gè)保留字。<5>語(yǔ)句中表達(dá)式的值均為雙精度類(lèi)型，旋轉(zhuǎn)角度單位為弧度且為逆時(shí)針旋轉(zhuǎn)，平移單位為點(diǎn)。）語(yǔ)句5語(yǔ)法：FOR

T

FROM起點(diǎn)TO終點(diǎn)STEP步長(zhǎng)DRAW(橫坐標(biāo),縱坐標(biāo)語(yǔ)義)：;令T從起點(diǎn)到終點(diǎn)、每次改變一個(gè)步長(zhǎng)，繪制出由(橫坐標(biāo)，縱舉例坐：標(biāo))所規(guī)定的點(diǎn)的軌跡。說(shuō)明F：OR

T

FROM

0

TO

2*PI

STEP

PI/50

DRAW

(cos(T),sin(T));語(yǔ)句的作用是令T從0到2*PI、步長(zhǎng)PI/50，繪制出各個(gè)點(diǎn)的坐注意標(biāo)：(cos(T)，sin(T))，即一個(gè)單位園。由于繪圖系統(tǒng)的默認(rèn)值是ORIGIN

IS

(0,0);ROT

IS

0;SCALE

IS

(1,

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

IS(橫坐標(biāo)比例因子，縱坐標(biāo)比例因子);語(yǔ)義：設(shè)置橫坐標(biāo)和縱坐標(biāo)的比例，并分別按照比例因子進(jìn)行縮放。舉例：SCALE

IS

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

IS

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

IS(橫坐標(biāo)，縱坐標(biāo));語(yǔ)義：將坐標(biāo)系的原點(diǎn)平移到橫坐標(biāo)和縱坐標(biāo)規(guī)定的點(diǎn)處。舉例：ORIGIN

IS

(360,240);說(shuō)明：將原點(diǎn)從(0,0)平移到(360,240)處。2.2.4角度旋轉(zhuǎn)(ROT)語(yǔ)句7語(yǔ)法：ROT

IS角度；語(yǔ)義：逆時(shí)針旋轉(zhuǎn)角度所規(guī)定的弧度值。具體計(jì)算公式：旋轉(zhuǎn)后X=旋轉(zhuǎn)前X*COS(角度)+旋轉(zhuǎn)前Y*SIN(角度)旋轉(zhuǎn)后Y=旋轉(zhuǎn)前Y*COS(角度)-旋轉(zhuǎn)前X*SIN(角度舉例：)說(shuō)明：ROT

IS

PI/2;逆時(shí)針旋轉(zhuǎn)PI/2，即逆時(shí)針旋轉(zhuǎn)90度。2.2.5注釋語(yǔ)句注釋的作用：便于理解；屏蔽暫時(shí)不需要的語(yǔ)句。語(yǔ)法： //

This

is

a

comment

line或--此行是注釋語(yǔ)義：

//

或--

之后，直到行尾，均是注釋語(yǔ)句功能的測(cè)試ORIGIN

IS

(360,

240);SCALE

IS

(100,

100);SCALE

IS

(100,

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

IS

PI/2;

//(4)逆時(shí)針旋轉(zhuǎn)90度--繪制園的軌跡FOR

T

FROM

0

TO

2*PI

STEP

PI/50

DRAW

(cos(T),

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

SCALE,

ROT,

IS,

TO,STEP,

DRAW,

FOR,

FROM<5>運(yùn)算符PLUS,

MINUS,

MUL,即:

+

-

*<6>分隔符DIV,

POWER/

**R_BRACKET,SEMICO,

L_BRACKET,COMMA即:

;

(

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

Token

//記號(hào)的數(shù)據(jù)結(jié)構(gòu){

Token_Type

type;

//類(lèi)別char

*

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

value;

//屬性，若記號(hào)是常數(shù)則是常數(shù)的值double

(*

FuncPtr)(double);//屬性，若記號(hào)是函數(shù)則15

是函數(shù)指4.1詞法分析器的構(gòu)造（續(xù)1）16<4>函數(shù)繪圖語(yǔ)言中記號(hào)的分類(lèi)與表示enum

Token_Type{

ORIGIN,

SCALE,

ROT,

IS,//記號(hào)的類(lèi)別//保留字（一字一碼）};TO,STEP,DRAW,FOR,FROM,//保留字T,

//參數(shù)SEMICO,

L_BRACKET,

R_BRACKET,

COMMA,//

分隔符PLUS,

MINUS,

MUL,

DIV,

POWER,

//

運(yùn)算符FUNC,CONST_ID,NONTOKEN,ERRTOKEN//函數(shù)//常數(shù)//空記號(hào)（源程序結(jié)束）//出錯(cuò)記號(hào)（非法輸入）4.1.2模式的正規(guī)式表示17letterdigit=

[a-zA-Z]=

[0-9]COMMENT =

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

";"=

"("=

")"=

","=

"+"=

"-"=

"*"=

"/"=

"**"SEMICOL_BRACKETR_BRACKETCOMMAPLUSMINUS

MULDIVPOWERCONST_IDID=

digit+("."

digit*)?=

letter+由于是手工構(gòu)造詞法分析器，而正規(guī)式個(gè)數(shù)越少越便于程序的編寫(xiě)，因此設(shè)計(jì)上采用相同模式的記號(hào)共用一個(gè)正規(guī)式的方法。=(""|\t|\n)+常數(shù)的字面量部分設(shè)計(jì)為CONST_ID，而常量名則合并到ID中。這就帶來(lái)一個(gè)問(wèn)題，函數(shù)繪圖語(yǔ)言中的保留字、常量名、參數(shù)名、以及函數(shù)名均被描述為ID，當(dāng)識(shí)別出ID時(shí)，如何再細(xì)分它們？static

Token

TokenTab[]

=3.1415926,NULL}{

{CONST_ID,

"PI",,NULL},4.1.3區(qū)分記號(hào)的預(yù)先符定義號(hào)且內(nèi)表容不變的符號(hào)表更多被習(xí)慣地稱(chēng)為字典。{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語(yǔ)句ROT

IS

PI/6的記號(hào)流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正規(guī)式的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（白空）沒(méi)有在DFA中。

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

Token

token={ERRTOKEN,“”,0.0,NULL};//用于返回記號(hào)cthoakren=.GletxCehmaer(=)T;okenBuffer;//從記源號(hào)文的件字中符讀指取針一指?jìng)€(gè)向字符緩沖區(qū)……

//空格、TAB、回車(chē)等字符的過(guò)濾AddInTokenString

(char);

//將讀入的字符放進(jìn)緩沖區(qū)TokenBuffer中if

(isalpha(char)){……}

//識(shí)別IDelse

if

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

switch(char){ case

‘;’:

token.type

=

SEMICO;return

token;……}}21<1>詞法分析的器的接測(cè)口試#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("記號(hào)類(lèi)別