實驗一詞法分析器課件

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

坐標平移（ORIGIN）注釋

（--

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

is

(100,

300);rot

is

0;scale

is

(1,

1);--設置原點的偏移量--設置旋轉(zhuǎn)角度(不旋轉(zhuǎn))--設置橫坐標和縱坐標的比例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;scale

is

(1,

1)語句滿足下述規(guī)定(原se則m)：antics）4<1>各類語句可以按任意次序書寫，且語句以分號結尾。源程序中的語句以它們出現(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等，均被認為是同一個保留字。<5>語句中表達式的值均為雙精度類型，旋轉(zhuǎn)角度單位為弧度且為逆時針旋轉(zhuǎn)，平移單位為點。）語句5語法：FOR

T

FROM起點TO終點STEP步長DRAW(橫坐標,縱坐標語義)：;令T從起點到終點、每次改變一個步長，繪制出由(橫坐標，縱舉例坐：標)所規(guī)定的點的軌跡。說明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))，即一個單位園。由于繪圖系統(tǒng)的默認值是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(橫坐標，縱坐標);語義：將坐標系的原點平移到橫坐標和縱坐標規(guī)定的點處。舉例：ORIGIN

IS

(360,240);說明：將原點從(0,0)平移到(360,240)處。2.2.4角度旋轉(zhuǎn)(ROT)語句7語法：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(角度舉例：)說明：ROT

IS

PI/2;逆時針旋轉(zhuǎn)PI/2，即逆時針旋轉(zhuǎn)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)逆時針旋轉(zhuǎn)90度--繪制園的軌跡FOR

T

FROM

0

TO

2*PI

STEP

PI/50

DRAW

(cos(T),

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

Token

//記號的數(shù)據(jù)結構{

Token_Type

type;

//類別char

*

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

value;

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

(*

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

是函數(shù)指4.1詞法分析器的構造（續(xù)1）16<4>函數(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,CONST_ID,NONTOKEN,ERRTOKEN//函數(shù)//常數(shù)//空記號（源程序結束）//出錯記號（非法輸入）4.1.2模式的正規(guī)式表示17letterdigit=

[a-zA-Z]=

[0-9]COMMENT =

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

";"=

"("=

")"=

","=

"+"=

"-"=

"*"=

"/"=

"**"SEMICOL_BRACKETR_BRACKETCOMMAPLUSMINUS

MULDIVPOWERCONST_IDID=

digit+("."

digit*)?=

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

Token

TokenTab[]

=3.1415926,NULL}{

{CONST_ID,

"PI",,NULL},4.1.3區(qū)分記號的預先符定義號且內(nèi)表容不變的符號表更多被習慣地稱為字典。{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正規(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};//用于返回記號cthoakren=.GletxCehmaer(=)T;okenBuffer;//從記源號文的件字中符讀指取針一指個向字符緩沖區(qū)……

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

(char);

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

(isalpha(char)){……}

//識別IDelse

if

(isdigit(char)){……}//識別數(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("記號類別