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

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

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

（--

或//）<2>屏幕（窗口）的坐標(biāo)系左上角為原點(diǎn)x方向從左向右增長y方向從上到下增長(與一般的坐標(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)語句滿足下述規(guī)定(原se則m)：antics）4<1>各類語句可以按任意次序書寫，且語句以分號(hào)結(jié)尾。源程序中的語句以它們出現(xiàn)的先后順序處理。<2>ORIGIN、ROT和SCALE語句只影響其后的繪圖語句，且遵循最后出現(xiàn)的語句有效的原則。例如，若有下述ROT語句序列：ROT

IS

0.7

；ROT

IS

1.57

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

T

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

T

FROM

0

TO

2*PI

STEP

PI/50

DRAW

(cos(T),sin(T));語句的作用是令T從0到2*PI、步長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)語句6語法：SCALE

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

IS

(100,100);說明：將橫坐標(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)語句語法：ORIGIN

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

IS

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

IS角度；語義：逆時(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(角度舉例：)說明：ROT

IS

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

This

is

a

comment

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

//

或--

之后，直到行尾，均是注釋語句功能的測試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)的語法和語義10記號(hào)的種類：常數(shù)、參數(shù)、函數(shù)、保留字、運(yùn)算符、分隔符<1>常數(shù)常數(shù)字面量和標(biāo)識(shí)符形式的常量名均稱為常數(shù)。字面量的形式為普通的數(shù)值，如果沒有小數(shù)部分，可以省略小數(shù)點(diǎn)。例如2、2.、2.0都是合法的常數(shù)。標(biāo)識(shí)符PI、E也是常數(shù)，它們分別代表圓周率和自然對數(shù)的底。常數(shù)不能有符號(hào)位，如-<12和>參+2數(shù)不是常數(shù)而是（一元運(yùn)算的）表達(dá)式。本作圖語言中唯一的、已經(jīng)被定義好的變量名T被稱為參數(shù)，它也是一個(gè)表達(dá)式。由于作圖語言中只有這唯一的變量，因此作圖語言中無需變量或參數(shù)的聲明和定義語句。<3>函數(shù)（調(diào)用）為簡單起見，當(dāng)前的函數(shù)僅支持正弦函數(shù)Sin，余弦函數(shù)Cos，正切函數(shù)Tan，算術(shù)平方根函數(shù)Sqrt以及指數(shù)函數(shù)Exp和對數(shù)函數(shù)Ln。有興趣的同學(xué)可以再加入其他函數(shù)。2.3記號(hào)的語法和語義（續(xù)）11<4>保留字語句中具有固定含義的標(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ù)繪圖語言編寫一個(gè)解釋器解釋器接受用繪圖語言編寫的源程序，經(jīng)語法和語義分析之后，將源程序所規(guī)定的圖形顯示在顯示屏（或窗口）中。目的：通過自己動(dòng)手編寫解釋器，掌握語言翻譯特別是語言識(shí)別的基本方法。3.1解釋器的實(shí)現(xiàn)方法用某種程序設(shè)計(jì)語言（如C/C++、Pascal、Java等）和遞歸下降子程序方法編寫完整的解釋器，由于環(huán)境限制，本書統(tǒng)一采用C/C++程序設(shè)計(jì)語言；利用編譯器編寫工具LEX/YACC提供的方式規(guī)定繪圖語言的詞法和語法，用C/C++語言編寫解釋器的語義。3.1解釋器的實(shí)現(xiàn)方法兩種方法的語義部分基本相同，主要區(qū)別在于詞法和語法分析器的構(gòu)造是手工完成還是借助于工具完成。133.3任務(wù)劃分與上機(jī)報(bào)告14任務(wù)劃分：（三個(gè)階段）詞法分析器、語法分析器、語義分析器機(jī)時(shí)比例（大概）：2:3:3要求：驗(yàn)收經(jīng)過測試的程序提交上機(jī)報(bào)告。其中上機(jī)報(bào)告可以包括以下內(nèi)容：<1>任務(wù)與目的<2>軟件設(shè)計(jì)軟件的總體結(jié)構(gòu)與模塊劃分關(guān)鍵算法與重要數(shù)據(jù)結(jié)構(gòu)<3>測試?yán)淘O(shè)計(jì)與測試結(jié)果分析<4>總結(jié)、體會(huì)、改進(jìn)建議等工作方法建議：每個(gè)階段均進(jìn)行設(shè)計(jì)與測試，并且寫出報(bào)告；采用增量式設(shè)計(jì)；工作全部完成后將三個(gè)階段的工作進(jìn)行總結(jié)即可。決方案步驟4：.正1規(guī)詞式－法NFA分－DF析A－最器小的DFA－構(gòu)編寫造程序－測試記號(hào)的設(shè)計(jì)<1>詞法分析器的三個(gè)任務(wù)：濾掉源程序中的無用成分；輸出記號(hào)供語法分析器使用；識(shí)別非法輸入，并將其標(biāo)記為“出錯(cuò)記號(hào)”。<2>記號(hào)的組成：記號(hào)的類別和屬性。<3>記號(hào)的數(shù)據(jù)結(jié)構(gòu)：struct

Token

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

Token_Type

type;

//類別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ù)繪圖語言中記號(hào)的分類與表示enum

Token_Type{

ORIGIN,

SCALE,

ROT,

IS,//記號(hào)的類別//保留字（一字一碼）};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ù)越少越便于程序的編寫，因此設(shè)計(jì)上采用相同模式的記號(hào)共用一個(gè)正規(guī)式的方法。=(""|\t|\n)+常數(shù)的字面量部分設(shè)計(jì)為CONST_ID，而常量名則合并到ID中。這就帶來一個(gè)問題，函數(shù)繪圖語言中的保留字、常量名、參數(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í)慣地稱為字典。{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的記號(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（白空）沒有在DFA中。

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

Token

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

//空格、TAB、回車等字符的過濾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>詞法分析的器的接測口試#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)類別